Accelerated Mixing Time of Randomized Hamiltonian Monte Carlo

arXiv:2607.12902v1 Announce Type: cross Abstract: 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 alpha-Talagrand inequality (for example, if the target distribution is alpha-strongly log-concave), if we use a random integration time from either the triangular or the exponential distribution with mean Theta(alpha^{-1/2}), then RHMC converges exponentially fast in KL divergence, and the total integration time to reach error arepsilon in KL divergence scales as O(alpha^{-1/2} log(arepsilon^{-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 arepsilon in KL divergence scales as O(arepsilon^{-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.

Related

• Hamiltonian Monte Carlo with Asymmetrical Momentum Distributions
• When Langevin Monte Carlo Meets Randomization: Non-asymptotic Error Bounds beyond Log-Concavity and Gradient Lipschitzness
• Adaptive Meta-Learning Stochastic Gradient Hamiltonian Monte Carlo Simulation for Bayesian Updating of Structural Dynamic Models

Source: arXiv cs.LG | 2026-07-15