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. HW1.
Sep 13. Independent Component Analysis. Notes. Chap 3 here.
Sep 15. Robust Estimation. Notes.
Sep 20, 22, 27. Clustering: k-means, spectral, hierarchical, fair.
Sep 29. Midterm I.
- Supervised Learning
Oct 4. PAC, Mistake-bound models.
Oct 6. Halfspace learning, Perceptron, kernel trick.
Oct 11. Fall recess.
Oct 13. Experts, Weighted Majority, Winnow.
Oct 18. Boosting.
Oct 20. Support Vector Machines.
Oct 25, 27. VC-dimension, Rademacher complexity.
Nov 1. Fourier learning
Nov 3. Statistical query model: lower bound for parity
Nov 8. Follow the perturbed leader.
Nov 10. Online convex optimization.
Nov 15. Midterm II
- Contemporary theories of Neural Networks
Nov 17, 22. Deep Neural Networks.
Nov 29, Dec 1. Brain.
Dec 6. Transformers.