# On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness

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

## Key facts

- Cited by 55 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2020.

## Built on by (most cited first, 30 of 55)

- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [Convex Analysis of the Mean Field Langevin Dynamics](https://mlsanity.com/paper/2201.10469/) (2022)
- [Reverse Diffusion Monte Carlo](https://mlsanity.com/paper/2307.02037/) (2023)
- [Model-Based Diffusion for Trajectory Optimization](https://mlsanity.com/paper/2407.01573/) (2024)
- [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)
- [Improved Discretization Analysis for Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2302.08049/) (2023)
- [Sqrt(d) Dimension Dependence of Langevin Monte Carlo](https://mlsanity.com/paper/2109.03839/) (2021)
- [CPR: Retrieval Augmented Generation for Copyright Protection](https://mlsanity.com/paper/2403.18920/) (2024)
- [A Proximal Algorithm for Sampling](https://mlsanity.com/paper/2202.13975/) (2022)
- [Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling](https://mlsanity.com/paper/2210.08448/) (2022)
- [Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition](https://mlsanity.com/paper/2206.00508/) (2022)
- [Fisher information lower bounds for sampling](https://mlsanity.com/paper/2210.02482/) (2022)
- [Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Covers](https://mlsanity.com/paper/2209.08951/) (2022)
- [Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited](https://mlsanity.com/paper/2306.08494/) (2023)
- [Parallelized Midpoint Randomization for Langevin Monte Carlo](https://mlsanity.com/paper/2402.14434/) (2024)
- [Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms](https://mlsanity.com/paper/2206.03792/) (2022)
- [Taming under isoperimetry](https://mlsanity.com/paper/2311.09003/) (2023)
- [Tamed Langevin sampling under weaker conditions](https://mlsanity.com/paper/2405.17693/) (2024)
- [Heavy-tailed Sampling via Transformed Unadjusted Langevin Algorithm](https://mlsanity.com/paper/2201.08349/) (2022)
- [A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers](https://mlsanity.com/paper/2405.16736/) (2024)
- [The Poisson Midpoint Method for Langevin Dynamics: Provably Efficient Discretization for Diffusion Models](https://mlsanity.com/paper/2405.17068/) (2024)
- [Fast Conditional Mixing of MCMC Algorithms for Non-log-concave Distributions](https://mlsanity.com/paper/2306.10506/) (2023)
- [Mixing of the No-U-Turn Sampler and the Geometry of Gaussian Concentration](https://mlsanity.com/paper/2410.06978/) (2024)
- [On Forgetting and Stability of Score-based Generative models](https://mlsanity.com/paper/2601.21868/) (2026)
- [Mean-Square Analysis of Discretized Ito Diffusions for Heavy-tailed Sampling](https://mlsanity.com/paper/2303.00570/) (2023)
- [NF-ULA: Langevin Monte Carlo with Normalizing Flow Prior for Imaging Inverse Problems](https://mlsanity.com/paper/2304.08342/) (2023)
- [Bayesian Federated Learning with Hamiltonian Monte Carlo: Algorithm and Theory](https://mlsanity.com/paper/2407.06935/) (2024)
- [Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias](https://mlsanity.com/paper/2408.13115/) (2024)
- [Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion](https://mlsanity.com/paper/2501.00565/) (2024)

## Abstract (arXiv)

We study sampling from a target distribution nu_* = e-f using the unadjusted Langevin Monte Carlo (LMC) algorithm. For any potential function f whose tails behave like |x|α for α ∈ [1,2], and has β-H"older continuous gradient, we prove that widetildeO Big(d^frac1β+frac1+ββ(frac2α - boldsymbol1_α neq 1) ε^-frac1βBig) steps are sufficient to reach the ε -neighborhood of a d-dimensional target distribution nu_* in KL-divergence. This convergence rate, in terms of ε dependency, is not directly influenced by the tail growth rate α of the potential function as long as its growth is at least linear, and it only relies on the order of smoothness β. One notable consequence of this result is that for potentials with Lipschitz gradient, i.e. β=1, our rate recovers the best known rate widetildeO(dε-1) which was established for strongly convex potentials in terms of ε dependency, but we show that the same rate is achievable for a wider class of potentials that are degenerately convex at infinity. The growth rate α starts to have an effect on the established rate in high dimensions where d is large; furthermore, it recovers the best-known dimension dependency when the tail growth of the potential is quadratic, i.e. α = 2, in the current setup. Our framework allows for finite perturbations, and any order of smoothness β∈(0,1]; consequently, our results are applicable to a wide class of non-convex potentials that are weakly smooth and exhibit at least linear tail growth.