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

Schedule (tentative):

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

  3. Unsupervised Learning
  4. 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.

  5. Supervised Learning
  6. 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

  7. Contemporary theories of Neural Networks
  8. Nov 17, 22. Deep Neural Networks.
    Nov 29, Dec 1. Brain.
    Dec 6. Transformers.