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: Thursday 11-12, SEC 3.317
• Marvin Li (marvinli@college.harvard.edu), Office hours: Friday 4-5, SEC SEC 3.317

Pset office hour: Tuesday 3:15-5:15pm, SEC 3.317

Canvas (for lecture recordings only)

Gradescope

Ed (discussion)

Course Policies: See syllabus for detailed overview.

Announcements

• Pset 4 due November 11, 11:59pm.

• 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
• Pset 4 (due 11/11 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]
Oct 16	Supervised learning V: mean field limit	instructor notes, slides, scribe notes	Lecture notes on linearized networks: [Misiakiewicz-Montanari] (chapter 6, extensive literature review in Appendix B) Original mean-field neural net papers: [Mei-Montanari-Nguyen '18] (blackboard part of this lecture on propagation of chaos), [Chizat-Bach '18], [Rotskoff-Vanden-Eijnden '18], [Sirignano-Spiliopoulos '18] Improved non-asymptotic convergence: [Mei-Misiakiewicz-Montanari '19] Single index models and information exponent: [Ben Arous-Gheissari-Jagannath '20], leap complexity and mean-field for multi-index models: [Abbe-Boix-Adsera-Misiakiewicz '23], see also earlier works: [Abbe-Boix-Adsera-Misiakiewicz '22], [Abbe-Boix-Adsera-Brennan-Bresler-Nagaraj '21] Mean field for learning time-scales: [Berthier-Montanari-Zhou '23] Textbook on Wasserstein gradient flows: [Ambrosio-Gigli-Savare]
Oct 21	Computational complexity I: hardness basics, SQ lower bounds	instructor notes, slides, scribe notes	Original statistical query learning paper: [Kearns et al. '98], survey paper: [Reyzin '20], paper defining CSQ: [Bshouty-Feldman '02] Simple proof that SQ dimension suffices: [Szorenyi '09] Pairwise independence and statistical queries: [Bogdanov-Rosen '17] (see Section 7.7)
Oct 23	Computational complexity II: SQ dimension (application to MLPs), statistical dimension (applications to Gaussian mixtures, generative models)	instructor notes, slides, scribe notes	Moment matching recipe for SQ lower bounds for unsupervised problems: [Diakonikolas-Kane-Stewart '17], slides on this work: [Diakonikolas '17] Statistical dimension: [Feldman-Grigorescu-Reyzin-Vempala-Xiao '12], see also refinement by [Feldman '16] CSQ lower bounds for MLPs: [Diakonikolas et al. '20], [Goel et al. '20] "Cheating" SQ algorithm for learning real-valued functions: [Vempala-Wilmes '18] (see Section 4) SQ lower bound for learning simple generative models: [Chen-Li-Li '22]
Oct 28	Computational complexity III: cryptographic lower bounds, continuous LWE	instructor notes, slides	Reading list from a [reading group] on crypto and learning Cryptography resources: CS 127 [Barak], Goldreich's textbook [Goldreich], MIT 6.875 [Vaikuntanathan '23] Public key crypto and hardness of learning: original paper showing connection: [Kearns-Valiant '94], AC0 and TC0 (distribution specific): [Kharitonov '93], intersections of halfspaces: [Klivans-Sherstov '06], juntas: [Applebaum-Barak-Wigderson '09] Pseudorandom functions survey: [Bogdanov-Rosen '17] Hardness of agnostic learning: halfspaces and noisy parity: [Kalai-Klivans-Mansour-Servedio '06], connections to CSP refutation: [Kothari-Livni '17],, [Vadhan '17], [Daniely '15], hardness from LWE: [Diakonikolas-Kane-Ren '23], [Tiegel '22] Local PRGs: slides from survey talk: [Ishai], cryptography in NC0: [Applebaum-Ishai-Kushilevitz '06], Goldreich's construction: [Goldreich '01] Daniely-Vardi lifting: original paper for worst-case depth-3 MLPs: [Daniely-Vardi '21], extension to SQ for two-hidden-layer MLPs: [Chen-Gollakota-Klivans-Meka '22], extension to hardness in the smoothed analysis setting: [Daniely-Srebro-Vardi '23] Learning with errors: survey on classical LWE: [Regev '10], continuous LWE: [Bruna-Regev-Song-Tang '20], CLWE as hard as LWE: [Gupte-Vafa-Vaikuntanathan '22], CLWE hardness for single index models: [Song-Zadik-Bruna '21], CLWE hardness for one-hidden-layer networks: [Li-Zadik-Zampetakis '24]
Oct 30	Computational complexity IV: continuous LWE (cont'd)	instructor notes (board talk only)
Nov 4	Statistical physics I: intro to graphical models and variational inference	instructor notes (board talk only), scribe notes	Textbook on statistical physics and inference: [Mezard-Montanari '09] Lecture notes on statistical physics / optimization / learning: [Krzakala-Zdeborova '22] (see chapters 1 and 4.1) Lecture notes on graphical models: [Montanari '11] (see chapter 1), [Ermon '22] (see first two sections) Textbook on graphical models / variational inference: [Wainwright-Jordan '08] St. Flour lectures on statistical mechanics and sparse random graphs: [Montanari '14]
Nov 6	Statistical physics II: belief propagation, Bethe free energy	instructor notes, slides, scribe notes	Textbook on statistical physics and inference: [Mezard-Montanari '09] (see chapter 14) Lecture notes on statistical physics / optimization / learning: [Krzakala-Zdeborova '22] (see chapter 4.2) Lecture notes on graphical models: [Montanari '11] (see chapters 2 and 4.3), [Ermon '22] (see Inference section) Lecture notes on Bethe free energy / BP: [Macris '11], [Pfister '14] (see also the course page for an extensive reading list) Global convergence of BP for ferromagnetic Ising model: [Koehler '19]
Nov 11	Statistical physics III: derivation of AMP, state evolution, Z2 synchronization	instructor notes, slides, scribe notes	See the extensive survey on AMP by [Feng-Venkataramanan-Rush-Samworth '21] for pointers to the large literature on AMP Tutorials on AMP: survey on mean-field spin glass techniques: [Montanari-Sen '22] (see Section 2.4 for derivation of AMP and proof sketch for state evolution), lecture notes on high-dimensional inference [El Alaoui '21] (see Lectures 8 to 12 for details on state evolution), lecture notes on statistical physics / optimization / learning: [Krzakala-Zdeborova '22] (see chapter 8 for cavity method perspective on AMP), short lecture on AMP for Z2 synchronization [Wein '17], video recording of tutorial on statistical physics methods: [El Alaoui '22] Survey on low rank matrix estimation: [Miolane '19] First work rigorously proving state evolution for AMP (for solving TAP equation) [Bolthausen '12], state evolution result from class: [Bayati-Montanari '10]
Nov 13	Statistical physics IV: optimality of AMP for Z2 synchronization	instructor notes, slides, scribe notes	Proof in lecture of optimality comes from: [Deshpande-Abbe-Montanari '15] TAP free energy perspective: [Fan-Mei-Montanari '18], [Celentano-Fan-Mei '21], [Celentano '22], [Celentano-Fan-Lin-Mei '23], survey on TAP equation: [Bolthausen] Spectral algorithms from BP: "spectral redemption" using nonbacktracking operator: [Krzakala et al. '13], rigorous results on spectrum of nonbacktracking operator and related matrices: [Massoulie '13], [Mossel-Neeman-Sly '13], [Bordenave-Lelarge-Massoulie '15], [Abbe-Sandon '15], spectral algorithms for general "Bayesian constraint satisfaction problems" inspired by cavity method: [Liu-Mohanty-Raghavendra '21] Surveys on community detection: [Moore '17], [Abbe '18], optimal recovery for two communities: [Mossel-Neeman-Sly '13], [Yu-Polyanskiy '22]
Nov 18	Generative modeling I: stochastic calculus, Langevin diffusion	instructor notes, slides	Lecture notes: [Chewi '24], [Tian '23]
Nov 20	Generative modeling II: intro to diffusion models	instructor notes, slides, scribe notes
Nov 25	Generative modeling III: Girsanov's theorem and discretization analysis	instructor notes, slides
Dec 2	Generative modeling IV: Probability flow ODE, reverse transport inequalities, and shifted composition	slides
Dec 4	Generative modeling V: polynomial approximation and diffusions for learning Gaussian mixtures	instructor notes, slides