Underdamped Langevin MCMC: A non-asymptotic analysis

Abstract

We study the underdamped Langevin diffusion when the log of the target distribution is smooth and strongly concave. We present a MCMC algorithm based on its discretization and show that it achieves $\epsilon$ error (in 2-Wasserstein distance) in $\mathcal{O}(\sqrt{d}/\epsilon )$ steps. This is a significant improvement over the best known rate for overdamped Langevin MCMC, which is $\mathcal{O}(d/{\epsilon }^2)$ steps under the same smoothness/concavity assumptions. The underdamped Langevin MCMC scheme can be viewed as a version of Hamiltonian Monte Carlo (HMC) which has been observed to outperform overdamped Langevin MCMC methods in a number of application areas. We provide quantitative rates that support this empirical wisdom.

23 pages; Correction to Corollary 7

References in corpus (1)

• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions

Cited by in corpus (13)

• On the Random Batch Method for second order interacting particle systems
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• Exponential ergodicity of mirror-Langevin diffusions
• An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
• Wasserstein Control of Mirror Langevin Monte Carlo
• Acceleration and Averaging in Stochastic Mirror Descent Dynamics
• SVGD as a kernelized Wasserstein gradient flow of the chi-squared divergence
• Accelerated Flow for Probability Distributions
• The shifted ODE method for underdamped Langevin MCMC
• Non-asymptotic error bounds for scaled underdamped Langevin MCMC
• Stochastic Approximate Gradient Descent via the Langevin Algorithm
• Stochastic Gradient Langevin with Delayed Gradients
• Distribution-Dependent Analysis of Gibbs-ERM Principle