Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions

Zongchen Chen, Santosh Vempala

arXiv (Cornell University) · 2019 · 17 citations · 16 references

DOIFull text

Open access

Concepts

Abstract

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.

References

16