mlsanityData to 7 Oct 2026

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

arXiv 2203.05093 ↗First posted 10 Mar 2022math.PR cond-mat.dis-nn cs.DScited by 48

Not on the map. Why?

Cited by 21 in Diffusion models, but placed by its own abstract, which didn’t fit.

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 14; 2024: 9; 2025: 13; 2026: 10.

48 papers.

Sort:

By area:

  1. 2023Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localizationcited by 230
  2. 2022Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptionscited by 215
  3. 2023The probability flow ODE is provably fastcited by 145
  4. 2024Dynamical Regimes of Diffusion Modelscited by 133
  5. 2023Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Modelscited by 84
  6. 2024An Overview of Diffusion Models: Applications, Guided Generation, Statistical Rates and Optimizationcited by 72
  7. 2024A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Modelscited by 64
  8. 2023Learning Mixtures of Gaussians Using the DDPM Objectivecited by 56
  9. 2024Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptionscited by 45
  10. 2024Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexitycited by 42
  11. 2023Reverse Diffusion Monte Carlocited by 41
  12. 2023Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Modelscited by 39
36 more
  1. 2023Sampling, Diffusions, and Stochastic Localizationcited by 38
  2. 2023The statistical thermodynamics of generative diffusion models: Phase transitions, symmetry breaking and critical instabilitycited by 37
  3. 2023Probabilistic Adaptation of Text-to-Video Modelscited by 29
  4. 2024Stochastic Localization via Iterative Posterior Samplingcited by 27
  5. 2023Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspectivecited by 26
  6. 2024U-Nets as Belief Propagation: Efficient Classification, Denoising, and Diffusion in Generative Hierarchical Modelscited by 17
  7. 2023A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Widthcited by 13
  8. 2024Posterior Sampling with Denoising Oracles via Tilted Transportcited by 12
  9. 2025Diffusion Models are Secretly Exchangeable: Parallelizing DDPMs via Autospeculationcited by 11
  10. 2022Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energycited by 9
  11. 2023Learning Hard-Constrained Models with One Samplecited by 7
  12. 2023Provably Fast Finite Particle Variants of SVGD via Virtual Particle Stochastic Approximationcited by 6
  13. 2025Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDTcited by 5
  14. 2025A CLuP algorithm to practically achieve ~ 0.76 SK--model ground state free energycited by 5
  15. 2026How Out-of-Equilibrium Phase Transitions can Seed Pattern Formation in Trained Diffusion Modelscited by 5
  16. 2025CLuP practically achieves ~ 1.77 positive and ~ 0.33 negative Hopfield model ground state free energycited by 3
  17. 2025Binary perceptron computational gap -- a parametric fl RDT viewcited by 3
  18. 2026Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problemscited by 3
  19. 2024Building Conformal Prediction Intervals with Approximate Message Passingcited by 2
  20. 2025Computational bottlenecks for denoising diffusionscited by 2
  21. 2025Joint stochastic localization and applicationscited by 2
  22. 2025Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Couplingcited by 2
  23. 2025Perspectives on Stochastic Localizationcited by 2
  24. 2025Estimating Ising Models in Total Variation Distancecited by 2
  25. 2025Generative diffusion for perceptron problems: statistical physics analysis and efficient algorithmscited by 1
  26. 2026Parametric RDT approach to computational gap of symmetric binary perceptroncited by 1
  27. 2026Provably Reliable Classifier Guidance via Cross-Entropy Controlcited by 1
  28. 2026Score Shocks: The Burgers Equation Structure of Diffusion Generative Modelscited by 1
  29. 2023From Estimation to Sampling for Bayesian Linear Regression with Spike-and-Slab Priorcited by 0
  30. 2025Phase transition of descending phase retrieval algorithmscited by 0
  31. 2025A large deviation view of stationarized fully lifted blirp interpolationcited by 0
  32. 2026Functional Stochastic Localizationcited by 0
  33. 2026Total Variation Guarantees for Sampling with Stochastic Localizationcited by 0
  34. 2026Ultrametric OGP - parametric RDT symmetric binary perceptron connectioncited by 0
  35. 2026On McDiarmid's Inequality under Dependence via Approximate Tensorization of Entropycited by 0
  36. 2026Simulation-free and finite-time diffusion modelcited by 0