Simulated annealing achieves precise sampling for spin glass models
Simulated annealing and Weak Poincaré inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick model
Data Structures and Algorithms
Summary
Sampling from complex probability models like the Sherrington-Kirkpatrick spin glass is important but very challenging. The authors present a simulated annealing method that efficiently produces samples very close to the true model distribution with polynomial-time guarantees. Their approach relies on sophisticated mathematical inequalities and new techniques to control errors that arise when approximating these complex systems. This work advances the understanding of how to accurately analyze and approximate difficult random systems using computational methods.
What this means in practice
- •For optimization algorithm designers: Use the method to sample accurately from complex probability models with provable precision guarantees in polynomial time.
- •For statistical physics modelers: Estimate partition functions and analyze phase behavior rigorously on the Sherrington-Kirkpatrick spin glass model using this controlled simulated annealing approach.
A theory result. No direct application yet.
Authors
Zhe Hou, Jingcheng Liu, Yixiao Yu
Abstract
We study sampling from the Gibbs distribution of the Sherrington-Kirkpatrick (SK) model with Glauber dynamics. For every fixed inverse temperature $0\leqβ<1$ and every fixed $M,D>0$, we give a polynomial-time simulated annealing algorithm whose output distribution is within $n^{-M}$ total-variation distance of the Gibbs distribution, with probability at least $1-n^{-D}$ over the interaction matrix. The algorithm starts from uniform product spins and uses Glauber dynamics along an increasing inverse-temperature schedule. The same approach also yields partition-function estimates with relative error $n^{-M}$. The key ingredient is a quantitative weak Poincaré inequality. Building on the stochastic-localization approach to weak Poincaré inequalities [Davies, Lee, Sandhu, and Shi, arXiv:2607.08160, 2026], we use Gaussian isoperimetry to directly compare exact stochastic localization paths. Our comparison tolerates failures of local Lipschitz continuity of the posterior mean by controlling their accumulated cost. The local Lipschitzness comes from approximating the posterior means by stationary points of the Thouless-Anderson-Palmer (TAP) free energy in locally strongly convex regions located by approximate message passing, a paradigm introduced by algorithmic stochastic localization [El Alaoui, Montanari, and Sellke, 2025; Celentano, 2024]. The approximation errors are roughly characterized by the validity of the TAP gradient equations, but in a different coordinate. To show that the errors rarely accumulate too much, we need a strong concentration control. A direct argument would require solving a variant of an open problem by Talagrand [2010, Research Problem 1.7.9]. We bypass this open problem with an intermediate conditioning step and transfer the control back by establishing the stability of the TAP gradient under deletion of coordinates.