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