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

Abstract

Hamiltonian Monte Carlo (HMC) is a very popular and generic 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: under conditions that are satisfied for many common statistical models, optimally-tuned HMC algorithms have a running time that scales like $d^{0.25}$. In stark contrast, the running time of the usual Random-Walk Metropolis (RWM) algorithm, optimally tuned, scales like $d$. This superior scaling of the HMC algorithm with dimension is attributed to the fact that it, unlike RWM, incorporates the gradient information in the proposal distribution. In this paper, we investigate a different scaling question: does HMC beat RWM for highly $\text{multimodal}$ targets? We find that the answer is often $\text{no}$. We compute the spectral gaps for both the algorithms for a specific class of multimodal target densities, and show that they are identical. The key reason is that, within one mode, the gradient is effectively ignorant about other modes, thus negating the advantage the HMC algorithm enjoys in unimodal targets. We also give heuristic arguments suggesting that the above observation may hold quite generally. Our main tool for answering this question is a novel simple formula for the conductance of HMC using Liouville's theorem. This result allows us to compute the spectral gap of HMC algorithms, for both the classical HMC with isotropic momentum and the recent Riemannian HMC, for multimodal targets.

References in corpus (7)

• A Conceptual Introduction to Hamiltonian Monte Carlo
• On the Geometric Ergodicity of Hamiltonian Monte Carlo
• Randomized Hamiltonian Monte Carlo
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo
• Curvature and Concentration of Hamiltonian Monte Carlo in High Dimensions
• Simple Conditions for Metastability of Continuous Markov Chains

Cited by in corpus (9)

• Stacking for Non-mixing Bayesian Computations: The Curse and Blessing of Multimodal Posteriors
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• Accelerating Parallel Tempering: Quantile Tempering Algorithm (QuanTA)
• Schr{ö}dinger-F{ö}llmer Sampler: Sampling without Ergodicity
• Simple Conditions for Metastability of Continuous Markov Chains
• HMC: avoiding rejections by not using leapfrog and some results on the acceptance rate
• Adaptive Path Sampling in Metastable Posterior Distributions
• Optimal Temperature Spacing for Regionally Weight-preserving Tempering
• A splitting Hamiltonian Monte Carlo method for efficient sampling