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.
- 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%).
Aug 23. Topics overview. Notes. HW0.
- 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.
- 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
- 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.