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

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

## Key facts

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

## Builds on (most cited first, 30 of 35)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Diffusion Schr"odinger Bridge with Applications to Score-Based Generative Modeling](https://mlsanity.com/paper/2106.01357/) (2021)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization](https://mlsanity.com/paper/2308.03686/) (2023)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions](https://mlsanity.com/paper/2211.01916/) (2022)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Convergence for score-based generative modeling with polynomial complexity](https://mlsanity.com/paper/2206.06227/) (2022)
- [Flow Annealed Importance Sampling Bootstrap](https://mlsanity.com/paper/2208.01893/) (2022)
- [User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient](https://mlsanity.com/paper/1710.00095/) (2017)
- [Iterated Denoising Energy Matching for Sampling from Boltzmann Densities](https://mlsanity.com/paper/2402.06121/) (2024)
- [Deep Generative Learning via Schr"odinger Bridge](https://mlsanity.com/paper/2106.10410/) (2021)
- [A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1702.05575/) (2017)
- [Sampling Can Be Faster Than Optimization](https://mlsanity.com/paper/1811.08413/) (2018)
- [Particle Denoising Diffusion Sampler](https://mlsanity.com/paper/2402.06320/) (2024)
- [Bayesian Learning via Neural Schr"odinger-F"ollmer Flows](https://mlsanity.com/paper/2111.10510/) (2021)
- [On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness](https://mlsanity.com/paper/2005.13097/) (2020)
- [Target Score Matching](https://mlsanity.com/paper/2402.08667/) (2024)
- [Learning general Gaussian mixtures with efficient score matching](https://mlsanity.com/paper/2404.18893/) (2024)
- [Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence](https://mlsanity.com/paper/2007.11612/) (2020)
- [Reverse Diffusion Monte Carlo](https://mlsanity.com/paper/2307.02037/) (2023)
- [Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo](https://mlsanity.com/paper/1710.02736/) (2017)
- [Langevin Monte Carlo without smoothness](https://mlsanity.com/paper/1905.13285/) (2019)
- [Stochastic Localization via Iterative Posterior Sampling](https://mlsanity.com/paper/2402.10758/) (2024)
- [A Contour Stochastic Gradient Langevin Dynamics Algorithm for Simulations of Multi-modal Distributions](https://mlsanity.com/paper/2010.09800/) (2020)
- [Training Neural Samplers with Reverse Diffusive KL Divergence](https://mlsanity.com/paper/2410.12456/) (2024)
- [Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion](https://mlsanity.com/paper/2402.17886/) (2024)

## Built on by (most cited first, 4 of 4)

- [Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond](https://mlsanity.com/paper/2502.04575/) (2025)
- [Sobolev Regularized MMD Gradient Flow](https://mlsanity.com/paper/2605.11884/) (2026)
- [On Forgetting and Stability of Score-based Generative models](https://mlsanity.com/paper/2601.21868/) (2026)
- [Dimension-Free Multimodal Sampling via Preconditioned Annealed Langevin Dynamics](https://mlsanity.com/paper/2602.01449/) (2026)

## 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.