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 $arepsilon$ error (in 2-Wasserstein distance) in $mathcal{O}(sqrt{d}/arepsilon)$ steps. This is a significant improvement over the best known rate for overdamped Langevin MCMC, which is $mathcal{O}(d/arepsilon^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.
展开▼
