Course Details

This is a graduate-level topics class on algorithmic challenges arising in modern machine learning and data science more broadly. The course will touch upon a number of well-studied problems (generative modeling, deep learning theory, adversarial robustness, inverse problems, inference) and frameworks for algorithm design (gradient descent, spectral methods, tensor/moment methods, message passing, convex programming hierarchies, Markov chains). As we will see, proving rigorous guarantees for these problems often draws upon a wide range of techniques from stochastic calculus, harmonic analysis, random matrix theory, algebra, and statistical physics. We will also explore the myriad modeling challenges that go into building theory for ML and discuss prominent paradigms (semi-random models, smoothed analysis, oracles) for going beyond traditional worst-case analysis.

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

Instructor: Sitan Chen (sitan@seas.harvard.edu)
Office hours: SEC 3.325, Thursday 4-5

Teaching Fellows:

• David Brewster (dbrewster@g.harvard.edu), Office hours: Maxwell-Dworkin 123, Tuesday 5-6
• Depen Morwani (dmorwani@g.harvard.edu), Office hours: SEC 1.404, Wednesday 11-12
• Rosie Zhao (rosiezhao@g.harvard.edu), Office hours: SEC 2.330, Monday 11-12

Pset office hour: SEC 3.314, Thursday 4-6 on weeks with a pset deadline

Canvas (for lecture recordings and announcements)

Gradescope

Ed (discussion)

Course Policies: See syllabus for detailed overview.

Student projects

• Yuyang Zhang: Difficulties and Solutions in Learning Latent Variable Models

• Prashanth Amireddy: Unsupervised Learning via Algebraic Circuit Reconstruction

• Itai Shapira: Edge of Stability Training Dynamics

• Alan Chung, Ben Schiffer, Kevin Luo: Non-Asymptotic Convergence of Diffusion Models

• Alexander Cai, Oliver Cheng, Tianze Jiang: Mean-field approximation and correlation rounding

• Shi Feng, Xiaodong Yang: Posterior Sampling via Diffusion Processes

• Arif Kerem Dayi: Leap Complexity: How SGD Exploits Hierarchical Structure in Functions to Learn Efficiently

Announcements

• 10/24: Pset 4 (final) is out, see below.

• 10/10: Pset 3 is out, see below.

• 10/2: See canvas announcement for information about final project.

• 9/25: Pset 2 is out, see below.

• 9/11: Pset 1 is out, see below.

• See Canvas for link to sign up for pset office hour preferences

• Notifications of course placement will be sent out Thursday afternoon, Aug 31.

Assignments

• Scribing template and instructions: TeX, bib file, PDF
• Pset 0 (due 08/29 at 11:59pm): PDF
• Pset 1 (due 09/22 at 3:59pm): PDF
• Pset 2 (due 10/09 at 11:59pm): PDF
• Pset 3 (due 10/23 at 11:59pm): PDF
• Pset 4 (due 11/06 at 11:59pm): PDF

Miscellaneous Materials

• Helpful references:
  • Roman Vershynin. High-Dimensional Probability (Chapters 1-2, 3-4 also helpful)
• Some relevant past courses:
  • Ankur Moitra. Algorithmic Aspects of Machine Learning
  • Tselil Schramm. The Sum-of-Squares Algorithmic Paradigm in Statistics
  • 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.

Lectures

Date	Topic	Lecture Notes	Resources
Sep 6	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 11	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 13	Tensors II: Iterative methods (gradient descent, tensor power method, alternating least squares)	instructor notes, slides, scribe notes 1, scribe notes 2	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 18	Tensors III: overcomplete tensor decomposition via smoothed analysis	instructor notes, slides, scribe notes 1, scribe notes 2	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 20	Sum-of-squares I: pseudo-distributions, application to robust regression	instructor notes, slides, scribe notes	Sum-of-squares resources: graduate course 1: [Barak-Steurer], graduate course 2: [Schramm '21], graduate course 3: [Kunisky '22], graduate course 4 (youtube videos) [Kothari '20], SoS and estimation survey [Raghavendra-Schramm-Steurer '19] 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 II: mixtures of spherical Gaussians, certifiable hypercontractivity	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 27	Sum-of-squares III: high-entropy constraints, noisy orthogonal tensor decomposition	instructor notes (board talk only), scribe notes	This lecture (SoS and maximum entropy constraints for tensor decomposition): [Ma-Shi-Steurer '16], expository notes: [Hopkins '18] Earlier works on SoS for tensor decomposition: [Barak-Kelner-Steurer '15], [Ge-Ma '15]
Oct 2	Sum-of-squares IV: rounding SoS relaxations with Jennrich's, overcomplete tensor decomposition	instructor notes, slides, scribe notes	Fast spectral algorithms for tensor decomposition inspired by SoS: overcomplete tensor decomposition: [Hopkins-Schramm-Shi-Steurer '15], [Ding-D'Orsi-Liu-Steurer-Tiegel], noisy orthogonal tensor decomposition: [Schramm-Steurer '17] Faster algorithm for clustering Gaussian mixtures at optimal separation: [Li-Liu '21]
Oct 4	Robust statistics I: motivation, iterative filtering	instructor notes, slides, scribe notes	Original computationally efficient robust statistics papers: [Diakonikolas-Kamath-Kane-Li-Moitra-Stewart '16], [Lai-Rao-Vempala '16] Graduate textbook on robust statistics: [Diakonikolas-Kane '22] (see chapters 1 - 3) Graduate course on robust statistics: [Li '19] (see lectures 4, 5) Subtleties between contamination models: better error bound under additive contamination: [Diakonikolas-Kamath-Kane-Li-Moitra-Stewart '17], log factor is necessary for strong contamination: [Diakonikolas-Kane-Stewart '16], separations between different models for robust mean testing: [Canonne-Hopkins-Li-Liu-Narayanan '23] Very fast algorithm for robust mean estimation using online learning: [Dong-Hopkins-Li '19] Application to defenses against poisoning neural nets: [Tran-Li-Madry '18]
Oct 11	Robust statistics II: list-decodable learning, subspace isotropic filtering	instructor notes (board talk only), supplemental instructor notes [pdf], scribe notes	Graduate textbook on robust statistics: [Diakonikolas-Kane '22] (see chapter 5) Subspace isotropic filtering paper (this lecture): [Diakonikolas-Kane-Kongsgaard-Li-Tian '20] Previous results on list-decodable mean estimation: paper introducing list-decodable learning [Balcan-Blum-Vempala '08], modern formulation of list-decodable learning: [Charikar-Steinhardt-Valiant '17], list-decodable mean estimation via multifilter: [Diakonikolas-Kane-Kongsgaard], first near-linear time algorithm: [Cherapanamjeri-Mohanty-Yau '20] List-decodable regression: [Karmalkar-Klivans-Kothari '19], [Raghavendra-Yau '19] List-decodable subspace recovery: [Raghavendra-Yau '20], [Bakshi-Kothari '16]
Oct 16	Robust statistics III: learning halfspaces under Massart noise	instructor notes, slides, scribe notes	Efficient distribution-free learning of halfspaces under Massart noise: [Diakonikolas-Gouleakis-Tzamos '19], [Chen-Koehler-Moitra-Yau '20] (this lecture), see also improved lower bound: [Diakonikolas-Kane '20, [Nasser-Tiegel '22], [Diakonikolas-Kane-Manurangsi-Ren] 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], see also: [Kalai-Klivans-Mansour-Servedio '06], [Klivans-Kothari '14], [Daniely-Vardi '21], [Diakonikolas-Kane-Pittas-Zarifis '21] Algorithm for learning halfspaces under RCN without margin assumption: [Blum-Frieze-Kannan-Vempala '97], [Cohen '97], [Dunagan-Vempala '04a], [Dunagan-Vempala '04b]
Oct 18	Supervised learning I: PAC basics, low-degree algorithm, L1/L2 polynomial regression, polynomial threshold functions	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]
Oct 23	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] CSQ lower bounds: [Goel-Gollakota-Jin-Karmalkar-Klivans '20], [Diakonikolas-Kane-Kontonis-Zarifis '20]
Oct 25	Supervised learning III: filtered PCA	instructor notes, slides, scribe notes	Filtered PCA: [Chen-Klivans-Meka '20], [Chen-Meka '20]
Oct 30	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]
Nov 1	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]
Nov 6	Computational complexity I: hardness basics, SQ lower bounds, noisy parity	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)
Nov 8	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]
Nov 13	Computational complexity III: cryptographic lower bounds, Daniely-Vardi lifting	instructor notes, slides, scribe notes	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]
Nov 15	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 20	Statistical physics II: belief propagation, Bethe free energy	instructor notes, slides, supplemental instructor notes [pdf], 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 27	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 29	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 29	Diffusion models	instructor notes, slides, scribe notes