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