mlsanityData to 7 Oct 2026

Sqrt(d) Dimension Dependence of Langevin Monte Carlo

arXiv 2109.03839 ↗First posted 8 Sep 2021cs.LG cs.NA math.NAcited by 25

Not on the map. Why?

Abstract (arXiv)

This article considers the popular MCMC method of unadjusted Langevin Monte Carlo (LMC) and provides a non-asymptotic analysis of its sampling error in 2-Wasserstein distance. The proof is based on a refinement of mean-square analysis in Li et al. (2019), and this refined framework automates the analysis of a large class of sampling algorithms based on discretizations of contractive SDEs. Using this framework, we establish an tildeO(√d/ε) mixing time bound for LMC, without warm start, under the common log-smooth and log-strongly-convex conditions, plus a growth condition on the 3rd-order derivative of the potential of target measures. This bound improves the best previously known tildeO(d/ε) result and is optimal (in terms of order) in both dimension d and accuracy tolerance ε for target measures satisfying the aforementioned assumptions. Our theoretical analysis is further validated by numerical experiments.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Builds on 24 of its 43 references that are in the map. First posted on arXiv 8 Sep 2021.

Builds on

24 of 43 references.

References · 24

  1. 2016Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithmcited by 498
  2. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 422
  3. 2017Stochastic Gradient Descent as Approximate Bayesian Inferencecited by 298
  4. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 224
  5. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 206
  6. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 195
  7. 2016High-dimensional Bayesian inference via the Unadjusted Langevin Algorithmcited by 144
  8. 2017Underdamped Langevin MCMC: A non-asymptotic analysiscited by 131
  9. 2018Analysis of Langevin Monte Carlo via convex optimizationcited by 126
  10. 2018Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problemcited by 123
  11. 2017Convergence of Langevin MCMC in KL-divergencecited by 86
  12. 2019The Randomized Midpoint Method for Log-Concave Samplingcited by 77
12 more
  1. 2018Sharp convergence rates for Langevin dynamics in the nonconvex settingcited by 67
  2. 2018On sampling from a log-concave density using kinetic Langevin diffusionscited by 61
  3. 2020Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithmcited by 57
  4. 2020On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothnesscited by 55
  5. 2018A Unified Particle-Optimization Framework for Scalable Bayesian Samplingcited by 44
  6. 2019Improved Bounds for Discretization of Langevin Diffusions: Near-Optimal Rates without Convexitycited by 38
  7. 2019High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithmcited by 36
  8. 2018Policy Optimization as Wasserstein Gradient Flowscited by 33
  9. 2019Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyondcited by 33
  10. 2021The Langevin Monte Carlo algorithm in the non-smooth log-concave casecited by 26
  11. 2018Approximate inference with Wasserstein gradient flowscited by 12
  12. 2020Hessian-Free High-Resolution Nesterov Acceleration for Samplingcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 5; 2023: 5; 2024: 5; 2025: 6; 2026: 2.

25 papers.

Sort:

By area:

  1. 2023Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localizationcited by 230
  2. 2021The Mirror Langevin Algorithm Converges with Vanishing Biascited by 37
  3. 2023Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequalitycited by 31
  4. 2023Improved dimension dependence of a proximal algorithm for samplingcited by 29
  5. 2025Beyond Log-Concavity and Score Regularity: Improved Convergence Bounds for Score-Based Generative Models in W2-distancecited by 27
  6. 2022Convergence of the Riemannian Langevin Algorithmcited by 23
  7. 2024Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusioncited by 19
  8. 2022Self-Consistency of the Fokker-Planck Equationcited by 18
  9. 2021On Convergence of Federated Averaging Langevin Dynamicscited by 14
  10. 2023Chain of Log-Concave Markov Chainscited by 13
  11. 2023Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithmcited by 11
  12. 2022Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Timecited by 7
13 more
  1. 2025Non-asymptotic error bounds for probability flow ODEs under weak log-concavitycited by 7
  2. 2022Constrained Langevin Algorithms with L-mixing External Random Variablescited by 6
  3. 2024Convergence of Kinetic Langevin Monte Carlo on Lie groupscited by 6
  4. 2024A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplerscited by 5
  5. 2024Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Biascited by 4
  6. 2024Hierarchic Flows to Estimate and Sample High-dimensional Probabilitiescited by 3
  7. 2025Mirror Mean-Field Langevin Dynamicscited by 3
  8. 2022A Dynamical System View of Langevin-Based Non-Convex Samplingcited by 2
  9. 2025Random Reshuffling for Stochastic Gradient Langevin Dynamicscited by 2
  10. 2025Anchored Langevin Algorithmscited by 2
  11. 2026MGD: Moment Guided Diffusion for Maximum Entropy Generationcited by 1
  12. 2026Wasserstein mixing time of the unadjusted Langevin algorithmcited by 1
  13. 2025When Langevin Monte Carlo Meets Randomization: New Sampling Algorithms with Non-asymptotic Error Bounds beyond Log-Concavity and Gradient Lipschitznesscited by 0