Sampling from Mean-Field Gibbs Measures via Diffusion Processes

2023/10/13 by A. El Alaoui, Andrea Montanari, Alaoui, Ahmed El +3 · 10 citations
Computer Science · Mathematics · Physics and Astronomy · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Theoretical and Computational Physics #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2310.08912

openalex publication_date 2023/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

We consider Ising mixed p-spin glasses at high-temperature and without external field, and study the problem of sampling from the Gibbs distribution μ in polynomial time. We develop a new sampling algorithm with complexity of the same order as evaluating the gradient of the Hamiltonian and, in particular, at most linear in the input size. We prove that, at sufficiently high-temperature, it produces samples from a distribution μ^alg which is close in normalized Wasserstein distance to μ. Namely, there exists a coupling of μ and μ^alg such that if (\boldsymbol x,\boldsymbol x^alg)∈\-1,+1\ⁿ× \-1,+1\ⁿ is a pair drawn from this coupling, then n^-1\mathbb E\‖\boldsymbol x-\boldsymbol x^alg‖₂²\=o_n(1). For the case of the Sherrington-Kirkpatrick model, our algorithm succeeds in the full replica-symmetric phase. We complement this result with a negative one for sampling algorithms satisfying a certain `stability' property, which is verified by many standard techniques. No stable algorithm can approximately sample at temperatures below the onset of shattering, even under the normalized Wasserstein metric. Further, no algorithm can sample at temperatures below the onset of replica symmetry breaking. Our sampling method implements a discretized version of a diffusion process that has become recently popular in machine learning under the name of `denoising diffusion.' We derive the same process from the general construction of stochastic localization. Implementing the diffusion process requires to efficiently approximate the mean of the tilted measure. To this end, we use an approximate message passing algorithm that, as we prove, achieves sufficiently accurate mean estimation.

Cited by

• Fast mixing in Ising models with a negative spectral outlier via Gaussian approximation
• Causal inference under interference: computational barriers and algorithmic solutions
• Exponentially Slow Mixing of the Low Temperature SK Model
• Average-case quantum complexity from glassiness
• Polynomial-time sampling despite disorder chaos
• On zeros and algorithms for disordered systems: mean-field spin glasses
• Computational Thresholds in Multi-Modal Learning via the Spiked Matrix-Tensor Model
• On the Discontinuous Breaking of Replica Symmetry and Shattering in Mean-Field Spin Glasses
• Sampling from Binary Quadratic Distributions via Stochastic Localization
• Learning with Restricted Boltzmann Machines: Asymptotics of AMP and GD in High Dimensions

Related

• Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization
• Sampling from Spherical Spin Glasses in Total Variation via Algorithmic Stochastic Localization
• On sampling diluted Spin Glasses using Glauber dynamics
• Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
• On sampling symmetric Gibbs distributions on sparse random graphs and\n hypergraphs