Optimal tuning of the hybrid Monte Carlo algorithm

By Alexandros Beskos, Natesh S. Pillai, Gareth O. Roberts, Jesús María Sanz-Serna, Andrew M. Stuart. 2010

355 citations recorded by the source corpus.

We investigate the properties of the Hybrid Monte Carlo algorithm (HMC) in high dimensions. HMC develops a Markov chain reversible w.r.t. a given target distribution . by using separable Hamiltonian dynamics with potential -log .. The additional momentum variables are chosen at random from the Boltzmann distribution and the continuous-time Hamiltonian dynamics are then discretised using the leapfrog scheme. The induced bias is removed via a Metropolis- Hastings accept/reject rule. In the simplified scenario of independent, identically distributed components, we prove that, to obtain an O(1) acceptance probability as the dimension d of the state space tends to ., the leapfrog step-size h should be scaled as h=l ×d−1/ 4 . Therefore, in high dimensions, HMC requires O(d1/ 4 ) steps to traverse the state space. We also identify analytically the asymptotically optimal acceptance probability, which turns out to be 0.651 (to three decimal places). This is the choice which optimally balances the cost of generating a proposal, which decreases as l increases (because fewer steps are required to reach the desired final integration time), against the cost related to the average number of proposals required to obtain acceptance, which increases as l increases

Subfields: Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/602e9f9844ce34c72e0bb6dceb80fb7c8e4d2e2a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistics and Probability

Citations in the corpus

The Kernel Interaction Trick: Fast Bayesian Discovery of Pairwise Interactions in High Dimensions (2019, background): “Even for p moderately large, the ⇥(p2 + dim(⌧)) number of parameters might require many MCMC iterations to properly explore such a large space (Beskos et al., 2013; MacKay, 1998; Pillai et al., 2012); see also Fig.”
Optimal Scaling and Diffusion Limits for the Langevin Algorithm in High Dimensions (2011, background): “• In [4] it is shown that the Hybrid Monte Carlo algorithm (HMC) requires, for target measures of the form (1.”
Bayesian computation: a perspective on the current state, and sampling backwards and forwards (2015, background): “nthal (1998) and conrmed in innite-dimensional settings in Pillai et al. (2012) along with the stepsize ˙2 d = l 2d 1=3. Hybrid Monte Carlo (see Section 2.3) has been analysed in a similar spirit by Beskos et al. (2013) resulting in an optimal acceptance rate of 0:651 and leapfrog step size h= l d 1”
On the stability of sequential Monte Carlo methods in high dimensions (2011, background): “In addition, there is a vast literature on the performance of high-dimensional Markov chain Monte Carlo (MCMC) algorithms, for example, [10, 43, 44]; our aim is to obtain a similar analytical understanding about the effect of dimension on SMC methods.”
Learning Energy-based Model with Flow-based Backbone by Neural Transport MCMC (2020, neutral): “651 [5].”
Posterior Computation with the Gibbs Zig-Zag Sampler (2020, neutral): “651 (Beskos et al., 2013).”
The Geometric Foundations of Hamiltonian Monte Carlo (2014, background): “When the target distribution decomposes into a product of many independent and identically distributed measures, the optimal compromise between these extremes can be computed directly (Beskos et al., 2013).”
Optimizing The Integrator Step Size for Hamiltonian Monte Carlo (2014, methodology): “At present the integrator step size is typically set by applying the analysis in Beskos et al. (2013), which derived a lower bound for the cost of the algorithm as a function of the integrator step size when targeting an independently and identically distributed target distribution and a…”
Bayesian computation: a summary of the current state, and samples backwards and forwards (2015, background): “Hybrid Monte Carlo (see Sect.2.3) has been analysed in a similar spirit by Beskos et al. (2013) and Betancourt et al. (2014) concluding that any value ∈ [ 0 .”
The computation of averages from equilibrium and nonequilibrium Langevin molecular dynamics (2013, background): “Keywords: Langevin dynamics; Stochastic differential equations; Numerical discretization.”