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.
Sum-of-Squares & Gaussian Processes I: Certification
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
We introduce a class of distributions which may be considered as a smoothed probabilistic version of the ultrametric property that famously characterizes the Gibbs distributions of various spin glass models. This class of \emph{high-entropy step} (HES) distributions is expressive enough to capture a distribution achieving near-optimal average energy on spin glass models in the so-called full Replica-Symmetry Breaking (fRSB) regime. Simultaneously, with high probability, there are polynomial-size certificates on the average energy achievable by \emph{any} HES distribution which are tight within a constant factor. These certificates can be found in polynomial time by a semidefinite program corresponding to a sum-of-squares (SoS) hierarchy we introduce, termed the HES SoS hierarchy. This improves over classical sum-of-squares certificates which are loose by a factor of $n^{\lfloor p/2 - 1\rfloor/2}$.
fields
math.PR 3representative citing papers
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.
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.
-
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.