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

arXiv: https://arxiv.org/abs/2203.05093 · HTML: https://mlsanity.com/paper/2203.05093/

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2022.

## Built on by (most cited first, 30 of 48)

- [Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization](https://mlsanity.com/paper/2308.03686/) (2023)
- [Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions](https://mlsanity.com/paper/2211.01916/) (2022)
- [The probability flow ODE is provably fast](https://mlsanity.com/paper/2305.11798/) (2023)
- [Dynamical Regimes of Diffusion Models](https://mlsanity.com/paper/2402.18491/) (2024)
- [Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models](https://mlsanity.com/paper/2306.09251/) (2023)
- [An Overview of Diffusion Models: Applications, Guided Generation, Statistical Rates and Optimization](https://mlsanity.com/paper/2404.07771/) (2024)
- [A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models](https://mlsanity.com/paper/2408.02320/) (2024)
- [Learning Mixtures of Gaussians Using the DDPM Objective](https://mlsanity.com/paper/2307.01178/) (2023)
- [Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions](https://mlsanity.com/paper/2402.15602/) (2024)
- [Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity](https://mlsanity.com/paper/2405.15986/) (2024)
- [Reverse Diffusion Monte Carlo](https://mlsanity.com/paper/2307.02037/) (2023)
- [Sampling, Diffusions, and Stochastic Localization](https://mlsanity.com/paper/2305.10690/) (2023)
- [Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Models](https://mlsanity.com/paper/2309.11420/) (2023)
- [The statistical thermodynamics of generative diffusion models: Phase transitions, symmetry breaking and critical instability](https://mlsanity.com/paper/2310.17467/) (2023)
- [Probabilistic Adaptation of Text-to-Video Models](https://mlsanity.com/paper/2306.01872/) (2023)
- [Stochastic Localization via Iterative Posterior Sampling](https://mlsanity.com/paper/2402.10758/) (2024)
- [Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective](https://mlsanity.com/paper/2308.14085/) (2023)
- [U-Nets as Belief Propagation: Efficient Classification, Denoising, and Diffusion in Generative Hierarchical Models](https://mlsanity.com/paper/2404.18444/) (2024)
- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [Posterior Sampling with Denoising Oracles via Tilted Transport](https://mlsanity.com/paper/2407.00745/) (2024)
- [Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculation](https://mlsanity.com/paper/2505.03983/) (2025)
- [Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energy](https://mlsanity.com/paper/2208.09550/) (2022)
- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [Provably Fast Finite Particle Variants of SVGD via Virtual Particle Stochastic Approximation](https://mlsanity.com/paper/2305.17558/) (2023)
- [How Out-of-Equilibrium Phase Transitions can Seed Pattern Formation in Trained Diffusion Models](https://mlsanity.com/paper/2603.20092/) (2026)
- [Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT](https://mlsanity.com/paper/2506.19276/) (2025)
- [A CLuP algorithm to practically achieve ~ 0.76 SK--model ground state free energy](https://mlsanity.com/paper/2507.09247/) (2025)
- [Computational bottlenecks for denoising diffusions](https://mlsanity.com/paper/2503.08028/) (2025)
- [CLuP practically achieves ~ 1.77 positive and ~ 0.33 negative Hopfield model ground state free energy](https://mlsanity.com/paper/2507.22396/) (2025)
- [Binary perceptron computational gap -- a parametric fl RDT view](https://mlsanity.com/paper/2511.01037/) (2025)

## Abstract (arXiv)

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(n2) 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,xalg)∈-1,+1n× -1,+1n is a pair drawn from this coupling, then n-1mathbb E||x-xalg||22=on(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.