Accelerated Mixing Time of Randomized Hamiltonian Monte Carlo

This paper investigates the theoretical mixing time of Randomized Hamiltonian Monte Carlo (RHMC) for sampling from log-concave probability distributions. The authors seek to determine if RHMC can achieve accelerated convergence rates—analogous to those found in accelerated convex optimization—by randomizing the integration time of the Hamiltonian dynamics between velocity refreshments.

The authors analyze RHMC, an algorithm that alternates between simulating deterministic Hamiltonian dynamics and resetting velocities from a Gaussian distribution. They explore three specific strategies for choosing integration times: a triangular distribution, an exponential distribution, and an endpoint-biased triangular distribution. The analysis relies on bounding the average KL divergence along the Hamiltonian flow, drawing a formal connection between sampling dynamics and accelerated gradient flow methods in optimization. By leveraging the Wasserstein geometry of probability distributions, the authors derive convergence guarantees for both strongly log-concave and general log-concave target distributions.

The study establishes that RHMC provides significant speedups over standard Langevin dynamics. For distributions satisfying an alpha-Talagrand inequality (such as strongly log-concave distributions), RHMC achieves an accelerated KL-mixing time of O(alpha^-1/2 log(epsilon^-1)). Furthermore, for general log-concave distributions, the authors demonstrate that using a sequence of triangular integration times with exponentially increasing means allows the algorithm to reach error epsilon in O(epsilon^-1/2) total integration time. These results match the theoretical acceleration limits observed in convex optimization and eliminate the dependence on the smoothness parameter often found in deterministic Hamiltonian Monte Carlo analyses.