Instructor: Avrim Blum
Time: MW 1:30-2:50
Place: Wean 5409
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.

The final exam is Tuesday 5/16 1:00-4:00pm in Wean 6423 (not 4623)


Lecture Notes & tentative plan

  1. 01/18: Introduction, basic definitions, the consistency model.
  2. 01/23: The Mistake-bound model.
  3. 01/25: The Winnow algorithm + applications.
  4. 01/30: The Perceptron Algorithm, Margins, and Kernel functions.
  5. 02/01: Combining expert advice, Weighted-Majority, Regret-bounds and connections to game theory.
  6. 02/06: Kalai-Vempala algorithm.
  7. 02/08: PAC model I: basic results and Occam's razor.
  8. 02/13: PAC model II: Chernoff/Hoeffding bounds, MB->PAC [pdf]. Handout on tail inequalities
  9. 02/15: VC-dimension I: Proof of Sauer's lemma. slides and notes.
  10. 02/20: [no class today]
  11. 02/22: VC-dimension II.
  12. 02/27: Boosting I: weak vs strong learning, basic issues.
  13. 03/01: Boosting II: Adaboost.
  14. 03/06: Cryptographic hardness results.
  15. 03/08: Maxent and maximum-likelihood exponential models. Connection to winnow.
  16. 03/20: Learning from noisy data. The Statistical Query model.
  17. 03/22: Characterizing SQ learnability with Fourier analysis.
  18. 03/27: Finish SQ hardness. Using Fourier for learning.
  19. 03/29: Membership queries I: basic algorithms, KM algorithm.
  20. 04/03: Membership queries II: Fourier spectrum of DTs & DNFs, Bshouty's alg.
  21. 04/05: Membership queries III: Angluin's algorithm for learning DFAs. Additional notes.
  22. 04/10: Learning finite-state environments without a reset.
  23. 04/12: MDPs and reinforcement learning.
  24. 04/17: MDPs and reinforcement learning II.
  25. 04/19: Semi-supervised learning, active learning.
  26. 04/24: Boosting and margins
  27. 04/26: Kernels and similarity functions
  28. 05/01: Project presentations
  29. 05/03: Project presentations

Additional Readings & More Information

Very new results:

Presentations on the Web:

Books (general):

Online Learning:

PAC model: Boosting:

Fourier analysis, weak learning, SQ learning:

Web sites on maxent: