
Revised: September 23, 2020
Published: April 30, 2022
Abstract: [Plain Text Version]
We study the Hamiltonian Monte Carlo (HMC) algorithm for sampling from a strongly logconcave density proportional to \eee^{-f} where f:\R^d \to \R is \mu-strongly convex and L-smooth (the condition number is \kappa = L/\mu). We show that the relaxation time (inverse of the spectral gap) of ideal HMC is O(\kappa), improving on the previous best bound of O(\kappa^{1.5}) (Lee et al., 2018); we complement this with an example where the relaxation time is \Omega(\kappa), for any step-size. When implemented with an ODE solver, HMC returns an \eps-approximate point in 2-Wasserstein distance using \tilde{O}((\kappa d)^{0.5} \eps^{-1}) gradient evaluations per step and \tilde{O}((\kappa d)^{1.5}\eps^{-1}) total time.
----------------------
A conference version of this paper appeared in the Proceedings of the 23rd International Conference on Randomization and Computation (RANDOM 2019).