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

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]
[Dmitry Panchenko's book] is a good way to learn the proof of the Parisi formula.
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: geometric construction   [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: completing the proof   [Notes] [Alaoui-Montanari-S, Section 3]
03/07 Shattering III: no stable sampling   [Notes] [Alaoui-Montanari-S, Section 5]
Disorder chaos: [Chatterjee]
Analogous barrier from replica symmetry breaking: [Alaoui-Montanari-S 22, Section 5]
Spring Break -- -- --
03/19 Subag's Optimization Algorithm and Ultrametricity   [Notes] Original algorithm: [Subag 18]
Ising spin glasses: [Montanari], [Alaoui-Montanari-S-20]
Solving random polynomial equations: [Montanari-Subag]
Characterization of full RSB on the sphere: [Chen-Sen]
See Sections 1.3-1.5 of [Panchenko's book] for general properties of limiting overlap distributions.
03/21 Overlap Gap Property and Hardness of Optimization   [Notes] Original independent set paper: [Gamarnik-Sudan 13]
Random k-SAT: [Gamarnik-Sudan 14], [Bresler-Huang]
Submatrices with large mean: [Gamarnik-Li]
Recent Survey: [Gamarnik]
03/26 Multi-OGP   [Notes] Optimal bounds for Max-Ind-Set using multi-OGP: [Rahman-Virag], [Wein]
1-RSB prediction for Max-Ind-Set on random regular graphs: [Ding-Sly-Sun]
Algorithms and Barriers for Symmetric binary perceptron: [Bansal-Spencer], [Gamarnik-Kızıldağ-Perkins-Xu-22], [Gamarnik-Kızıldağ-Perkins-Xu-23]
03/28 OGP for Inference (Sparse PCA)   [Notes] Analysis of MLE: [Banks-Moore-Verzelen-Vershynin-Xu]
Faster Algorithm: [Ding-Kunisky-Wein-Bandeira]
OGP for Sparse PCA: [Ben Arous-Wein-Zadik]
Sparse regression: [Gamarnik-Zadik]
04/02 Branching OGP and Optimality of Subag's algorithm   [Notes] Argument from class: [Huang-S-23a]
Introduction of Branching OGP: [Huang-S-21],
Application to random graph alignment: [Du-Gong-Huang]
04/04 Ruelle Probability Cascades   [Notes] Ruelle cascades: [Panchenko, Chapter 2], or original paper [Ruelle]
Two-parameter generalization: [Pitman-Yor]
04/09 Upper Bound: Guerra's Interpolation Bound   [Notes] Original interpolation for Ising spin glasses: [Guerra]
Spherical model: [Talagrand]
04/11 Proof of Spherical Parisi Formula   [Notes] Lecture was based on [Huang-S-23c]
See also: [Talagrand], [Panchenko], [Chen], [Chen-Sen]
04/16 Student Presentations [Slides by Zad and Jarell]
04/18 Student Presentations
04/23 Student Presentations

Scribing Template

Useful References

Some Relevant Past Courses