Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions

We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly logconcave density proportional to $e^{-f}$ where $f:$\mathbb{R}$^d \to $\mathbb{R}$$is$\mu$-stronglyconvexand$L$-smooth(theconditionnumberis$\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})$; we complement this with an example where the relaxation time is $\mathrm{\Omega }(\kappa )$. When implemented using a nearly optimal ODE solver, HMC returns an $\epsilon$-approximate point in $2$-Wasserstein distance using $\tilde{O}((\kappa d{)}^{0.5}{\epsilon }^{-1})$ gradient evaluations per step and $\tilde{O}((\kappa d{)}^{1.5}{\epsilon }^{-1})$ total time.