Search papers, labs, and topics across Lattice.
This paper establishes that the Randomized Hamiltonian Monte Carlo (RHMC) algorithm can achieve accelerated mixing time for sampling log-concave distributions by employing random integration times and resetting velocities to independent Gaussian variables. The authors demonstrate that under certain conditions, including the satisfaction of an α-Talagrand inequality, RHMC converges exponentially fast in KL divergence, with integration time scaling as O(α^{-1/2} log(ε^{-1})). Additionally, they show that using a sequence of triangular distribution integration times with exponentially increasing means leads to a total integration time scaling as O(ε^{-1/2}), significantly improving sampling efficiency.
RHMC can exponentially accelerate convergence for log-concave distributions, achieving remarkable efficiency in sampling with tailored random integration times.
We show the Randomized Hamiltonian Monte Carlo (RHMC) algorithm has accelerated mixing time guarantees for sampling from log-concave probability distributions. RHMC proceeds by repeatedly simulating the continuous-time Hamiltonian dynamics for some random integration times, and resetting the velocity to be an independent Gaussian random variable between each simulation. We show that when the target distribution is log-concave and satisfies an $α$-Talagrand inequality (for example, if the target distribution is $α$-strongly log-concave), if we use a random integration time from either the triangular or the exponential distribution with mean $Θ(α^{-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(α^{-1/2} \log(\varepsilon^{-1}))$. We also show that when the target distribution is log-concave, if we use a sequence of random integration times from the 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 relies on a bound on the average KL divergence along Hamiltonian dynamics, which is inspired by an analogous result on accelerated optimization methods based on Hamiltonian dynamics.
