mlsanityData to 7 Oct 2026

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

arXiv 2407.16936 ↗First posted 24 Jul 2024stat.ML cs.LG math.STcited by 23

Not on the map. Why?

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.

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

Builds on

38 of 64 references.

References · 38

  1. 2020Denoising Diffusion Probabilistic Modelscited by 20,851
  2. 2020Denoising Diffusion Implicit Modelscited by 9,655
  3. 2020Score-Based Generative Modeling through Stochastic Differential Equationscited by 8,964
  4. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,067
  5. 2020Improved Techniques for Training Score-Based Generative Modelscited by 1,036
  6. 2022Fast Sampling of Diffusion Models with Exponential Integratorcited by 526
  7. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptionscited by 440
  8. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 224
  9. 2021Path Integral Sampler: a stochastic control approach for samplingcited by 175
  10. 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 158
  11. 2023Denoising Diffusion Samplerscited by 144
  12. 2018Analysis of Langevin Monte Carlo via convex optimizationcited by 126
26 more
  1. 2022gDDIM: Generalized denoising diffusion implicit modelscited by 125
  2. 2023Improved sampling via learned diffusionscited by 103
  3. 2019Subspace Robust Wasserstein Distancescited by 89
  4. 2018Sampling Can Be Faster Than Optimizationcited by 68
  5. 2022Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlocited by 63
  6. 2023Reverse Diffusion Monte Carlocited by 41
  7. 2017Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlocited by 33
  8. 2023Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequalitycited by 31
  9. 2023Improved dimension dependence of a proximal algorithm for samplingcited by 29
  10. 2019Langevin Monte Carlo without smoothnesscited by 27
  11. 2021A Proximal Algorithm for Sampling from Non-smooth Potentialscited by 23
  12. 2022A Proximal Algorithm for Samplingcited by 21
  13. 2024Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusioncited by 19
  14. 2018Simulated Tempering Langevin Monte Carlo II: An Improved Proof using Soft Markov Chain Decompositioncited by 16
  15. 2019Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Boundscited by 16
  16. 2022Annealed Langevin Dynamics for Massive MIMO Detectioncited by 16
  17. 2014Information Theoretical Estimators Toolboxcited by 15
  18. 2024Faster Sampling without Isoperimetry via Diffusion-based Monte Carlocited by 15
  19. 2022Fisher information lower bounds for samplingcited by 12
  20. 2023Query lower bounds for log-concave samplingcited by 12
  21. 2023Solving Linear Inverse Problems using Higher-Order Annealed Langevin Diffusioncited by 6
  22. 2017Normalizing constants of log-concave densitiescited by 5
  23. 2023Fast Conditional Mixing of MCMC Algorithms for Non-log-concave Distributionscited by 5
  24. 2018Stochastic control and non-equilibrium thermodynamics: fundamental limitscited by 4
  25. 2023Improved Bound for Mixing Time of Parallel Temperingcited by 4
  26. 2020Maximal power output of a stochastic thermodynamic enginecited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 12; 2026: 9.

23 papers.

Sort:

By area:

  1. 2025MDNS: Masked Diffusion Neural Sampler via Stochastic Optimal Controlcited by 20
  2. 2025Proximal Diffusion Neural Samplercited by 16
  3. 2025Density Ratio Estimation with Conditional Probability Pathscited by 13
  4. 2025Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyondcited by 11
  5. 2024Provable Convergence and Limitations of Geometric Tempering for Langevin Dynamicscited by 10
  6. 2025Non-equilibrium Annealed Adjoint Samplercited by 8
  7. 2025On the query complexity of sampling from non-log-concave distributionscited by 5
  8. 2025Sequential Monte Carlo approximations of Wasserstein--Fisher--Rao gradient flowscited by 5
  9. 2024A noise-corrected Langevin algorithm and sampling by half-denoisingcited by 3
  10. 2025Efficient Approximate Posterior Sampling with Annealed Langevin Monte Carlocited by 3
  11. 2026Diffusion Path Samplers via Sequential Monte Carlocited by 2
  12. 2026Dimension-Free Multimodal Sampling via Preconditioned Annealed Langevin Dynamicscited by 2
11 more
  1. 2025Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributionscited by 1
  2. 2025Sampling by averaging: A multiscale approach to score estimationcited by 1
  3. 2026Alternating Diffusion for Proximal Sampling with Zeroth Order Queriescited by 1
  4. 2025Improved sampling algorithms and functional inequalities for non-log-concave distributionscited by 0
  5. 2025A Systems-Theoretic View on the Convergence of Algorithms under Disturbancescited by 0
  6. 2026Sampling via Stochastic Interpolants by Langevin-based Velocity and Initialization Estimation in Flow ODEscited by 0
  7. 2026Rethinking the Flow-Based Gradual Domain Adaptation: A Semi-Dual Optimal Transport Perspectivecited by 0
  8. 2026Properties and limitations of geometric tempering for gradient flow dynamicscited by 0
  9. 2026Complexity of Non-Log-Concave Sampling in Fisher Informationcited by 0
  10. 2026Dimension-Uniform Discretization Analysis of Preconditioned Annealed Langevin Dynamics for Multimodal Gaussian Mixturescited by 0
  11. 2026R'enyi Tracking Bounds for Langevin Dynamics with Moving Targetscited by 0