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