COS511/ECE434/COS434: Theoretical Machine Learning
Fall 2023, Fri. 01:30 pm - 4:20 pm, ComSciBldg 104
Instructor: Chi Jin Office hour: Thu 3:00-4:00 pm [Equad C332]
TA: Jiawei Ge Office hour: Wed 4:30-5:30 pm [Equad E219]
TA: Shange Tang Office hour: Fri 5:00-6:00 pm [COS 003]
TA: Yuanhao Wang Office hour: Mon 3:00-4:00 pm [COS 003]
Contents: An overview of theoretical machine learning.
Grades:
COS511: 5 problem sets (60%), and 1 take-home final exam (40%).
ECE434/COS434: 5 problem sets (60%), participation (10%) and 1 take-home final exam (30%).
Problem sets and final of undergraduate courses will be easier than the graduate version.
No late homework.
Lecture Notes
Statistical Learning
9/8, Intro to learning theory, concentration inequalities [note1]
9/15, Excess risk bounds, Rademacher complexity [note2]
9/22, Boolean class, VC dimension, SSVC theorem [note3]
9/29, Classification, Kernel, RKHS [note4]
10/6, Regression, Covering number [note5]
Optimization
10/13, Representer theorem, intro to optimization [note6]
10/27, (Stochastic) gradient descent [note7]
11/10, Nonconvex optimization, intro to online learning [note8]
Online Learning
*this part uses the contents of CSCI 699 by Haipeng Luo at USC, we thank Haipeng for kindly offering supportive course material
Problem Sets
Problem set 1 [due 10/1 11:59 pm]
Problem set 2 [due 10/23 11:59 pm]
Problem set 3 [due 11/6 11:59 pm]
Problem set 4 [due 11/29 11:59 pm]
Problem set 5 [for practice only]
Tentative Syllabus
Supervised learning
Generalization, uniform concentration
Rademacher complexity, VC dimension
Reproducing Hilbert kernel space
Deep neural networks
Sparse linear regression, Low-rank matrix problems
Optimization
Online learning
Online formulation, empirical process with dependent data
Sequential Rademacher complexity, little stone dimension
Online algorithms
Unsupervised learning
Latent variable models, density estimation vs parameter estimation
Maximum likelihood estimation, EM algorithm
Method of moments, tensor methods
Representation learning, foundation model
Reinforcement learning
Guidelines
Lecture notes will be released on the following Monday.
Problem sets will be released every two weeks.
Each problem set has 13 pts in total, but the maximum amount of obtainable points is 12. 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.
Related Courses
Prior Version of theoretical machine learning courses at Princeton [COS511@2022 (by Elad Hazan)] [ECE434@2021] [COS511@2019 (by Robert Schapire)]
Theoretical Machine Learning by Haipeng Luo at USC.
References
Foundations of Machine Learning by Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.
High-Dimensional Probability: An Introduction with Applications in Data Science by Roman Vershynin
High-Dimensional Statistics: A Non-Asymptotic Viewpoint by Martin Wainwright.