MIT researchers speed up Hamiltonian Monte Carlo sampling by O(1/√ε)
New proof shows RHMC converges exponentially faster for log-concave distributions.
Deep Dive
Siddharth Mitra, Vishwak Srinivasan, Xiuyuan Wang, and Andre Wibisono prove Randomized Hamiltonian Monte Carlo (RHMC) achieves accelerated mixing for log-concave sampling. When the target is α-strongly log-concave, total integration time scales as O(α^{-1/2} log(1/ε)) in KL divergence. For general log-concave, they achieve O(ε^{-1/2}) using triangular random integration times with increasing means.
Key Points
- Proves RHMC mixes in O(α^{-1/2} log(1/ε)) integration time for strongly log-concave targets — exponentially faster than unaccelerated methods.
- For general log-concave distributions, achieves O(ε^{-1/2}) total integration time using triangular random integration times with growing means.
- Establishes a new connection between Hamiltonian Monte Carlo and accelerated gradient descent via KL divergence bounds along Hamiltonian dynamics.
Why It Matters
Faster sampling unlocks Bayesian deep learning and large-scale probabilistic models previously hindered by slow MCMC mixing.