Week 1 - Introduction and Overview

Recap of the Meeting

• We introduced the Sherrington-Kirkpatrick model, translating spin glass vocabulary such as overlap, the partition function, and free energy, to concepts in optimization.

• We stated the Parisi Variational Principle and attempted to build a geometric picture of how the dynamics in Parisi’s equations evolve.

• We stated an anology between Parisi’s equations and Hamilton-Jacobi equations where the “Hamiltonian” is given by the L2-norm squared.

• We outlined various conjectures regarding how certain first-order optimization methods such as (stochastic) gradient descent might arise from a more algorithmic proof of Parisi’s Variational Principle, using how we currently understand them to arise from the studying Hamilton-Jacobi equations as an analogy.

• We stated the over-arching theme of this tutorial sequence, and outlined plans for subsequent meetings.

• Next time we focus on the mathematical objects that arise in proving Parisi’s variational principle, and begin discussing the replica symmetry (breaking) ansatzen.

Material

• [pdf] Scanned presentation notes

• [link] Scribe notes – Juspreet Singh Sandhu (see Day 1)

Full Reference List

Historical origins of Parisi’s variational principle

• (1975) Solvable model of a spin-glass – David Sherrington, Scott Kirkpatrick
• (1977) Solution of ‘Solvable model of a spin glass’ – David J. Thouless, Philip W. Anderson, and Robert G. Palmer
• (1979) Toward a mean field theory for spin glasses – Giorgio Parisi
• (1979) Infinite number of order parameters for spin-glasses – Giorgio Parisi
• (1980) A sequence of approximated solutions for the S-K model for spin glasses – Giorgio Parisi
• (1981) Random-energy model: an exactly solvable model of disordered systems – Bernard Derrida
• (1983) Order parameter for spin-glasses – Giorgio Parisi
• (1984) Replica symmetry breaking and the nature of the spin glass phase – Marc Mezard, Giorgio Parisi, Nicolas Sourlas, Gerard Toulouse, Miguel Virasoro
• (1985) The microstructure of ultrametricity – Marc Mezard, Miguel Virasoro
• (1986) Metastable states in spin glasses – Alan J. Bray, Michael A. Moore
• (1986) Marc Mezard, Giorgio Parisi, and Miguel Virasoro’s “Spin Glass Theory and Beyond”

Proving the Parisi variational principle

• (1987) A mathematical reformulation of Derrida’s REM and GREM – David Ruelle
• (1998) The Sherrington-Kirkpatrick model: A challenge for mathematicians – Michele Talagrand
• (2002) The thermodynamic limit in mean field spin glass models – Francesco Guerra, Fabio L. Toninelli
• (2003) An extended variational principle for the SK spin-glass model – Michael Aizenman, Robert Sims, Shannon L. Starr
• (2006) The Parisi formula – Michele Talagrand
• (2006) Parisi measures – Michele Talagrand (a tutorial paper published to the Journal of Functional Analysis)
• (2011) The Parisi ultrametricity conjecture – Dmitry Panchenko
• (2013) A Parisi formula for mixed p-spin models – Dmitry Panchenko

Pure state geometry of the Gibbs distribution

• (2008) Clusters of solutions and replica symmetry breaking in random k-satisfiability – Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian
• (2014) Approximate ultrametricity for random measures and applications to spin glasses – Aukosh Jagganath
• (2015) The legendre structure of the Parisi formula – Antonio Auffinger, Wei-Kuo Chen
• (2016) The Geometry of the Gibbs in Pure Spherical Spin Glass – Eliran Subag
• (2018) Free Energy Landscape in Spherical Spin Glass – Eliran Subag
• (2018) Geometric description of the spherical spin glass Gibbs measures and temperature chaos – Gerard Ben Arous (CIRM talk)

Modern algorithmic applications of the variational principle

• (2010) The dynamics of message passing on dense graphs, with applications to compressed sensing – Mohsen Bayati, Andrea Montanari
• (2018) Following the Ground State of full-RSB Spherical Spin Glass – Eliran Subag
• (2018) Optimization of the Sherrington-Kirkpatrick Hamiltonian – Andrea Montanari
• (2020) Optimization of mean-field spin glasses – Ahmed Al Alaoui, Andrea Montanari, Mark Sellke
• (2020) Incremental Approximate Message Passing – Ahmed Al Alaoui (Simons semester on Computation Phase Transitions)
• (2021) Local algorithms for Maximum Cut and Minimum Bisection on locally treelike regular graphs of large degree – Ahmed Al Alaoui, Andrea Montanari, Mark Sellke

Textbooks

• (2001) Hidetoshi Nishimori’s “Statistical Physics of Spin Glasses and Information Processing An Introduction”
• (2009) Marc Mezard, and Andrea Montanari’s “Information, Physics, and Computation”
• Dmitry Panchenko’s “The Sherrington-Kirkpatrick Model” (specifically chapters 1, 2, 3 and the bonus chapter)
• Michele Talagrand’s “Mean Field Models for Spin Glasses” [Vol. 1] [Vol. 2] (specifically chapters 1, 12, 13, 14)
• Michele Talagrand’s page on spin glass publications

Online lectures

• (2020) A brief introduction to mean-field spin glass models [1], [2], [3], [4] – Aukosh Jagganath (OOPS)
• (2020) Optimization of full-RSB spherical spin glasses – Eliran Subag (Simons semester on Computational Phase Transitions)
• (2021) TAP approach and optimization of full-RSB spherical spin glasses – Eliran Subag (OOPS)
• (2020) Mean-field methods in high-dimensional statistics and nonconvex optimization [1], [2], [3], [4], [5] – Andrea Montanari (OOPS)
• (2020) Incremental Approximate Message Passing – Ahmed Al Alaoui (Simons semester on Computation Phase Transitions)
• (2021) Approximate Message Passing Algorithms [1], [2] – Cynthia Rush (Simons semester on the Computational Complexity of Statistical Inference)
• (2021) Optimal iterative algorithms for problems with random data [1], [2] – Andrea Montanari (Simons semester on the Computational Complexity of Statistical Inference)