ECE434/COS434: Machine Learning Theory
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.
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 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)
Statistical Learning Theory
Concentration inequalities
Generalization, uniform convergence
Rademacher complexity, VC dimension [Homework 1 due]
Linear/logistic regression, and their generalization bounds
Reproducing Hilbert kernel space [Homework 2 due]
Optimization Theory
Convex optimization, convergence analysis of (stochastic) gradient descent
Nonconvex optimization and saddle points escaping [Homework 3 due]
Deep Learning Theory
Basic approximation theory
Optimization and generalization. [Homework 4 due]
Reinforcement Learning Theory
MDP, Bellman equations, planning, generative model
Sample complexity of value iterations, and Q-learning [Homework 5 due]
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.
Foundations of Machine Learning by Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.
Deep Learning Theory Lecture Notes by Matus Telgarsky.