arXiv preprint ·
Simulated annealing and Weak Poincaré inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick model
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study sampling from the Gibbs distribution of the Sherrington-Kirkpatrick (SK) model with Glauber dynamics. For every fixed inverse temperature $0\leqβ 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Reflected Anchored Langevin Algorithms
Accelerating Non-Smooth and Heavy-Tailed Sampling
Fluctuations of Nonlinear Observables in Mean Field Neural Network Training
Weighted selection from elliptical distributions: a stochastic representation and an application to portfolio separation
The Geometry of Hierarchical Navigation: Accuracy and Query Cost for Point Process Input
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.