Course Description
This is an advanced graduate course in the theory of machine learning. The course is ideal for graduate students and senior undergraduates who are theoretically inclined and want to know more about related research challenges in the field of machine learning. A tentative list of topics include the following:
Statistical learning theory, VC theory and PAC model
Online learning, bandit algorithms, connections to game theory
Theory of regression, classification, kernel methods
Graphical Models and high dimensional learning
Unsupervised and semi supervised Learning
Theory of convex and nonconvex optimization
Grading
Each student is expected to prepare scrbe notes for 2 lectures. In addition, there will be a final project. The final project will involve either thinking about an open problem or reading and summarizing 23 related papers in a topic of your interest. The final project can involve programming but needs to have a significant theoretical component. The project will be graded on the basis of a final report.
Instructions for Scribe Notes
Each student is expected to produce high quality lecture notes for 2 classes. Failure to do so will automatically result in a C grade. The purpose of each scribe note is to document a given lecture from start to finish including proofs and details. The notes should be such that anyone who might have missed the lecture can easily understand what was covered. Of course, it is not easy to produce such notes on the first try. Typically a student will email me his scribe notes and then I will provide feedback on how to improve it. Once done, the notes will be put up online on the course webpage. The first draft of the notes will be due within a week of the lecture. The latex template for the scribe notes is
here.
Lectures

Lec 1 & 2: Introduction to PAC model
[notes]

Lec 3: PAC model continued
[notes]

Lec 4: Symmetrization and Rademacher Averages
[notes]

Lec 5: Online Learning
[notes]

Lec 6: Randomized Multiplicative Weights
[notes]

Lec 7: EXP3 and Follow the Leader
[notes]

Lec 8: Boosting
[notes]

Lec 9: Support Vector Machines
[notes]

Lec 10: Generalization and Stability
[notes]

Lec 11: Kernel Methods
[notes]

Lec 12: Linear Algebra Basics
[notes]

Lec 13: Stochastic Block Models
[notes]

Lec 14: Stochastic Block Models (continued)
[notes]

Lec 15: Proof of Decomposition Theorem
[no volunteer]

Lec 16: Non Negative Matrix Factorization
[notes]

Lec 17: Matrix Completion
[notes]

Lec 18: Matrix Completion (continued)
[notes]

Lec 19: Randomized SVD
[notes]

Lec 20: Convex Optimization
[notes]

Lec 21: Convex Optimization (continued)
[notes]

Lec 22: Stochastic Optimization
[notes]

Lec 23: NonConvex Optimization and Wrap up
[notes]