Underdamped Langevin MCMC: A non-asymptotic analysis

By Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, Michael I. Jordan. Annual Conference Computational Learning Theory, 2017

342 citations recorded by the source corpus.

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

Subfields: Condensed Matter Physics, Radiology, Nuclear Medicine and Imaging, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/24e31e8cf65a099950ac3a5a3c18328f500887df

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Condensed Matter Physics

In Radiology, Nuclear Medicine and Imaging

In Statistics and Probability

Citations in the corpus

SVGD as a kernelized Wasserstein gradient flow of the chi-squared divergence (2020, methodology): “This optimization perspective on Markov Chain Monte Carlo (MCMC) has not only renewed our understanding of algorithms based on Langevin diﬀusions [Dal17a,Ber18,CB18,Wib18,DMM19,VW19], but has also fueled the discovery of new MCMC algorithms inspired by the diverse and powerful optimization toolbox [”
Stochastic Gradient Markov Chain Monte Carlo (2019, methodology): “These results are for bounds on the Wasserstein distance between the target distribution and the distribution of the SGMCMC algorithm samples at iteration k , for an optimally chosen step size (Cheng et al. , 2017).”
Log-concave sampling: Metropolis-Hastings algorithms are fast! (2018, methodology): “Algorithms related to the Langevin diﬀusion include the Metropolis adjusted Langevin Algorithm (MALA) (Roberts and Tweedie, 1996a; Roberts and Stramer, 2002; Bou-Rabee and Hairer, 2012), the unadjusted Langevin algorithm (ULA) (Parisi, 1981; Grenander and Miller, 1994; Roberts and Tweedie, 1996a; Da”
Generalized Energy Based Models (2020, methodology): “…samplers were shown to better explore the modes of the invariant distribution ν compared to Overdamped ones (see (Neal, 2010; Betancourt et al., 2017) for empirical results and (Cheng et al., 2017) for theory), as also confirmed empirically in Appendix D for image generation tasks using GEBMs.”
Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints (2017, methodology): “The SGLD algorithm exhibits several nice properties even for non-convex functions, and has been used for sampling (Bubeck et al., 2015; Nagapetyan et al., 2017; Dalalyan, 2017; Cheng et al., 2017; Cheng and Bartlett, 2017) and non-convex optimization (Raginsky et al.”