Most recent:

• New Directions in Learning Theory, invited talk at SODA (ACM-SIAM Symposium on Discrete Algorithms), 2015.

• Approximation Stability and Proxy Objectives [pdf], Stanford Workshop on Beyond Worst-Case Analysis, 2011. See 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.
  • A Computational Theory of Clustering, EaGL Theory Workshop, Sept 2008.
  • A Discriminative Framework for Clustering via Similarity Functions, with Nina Balcan and Santosh Vempala (STOC 2008).
  • Approximate Clustering without the Approximation, with Nina Balcan and Anupam Gupta (SODA 2009).

• Semi-Supervised Learning, USC Distinguished Lecture Series, 2008. A related paper on a new theoretical framework for Semi-Supervised 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 a Theory of Learning with Similarity Functions, with Nina Balcan. (ICML 2006).
  • Improved Guarantees for Learning via Similarity Functions, with Nina Balcan and Nati Srebro. (COLT 2008).
  • A Discriminative Framework for Clustering via Similarity Functions, with Nina Balcan and Santosh Vempala (STOC 2008).

• On decision-making 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. 52--68, 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 Learning tools for Online Algorithms, Dagstuhl workshop on Online Algorithms, July 2002.

  • Online Learning and Prediction, a series of talks given at the Lipari summer school, July 2000.

  • Online Learning and the Metrical Task System Problem, DIMACS workshop on Online Decision Making, July 1999.

  • A survey paper based on a presentation given at the Dagstuhl workshop on Online Algorithms, June 1996. This survey now appears as Chapter 14 in Online Algorithms: the State of the Art, Springer LNCS "State-of-the-Art Survey" series 1442, Fiat and Woeginger eds.

• 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 hand-drawn, so this is only a sketch.

  • References for AAAI-97 workshop talk on Online Search in Theoretical Computer Science.

• General machine learning
  • Tutorial on Machine Learning Theory given at FOCS 2003.

  • My favorite open problems in computational learning (talk given at NeuroCOLT workshop, 2001).

  • Relevant Examples and Relevant Features: thoughts from Computational Learning Theory. Given at the 1994 AAAI Fall Symposium on "Relevance" (short article). Here is a longer article joint with Pat Langley that also discusses the experimental literature (appears in Artificial Intelligence, 97:245--272, 1997).