Syllabus

The course syllabus is structured into the following modules:
- Matrix and tensor algebra, and optimization (6 lectures)
- Generalization (12 lectures)
- Paper reading and presentations (5 lectures): A list of papers will be provided when the schedule of paper discussions gets close; For each paper, a student leads the presentation with another student leading the discussion
- In class final project report discussion (1 lecture)

Textbooks

There are no textbooks for this class. A list of suggested course materials can be found at the bottom of the page.

Course Schedule

Updated regularly throughout the semester to reflect what was covered, along with corresponding readings and notes.

Date	Event	Description	Class Materials	Suggested Reading
Week 1 01/09, 01/11	Lecture 1	Logistics and course overview Topic modeling, matrix completion, and basic neural networks	Introduction	Chap. 2 of AAML
Week 1 01/09, 01/11	Lecture 2	Review of linear algebera Matrix methods	SVD, and power methods Matrix perturbation	SoftImpute
Week 2 01/18	Lecture 3	Tensor decompositions and their applications	Tensor rank and Jennrich's algorithm Phylogenetic reconstruction and topic models	Chap. 3 of AAML
Week 3 01/23, 01/25	Lecture 4	Start of Optimization	Smoothness; convergence rates for smooth objectives	Chap. 1, 9, 10 of DLT
Week 3 01/23, 01/25	Lecture 5	Basics of convex optimization	Convexity and Strong convexity Stochastic Gradidents	Chap. 11, 12 of DLT
Week 4 01/30, 02/01	Lecture 6	Neural Tangent Kernel	Basics of Kernel methods NTK for Shallow Networks	Chap. 4 of Percy Liang's notes
Week 4 01/30, 02/01	Lecture 7	Neural Tangent Kernel	Global convergence of GD for NTK Multi-layer neural nets	Chap. 8 of ToDL
Week 5 02/06, 02/08	Lecture 8	Implicit regularization	Nonsmoothness Gradient descent maximizes margin on separable data	Chap 14-15 of DLT
Week 5 02/06, 02/08	Lecture 9	Uniform convergnce	Fixed design linear regression Finite and realizable hypothesis class	Chap 17 of DLT
Week 6 02/13, 02/15	Lecture 10	Concentration inequalities	MGF, Finite hypothesis class Introducing Rademacher complexity	Chap. 3 of Percy Liang's notes
Week 6 02/13, 02/15	Lecture 11	Rademacher complexity	Generalization bound based on Rademacher complexity Logistic regression and Margin bounds	Chap 18 of DLT
Week 7 02/22	Lecture 12	Rademacher complexity (cont'd)	Norm bounded hypothesis classes Binary classification using linear predictors	Chap. 3 of Percy Liang's notes
Week 8 02/27, 03/01	Lecture 13	Applications of Rademacher complexity based generalization bounds	Matrix completion Generalization bounds for two-layer neural nets using path norm	Tengyu Ma's lecture notes 1 , 2 Matrix Bernstein: section 6.1 of Joel Tropp's notes
Week 8 02/27, 03/01	Lecture 14	Shattering coefficient and VC dimension	VC dimension based generalization bounds	Chap. 20-21 of DLT
Week 10 03/13, 03/15	Lecture 15	Covering numbers, Algorithmic Stability	Deriving Generalization bounds using covering numbers Chaining	A survey article
Week 10 03/13, 03/15	Lecture 16	Algorithmic Stability PAC-Bayesian analysis	Occam's bound McAllester's bound	See handouts
Week 11 03/20, 03/22	Lecture 17	Non-vacuous PAC-Bayesian bounds for deepnets	Hessian-based generalization analysis for deep neural networks
Week 11 03/20, 03/22	Lecture 18	Graph neural networks Applications of PAC-Bayesian analysis to graph neural networks	Hessian-based measures for graph neural networks
Week 12 03/27, 03/29	Lecture 19	Paper presentations
Week 12 03/27, 03/29	Lecture 20	Paper presentations
Week 13 04/03, 04/05	Lecture 21	Paper presentations
Week 13 04/03, 04/05	Lecture 22	Paper presentations
Week 14 04/10, 04/12	Lecture 23	Paper presentations
Week 14 04/10, 04/12	Lecture 24	Paper presentations
Week 15 04/19	Lecture 25	In class discussion of final project reports

References

Part of the class materials are based on the following courses.

Deep Learning Theory by Matus Telgarsky
Algorithmic Aspects of Machine Learning by Ankur Moitra
Algorithmic Aspects of Machine Learning by Rong Ge
Learning from Limited Data by Stephen Bach
Theory of deep learning (ToDL) by Sanjeev Arora et al.
High-Dimensional Statistics: A Non-Asymptotic Viewpoint by Martin Wainwright