Machine Learning Theory, CS7545

Fall 2021. MW: 9:30-10:45. Kendeda 210.

Instructor: Santosh Vempala, OH: Tue 11-12, benches outside Klaus.
TAs: He Jia, OH: Thu 3-5pm; Aditi Laddha, OH: Fri 3-5pm; outside Klaus 2116.

Prerequisite: basic knowledge of algorithms, probability, linear algebra.

Grading:

• 4 HW sets (50%). You are encouraged to collaborate on homework (except HW0, which you must do on your own), and expected to write your own solutions. Submit via gradescope (link on canvas).
  
• 2 Midterm exams (40%).
  
• 1 Research report on one current topic in ML of theoretical interest (10%).
  
  

References:

• Foundations of Data Science (FoDS), Blum, Hopcroft, Kannan.
  
• An Introduction to Computational Learning Theory, Kearns and U. Vazirani
  
• Spectral Algorithms, Kannan, Vempala
  
• Avrim Blum's Learning Theory course.
  
• Some research articles

Schedule (tentative):

1. Introduction
Aug 23. Topics overview. Notes. HW0.


2. Unsupervised Learning
Aug 25 Statistical Estimation: Any single Gaussian. Notes. Scribed. Chap 2 of FoDS.
Aug 30, Sep 1. Mixture models, PCA, Random Projection. Notes. Chapters 1 and 2 here. Chap 3 of FoDS.
Sep 6. Labor day.
Sep 8. Tensor factorization. Chap 7 here. HW1.
Sep 13. Independent Component Analysis. Notes. Chap 3 here.
Sep 15. Robust Estimation. Notes. Scribed.
Sep 20, 22, 27. Clustering: k-means, spectral, hierarchical, fair.
Notes1, Notes2. Chap 7 of FoDS. Chap 5 here.
Sep 29. Midterm I.


3. Supervised Learning
Oct 4. PAC, Mistake-bound models.
Oct 6. Halfspace learning, Perceptron, kernel trick. Notes. Chap 5 of FoDS.
Oct 11. Fall recess.
Oct 13. Experts, Weighted Majority, Winnow. Notes. Scribed (10/4-10/13). HW2.
Oct 18, 20. VC-dimension. Notes. Scribed.
Oct 25. Boosting. Notes. 
Oct 27. Margins: Support Vector Machines, Perceptron, Random Projection. Notes. Scribed.
Nov 1, 3. Fourier learning. Notes. Scribed.
Nov 8, 10. Statistical query model: lower bound for parity. Notes. Scribed. HW3.
Nov 15. Midterm II
Nov 17. Online Decision Making: Follow the perturbed leader. Notes. article


4. Contemporary theories of Neural Networks
Nov 22. Deep Neural Networks. HW4.
Nov 29, Dec 1. Brain.
Dec 3. Project Report due date.
Dec 6. Transformers.