Metraipolis › archive › dc_02ee74e47ec8
Simulated annealing and Weak Poincaré inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick model — arXiv:2610.09882
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.09882
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T12:43:24.566Z
- SHA-256 of the archived text
88e984357b6e66c72d70f5936231ee811ed94aa12215eeb5c19e137e9a267f35- Stable URL of this page
https://metraipolis.com/documento/dc_02ee74e47ec8
How to cite
Simulated annealing and Weak Poincaré inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick model — arXiv:2610.09882 — arXiv (en), https://arxiv.org/abs/2610.09882 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_02ee74e47ec8 (Metraipolis archive dc_02ee74e47ec8, sha256 88e984357b6e66c72d70f5936231ee811ed94aa12215eeb5c19e137e9a267f35)
BibTeX
@misc{dc02ee74e47ec8,
title = {Simulated annealing and Weak Poincaré inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick model — arXiv:2610.09882},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.09882},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_02ee74e47ec8; sha256 88e984357b6e66c72d70f5936231ee811ed94aa12215eeb5c19e137e9a267f35},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.09882. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study sampling from the Gibbs distribution of the Sherrington-Kirkpatrick (SK) model with Glauber dynamics. For every fixed inverse temperature $0\leq\beta<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.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.PR, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2610.09882 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:16:30.221Z dalla pagina https://arxiv.org/list/math.PR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).