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.

Announcements

• 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.

• Pset 0 and course application form due August 29, 11:59pm

Assignments

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

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

Miscellaneous Materials

• Helpful references:
  • Roman Vershynin. High-Dimensional Probability (Chapters 1-2, 3-4 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
  • 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	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	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	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]