Accelerated Mixing Time of Randomized Hamiltonian Monte Carlo

We show the Randomized Hamiltonian Monte Carlo RHMC algorithm has accelerated mixing time for sampling from log-concave probability distributions. RHMC proceeds by repeatedly simulating the continuous-time Hamiltonian dynamics for some random integration times, and resample the velocity from an independent Gaussian distribution between each simulation. We show that when the target distribution is log-concave and satisfies an $\alpha$-Talagrand inequality (implying that log-Sobolev inequality is also satisfied), if we draw the integration time from the triangular distribution with mean $\Theta(\alpha^{-1/2})$, then RHMC converges exponentially fast in KL divergence, and the total integration time to reach error $\varepsilon$ in KL divergence scales as $O(\alpha^{-1/2} \log(\varepsilon^{-1}))$. We also show that when the target distribution is log-concave, if we draw the integration times from triangular distribution with exponentially increasing means, then the total integration time to reach error $\varepsilon$ in KL divergence scales as $O(\varepsilon^{-1/2})$. Our analysis is inspired by recent works using Hamiltonian dynamics for convex optimization.