Approximate stochastic localization plus conductance transfers yield a weak Poincaré inequality for the SK model at β < 1/2, enabling efficient Glauber sampling from a warm start.
Sampling from spherical spin glasses in total variation via algorithmic stochastic localization
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
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''(s) < \frac{1}{(1-s)^2}, \qquad \forall s\in [0,1).$$ This includes the pure $p$-spin glasses above a critical temperature that is within an absolute ($p$-independent) constant of the so-called shattering phase transition. Our algorithm follows the algorithmic stochastic localization approach introduced in (Alaoui, Montanari, Sellke, 20022). 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 opens the way to perform inference about one-dimensional projections of the measure.
fields
math.PR 5representative citing papers
Derives McDiarmid-type inequalities for dependent variables via approximate tensorization of entropy, with applications improving DKW rates to 1/sqrt(n) under weak dependence for log-concave measures.
Polynomial-time algorithm samples the Sherrington-Kirkpatrick Gibbs measure at beta < 1/2 with o(1) TVD error by combining potential Hessian ascent, stochastic localization, covariance estimates, and Jarzynski equality with rejection sampling.
Presents the first iterative spectral algorithm for near-optimal solutions to random quadratic optimization over the hypercube, resolving Subag's conjecture via potential Hessian ascent and SDE approximation.
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.
citing papers explorer
-
Weak Poincar\'e Inequalities via Approximate Stochastic Localization: Application to Sampling the Sherrington-Kirkpatrick Model
Approximate stochastic localization plus conductance transfers yield a weak Poincaré inequality for the SK model at β < 1/2, enabling efficient Glauber sampling from a warm start.
-
On McDiarmid's Inequality under Dependence via Approximate Tensorization of Entropy
Derives McDiarmid-type inequalities for dependent variables via approximate tensorization of entropy, with applications improving DKW rates to 1/sqrt(n) under weak dependence for log-concave measures.
-
Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta < 1/2
Polynomial-time algorithm samples the Sherrington-Kirkpatrick Gibbs measure at beta < 1/2 with o(1) TVD error by combining potential Hessian ascent, stochastic localization, covariance estimates, and Jarzynski equality with rejection sampling.
-
Potential Hessian Ascent: The Sherrington-Kirkpatrick Model
Presents the first iterative spectral algorithm for near-optimal solutions to random quadratic optimization over the hypercube, resolving Subag's conjecture via potential Hessian ascent and SDE approximation.
-
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.