Course Details

This is a graduate topics class on algorithmic challenges in modern machine learning and data science. We will touch upon a number of domains (generative modeling, deep learning theory, robust statistics, Bayesian inference) and frameworks for algorithm design (spectral/tensor methods, gradient descent, message passing, MCMC, diffusions), focusing on provable guarantees. The theory draws upon a range of techniques from stochastic calculus, harmonic analysis, statistical physics, algebra, and beyond. We will also explore the myriad modeling challenges in building this theory and prominent paradigms (average-case complexity, smoothed complexity, oracles) for going beyond traditional worst-case analysis.

Time/Location: MW 2:15-3:30, SEC 1.413

Instructor: Sitan Chen (sitan@seas.harvard.edu)
Office hours: SEC 3.325, Monday 5:30-6:30

Teaching Fellows:

• Weiyuan Gong (wgong@g.harvard.edu), Office hours: Tuesday 4-5, SEC 3.317
• Marvin Li (marvinli@college.harvard.edu), Office hours: Friday 4-5, SEC 4.307 + 4.308

Pset office hour: Tuesday 10am-12pm, SEC 6.301 + 6.302

Canvas (for lecture recordings only)

Gradescope

Ed (discussion)

Course Policies: See syllabus for detailed overview.

Announcements

• Pset 3 due October 29, 11:59pm.

• Pset 2 due October 9, 11:59pm.

• Pset 1 due September 20, 11:59pm.

• Notifications of course placement will be sent out by Aug 31 at the latest.

• Pset 0 and course application form due September 3, 4:59pm

Assignments

Assignments will be posted below and in the course Overleaf when they become available.

• Pset 0 (due 09/03 at 4:59pm): PDF
• Pset 1 (due 09/20 at 11:59pm): PDF
• Pset 2 (due 10/09 at 11:59pm): PDF
• Pset 3 (due 10/29 at 11:59pm): PDF

Miscellaneous Materials

• Helpful references:
  • Roman Vershynin. High-Dimensional Probability (primarily Chapters 1-2, though 3-4 are also helpful)
• Compilation of recurring notation used in the course
• Some relevant past courses:
  • Ankur Moitra. Algorithmic Aspects of Machine Learning
  • Tselil Schramm. The Sum-of-Squares Algorithmic Paradigm in Statistics
  • Sam Hopkins. The Sum of Squares Method
  • Prasad Raghavendra. Efficient Algorithms and Computational Complexity in Statistics
  • Sanjeev Arora. Theory of Deep Learning
  • Song Mei. Mean Field Asymptotics in Statistical Learning
  • Lenka Zdeborova & Florent Krzakala. Statistical Physics For Optimization and Learning
  • Ahmed El-Alaoui. Topics in High-Dimensional Inference
  • Subhabrata Sen. STAT 217: Topics in High-Dimensional Statistics - Methods from Statistical Physics.
  • Kevin Tian. Continuous Algorithms.
  • Mark Sellke. Random High-Dimensional Optimization: Landscapes and Algorithmic Barriers.
  • Sam Hopkins and Costis Daskalakis. Algorithmic Statistics

Lectures

Date	Topic	Lecture Notes	Resources
Sep 4	Logistics, vignette: diffraction limit and learning theory	instructor notes, slides	Airy disks and mixture models: [Chen-Moitra '20] (lecture covered Sections 4.1 and 4.2) Learning mixtures of exponentials: [Moitra '15, extremal functions and Vandermonde matrices], see also [Liao-Fannjiang '14, "MUSIC" algorithm] and [Candes-Fernandez-Granda '12, theory of super-resolution]
Sep 9	Tensors I: Jennrich's algorithm, applications (super-resolution, Gaussian mixtures, independent component analysis)	instructor notes, slides, scribe notes	Book chapter on tensor decomposition: [Vijayaraghavan '20] Applications: learning mixtures of spherical Gaussians with linearly independent means: [Hsu-Kakade '13], mixtures of exponentials via tensor methods: [Huang-Kakade '15'], independent component analysis: [Comon '94], tensor methods for latent variable models: [Ananadkumar et al. '12] History of Jennrich's algorithm: [blog post] Karl Pearson, crabs, and method of moments: [blog post]
Sep 11	Tensors II: Iterative methods (gradient descent, tensor power method, alternating least squares)	instructor notes, slides, scribe notes	Tensor power method from random initialization, experiments comparing different methods: [Sharan-Valiant '17] Practicalities of tensor decomposition: [Janzamin et al. '19] (chapters 3 and 6) Additional readings: tensor power method with whitening: [Anandkumar et al. '12], gradient descent without deflation: [Ge et al. '15], surprising lower bounds for tensor power method: [Wu-Zhou '22], optimization landscape for random overcomplete tensors: [Ge-Ma '17], evidence for computational phase transition for overcomplete tensor decomposition: [Wein '23]
Sep 16	Tensors III: overcomplete tensor decomposition via smoothed analysis	instructor notes, slides, scribe notes	Original paper proposing smoothed analysis for tensor decomposition: [Bhaskara et al. '13] Simpler proof presented in class for condition number bound in smoothed bound: [Anari et al. '18], see also Section 4 of [Vijayaraghavan '20] Handles smoothing that is the same across modes via decoupling: [Bhaskara et al. '18] Smoothed analysis in algorithm design: simplex method [Spielman-Teng '01], condition number [Sankar-Spielman-Teng '03], CACM survey [Spielman-Teng '09]
Sep 18	Sum-of-squares I: pseudo-distributions, sum-of-squares proofs	instructor notes, slides	Sum-of-squares resources: graduate course 1: [Hopkins '24], graduate course 2: [Barak-Steurer], graduate course 3: [Schramm '21], graduate course 4: [Kunisky '22], graduate course 5 (youtube videos) [Kothari '20], SoS and estimation survey [Raghavendra-Schramm-Steurer '19]
Sep 23	Sum-of-squares II: robust regression and certifiable hypercontractivity	instructor notes, scribe notes	Robust regression via sum-of-squares: result covered in class: [Klivans-Kothari-Meka '18], better error guarantee: [Bakshi-Prasad '20], robust regression without distributional assumptions: [Chen-Koehler-Moitra-Yau '20], heavy-tailed regression: [Cherapanamjeri et al. '19]
Sep 25	Sum-of-squares III: mixtures of spherical Gaussians, entropy maximization	instructor notes, slides, scribe notes	Older papers on learning mixtures of Gaussians: [Dasgupta '99], [Arora-Kannan '05], [Dasgupta-Schulman '07], [Vempala-Wang '04], [Moitra-Valiant '10] Information-theoretic threshold at separation sqrt log k: [Regev-Vijayaraghavan '17] Notes on clustering spherical Gaussian mixtures with SoS: [Hopkins '18] Original papers on clustering spherical Gaussian mixtures at the optimal threshold: [Hopkins-Li '17], [Kothari-Steinhardt-Steurer '17], see also [Diakonikolas-Kane-Stewart '17] Follow-up paper achieving optimal threshold in polynomial time: [Li-Liu '21]
Sep 30	Supervised learning I: PAC learning, Fourier analysis, semirandom noise	slides, scribe notes	Fourier analysis of Boolean functions ("the bible"): [O'Donnell '14] (see chapters 1 and 3) Foundational works on PAC learning: paper introducing the model: [Valiant '84], low-degree algorithm: [Linial-Mansour-Nisan '93], PAC learning and VC dimension: [Blumer et al. '89] L1 polynomial regression for agnostic learning: [Kalai-Klivans-Mansour-Servedio '06] PTFs for distribution-free learning of DNFs: [Klivans-Servedio '01] PAC learning beyond AC0: [Jackson-Klivans-Servedio '02] Efficient distribution-free learning of halfspaces under Massart noise: [Diakonikolas-Gouleakis-Tzamos '19], [Chen-Koehler-Moitra-Yau '20] (this lecture) Lecture notes on matching loss and generalized linear models: [Kanade '22] (see Section 8.5) Hardness of agnostic learning of halfspaces: under Feige's random 3SAT hypothesis: [Daniely '15], under hardness of lattice problems: [Tiegel '22]
Oct 2	Supervised learning II: noise sensitivity, one-hidden layer MLPs, Hermite analysis, CSQ algorithms	instructor notes, slides, scribe notes	Noise sensitivity and Fourier concentration: [Klivans-O'Donnell-Servedio '02] Polynomial regression over continuous inputs: [Goel-Kanade-Klivans-Thaler '16], [Diakonikolas-Goel-Karmalkar-Klivans-Soltanolkotabi '20], [Diakonikolas-Kane-Pittas-Zarifis '21] (matching lower bounds) Tensor decomposition for learning one-hidden-layer MLPs: [Janzamin-Sedghi-Anandkumar '15], smoothed analysis setting: [Awasthi-Tang-Vijayaraghavan '21] Learning one-hidden-layer MLPs with poly(1/eps) dependence: [Chen-Dou-Goel-Klivans-Meka '23], [Chen-Narayanan '23], [Diakonikolas-Kane '23]
Oct 7	Supervised learning III: filtered PCA	instructor notes, slides, scribe notes	CSQ lower bounds: [Goel-Gollakota-Jin-Karmalkar-Klivans '20], [Diakonikolas-Kane-Kontonis-Zarifis '20] Filtered PCA: [Chen-Klivans-Meka '20], [Chen-Meka '20]
Oct 9	Supervised learning IV: linearized networks	instructor notes, slides, scribe notes	Lecture notes on linearized networks: [Misiakiewicz-Montanari](chapters 1-5, extensive literature review in Appendix B) Lazy training is consequence of choice of scaling: [Chizat-Oyallon-Bach '18], [Telgarsky '21] (blackboard part of this lecture) Convergence for training deep networks in NTK regime: original NTK paper: [Jacot-Gabriel-Hongler '18], convergence for deep networks: [Du et al. '18] and [Allen-Zhu-Li-Song '18] (see P. 3 for comparison), [Zou et al. '18] (classification instead of regression) Excellent slides on kernel methods: [Mairal-Vert '17] Generalization for random features and NTK: [Ghorbani-Mei-Misiakiewicz-Montanari '19], [Mei-Misiakiewicz-Montanari '21], [Montanari-Zhong '20]