STAT 291, Spring 2024
Random High-Dimensional Optimization: Landscapes and Algorithmic Barriers

Instructor

Mark Sellke (msellke@fas.harvard.edu)

Teaching Fellow

Yufan Li (yufan_li@g.harvard.edu)

Course Description

This is a graduate topics course focusing on paradigmatic optimization problems with random objective functions. We will develop the tools needed to understand the geometric behavior of complex random landscapes, the different phase transitions that can occur, and how these transitions are linked to the success and failure of efficient algorithms. Topics will include:

Homework

Homework 1, due February 9

Homework 2, due February 26

Homework 3, due March 22 (recommended due date: March 8)

Extra Credit Problems, due anytime

List of Suggested Projects (choose before Spring break)

Meeting Time

Tuesday/Thursday, 10:30am-11:45am, Science Center 309A

Office Hours

Thursday, 2pm-4pm

Course Schedule (subject to change)

Date Topic Link to Notes Other References and Resources
01/23 Course logistics, overview of phase transitions in disordered landscapes   [Slides] Predicted phase diagram: [Krzakala-Montanari-Ricci–Tersenghi-Zdeborova]
Tensor PCA: [Montanari-Richard]
Random XOR-SAT: [Dubois-Mandler] for 3-XORSAT threshold, [Ibrahimi-Kanoria-Kraning-Montanari] for structural transition, [Ayre-Coja–Oghlan-Gao-Müller] for general satisfiability threshold
01/25 Free energies, moment computations   [Notes] Classical statistical mechanics: [David Tong's Notes]
Second moment method for the SK model: [Talagrand]
01/30 Concentration-enhanced second moment method   [Notes] Concentration of measure: for a primer, see this blog post by Terry Tao (we showed Theorem 8 in class). See the references by van Handel and Vershynin below for more.
An early use of the "concentration-enhanced second moment" is by [Frieze] on independent sets in random graphs.
02/01 Geometric and statistical consequences of annealed free energy   [Notes] Section 1.2 of [Dmitry Panchenko's book] explains the Gaussian integration by parts computation in much generality.
02/06 Kac-Rice I: general formula   [Notes] Original paper: [Kac]
Book Treatments: [Berzin-Latour-Léon], [Adler-Taylor]
02/08 Kac-Rice II: spherical spin glasses   [Notes] Semicircle law for GOE matrices: see Section 2.1 (or 2.4 or 2.5) of the excellent book by [Anderson-Guionnet-Zeitouni]. The Hoffman-Wielandt inequality is Lemma 2.1.19. See e.g. this note for the Birkhoff-von Neumann theorem on doubly stochastic matrices.
1st moment analysis of critical points: [Auffinger-Ben Arous-Černý], [Auffinger-Ben Arous]
Comprehensive analysis of random determinants: [Ben Arous-Bourgade-McKenna]
Survey: [Ros-Fyodorov]
02/13 Kac-Rice III: second moments and E threshold   [Notes] 2nd moment analysis: [Subag], [Ben Arous-Subag-Zeitouni]
02/15 Kac-Rice IV: topological trivialization   [Notes] Spin glasses with external field: [Fyodorov-Le Doussal], [Belius-Černý-Nakajima-Schmidt]
Strong topological trivialization: [Huang-S-23b]
02/20 Langevin dynamics: fast mixing at high temperature   [Notes] Fast mixing at high temperature: [Gheissari-Jagannath]
Fast mixing for Ising spin glasses: [Eldan-Koehler-Zeitouni], [Adhikari-Brenneck-Xu-Yau], [Anari-Jain-Koehler-Pham-Vuong]
02/22 Langevin dynamics: concentration properties   [Notes] Concentration properties:
[Gamarnik-Jagannath, Section 6], [Huang-S, Section 8]
Cugliandolo-Kurchan equations for Langevin dynamics: [Cugliandolo-Kurchan] (non-rigorous analysis)
[Ben Arous-Dembo-Guionnet] (soft dynamics)
[Dembo-Guionnet-Mazza] (high temperature)
[S] (non-soft dynamics, threshold energy for pure models)
02/27 High-temperature with external field   [Notes] The lower bound technique from class has been used in several high-temperature models with external field. Usually instead of topological trivialization, an explicit algorithm is used to find the centering point:
Sherrington-Kirkpatrick: [Bolthausen] (introducing the method), [Brennecke-Yau]
Ising perceptron: [Ding-Sun]
High-dimension linear regression: [Qiu-Sen]
02/29 Shattering I   [Notes] Spherical case: [Alaoui-Montanari-S]
Ising case: [Gamarnik-Jagannath-Kızıldağ]
Random k-SAT: [Achlioptas-Coja–Oghlan]
See also Chapter 16 of [Talagrand]
03/05 Shattering II
03/07 Shattering III
Spring Break -- -- --
03/19 Subag's Optimization Algorithm and Ultrametricity
03/21 Overlap Gap Property and Hardness of Optimization
03/26 OGP for Inference Problems
03/28 Multi-OGP
04/02 Branching OGP and optimality of Subag's algorithm
04/04 General interpolation bound for the Parisi formula
04/09 Properties of Parisi's variational principle
04/11 Proof of Spherical Parisi Formula: return of Kac-Rice
04/16 Student Presentations
04/18 Student Presentations
04/23 Student Presentations

Scribing Template

Useful References on High-Dimensional Probability

Some Relevant Past Courses