Click here for the most recent version of this class.

CMU 15-859(B), Spring 2007


Avrim Blum and Nina Balcan

Time: TR 10:30-11:50, Place: Wean 4623

Course description: This course will focus on theoretical aspects of machine learning. We will examine questions such as: What kinds of guarantees can one prove about learning algorithms? What are good algorithms for achieving certain types of goals? Can we devise models that are both amenable to mathematical analysis and make sense empirically? What can we say about the inherent ease or difficulty of learning problems? Addressing these questions will require pulling in notions and ideas from statistics, complexity theory, information theory, cryptography, game theory, and empirical machine learning research.

Text: An Introduction to Computational Learning Theory by Michael Kearns and Umesh Vazirani, plus papers and notes for topics not in the book.

Office hours: Just stop by my office or make an appointment.


Lecture Notes & tentative plan

  1. 01/16: Introduction. PAC model and Occam's razor.
  2. 01/18: The Mistake-Bound model. Combining expert advice. Connections to info theory and game theory.
  3. 01/23: The Winnow algorithm + applications.
  4. 01/25: The Perceptron Algorithm, Margins, and Kernel functions.
  5. 01/30: Support Vector Machines [Andrew Ng's notes]
  6. 02/01: Maxent and maximum-likelihood exponential models. Connection to winnow.
  7. 02/06: Uniform convergence and VC-dimension I. Slides for 1st half + Notes for 2nd half.
  8. 02/08: VC-dimension II.
  9. 02/13: Boosting I: weak vs strong learning, basic issues.
  10. 02/15: Boosting II: Adaboost.
  11. 02/20: Offline->online optimization. Kalai-Vempala algorithm.
  12. 02/22: Semi-supervised learning, epsilon-cover bounds. See also the SSL book chapter.
  13. 02/27: Margins, Kernels and Similarity functions. See also DG paper on JL lemma.
  14. 03/01: Cryptographic hardness results.
  15. 03/06: Learning from noisy data. The Statistical Query model.
  16. 03/08: Characterizing SQ learnability with Fourier analysis. [BFJKMR paper]
  17. 03/13: [spring break - no classes]
  18. 03/15: [spring break - no classes]
  19. 03/20: Using Fourier for learning.
  20. 03/22: Membership queries I: basic algorithms, KM algorithm. [Mansour survey article]
  21. 03/27: Membership queries II: Fourier spectrum of DTs & DNFs, Bshouty's alg. [summary]
  22. 03/29: Membership queries III: Angluin's algorithm for learning DFAs [ppt].
  23. 04/03: Learning finite-state environments without a reset.
  24. 04/05: MDPs and reinforcement learning I.
  25. 04/10: MDPs and reinforcement learning II.
  26. 04/12: Active learning: slides and notes.
  27. 04/17: Margin bounds, MB=>PAC bounds.
  28. 04/19: [carnival - no classes]
  29. 04/24: Rademacher bounds, McDiarmid's inequality.
  30. 04/26: Leave-one-out cross-validation bounds. Course retrospective.
  31. 05/01: Project presentations
  32. 05/03: Project presentations

Project ideas

Additional Readings & More Information

Books and tutorials:

Online Learning:

PAC sample complexity: Boosting:

More on Kernels:

Fourier analysis, weak learning, SQ learning:

Computational hardness results:

Web sites on maxent: