Sampling from Spherical Spin Glasses in Total Variation via Algorithmic Stochastic Localization

Abstract

We consider the problem of algorithmically sampling from the Gibbs measure of a mixed $p$-spin spherical spin glass. We give a polynomial-time algorithm that samples from the Gibbs measure up to vanishing total variation error, for any model whose mixture satisfies $${\xi }^{\prime \prime }(s)<\frac{1}{(1-s{)}^2},\forall s\in [0,1).$$ Our algorithm follows the algorithmic stochastic localization (SL) approach introduced in (Alaoui, Montanari, Sellke, 2022) and in fact achieves a more difficult task. Namely, it (approximately) generates a sample path $({\mathbf{y}}_t{)}_{t\ge 0}$ from the SL process. For large $T$, ${\mathbf{y}}_T/T$ is an approximate sample from the target Gibbs measure, and hence we solve the original problem as a special case. We provide evidence that the condition ${\xi }^{\prime \prime }(s)<(1-s{)}^{-2}$ is sharp for the task of sampling SL sample paths. Furthermore, we prove that it is optimal within a class of generalized SL processes. Remarkably this threshold is close to the conjectured threshold for sampling from the original Gibbs measure. In particular, for the pure $p$-spin glasses it is within an absolute ($p$-independent) constant of the so-called shattering phase transition. Earlier work on related models was suboptimal by a factor diverging polynomially in $p$. A key step of this approach is to estimate the mean of a sequence of tilted measures. We produce an improved estimator for this task by identifying a suitable correction to the TAP fixed point selected by approximate message passing (AMP). As a consequence, we improve the algorithm's guarantee over previous work, from normalized Wasserstein to total variation error. In particular, the new algorithm and analysis open the way to perform inference about one-dimensional projections of the measure.

arXiv comment97 pages