CS Paper Radar

Simulated annealing and Weak Poincaré inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick model

Zhe Hou, Jingcheng Liu, Yixiao Yu

cs.DS math.PR ·submitted 2026-10-07 11:41 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Sampling from the Sherrington-Kirkpatrick Model up to Criticality

cs.DS math.PRcond-mat.dis-nnmath-ph ·2026-10-13 ·Hang Du, Brice Huang, Sidhanth Mohanty, Amit Rajaraman
theory similarity 0.74
Abstract · 56 pages

We prove that the simulated annealing algorithm efficiently samples from the Sherrington-Kirkpatrick model at inverse temperature $β< 1$ to an arbitrary inverse polynomial accuracy in total variation.

0.37

Optimal Mixing of Glauber Dynamics for the Sherrington-Kirkpatrick Model at $β< 1/2$

cs.DS math.PRmath-ph ·2026-08-23 ·Sihan Wang
theoryhighly cited similarity 0.73
Abstract · Revised version; added related references and improved exposition

We prove that for every fixed inverse temperature $β< 1 / 2$, with high probability over the disorder, the single-site Glauber dynamics for the $n$-spin Sherrington-Kirkpatrick model mixes from every initial configuration to within total variation distance $\varepsilon$ in $O_β\left(n \log\left(n / \varepsilon\right)\right)$ steps. The bound holds uniformly over all external fields and is optimal up to constants depending only on $β$. The main ingredient is a deterministic criterion for optimal-order Poincaré inequalities in general Ising models, established via the integrated Bakry-Émery criterion together with a new two-spin estimate. A standard application of the localization-scheme framework of Chen and Eldan then upgrades the Poincaré inequality to a modified log-Sobolev inequality, yielding the optimal mixing-time bound. The main ideas underlying the proof of the Poincaré inequality were generated by GPT-5.6 Sol Ultra.

0.46

Potential Hessian Ascent IV: Sampling the Sherrington-Kirkpatrick model at $β< 1$

cs.DS math.PRmath-ph ·2026-09-24 ·Holden Lee, Juspreet Singh Sandhu, Jonathan Shi
highly cited similarity 0.69
Abstract · 52 pages, zero figures

We give a polynomial-time algorithm to sample from the Gibbs measure of the Sherrington-Kirkpatrick (SK) model with $o_n(1)$ error in total-variation distance (TVD) at any inverse-temperature $β< 1$. The algorithm combines algorithmic stochastic localization (ASL) with rejection sampling over path-space via Jarzynski's equality (JE). The analysis extends the authors' prior $β< 1/2$ result [arXiv:2605.03718] by replacing all global regularity requirements in the stochastic differential equation (SDE) error analysis with local regularity around likely trajectories. The relaxed regularity is established using Celentano's proof of the local strong convexity of the TAP free energy [arXiv:2208.09550]. The analysis utilizes the cavity interpolation theory and free probability toolkit developed in the authors' previous result, where the former applies nearly verbatim and the latter applies supplemented with Lipschitz and $C^2$ extensions of various functions. The ASL and JE analysis arises from using the TAP free energy as an efficiently computable proxy for the actual free energy of the stochastically localized Gibbs measure [$ §$ 3, arXiv:2605.03718]. We give a list of \vocab{desiderata} encapsulating the approximation and regularity properties required of the TAP free energy, relaxing those of [$ §$ 2.5, arXiv:2605.03718] to only require local regularity. These generic desiderata are potentially applicable in other settings where a free energy surrogate exists, giving algorithmic sampling guarantees while bypassing the usual functional inequalities based approach.

0.46

Color Coding for the Sherrington-Kirkpatrick Model

cs.DS math-ph ·2026-10-07 ·Alina Harbuzova, Saba Lepsveridze, Mahbod Majid, Ankur Moitra
similarity 0.66
Abstract · 33 pages

We give a polynomial-time algorithm for approximating the partition function of mean-field mixed $p$-spin models to arbitrarily high accuracy throughout the second-moment regime. This improves the quasipolynomial-time algorithm of Bencs, Huang, Lee, Liu, and Regts (arXiv:2507.15616) and answers their open question. In particular, our result covers the entire replica-symmetric regime of the Sherrington--Kirkpatrick model. The algorithm is deterministic, runs in time polynomial in $n$ and $1/\varepsilon$, and succeeds for every typical realization of the disorder. Our main technical contribution is a new algorithmic application of color coding to the classical high-temperature expansion introduced by Aizenman, Lebowitz, and Ruelle in their study of fluctuations of the Sherrington--Kirkpatrick partition function. We combine this approach with the zero-freeness established by Bencs et al. (arXiv:2507.15616) to convert additive approximations into multiplicative ones.

0.54

Rapid mixing within a phase for Ising models

cs.DS math.PRmath-ph ·2026-10-16 ·Vasyl Paliy, Youngtak Sohn
theory similarity 0.66
Abstract · 42 pages

We study Glauber dynamics for Ising measures conditioned to have a sufficiently large majority of $+1$ spins. Under a sparse spectral width condition on the interaction matrix, we derive a Poincaré inequality for the conditioned measures from a magnetization drift condition, and a modified logarithmic Sobolev inequality from a stronger, entropy weighted condition. As applications, we obtain approximate posterior sampling in total variation distance for $\mathbb{Z}_2$ synchronization at high enough signal-to-noise ratio using $O(n\log n)$ Glauber updates from a spectral initialization. For ferromagnetic Ising models on random $d$-regular graphs, we prove rapid phase ordering down to inverse temperatures of order $1/d$, extending the temperature range of Gheissari, Sly, and Sohn (2025). Finally, we extend these inequalities to unconditioned Ising measures under an inward drift condition outside the conditioned region. This yields $O(n\log n)$ mixing of Glauber dynamics for the Sherrington-Kirkpatrick model at every fixed inverse temperature when the external field is sufficiently large.

0.20

Deterministic Approximation of the Total Variation Distance Between Spin Systems

cs.DS ·2026-10-08 ·Zelin Li, Minji Yang
similarity 0.63
Abstract

We study deterministic relative approximation of the total variation distance between two Gibbs distributions induced by spin systems on the same bounded-degree graph. For the hard-core model, we give a deterministic polynomial-time $\varepsilon$-relative-error approximation when both external-field vectors lie in $[b,(1-η)λ_{\mathrm c}(Δ)]^V$, where $b>0$ and $η\in(0,1)$ are fixed and $λ_{\mathrm c}(Δ)$ is the hard-core uniqueness threshold. For the Ising model, we obtain deterministic polynomial-time algorithms in two settings: the ferromagnetic Lee--Yang regime and the antiferromagnetic correlation-decay regime. We develop a new deterministic framework that reduces this task to estimating suitably chosen partition functions.

0.23

Approximate Counting for Mixed $p$-Spin Glasses in Weak External Fields via Cluster Expansion

cs.DS math.PRcond-mat.dis-nn ·2026-10-27 ·Qiang Wu
code/datahot direction similarity 0.62
Abstract · 38 pages, 3 figures. AI-assisted and a companion lean formalization in https://github.com/qiangwu2/approximate-counting-spin-glasses

We give algorithms for approximating the partition function $Z_N$ of the Sherrington--Kirkpatrick (SK) model and finite mixed Ising $p$-spin models with $p\ge 3$. The algorithms apply at a fixed margin below the second-moment threshold $β_{\mathrm f}$ with homogeneous weak external fields $|h|\leqρ_0N^{-1/4}$, for fixed $ρ_0>0$. For any accuracy $\varepsilon\in(0,1)$ and failure parameter $δ\in(0,1)$, they approximate $\log Z_N$ to additive error $\varepsilon$. The number of exact operations is polynomial jointly in $N$, $\varepsilon^{-1}$, and $δ^{-1}$. The disorder variables have i.i.d symmetric distribution with unit variance. The failure probability is at most $δ$ plus an explicit disorder tail bound. This tail bound tends to zero under a finite fourth moment condition. Our approach builds on the cluster expansions of Aizenman--Lebowitz--Ruelle~\cite{ALR87} and Dey--Wu~\cites{DW23,DW26}. For higher-order mixtures, we retain hypergraphs using few vertices and evaluate their total weight deterministically through local spin averages and inclusion--exclusion. For SK, we impose cutoffs on the number of vertices of degree at least three and on the total number of edges. We estimate the retained sum using randomized color coding~\cite{AYZ95}. A lower tail control based on reverse hypercontractivity~\cite{MOS13} converts the mean-square approximation of the normalized partition function into logarithmic accuracy.

0.46

Optimal Simulated Annealing for Partition Function Estimation

cs.DS ·2026-09-17 ·Heng Guo, Hongyang Liu, Xiongxin Yang, Yitong Yin, Yiyao Zhang
similarity 0.62
Abstract

In this note, we give a simple analysis of a non-adaptive simulated annealing algorithm for estimating the partition function of Gibbs distributions. This yields the most efficient reduction of this kind so far. We also establish lower bounds for both general and non-adaptive algorithms, showing that our algorithm is optimal over a broad range of parameters.

0.44