Theory of Computing
-------------------
Title : Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
Authors : Zongchen Chen and Santosh S. Vempala
Volume : 18
Number : 9
Pages : 1-18
URL : https://theoryofcomputing.org/articles/v018a009
Abstract
--------
e study the _Hamiltonian Monte Carlo_ (HMC) algorithm for sampling
from a strongly logconcave density proportional to $e^{-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).