Proves an exponential lower bound on the mixing time of Glauber dynamics for the p-spin glass at inverse temperatures above C ln(p)/p for large p, via energy landscape analysis with Gaussian decompositions and a bottleneck bound.
Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta < 1/2
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
We give a polynomial-time algorithm to sample from the Gibbs measure of the Sherrington-Kirkpatrick model with negligible total-variation distance (TVD) error up to inverse temperature $\beta < 1/2$. Prior work obtained TVD error guarantees only up to $\beta\approx 0.295$, while results covering the entire replica-symmetric regime $\beta < 1$ gave guarantees only in Wasserstein distance. Our approach demonstrates that the same potential Hessian ascent previously developed for optimization also functions as a sampling algorithm by implementing algorithmic stochastic localization at high temperature. By estimating the covariance of the tilted Gibbs distribution via Gaussian integration by parts, overlap concentration, and precise cavity estimates, we show that a Hessian-ascent process achieves an $O(1)$ Wasserstein error guarantee for finite-time localization, improving on the previous $o(n)$. A careful comparison of stochastic localization with the Hessian ascent process and a free probability argument controlling the diagonal sub-algebra of the Hessian improves this to $O(1)$ in KL divergence. We then use Jarzynski's equality with rejection sampling, along with entropy contraction on the time-$T$ localized distribution, to refine the error to $o(1)$ in TVD up to a constant time $T$ and to complete the sampling with the polarized walk.
fields
math.PR 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Lower bound on the mixing time of $p$-spin glasses
Proves an exponential lower bound on the mixing time of Glauber dynamics for the p-spin glass at inverse temperatures above C ln(p)/p for large p, via energy landscape analysis with Gaussian decompositions and a bottleneck bound.