CS Paper Radar

Optimal Simulated Annealing for Partition Function Estimation

Heng Guo, Hongyang Liu, Xiongxin Yang, Yitong Yin, Yiyao Zhang

cs.DS ·submitted 2026-09-17 13:06 UTC · v1

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.

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

An FPRAS for Antiferromagnetic Ising Models on Random Regular Bipartite Graphs

cs.DS math.PR ·2026-08-19 ·Zhidan Li, Kuan Yang
similarity 0.56
Abstract

We design randomized approximation schemes for the partition function of antiferromagnetic Ising models with uniform external field on random regular bipartite graphs. Our algorithm generalizes the approach of Kocurek, Oveis Gharan and Tjowasi (arXiv, 2026) for hard-core models on the same random graph model beyond the uniqueness threshold. We show that, as long as $λ$ is upper bounded by a constant and $λ(1 - β) \lesssim Δ^{-1/2}$, an efficient randomized algorithm approximates the partition function with high probability. The algorithm first truncates configurations that are large on either side of the bipartition and then samples from Gibbs distributions conditioned on fixed sizes on one or both sides. To choose an optimal truncation bound, we establish concentration properties of the Gibbs distribution on random regular bipartite graphs. Then we apply high-dimensional expansion and prove trickle-down theorems to obtain fast samplers for the conditioned distributions.

0.18

How Much Distribution Shift Can a Clustering Withstand? Exact Split and Merge Certificates for Structured Transports

cs.LG ·2026-11-16 ·Alisina Bayati, Srinivasa Salapaka, Shahriar Talebi
unusual similarity 0.49
Abstract

In clustering, the distribution of the population being clustered is often uncertain or changes over time, so the true distribution may shift away from the nominal distribution used to form the clustering. Once the clustering is committed and each member is assigned to a cluster, such shifts may change the distribution of each cluster. They can make a cluster too spread out for one representative at a given resolution, motivating a split, or bring distinct clusters close enough to share a representative at that resolution, motivating a merge. We make these split and merge events precise using a local stability criterion built on the phase-transition analysis in deterministic annealing. This notion of stability enables us to quantify how robust a clustering is against such events. Furthermore, motivated by applications in which uncertainty and population change are structured, we study shifts whose displacements are restricted to a prescribed subspace. The smallest structured shifts that reach the respective thresholds define the split and merge radii, for which we obtain exact semidefinite programming (SDP) reformulations. The split SDP has only two scalar decision variables. These convex reformulations enable us to combine the radii into a robustness certificate for the full clustering that gives the size of the smallest structured shift that reaches any monitored split or merge threshold.

0.28

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

Microcanonical Hamiltonian Monte Carlo and the Helmholtz Theorem

cs.AI cond-mat.stat-mech ·2026-09-07 ·Heinrich von Campe, Bjoern Malte Schaefer
publishedpositiontheory similarity 0.48
Abstract

The recently proposed Microcanonical Hamiltonian Monte Carlo algorithm has not yet been studied in detail from a thermodynamic point of view; this work aims to fill that gap. We demonstrate how thermodynamical state variables and potentials can be derived and thereby demonstrate that the construction of the algorithm formally represents a microcanonical thermodynamic ensemble. In particular, we demonstrate (analytically and numerically) that the algorithm fulfils the Helmholtz theorem, an alternative formulation of the first law of thermodynamics. Furthermore, we construct a new sampling algorithm that extends the original to lower-dimensional inference problems. Finally, we argue that canonical Markov Chain Monte Carlo algorithms are more natural than Microcanonical Hamiltonian Monte Carlo from the thermodynamic and information-theoretic point of view.

0.49

Deterministic Approximation of the Total Variation Distance Between Spin Systems

cs.DS ·2026-10-08 ·Zelin Li, Minji Yang
similarity 0.47
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

Provable Quantum-Classical Separation for Continuous Gibbs Sampling

cs.DS quant-phcs.ETcs.LG ·2026-08-25 ·Enrico Olivucci, Mariia Sobchuk, Sehmimul Hoque, Jeffrey Hnybida, Kyungho W. Kim +2 more
theory similarity 0.47
Abstract

We prove the first quantum-classical separation for a sampling problem over a continuous domain. For a class of Gibbs states $p\propto e^{-βE}$ on the torus $\mathbb{T}^d$ with smooth ($s$-Gevrey) potential and barrier amplitude $α=e^{βΔ}$, where $Δ= \max E-\min E$, every classical algorithm querying the value, gradient, or any higher-order derivatives of the log-density requires $Ω(α)$ queries to sample at constant accuracy in total variation distance, while a quantum algorithm based on quantum singular value thresholding and temperature annealing samples with $\tilde{O}\left(\sqrtα\right)$ queries to an oracle for the gradient. The advantage is quadratic in the barrier amplitude, which becomes exponential in the dimension, $e^{Ω(d)}$, at low temperature. The classical bound is information-theoretic, holding for every classical algorithm with query access to the Gibbs potential and its derivatives at any order.

0.26

On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum

cs.DS cond-mat.dis-nnmath-phmath.PR ·2026-10-29 ·Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, Guus Regts
similarity 0.46
Abstract · 98 pages

We give the first polynomial-time algorithm to estimate the partition function of the antiferromagnetic Ising model on the uniformly random $d$-regular graph to arbitrarily high accuracy for all inverse temperatures up to the Kesten-Stigum threshold. This is the entire regime in which the model is "replica symmetric," and is conjectured to be optimal for polynomial-time counting and sampling. To achieve our algorithmic result, we establish the absence of Fisher zeros for the partition function in a constant-width strip around the interval from $0$ up to the Kesten-Stigum threshold, with high probability over the randomness of the input graph. AI Disclosure: The overarching vision and proof architecture were developed solely by the authors without AI input. GPT 5.5 Pro was used, with extensive guidance from the authors, for only a few minor technical aspects of the proof. The authors independently verified correctness and wrote everything by hand. We take full responsibility for its contents. A more detailed statement can be found in Section 1.2.

0.26