Scroll down for CMU 15-859(B) Machine Learning Theory, Spring 2014

UIUC CS-589, Fall 2014


Avrim Blum

Wed/Fri 11:00-12:15, SC 1109

(Office hours: Tues 1:00-2:00, SC 3212)

Course description: This seminar class will focus on new results and directions in machine learning theory. Machine learning theory concerns questions such as: What kinds of guarantees can we prove about practical machine learning methods, and can we design algorithms achieving desired guarantees? (Why) is Occam's razor a good idea and what does that even mean? What can we say about the inherent ease or difficulty of different types of learning problems? Addressing these questions will bring in connections to probability and statistics, online algorithms, game theory, computational geometry, and empirical machine learning research.

The first half of the course will involve the instructor presenting some classic results and background including regret guarantees, combining expert advice, Winnow and Perceptron algorithms, VC-dimension, Rademacher complexity, SVMs, and Kernel functions. The second half will involve student-led discussions of recent papers in areas such as deep learning, multi-task learning, tensor methods, structured prediction, dictionary learning, and other topics

Lecture Notes and Tentative Plan

  1. 08/27: Introduction. The PAC model and Occam's razor.
  2. 08/29: The Online Mistake-Bound model, Combining Expert Advice / Multiplicative Weights, Regret Minimization and connections to Game Theory.
  3. 09/03: Shifting experts, the Winnow Algorithm, L_1 margin bounds.
  4. 09/05: The Perceptron Algorithm, Margins, and intro to Kernels.

CMU 15-859(B), Spring 2014


Avrim Blum

MW 10:30-11:50, GHC 4303

Course description: This course will focus on theoretical aspects of machine learning. We will examine questions such as: What kinds of guarantees can we prove about learning algorithms? Can we design algorithms for interesting learning tasks with strong guarantees on accuracy and amounts of data needed? What can we say about the inherent ease or difficulty of learning problems? Can we devise models that are both amenable to theoretical analysis and make sense empirically? Addressing these questions will bring in connections to probability and statistics, online algorithms, game theory, complexity theory, information theory, cryptography, and empirical machine learning research. Grading will be based on 6 homework assignments, class participation, a small class project, and a take-home final (worth about 2 homeworks). Students from time to time will also be asked to help with the grading of assignments.
[2009 version of the course]

Prerequisites: A Theory/Algorithms background or a Machine Learning background.

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

Office hours: Wed 3-4 or send email to make an appointment.


Tentative plan

  1. 01/13: Introduction. PAC model and Occam's razor.
  2. 01/15: The Mistake-Bound model. Combining expert advice. Connections to info theory.
  3. 01/20: The Winnow algorithm.
  4. 01/22: The Perceptron Algorithm, margins, & intro to kernels plus Slides.
  5. 01/27: Uniform convergence, tail inequalities (Chernoff/Hoeffding), VC-dimension I. [more notes]
  6. 01/29: VC-dimension II (proofs of main theorems).
  7. 02/03: Boosting I: Weak to strong learning, Schapire's original method.
  8. 02/05: Boosting II: Adaboost + connection to WM analysis + L_1 margin bounds
  9. 02/10: Rademacher bounds and McDiarmid's inequality.
  10. 02/12: Rademacher bounds II.
  11. 02/17: MB=>PAC, Support Vector Machines, L_2 margin uniform-convergence bounds.
  12. 02/19: Margins, kernels, and general similarity functions (L_1 and L_2 connection).
  13. 02/24: No class today. Nina Balcan talk at 10:00am in GHC 6115.
  14. 02/26: Learning with noise and the Statistical Query model I.
  15. 03/03: No class today. Open house.
  16. 03/05: Statistical Query model II: characterizing weak SQ-learnability.
  17. 03/17: Fourier-based learning and learning with Membership queries: the KM algorithm.
  18. 03/19: Fourier spectrum of decision trees and DNF. Also hardness of learning parities with kernels.
  19. 03/24: Learning Finite State Environments.
  20. 03/26: MDPs and reinforcement learning.
  21. 03/31: Maxent and maximum likelihood exponential models; connection to winnow
  22. 04/02: Offline->online optimization, Kalai-Vempala.
  23. 04/07: The Adversarial Multi-Armed Bandit Setting.
  24. 04/09: Game theory I (zero-sum and general-sum games).
  25. 04/14: Game theory II (achieving low internal/swap regret. Congestion/exact-potential games).
  26. 04/16: Semi-supervised learning
  27. 04/21: Some loose ends: Compression bounds, Bshouty's algorithm.
  28. 04/23: Project presentations
  29. 04/28: Project presentations
  30. 04/30: Project presentations

Additional Readings & More Information