CS Paper Radar

Sampling from the Sherrington-Kirkpatrick Model up to Criticality

Hang Du, Brice Huang, Sidhanth Mohanty, Amit Rajaraman

cs.DS math.PRcond-mat.dis-nnmath-ph ·submitted 2026-10-13 04:48 UTC · v1
theory

Abstract

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.

Comment
56 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS math.PR ·2026-10-07 ·Zhe Hou, Jingcheng Liu, Yixiao Yu
similarity 0.74
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.

0.39

Color Coding for the Sherrington-Kirkpatrick Model

cs.DS math-ph ·2026-10-07 ·Alina Harbuzova, Saba Lepsveridze, Mahbod Majid, Ankur Moitra
similarity 0.65
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

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.64
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

A Fully Polynomial Approximation Algorithm for the Sherrington-Kirkpatrick Model

cs.DS cond-mat.stat-mechmath.OCmath.PR+1 ·2026-11-03 ·Dylan Herman, Shouvanik Chakrabarti, Junhyung Lyle Kim, Guneykan Ozgul
similarity 0.60
Abstract

Montanari's incremental approximate message passing (IAMP) algorithm [FOCS 2019; SIAM J. Comput., 2025] and the zero-temperature formulation of El Alaoui, Montanari and Sellke (AMS) [Ann. Probab., 2021] find a $(1-\varepsilon)$ approximation to the maximum Sherrington-Kirkpatrick (SK) energy in $C(\varepsilon)N^2$ operations for fixed accuracy, with probability tending to one as $N\to\infty$, under their respective full-support and access-model assumptions. However, it was unknown whether this approximation could be achieved with work polynomial in both $N$ and $1/\varepsilon$, together with quantitative guarantees at finite dimension. Under the same assumptions as AMS, we introduce grouped IAMP with exact Gaussian query outputs (GEG-IAMP), which is the first SK approximation algorithm with total work polynomial in $N$ and $1/\varepsilon$ and a finite-size guarantee above a dimension threshold polynomial in $1/\varepsilon$ and $\log(1/α)$. More precisely, for every $α\in(0,1/2)$, it returns a $(1-\varepsilon)$ approximation with probability at least $1-α$ whenever $N\ge \mathsf{K}\varepsilon^{-2}\log^2(e/\varepsilon)\log(\mathsf{K}/α)$, using $O(N^2/\varepsilon)$ work and $O(N^2)$ storage. GEG-IAMP replaces the Onsager correction by Reeves's coupling construction [arXiv:2508.10782] and groups Euler-Maruyama steps into $O(1/\varepsilon)$ matrix-vector products. We also prove a relative guarantee for AMS IAMP with $O(N^2\varepsilon^{-3}\log^2(e/\varepsilon))$ work but a sufficient dimension exponential in inverse accuracy. By returning a fixed configuration below its dimension threshold, GEG-IAMP also provides an asymptotic fully polynomial randomized approximation scheme (AFPRAS), with an additive error independent of dimension.

0.22

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.59
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

High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear Regression

cs.DS cs.LGmath.PRmath.ST+1 ·2026-09-08 ·Syamantak Kumar, Purnamrita Sarkar, Kevin Tian, Yusong Zhu
similarity 0.51
Abstract · 61 pages

Sparsity is a powerful structural resource in optimization and statistics. We develop frameworks for leveraging sparsity in sampling problems over the Hamming slice $\mathcal{X}_k^d:=\{\mathbf{x}\in\{\pm 1\}^d:|\{i:\mathbf{x}_i=1\}|=k\}$, in high-dimensional regimes where $k\ll d$ (i.e., where $\mathcal{X}_k^d$ is \emph{highly magnetized}). We use our frameworks to design improved samplers for canonical problems in the study of \emph{Ising models} and \emph{Bayesian sparse linear regression}. Our first main result considers the \emph{Sherrington--Kirkpatrick} (SK) model restricted to fixed-magnetization slices $\mathcal{X}_k^d$. We give a polynomial-time sampler for fixed-magnetization SK models at any inverse temperature $β>0$, under arbitrary external fields, provided that $k\le c_βd$ for an appropriate constant $c_β$. By combining this result with an annealing strategy for estimating normalizing constants, we obtain polynomial-time samplers for the SK model at arbitrarily low temperatures under a sufficiently strong external field of strength $h$. In the large-$β$ limit, our framework permits sampling at field strengths within constant factors of the \emph{Almeida--Thouless line} delineating the replica-symmetric and replica-symmetry-breaking regions ([dAT78]), improving polynomially over the field strength $h(β)$ required by the recent work of [BAR26]. Our second main result concerns the measurement complexity of polynomial-time Bayesian sparse linear regression. Recent work by [KSTZ25] shows how to sample from the canonical \emph{Gaussian spike-and-slab posterior} with expected sparsity $k$, at any signal-to-noise ratio, given $n\gtrsim k^3\log^3 d$ Gaussian measurements. We improve this requirement to $n\gtrsim k^{3/2}\log^2 d+k\log^3 d$, using a common sparsity-aware framework underlying both our results.

0.26

Metropolis Random Walks Escape Deep Basins Faster in Higher Dimensions

eess.SY ·2026-11-11 ·Hansini Ramachandran, Bhaskar Krishnamachari
theory similarity 0.49
Abstract · 13 pages, 5 figures

Simulated Annealing (SA) is a widely used stochastic optimization algorithm. It is of great interest to understand how its ability to escape local minima at a fixed temperature depends on geometry and dimension. In prior work, we derived closed-form expressions for the expected basin escape time of a constant-temperature SA process on a one-dimensional piecewise-linear landscape. In this paper, we extend the analysis to $D$-dimensional cubic basins defined by the infinity-norm energy $V(x)=\|x\|_\infty$. The walk proposes nearest-neighbor moves uniformly and escapes upon first reaching the outer shell, that is, any site with $\|x\|_\infty=N$. We construct a one-dimensional birth-death shell-quotient chain by collapsing each concentric shell in the Metropolis electrical network to a single node while retaining its total stationary mass. We derive a closed-form expression for the mean escape time $Q_D(N)$ of this shell-quotient chain as a function of the acceptance probability $p$, the basin depth $N$, and the dimension $D$. For fixed $D$ and fixed $0<p<1$, the quotient escape time scales as $Θ(α^N/N^{D-1})$ as $N\to\infty$, where $α=1/p$. Relative to $D=1$, this gives an asymptotic speedup of order $N^{D-1}$ within this family of cubic basins. We prove that the true Metropolis mean escape time $H_D(N)$, without shell averaging, has the same $Θ(α^N/N^{D-1})$ scaling, establishing a lower bound via Rayleigh monotonicity and a matching upper bound through an explicit low-energy flow construction using Thomson's principle. Numerical solutions that exploit the walk's symmetries quantify the discrepancy between the quotient and true-chain means for $D=1,2,3$.

0.27

Fast Algorithms for Stoquastic Spin Systems

cs.CC quant-phcs.DSmath.CO ·2026-08-19 ·Ryan L. Mann
similarity 0.49
Abstract · 30 pages, 0 figures

We establish a general framework for developing fast sampling and counting algorithms for stoquastic spin systems at high temperature. Our framework is based on a rapidly mixing Markov chain for polymer models and a subcritical percolation process for sampling individual polymers. We apply our framework to obtain fast algorithms for approximating the partition function and sampling from the thermal distribution of (1) general stoquastic spin systems, (2) ferromagnetic Heisenberg models, and (3) antiferromagnetic Heisenberg models on bipartite graphs. For the Heisenberg models, we obtain an improved bound on the inverse temperature by using their respective cycle and loop representations.

0.44