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%).

- 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):

- Introduction Aug 23. Topics overview. Notes. HW0.
- Unsupervised Learning Aug 25 Statistical Estimation: Any single Gaussian. Notes. Scribed. Chap 2 of FoDS.
- Supervised Learning Oct 4. PAC, Mistake-bound models.
- Contemporary theories of Neural Networks Nov 22. Deep Neural Networks. HW4.

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.

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

Nov 29, Dec 1. Brain.

Dec 3. Project Report due date.

Dec 6. Transformers.