Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions

We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly\nlogconcave density proportional to $e^{-f}$ where $f:\\mathbb{R}^d \\to\n\\mathbb{R}$ is $\\mu$-strongly convex and $L$-smooth (the condition number is\n$\\kappa = L/\\mu$). We show that the relaxation time (inverse of the spectral\ngap) of ideal HMC is $O(\\kappa)$, improving on the previous best bound of\n$O(\\kappa^{1.5})$; we complement this with an example where the relaxation time\nis $\\Omega(\\kappa)$. When implemented using a nearly optimal ODE solver, HMC\nreturns an $\\varepsilon$-approximate point in $2$-Wasserstein distance using\n$\\widetilde{O}((\\kappa d)^{0.5} \\varepsilon^{-1})$ gradient evaluations per\nstep and $\\widetilde{O}((\\kappa d)^{1.5}\\varepsilon^{-1})$ total time.\n