Does Hamiltonian Monte Carlo mix faster than a random walk on multimodal densities?

Hamiltonian Monte Carlo (HMC) is a very popular collection of Markov chain Monte Carlo (MCMC) algorithms. One explanation for the popularity of HMC algorithms is their excellent performance as the dimension d of the target becomes large: theoretical analyses show that popular versions of HMC can have a running time that scales as well as d0.25 in good conditions, while even an optimally tuned random-walk metropolis (RWM) algorithm will not do better than d . In this paper, we investigate a different scaling question: does HMC beat RWM for targets with well-separated modes? We find that the answer is often no . Our main tool for answering this question is a novel and simple formula for the conductance of HMC based on Liouville’s theorem, and we also show how this new formula can be used to give very short proofs of results that seem tedious to show with the usual formula. We also use this result to compute the spectral gap of HMC algorithms, for both the classical HMC with isotropic momentum and the recent Riemannian HMC, for multimodal targets. While we focus on the concrete comparison of RWM and HMC, we expect qualitatively similar conclusions to hold for other gradient-based algorithms.