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).