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:
 Random constraint satisfaction problems, spin glasses, and tensor PCA
 Landscape complexity via critical point counting
 The overlap gap property as a geometric barrier to optimization
 Implications for Markov chain sampling
 Combining these ideas to prove the spherical Parisi formula
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:30am11:45am, Science Center 309A
Office Hours
Thursday, 2pm4pm
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:
[KrzakalaMontanariRicci–TersenghiZdeborova]
Tensor PCA: [MontanariRichard] Random XORSAT: [DuboisMandler] for 3XORSAT threshold, [IbrahimiKanoriaKraningMontanari] for structural transition, [AyreCoja–OghlanGaoMü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  Concentrationenhanced 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 "concentrationenhanced 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  KacRice I: general formula  [Notes] 
Original paper: [Kac]
Book Treatments: [BerzinLatourLéon], [AdlerTaylor] 
02/08  KacRice 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 [AndersonGuionnetZeitouni].
The HoffmanWielandt inequality is Lemma 2.1.19. See e.g.
this note
for the Birkhoffvon Neumann theorem on doubly stochastic matrices.
1st moment analysis of critical points: [AuffingerBen ArousČerný], [AuffingerBen Arous] Comprehensive analysis of random determinants: [Ben ArousBourgadeMcKenna] Survey: [RosFyodorov] 
02/13  KacRice III: second moments and E_{∞} threshold  [Notes] 
2nd moment analysis:
[Subag],
[Ben ArousSubagZeitouni]

02/15  KacRice IV: topological trivialization  [Notes] 
Spin glasses with external field:
[FyodorovLe Doussal],
[BeliusČernýNakajimaSchmidt]
Strong topological trivialization: [HuangS23b] 
02/20  Langevin dynamics: fast mixing at high temperature  [Notes] 
Fast mixing at high temperature:
[GheissariJagannath]
Fast mixing for Ising spin glasses: [EldanKoehlerZeitouni], [AdhikariBrenneckXuYau], [AnariJainKoehlerPhamVuong] 
02/22  Langevin dynamics: concentration properties  [Notes] 
Concentration properties: [GamarnikJagannath, Section 6], [HuangS, Section 8] CugliandoloKurchan equations for Langevin dynamics: [CugliandoloKurchan] (nonrigorous analysis) [Ben ArousDemboGuionnet] (soft dynamics) [DemboGuionnetMazza] (high temperature) [S] (nonsoft dynamics, threshold energy for pure models) 
02/27  Hightemperature with external field  [Notes] 
The lower bound technique from class has been used in several hightemperature models with external field.
Usually instead of topological trivialization, an explicit algorithm is used to find the centering point:
SherringtonKirkpatrick: [Bolthausen] (introducing the method), [BrenneckeYau] Ising perceptron: [DingSun] Highdimension linear regression: [QiuSen] 
02/29  Shattering I: geometric construction  [Notes] 
Spherical case:
[AlaouiMontanariS]
Ising case: [GamarnikJagannathKızıldağ] Random kSAT: [AchlioptasCoja–Oghlan] See also Chapter 16 of [Talagrand] 
03/05  Shattering II: completing the proof  [Notes]  [AlaouiMontanariS, Section 3] 
03/07  Shattering III: no stable sampling  [Notes] 
[AlaouiMontanariS, Section 5]
Disorder chaos: [Chatterjee] Analogous barrier from replica symmetry breaking: [AlaouiMontanariS 22, Section 5] 
Spring Break       
03/19  Subag's Optimization Algorithm and Ultrametricity  [Notes] 
Original algorithm: [Subag 18]
Ising spin glasses: [Montanari], [AlaouiMontanariS20] Solving random polynomial equations: [MontanariSubag] Characterization of full RSB on the sphere: [ChenSen] See Sections 1.31.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: [GamarnikSudan 13]
Random kSAT: [GamarnikSudan 14], [BreslerHuang] Submatrices with large mean: [GamarnikLi] Recent Survey: [Gamarnik] 
03/26  MultiOGP  [Notes] 
Optimal bounds for MaxIndSet using multiOGP:
[RahmanVirag],
[Wein]
1RSB prediction for MaxIndSet on random regular graphs: [DingSlySun] Algorithms and Barriers for Symmetric binary perceptron: [BansalSpencer], [GamarnikKızıldağPerkinsXu22], [GamarnikKızıldağPerkinsXu23] 
03/28  OGP for Inference (Sparse PCA)  [Notes] 
Analysis of MLE: [BanksMooreVerzelenVershyninXu]
Faster Algorithm: [DingKuniskyWeinBandeira] OGP for Sparse PCA: [Ben ArousWeinZadik] Sparse regression: [GamarnikZadik] 
04/02  Branching OGP and Optimality of Subag's algorithm  [Notes] 
Argument from class: [HuangS23a]
Introduction of Branching OGP: [HuangS21], Application to random graph alignment: [DuGongHuang] 
04/04  Ruelle Probability Cascades  [Notes] 
Ruelle cascades:
[Panchenko, Chapter 2], or original paper [Ruelle]
Twoparameter generalization: [PitmanYor] 
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 [HuangS23c]
See also: [Talagrand], [Panchenko], [Chen], [ChenSen] 
04/16  Student Presentations  [Slides by Zad and Jarell]  
04/18  Student Presentations  
04/23  Student Presentations 
Scribing Template
 Overleaf Link (copy into a new project)
Useful References
 Dmitry Panchenko, The SherringtonKirkpatrick Model
 Ramon van Handel, Probability in High Dimension
 Roman Vershynin, HighDimensional Probability
 Sinho Chewi, LogConcave Sampling