ECE434/COS434: Machine Learning Theory

Fall 2021, Mon. Wed. Fri. 09:00 am - 9:50 am, Equad D221

• Instructor: Chi Jin                Office hour:  Wed. 3:30 pm - 4:30 pm [Zoom]

• TA:             Yuanhao Wang    Office hour:  Thur. 4:00 pm - 5:00 pm [Zoom]

• TA:           Jimmy (Tsung-Yen) Yang Office hour:  Thur. 3:00 pm - 4:00 pm (on weeks that homework is due) [Zoom]

• Contents: An overview of theoretical machine learning.

• Grades:     5 problem sets (70%), and 1 take-home final exam (30%). 

• No late homework. 

Lecture Notes

• 9/1, 9/3. Introduction. [note1]

• 9/8, 9/10. Concentration inequalities. [note2]

• 9/13, 9/15, 9/17. Risk bounds, Rademacher complexity, VC dimension. [note3]

• 9/20, 9/22, 9/25. SSVC theorem, classification and regression. [note4]

• 9/27, 9/29, 10/1. Kernel methods, reproducing kernel Hilbert space. [note5]

• 10/4, 10/6, 10/8. Representer theorem, intro to optimization. [note6]

• 10/11, 10/13, 10/15. Convex optimization, (stochastic) gradient descent. [note7]

• 10/25, 10/27, 10/29. Nonconvex optimization, stationary points, saddle points. [note8]

• 11/1, 11/3, 11/5. Neural Networks and Universal Approximation. [note9]

• 11/8, 11/10, 11/12. Neural Tangent Kernel. [note10]

• 11/15, 11/17, 11/19. Intro to reinforcement learning. [note11]

• 11/22, 11/29, 12/1. Learning MDPs with Simulator. [note12]

• 12/3, 12/6. Markov games. [note13]

Homework

• Homework 1 (due on 10/1 in class).

• Homework 2 (due on 10/25 in class).

• Homework 3 (due on 11/8 in class).

• Homework 4 (due on 11/29 in class).

• Homework 5 (due on 12/10 on Canvas)

Schedule (weekly basis)

Statistical Learning Theory

1. Concentration inequalities

2. Generalization, uniform convergence

3. Rademacher complexity, VC dimension [Homework 1 due]

4. Linear/logistic regression, and their generalization bounds

5. Reproducing Hilbert kernel space [Homework 2 due]

Optimization Theory

6. Convex optimization, convergence analysis of (stochastic) gradient descent

7. Nonconvex optimization and saddle points escaping [Homework 3 due]

Deep Learning Theory

8. Basic approximation theory

9. Optimization and generalization. [Homework 4 due]

Reinforcement Learning Theory

10. MDP, Bellman equations, planning, generative model

11. Sample complexity of value iterations, and Q-learning [Homework 5 due]

Guidelines

• Lecture notes will be released by the end of each week.

• Problem sets will be released every two weeks.

• Each problem set has 15 pts in total, but the maximum amount of obtainable points is 14. That is, you can still obtain full scores even if you lose 1 pt per homework.

• You can discuss the homework with classmates and TAs, but you need to write the solution on your own. Copying written solutions is strictly prohibited. Discussion is not allowed for the final.

Recommended Textbook

• Foundations of Machine Learning by Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.

• Deep Learning Theory Lecture Notes by Matus Telgarsky.