Accelerated Mixing Time of Randomized Hamiltonian Monte Carlo

The paper proves that Randomized Hamiltonian Monte Carlo achieves "accelerated mixing time guarantees" for sampling from log-concave probability distributions. For targets satisfying an α-Talagrand inequality, using random integration times from triangular or exponential distributions yields convergence in KL divergence with total integration time scaling as O(α^{-1/2} log(ε^{-1})). For general log-concave distributions, triangular integration times with exponentially increasing means achieve O(ε^{-1/2}) total integration time. The analysis builds on bounds for average KL divergence along Hamiltonian dynamics.