Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
pdf icon
Volume 18 (2022) Article 9 pp. 1-18
APPROX-RANDOM 2019 Special Issue
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
Received: February 29, 2020
Revised: September 23, 2020
Published: April 30, 2022
Download article from ToC site:
[PDF (1062K)] [PS (2755K)] [Source ZIP]
Keywords: logconcave distribution, sampling, Hamiltonian Monte Carlo, spectral gap, strong convexity
ACM Classification: Theory of computation--Random walks and Markov chains, Design and analysis of algorithms
AMS Classification: 60J05, 60J25, 68W20

Abstract: [Plain Text Version]

\newcommand{\R}{{\mathbb R}} \newcommand{\eee}{\mathrm e} \newcommand{\eps}{\varepsilon}

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