Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
This provides a theoretical improvement in convergence rates for HMC, which is incremental but important for computational statistics and machine learning applications involving sampling.
The paper tackles the problem of sampling from strongly logconcave distributions using Hamiltonian Monte Carlo (HMC), showing that the relaxation time improves to O(κ) from the previous O(κ^{1.5}) and providing an implementation with Õ((κd)^{0.5} ε^{-1}) gradient evaluations per step.
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 $μ$-strongly convex and $L$-smooth (the condition number is $κ= L/μ$). We show that the relaxation time (inverse of the spectral gap) of ideal HMC is $O(κ)$, improving on the previous best bound of $O(κ^{1.5})$; we complement this with an example where the relaxation time is $Ω(κ)$. When implemented using a nearly optimal ODE solver, HMC returns an $\varepsilon$-approximate point in $2$-Wasserstein distance using $\widetilde{O}((κd)^{0.5} \varepsilon^{-1})$ gradient evaluations per step and $\widetilde{O}((κd)^{1.5}\varepsilon^{-1})$ total time.