# Sqrt(d) Dimension Dependence of Langevin Monte Carlo

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

## Key facts

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

## Builds on (most cited first, 24 of 24)

- [Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm](https://mlsanity.com/paper/1608.04471/) (2016)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Stochastic Gradient Descent as Approximate Bayesian Inference](https://mlsanity.com/paper/1704.04289/) (2017)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem](https://mlsanity.com/paper/1802.08089/) (2018)
- [Convergence of Langevin MCMC in KL-divergence](https://mlsanity.com/paper/1705.09048/) (2017)
- [The Randomized Midpoint Method for Log-Concave Sampling](https://mlsanity.com/paper/1909.05503/) (2019)
- [Sharp convergence rates for Langevin dynamics in the nonconvex setting](https://mlsanity.com/paper/1805.01648/) (2018)
- [On sampling from a log-concave density using kinetic Langevin diffusions](https://mlsanity.com/paper/1807.09382/) (2018)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness](https://mlsanity.com/paper/2005.13097/) (2020)
- [A Unified Particle-Optimization Framework for Scalable Bayesian Sampling](https://mlsanity.com/paper/1805.11659/) (2018)
- [Improved Bounds for Discretization of Langevin Diffusions: Near-Optimal Rates without Convexity](https://mlsanity.com/paper/1907.11331/) (2019)
- [High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm](https://mlsanity.com/paper/1908.10859/) (2019)
- [Policy Optimization as Wasserstein Gradient Flows](https://mlsanity.com/paper/1808.03030/) (2018)
- [Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond](https://mlsanity.com/paper/1906.07868/) (2019)
- [The Langevin Monte Carlo algorithm in the non-smooth log-concave case](https://mlsanity.com/paper/2101.10695/) (2021)
- [Approximate inference with Wasserstein gradient flows](https://mlsanity.com/paper/1806.04542/) (2018)
- [Hessian-Free High-Resolution Nesterov Acceleration for Sampling](https://mlsanity.com/paper/2006.09230/) (2020)

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

- [Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization](https://mlsanity.com/paper/2308.03686/) (2023)
- [The Mirror Langevin Algorithm Converges with Vanishing Bias](https://mlsanity.com/paper/2109.12077/) (2021)
- [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)
- [Beyond Log-Concavity and Score Regularity: Improved Convergence Bounds for Score-Based Generative Models in W2-distance](https://mlsanity.com/paper/2501.02298/) (2025)
- [Convergence of the Riemannian Langevin Algorithm](https://mlsanity.com/paper/2204.10818/) (2022)
- [Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion](https://mlsanity.com/paper/2402.17886/) (2024)
- [Self-Consistency of the Fokker-Planck Equation](https://mlsanity.com/paper/2206.00860/) (2022)
- [On Convergence of Federated Averaging Langevin Dynamics](https://mlsanity.com/paper/2112.05120/) (2021)
- [Chain of Log-Concave Markov Chains](https://mlsanity.com/paper/2305.19473/) (2023)
- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time](https://mlsanity.com/paper/2207.02189/) (2022)
- [Non-asymptotic error bounds for probability flow ODEs under weak log-concavity](https://mlsanity.com/paper/2510.17608/) (2025)
- [Constrained Langevin Algorithms with L-mixing External Random Variables](https://mlsanity.com/paper/2205.14192/) (2022)
- [Convergence of Kinetic Langevin Monte Carlo on Lie groups](https://mlsanity.com/paper/2403.12012/) (2024)
- [A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers](https://mlsanity.com/paper/2405.16736/) (2024)
- [Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias](https://mlsanity.com/paper/2408.13115/) (2024)
- [Hierarchic Flows to Estimate and Sample High-dimensional Probabilities](https://mlsanity.com/paper/2405.03468/) (2024)
- [Mirror Mean-Field Langevin Dynamics](https://mlsanity.com/paper/2505.02621/) (2025)
- [Anchored Langevin Algorithms](https://mlsanity.com/paper/2509.19455/) (2025)
- [A Dynamical System View of Langevin-Based Non-Convex Sampling](https://mlsanity.com/paper/2210.13867/) (2022)
- [Random Reshuffling for Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2501.16055/) (2025)
- [Wasserstein mixing time of the unadjusted Langevin algorithm](https://mlsanity.com/paper/2608.02430/) (2026)
- [When Langevin Monte Carlo Meets Randomization: New Sampling Algorithms with Non-asymptotic Error Bounds beyond Log-Concavity and Gradient Lipschitzness](https://mlsanity.com/paper/2509.25630/) (2025)
- [MGD: Moment Guided Diffusion for Maximum Entropy Generation](https://mlsanity.com/paper/2602.17211/) (2026)

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