mlsanityData to 7 Oct 2026

Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion

arXiv 2501.00565 ↗First posted 31 Dec 2024stat.CO cs.LG math.STcited by 4

Not on the map. Why?

Abstract (arXiv)

Even in low dimensions, sampling from multi-modal distributions is challenging. We provide the first sampling algorithm for a broad class of distributions -- including all Gaussian mixtures -- with a query complexity that is polynomial in the parameters governing multi-modality, assuming fixed dimension. Our sampling algorithm simulates a time-reversed diffusion process, using a self-normalized Monte Carlo estimator of the intermediate score functions. Unlike previous works, it avoids metastability, requires no prior knowledge of the mode locations, and relaxes the well-known log-smoothness assumption which excluded general Gaussian mixtures so far.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 35 of its 51 references that are in the map. First posted on arXiv 31 Dec 2024.

Builds on

35 of 51 references.

References · 35

  1. 2020Denoising Diffusion Probabilistic Modelscited by 20,851
  2. 2020Score-Based Generative Modeling through Stochastic Differential Equationscited by 8,964
  3. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,067
  4. 2021Diffusion Schr"odinger Bridge with Applications to Score-Based Generative Modelingcited by 594
  5. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptionscited by 440
  6. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
  7. 2023Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localizationcited by 230
  8. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 224
  9. 2022Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptionscited by 215
  10. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 195
  11. 2022Convergence for score-based generative modeling with polynomial complexitycited by 176
  12. 2022Flow Annealed Importance Sampling Bootstrapcited by 124
23 more
  1. 2017User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradientcited by 116
  2. 2024Iterated Denoising Energy Matching for Sampling from Boltzmann Densitiescited by 113
  3. 2021Deep Generative Learning via Schr"odinger Bridgecited by 103
  4. 2017A Hitting Time Analysis of Stochastic Gradient Langevin Dynamicscited by 70
  5. 2018Sampling Can Be Faster Than Optimizationcited by 68
  6. 2024Particle Denoising Diffusion Samplercited by 63
  7. 2021Bayesian Learning via Neural Schr"odinger-F"ollmer Flowscited by 56
  8. 2020On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothnesscited by 55
  9. 2024Target Score Matchingcited by 46
  10. 2024Learning general Gaussian mixtures with efficient score matchingcited by 43
  11. 2020Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergencecited by 42
  12. 2023Reverse Diffusion Monte Carlocited by 41
  13. 2017Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlocited by 33
  14. 2019Langevin Monte Carlo without smoothnesscited by 27
  15. 2024Stochastic Localization via Iterative Posterior Samplingcited by 27
  16. 2020A Contour Stochastic Gradient Langevin Dynamics Algorithm for Simulations of Multi-modal Distributionscited by 26
  17. 2024Training Neural Samplers with Reverse Diffusive KL Divergencecited by 21
  18. 2024Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusioncited by 19
  19. 2024Faster Sampling without Isoperimetry via Diffusion-based Monte Carlocited by 15
  20. 2023Chain of Log-Concave Markov Chainscited by 13
  21. 2021Convergence Analysis of Schr"odinger-F"ollmer Sampler without Convexitycited by 7
  22. 2024Tamed Langevin sampling under weaker conditionscited by 7
  23. 2022Unbiased Estimation using a Class of Diffusion Processescited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2025Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyondcited by 11
  2. 2026On Forgetting and Stability of Score-based Generative modelscited by 3
  3. 2026Sobolev Regularized MMD Gradient Flowcited by 3
  4. 2026Dimension-Free Multimodal Sampling via Preconditioned Annealed Langevin Dynamicscited by 2