Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time
Jun-Kun Wang, Andre Wibisono
Hamiltonian Monte Carlo (HMC) is a popular method in sampling. While there
are quite a few works of studying this method on various aspects, an
interesting question is how to choose its integration time to achieve
acceleration. In this work, we consider accelerating the process of sampling
from a distribution $\pi(x) \propto \exp(-f(x))$ via HMC via time-varying
integration time. When the potential $f$ is $L$-smooth and $m$-strongly convex,
i.e.\ for sampling from a log-smooth and strongly log-concave target
distribution $\pi$, it is known that under a constant integration time, the
number of iterations that ideal HMC takes to get an $\epsilon$ Wasserstein-2
distance to the target $\pi$ is $O( \kappa \log \frac{1}{\epsilon} )$, where
$\kappa := \frac{L}{m}$ is the condition number. We propose a scheme of
time-varying integration time based on the roots of Chebyshev polynomials. We
show that in the case of quadratic potential $f$, i.e., when the target $\pi$
is a Gaussian distribution, ideal HMC with this choice of integration time only
takes $O( \sqrt{\kappa} \log \frac{1}{\epsilon} )$ number of iterations to
reach Wasserstein-2 distance less than $\epsilon$; this improvement on the
dependence on condition number is akin to acceleration in optimization. The
design and analysis of HMC with the proposed integration time is built on the
tools of Chebyshev polynomials. Experiments find the advantage of adopting our
scheme of time-varying integration time even for sampling from distributions
with smooth strongly convex potentials that are not quadratic.