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

  • 2018-08-09 16:46:51
  • Oren Mangoubi, Natesh S. Pillai, Aaron Smith
  • 8


Hamiltonian Monte Carlo (HMC) is a very popular and generic collection ofMarkov chain Monte Carlo (MCMC) algorithms. One explanation for the popularityof HMC algorithms is their excellent performance as the dimension $d$ of thetarget becomes large: under conditions that are satisfied for many commonstatistical models, optimally-tuned HMC algorithms have a running time thatscales like $d^{0.25}$. In stark contrast, the running time of the usualRandom-Walk Metropolis (RWM) algorithm, optimally tuned, scales like $d$. Thissuperior scaling of the HMC algorithm with dimension is attributed to the factthat it, unlike RWM, incorporates the gradient information in the proposaldistribution. In this paper, we investigate a different scaling question: doesHMC beat RWM for highly $\textit{multimodal}$ targets? We find that the answeris often $\textit{no}$. We compute the spectral gaps for both the algorithmsfor a specific class of multimodal target densities, and show that they areidentical. The key reason is that, within one mode, the gradient is effectivelyignorant about other modes, thus negating the advantage the HMC algorithmenjoys in unimodal targets. We also give heuristic arguments suggesting thatthe above observation may hold quite generally. Our main tool for answeringthis question is a novel simple formula for the conductance of HMC usingLiouville's theorem. This result allows us to compute the spectral gap of HMCalgorithms, for both the classical HMC with isotropic momentum and the recentRiemannian HMC, for multimodal targets.


Introduction (beta)



Conclusion (beta)