Avrim Blum's survey talks and survey papers:
Most recent:
 Approximation Stability and
Proxy Objectives [pdf], Stanford
Workshop on Beyond WorstCase Analysis, 2011.
 Also Why Do We Want a Good Ratio
Anyway? Approximation Stability and Proxy Objectives,
Princeton Workshop on Approximation Algorithms: The Last
Decade and the Next, June 2011. See also:
 SemiSupervised Learning, USC
Distinguished Lecture Series, 2008.
A related paper on a
new theoretical framework for SemiSupervised Learning (with Nina Balcan).
 Thoughts on Learning and
Clustering, Cornell CS Colloquium, Jan 2007. A more detailed version given at
Yahoo! Research, 2008. See also:
 On decisionmaking
without regret, routing games, and convergence to
equilibria.
See also
Learning, Regret Minimization, and
Equilibria, book chapter in Algorithmic Game
Theory, with Yishay Mansour.
 Simple randomized algorithms for
auction and pricing problems (given at the DIMACS
workshop in honor of Joel Spencer's 60th birthday).
 New Horizons in Machine
Learning, given at the Workshop on New Horizons in
Computing, Kyoto, 2005.
 A survey article on the use of random
projection for learning, with connections to kernel functions
and feature selection. LNCS vol 3940, pp. 5268, 2006.
(Based on an invited presentation at a PASCAL workshop, 2005)
 Tutorial on Machine
Learning Theory given
at FOCS 2003.
Shorter version
given at the 2003 National Academy of Sciences "Frontiers of
Science" Symposium.
 A short essay on Machine Learning Theory.
Others:
 Online learning / metrical task systems / portfolio selection
 Online exploration

Udine lecture. These are
slides from a lecture at the 1998 School and Workshop on
Online Algorithms, Udine, Italy. Many of the slides for
that talk were handdrawn, so this is only a sketch.
 References for
AAAI97 workshop talk on Online Search in Theoretical
Computer Science.
 General machine learning