# Sharp convergence rates for Langevin dynamics in the nonconvex setting

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

## Key facts

- Cited by 68 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2018.

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

- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Improved Discretization Analysis for Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2302.08049/) (2023)
- [Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties](https://mlsanity.com/paper/2205.07069/) (2022)
- [Sqrt(d) Dimension Dependence of Langevin Monte Carlo](https://mlsanity.com/paper/2109.03839/) (2021)
- [Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions](https://mlsanity.com/paper/2206.07252/) (2022)
- [Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling](https://mlsanity.com/paper/2210.08448/) (2022)
- [Mean-field Variational Inference via Wasserstein Gradient Flow](https://mlsanity.com/paper/2207.08074/) (2022)
- [Heavy-tailed denoising score matching](https://mlsanity.com/paper/2112.09788/) (2021)
- [Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition](https://mlsanity.com/paper/2206.00508/) (2022)
- [When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint](https://mlsanity.com/paper/2110.01827/) (2021)
- [Fisher information lower bounds for sampling](https://mlsanity.com/paper/2210.02482/) (2022)
- [Kinetic Langevin MCMC Sampling Without Gradient Lipschitz Continuity -- the Strongly Convex Case](https://mlsanity.com/paper/2301.08039/) (2023)
- [Non-asymptotic estimates for TUSLA algorithm for non-convex learning with applications to neural networks with ReLU activation function](https://mlsanity.com/paper/2107.08649/) (2021)
- [Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimation](https://mlsanity.com/paper/2303.03237/) (2023)
- [Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited](https://mlsanity.com/paper/2306.08494/) (2023)
- [Gradient Norm Minimization of Nesterov Acceleration: o(1/k3)](https://mlsanity.com/paper/2209.08862/) (2022)
- [Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration](https://mlsanity.com/paper/2211.11003/) (2022)
- [Convergence Analysis of Schr"odinger-F"ollmer Sampler without Convexity](https://mlsanity.com/paper/2107.04766/) (2021)
- [Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms](https://mlsanity.com/paper/2206.03792/) (2022)
- [Bregman Proximal Langevin Monte Carlo via Bregman--Moreau Envelopes](https://mlsanity.com/paper/2207.04387/) (2022)
- [Statistical and Computational Trade-offs in Variational Inference: A Case Study in Inferential Model Selection](https://mlsanity.com/paper/2207.11208/) (2022)
- [Taming under isoperimetry](https://mlsanity.com/paper/2311.09003/) (2023)
- [Tamed Langevin sampling under weaker conditions](https://mlsanity.com/paper/2405.17693/) (2024)
- [Kinetic Interacting Particle Langevin Monte Carlo](https://mlsanity.com/paper/2407.05790/) (2024)
- [Heavy-tailed Sampling via Transformed Unadjusted Langevin Algorithm](https://mlsanity.com/paper/2201.08349/) (2022)
- [Constrained Langevin Algorithms with L-mixing External Random Variables](https://mlsanity.com/paper/2205.14192/) (2022)
- [Diffusion at Absolute Zero: Langevin Sampling Using Successive Moreau Envelopes [conference paper]](https://mlsanity.com/paper/2502.01358/) (2025)
- [Langevin dynamics based algorithm e-THvarepsilonO POULA for stochastic optimization problems with discontinuous stochastic gradient](https://mlsanity.com/paper/2210.13193/) (2022)
- [From Global to Local: A Scalable Benchmark for Local Posterior Sampling](https://mlsanity.com/paper/2507.21449/) (2025)

## Abstract (arXiv)

We study the problem of sampling from a distribution p^*(x) propto expleft(-U(x)right), where the function U is L-smooth everywhere and m-strongly convex outside a ball of radius R, but potentially nonconvex inside this ball. We study both overdamped and underdamped Langevin MCMC and establish upper bounds on the number of steps required to obtain a sample from a distribution that is within ε of p^* in 1-Wasserstein distance. For the first-order method (overdamped Langevin MCMC), the iteration complexity is tildeOleft(ecLR2d/ε2right), where d is the dimension of the underlying space. For the second-order method (underdamped Langevin MCMC), the iteration complexity is tildeOleft(ecLR2√d/εright) for an explicit positive constant c. Surprisingly, the iteration complexity for both these algorithms is only polynomial in the dimension d and the target accuracy ε. It is exponential, however, in the problem parameter LR2, which is a measure of non-log-concavity of the target distribution.