# Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 64 references that are in the map.
- First posted on arXiv 24 Jul 2024.

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

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (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)
- [Improved Techniques for Training Score-Based Generative Models](https://mlsanity.com/paper/2006.09011/) (2020)
- [Fast Sampling of Diffusion Models with Exponential Integrator](https://mlsanity.com/paper/2204.13902/) (2022)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Path Integral Sampler: a stochastic control approach for sampling](https://mlsanity.com/paper/2111.15141/) (2021)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Denoising Diffusion Samplers](https://mlsanity.com/paper/2302.13834/) (2023)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [gDDIM: Generalized denoising diffusion implicit models](https://mlsanity.com/paper/2206.05564/) (2022)
- [Improved sampling via learned diffusions](https://mlsanity.com/paper/2307.01198/) (2023)
- [Subspace Robust Wasserstein Distances](https://mlsanity.com/paper/1901.08949/) (2019)
- [Sampling Can Be Faster Than Optimization](https://mlsanity.com/paper/1811.08413/) (2018)
- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [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)
- [Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequality](https://mlsanity.com/paper/2303.03589/) (2023)
- [Improved dimension dependence of a proximal algorithm for sampling](https://mlsanity.com/paper/2302.10081/) (2023)
- [Langevin Monte Carlo without smoothness](https://mlsanity.com/paper/1905.13285/) (2019)
- [A Proximal Algorithm for Sampling from Non-smooth Potentials](https://mlsanity.com/paper/2110.04597/) (2021)
- [A Proximal Algorithm for Sampling](https://mlsanity.com/paper/2202.13975/) (2022)
- [Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion](https://mlsanity.com/paper/2402.17886/) (2024)
- [Simulated Tempering Langevin Monte Carlo II: An Improved Proof using Soft Markov Chain Decomposition](https://mlsanity.com/paper/1812.00793/) (2018)
- [Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds](https://mlsanity.com/paper/1911.03043/) (2019)
- [Annealed Langevin Dynamics for Massive MIMO Detection](https://mlsanity.com/paper/2205.05776/) (2022)
- [Information Theoretical Estimators Toolbox](https://mlsanity.com/paper/1405.2106/) (2014)
- [Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo](https://mlsanity.com/paper/2401.06325/) (2024)

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

- [MDNS: Masked Diffusion Neural Sampler via Stochastic Optimal Control](https://mlsanity.com/paper/2508.10684/) (2025)
- [Proximal Diffusion Neural Sampler](https://mlsanity.com/paper/2510.03824/) (2025)
- [Density Ratio Estimation with Conditional Probability Paths](https://mlsanity.com/paper/2502.02300/) (2025)
- [Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond](https://mlsanity.com/paper/2502.04575/) (2025)
- [Provable Convergence and Limitations of Geometric Tempering for Langevin Dynamics](https://mlsanity.com/paper/2410.09697/) (2024)
- [Non-equilibrium Annealed Adjoint Sampler](https://mlsanity.com/paper/2506.18165/) (2025)
- [On the query complexity of sampling from non-log-concave distributions](https://mlsanity.com/paper/2502.06200/) (2025)
- [Sequential Monte Carlo approximations of Wasserstein--Fisher--Rao gradient flows](https://mlsanity.com/paper/2506.05905/) (2025)
- [Diffusion Path Samplers via Sequential Monte Carlo](https://mlsanity.com/paper/2601.21951/) (2026)
- [A noise-corrected Langevin algorithm and sampling by half-denoising](https://mlsanity.com/paper/2410.05837/) (2024)
- [Efficient Approximate Posterior Sampling with Annealed Langevin Monte Carlo](https://mlsanity.com/paper/2508.07631/) (2025)
- [Dimension-Free Multimodal Sampling via Preconditioned Annealed Langevin Dynamics](https://mlsanity.com/paper/2602.01449/) (2026)
- [Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions](https://mlsanity.com/paper/2505.15059/) (2025)
- [Sampling by averaging: A multiscale approach to score estimation](https://mlsanity.com/paper/2508.15069/) (2025)
- [Alternating Diffusion for Proximal Sampling with Zeroth Order Queries](https://mlsanity.com/paper/2603.19633/) (2026)
- [Improved sampling algorithms and functional inequalities for non-log-concave distributions](https://mlsanity.com/paper/2507.11236/) (2025)
- [A Systems-Theoretic View on the Convergence of Algorithms under Disturbances](https://mlsanity.com/paper/2512.17598/) (2025)
- [Sampling via Stochastic Interpolants by Langevin-based Velocity and Initialization Estimation in Flow ODEs](https://mlsanity.com/paper/2601.08527/) (2026)
- [Rethinking the Flow-Based Gradual Domain Adaptation: A Semi-Dual Optimal Transport Perspective](https://mlsanity.com/paper/2602.01179/) (2026)
- [Properties and limitations of geometric tempering for gradient flow dynamics](https://mlsanity.com/paper/2604.20301/) (2026)
- [Complexity of Non-Log-Concave Sampling in Fisher Information](https://mlsanity.com/paper/2605.15859/) (2026)
- [Dimension-Uniform Discretization Analysis of Preconditioned Annealed Langevin Dynamics for Multimodal Gaussian Mixtures](https://mlsanity.com/paper/2605.16473/) (2026)
- [R'enyi Tracking Bounds for Langevin Dynamics with Moving Targets](https://mlsanity.com/paper/2609.17577/) (2026)

## Abstract (arXiv)

We consider the outstanding problem of sampling from an unnormalized density that may be non-log-concave and multimodal. To enhance the performance of simple Markov chain Monte Carlo (MCMC) methods, techniques of annealing type have been widely used. However, quantitative theoretical guarantees of these techniques are under-explored. This study takes a first step toward providing a non-asymptotic analysis of annealed MCMC. Specifically, we establish, for the first time, an oracle complexity of widetildeOleft(fracdβ2cal A2varepsilon6right) for the simple annealed Langevin Monte Carlo algorithm to achieve varepsilon2 accuracy in Kullback-Leibler divergence to the target distribution πproptorm e-V on ℝd with β-smooth potential V. Here, cal A represents the action of a curve of probability measures interpolating the target distribution π and a readily sampleable distribution.