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
List of Suggested Projects (choose before Spring break)
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] 
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  [Notes] 
Spherical case:
[AlaouiMontanariS]
Ising case: [GamarnikJagannathKızıldağ] Random kSAT: [AchlioptasCoja–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  MultiOGP  
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 KacRice  
04/16  Student Presentations  
04/18  Student Presentations  
04/23  Student Presentations 
Scribing Template
 Overleaf Link (copy into a new project)
Useful References on HighDimensional Probability
 Ramon van Handel, Probability in High Dimension
 Roman Vershynin, HighDimensional Probability
 Sinho Chewi, LogConcave Sampling