Time/location:

• Lectures: Mon/Wed 4-5:20pm

Instructor: Tengyu Ma

Course assistants:

• Chen Cheng
• Sifan Liu
• Jingyi Kenneth Tay
• Kangjie Zhou

Contact: Please use Piazza for all questions and discussions.

Description: When do machine learning algorithms work and why? How do we formalize what it means for an algorithm to learn from data? How do we use mathematical thinking to design better machine learning methods? This course focuses on developing a theoretical understanding of the statistical properties of learning algorithms.

Topics:

• Generalization bounds (Rademacher complexity)
• Implicit/algorithmic regularization
• Online learning
• Bandits problems
• Domain shift

Week 1

• Mon 01/11: Lecture 1: overview, formulation of supervised learning, empirical risk minimization and its asymptotics
• Wed 01/13: Lecture 2: asymptotics analysis of excess risk, non-asymptotic analysis, uniform convergence

Week 2

• Mon 01/18: Holiday, no class
• Mon 01/18: Homework 1 out
• Wed 01/20: Lecture 3: sub-Gaussianity, concentration inequalities
• Wed 01/20: Homework 0 (warmup) due

Week 3

• Mon 01/25: Lecture 4: uniform convergence of empirical loss, finite hypothesis class, brute-froce discretization
• Wed 01/27: Lecture 5: Rademacher complexity, empirical Rademacher complexity
• Wed 01/27: Homework 1 due
• Thu 01/28: Homework 2 out

Week 4

• Mon 02/01: Lecture 6: VC dimension, margin theory
• Wed 02/03: Lecture 7: Rademacher complexity for linear models and two-layer neural networks

Week 5

• Mon 02/08: Lecture 8: Refined upper bound for neural networks and Dudley chaining
• Wed 02/10: Lecture 9: Dudley's theorem and intro to deep learning theory

Week 6

• Mon 02/15: Holiday, no class
• Wed 02/17: Lecture 10: Optimization landscape, examples of local minimums are global minimums
• Wed 02/17: Homework 2 due
• Thu 02/18: Homework 3 out

Week 7

• Mon 02/22: Lecture 11: Remaining proofs of local minima are global minima, introduction to NTK
• Wed 02/24: Lecture 12: Proofs of neural tangent kernel
• Wed 02/24: (Optional) paper review part 1 due

Week 8

• Mon 03/01:
• Wed 03/03

Week 9

• Mon 03/08:
• Wed 03/10:
• Wed 03/10: Homework 3 due

Week 10

• Mon 03/15:
• Wed 03/17:
• Fri 03/19: Paper review due

• Percy Liang's course notes from previous offerings of this course

• Peter Bartlett's statistical learning theory course

• Boyd and Vandenberghe's Convex Optimization

• Sham Kakade's statistical learning theory course

• Martin Wainwright's statistical learning theory course