  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.
