Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization

2022/03/10 by Alaoui, Ahmed El, Montanari, Andrea, Sellke, Mark · 23 citations
#Data Structures and Algorithms (cs.DS) #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Probability (math.PR)

paper · doi:10.48550/arxiv.2203.05093

Abstract

We consider the Sherrington-Kirkpatrick model of spin glasses at high-temperature and no external field, and study the problem of sampling from the Gibbs distribution μ in polynomial time. We prove that, for any inverse temperature β<1/2, there exists an algorithm with complexity O(n²) that samples from a distribution μ^alg which is close in normalized Wasserstein distance to μ. Namely, there exists a coupling of μ and μ^alg such that if (x,x^alg)∈\-1,+1\ⁿ× \-1,+1\ⁿ is a pair drawn from this coupling, then n^-1\mathbb E\||x-x^alg||₂²\=o_n(1). The best previous results, by Bauerschmidt and Bodineau and by Eldan, Koehler, and Zeitouni, implied efficient algorithms to approximately sample (under a stronger metric) for β<1/4. We complement this result with a negative one, by introducing a suitable "stability" property for sampling algorithms, which is verified by many standard techniques. We prove that no stable algorithm can approximately sample for β>1, even under the normalized Wasserstein metric. Our sampling method is based on an algorithmic implementation of stochastic localization, which progressively tilts the measure μ towards a single configuration, together with an approximate message passing algorithm that is used to approximate the mean of the tilted measure.

Cited by

• Causal inference under interference: computational barriers and algorithmic solutions
• Exponentially Slow Mixing of the Low Temperature SK Model
• Estimating Ising Models in Total Variation Distance
• Binary perceptron computational gap -- a parametric fl RDT view
• How Out-of-Equilibrium Phase Transitions can Seed Pattern Formation in Trained Diffusion Models
• Average-case quantum complexity from glassiness
• Perspectives on Stochastic Localization
• Functional Stochastic Localization
• Ground state energies of multipartite p-spin models -- partially lifted RDT view
• Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling
• Polynomial-time sampling despite disorder chaos
• Efficient and simple Gibbs state preparation of the 2D toric code via duality to classical Ising chains
• On zeros and algorithms for disordered systems: mean-field spin glasses
• CLuP practically achieves ∼ 1.77 positive and ∼ 0.33 negative Hopfield model ground state free energy
• Optimizing Sparse SYK
• A CLuP algorithm to practically achieve ∼ 0.76 SK--model ground state free energy
• Proof of The TAP Free Energy for High-Dimensional Linear Regression with Spherical Priors at All Temperatures
• Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT
• A large deviation view of stationarized fully lifted blirp interpolation
• Phase transition of descending phase retrieval algorithms
• Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation
• Sampling from Binary Quadratic Distributions via Stochastic Localization
• Joint stochastic localization and applications

Related

• Sampling from Mean-Field Gibbs Measures via Diffusion Processes
• Sampling from Spherical Spin Glasses in Total Variation via Algorithmic Stochastic Localization
• Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta < 1/2
• On sampling symmetric Gibbs distributions on sparse random graphs and\n hypergraphs
• Sampling from the Continuous Random Energy Model in Total Variation Distance