Source-linked AI summary
Optimal tuning of the Hybrid Monte-Carlo Algorithm
Alexandros Beskos, Natesh S. Pillai, Gareth O. Roberts, Jesus M. Sanz-Serna, Andrew M. Stuart
TL;DR
The paper addresses limited theoretical guidance for tuning HMC in high dimensions. It analytically studies leapfrog discretization and establishes O(d^1/4) traversal scaling with a target-independent optimal acceptance probability of 0.651.
Problem
HMC lacks theoretical guidance for choosing its free parameters in high dimensions, despite proposed efficiency advantages over random-walk-like MCMC behavior.
Method
The paper analytically studies HMC using the leapfrog integrator under suitable high-dimensional assumptions.
Results
O(d^1/4) steps are required for HMC to make O(1) moves in state space, and the asymptotically optimal acceptance probability is 0.651.
Takeaways & Limitations
In high dimensions, tune HMC's free parameters to obtain an acceptance probability close to 0.651, balancing proposal-generation cost against the cost of rejected proposals.
Takeaways & Limitations
The analysis fixes the mass matrix M and integration time T, optimizing only the leapfrog step-size h.
Abstract
from arXiv · showhide
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 $\mathcal{O}(1)$ acceptance probability as the dimension $d$ of the state space tends to $\infty$, the leapfrog step-size $h$ should be scaled as $h= l \times d^{-1/4}$. Therefore, in high dimensions, HMC requires $\mathcal{O}(d^{1/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 {\em decreases} as $l$ increases, against the cost related to the average number of proposals required to obtain acceptance, which {\em increases} as $l$ increases.
1. Introduction
The paper develops theoretical guidance for tuning HMC in high-dimensional targets, analyzing its efficiency under an iid component structure. It establishes the step-size scaling needed for nonvanishing acceptance and identifies an analytically optimal acceptance probability.
- Motivation: HMC uses target-density derivatives to make guided, global moves, addressing random-walk behavior and limited theoretical tuning guidance in high-dimensional MCMC.The paper aims to develop theoretical tools for improving HMC efficiency.
- Setting: The analysis assumes a target distribution composed of d ≫ 1 independent, identically distributed vector components.The component dimension is m, with N = m × d.
- Scaling: O(d^1/4) steps are required for HMC to make O(1) moves through the state space under suitable hypotheses on V.This is the paper’s analytic high-dimensional scaling result for leapfrog HMC.
- Scaling: h = l · d^-1/4 leads to an average acceptance probability of O(1) as d →∞.The scaling applies to the leapfrog integrator.
- Optimal tuning: 0.651 is the asymptotically optimal acceptance probability, independent of the particular target Π in the stated setting.The paper recommends tuning free algorithmic parameters to obtain an acceptance probability close to this value.
- Optimal tuning: Increasing l decreases proposal-generation cost but increases the cost associated with the average number of proposals needed for acceptance.The optimal l balances these opposing costs.
- Comparison: HMC’s O(d^1/4) scaling compares with O(d) for RWM and O(d^1/3) for MALA in a similar context.The paper also notes that higher-order reversible, volume-preserving integrators have scaling O(d^(1/(2ν))).
2. Hybrid Monte Carlo (HMC)
HMC introduces momentum variables and uses Hamiltonian dynamics to generate proposals, with leapfrog discretization making the method practical. Metropolis-Hastings correction restores invariance, while high-dimensional analysis guides step-size tuning and relates HMC to RWM and MALA.
- Hamiltonian dynamics: H(Q, P) combines kinetic energy, determined by momentum P and mass matrix M, with potential energy V(Q) to form the total energy.Q is the location variable, while M is symmetric positive definite.
- Hamiltonian dynamics: Hamiltonian flow conserves energy and volume and is time reversible, properties that preserve distributions depending only on H.The marginal position density is proportional to exp(−V(Q)) under the corresponding invariant distribution.
- The HMC algorithm: The leapfrog scheme discretizes continuous-time Hamiltonian dynamics through a three-stage update from (Q0, P0) to (Qh, Ph).Repeated steps approximate the Hamiltonian flow over an integration time T.
- The HMC algorithm: Because leapfrog does not exactly conserve energy, an accept-reject step corrects the resulting bias and yields a Markov chain reversible with respect to Π.The integrator remains volume preserving and time reversible.
- The HMC algorithm: The momentum is auxiliary, while h, T, and the mass matrix M are user-controlled parameters; this paper focuses on optimizing h.The broader optimization would also vary M and T.
- Connections: HMC uses deterministic trajectory elements, whereas RWM and MALA use purely stochastic updates; HMC reduces to MALA when T ≡ h.That reduction corresponds to taking one leapfrog step per transition.
- Scope: The analysis assumes regularity conditions on V, including seven derivatives with polynomial growth bounds and finite moments of exp(−V).A technical requirement may be relaxed.
- Connections: RWM and MALA require O(d) and O(d^1/3) costs respectively, compared with HMC’s O(d^1/4) cost for O(1) moves under the stated scaling.For HMC, the scaling h = l · d^-1/4 yields average acceptance probability O(1).
3. Hybrid Monte Carlo in the limit d →∞.
In the iid high-dimensional setting, the paper analyzes leapfrog energy errors and identifies the step-size scaling that yields nontrivial HMC acceptance. It also characterizes the resulting one-transition dynamics and notes limitations arising when the assumptions behind the Gaussian limit fail.
- 3.1. HMC in the iid scenario.: HMC is analyzed in the iid scenario as d, the number of particles, tends to infinity, with individual location/momentum components treated separately.The leapfrog solution operator is applied to each particle, while particles are coupled through the global accept/reject decision.
- 3.2. Energy increments.: O(h^4) average energy increments determine the step-size scaling needed for nontrivial acceptance as d →∞.Leapfrog has O(h^2) integration error, but volume preservation and time reversibility make the average energy increment O(h^4).
- 3.3. Expected acceptance probability.: h = O(d^-1/4) yields an O(1) limiting acceptance probability for the leapfrog integrator under the stated regularity conditions.The scaling follows from aggregating d iid energy-increment terms whose expectation and standard deviation are both O(h^4).
- 3.3. Expected acceptance probability.: The Central Limit Theorem produces the limiting acceptance probability under the finite-variance assumptions used in Theorem 3.6.If the relevant variance is infinite, a Gaussian limit is not guaranteed and a different, potentially stable-law scaling may be needed.
- 3.5. The limit dynamics.: The marginal HMC process is not expected to be asymptotically Markovian because its dynamics depend on all particles through the acceptance probability.This contrasts with the asymptotic Markovian behavior described for RWM and MALA in the cited discussion.
- 3.5. The limit dynamics.: With probability a(l), a marginal HMC particle follows the correct Hamiltonian dynamics; with probability 1 − a(l), it remains at its current position.The rejection event reflects energy errors accumulated across all d particles during leapfrog integration.
4. Optimal tuning of HMC
The section derives how to tune HMC in high dimensions by balancing proposal-generation cost against acceptance probability. It identifies a target-independent asymptotic optimum of 0.651 and shows that finite-dimensional practice may favor higher acceptance.
- Optimal tuning: Increasing l lowers proposal cost but also lowers acceptance probability, so tuning must balance both effects.A proposal uses ⌈T/h⌉ leapfrog steps, with h scaled through l.
- Asymptotically optimal acceptance probability: 0.651 is the target-independent asymptotically optimal limiting acceptance probability.The value minimizes the asymptotic cost measure E*_{l,d}.
- Squared jumping distance: The 0.651 optimum is recovered by maximizing asymptotic expected squared jumping distance.This provides an alternative efficiency criterion with the same asymptotic optimizer.
- Optimal acceptance probability in practice: For finite but large d, the algorithm tends to benefit from average acceptance probabilities higher than 0.651.Proposal-count benefits converge more slowly than acceptance probabilities in the stated asymptotic analysis.
- Optimal acceptance probability in practice: A numerical study with d = 105 Gaussian components and 30-second runs found boxplot behavior consistent with higher finite-dimensional optimal acceptance.The study used 120 runs for each step-size choice and compared squared errors across four functions.
5. Estimates for the leapfrog algorithm
This section establishes regularity and growth conditions under which the leapfrog analysis is valid. It derives global-error and energy-increment estimates, then verifies the required conditions for two families of potentials.
- Assumptions: V is assumed four-times continuously differentiable, with the first three derivatives of the force uniformly bounded.These are the core smoothness assumptions used for the leapfrog estimates.
- Assumptions: If V grows faster than quadratically, constant-step leapfrog integration can be unstable for sufficiently large initial conditions.The stated assumptions therefore imply at-most-quadratic growth of V at infinity.
- Trajectory estimates: The analysis bounds derivatives of the Hamiltonian trajectory in terms of momentum and force magnitudes.These bounds control the higher-order terms entering the leapfrog error analysis.
- Global-error estimates: The global leapfrog error is estimated through stability bounds and an asymptotic expansion with leading coefficients from a variational system.The expansion tracks errors in both q_n and p_n over 0 ≤ t_n ≤ T.
- Energy-increment estimates: Under the assumptions, the leapfrog energy increment admits an asymptotic expansion involving the exact trajectory and variational-system solutions.Proposition 5.4 supplies the resulting expansion.
- Verification of conditions: The required conditions hold when the force is bounded or when V grows at least as C1|q|^γ for 0 < γ ≤ 1 outside a bounded region.These two potential families cover many useful target distributions according to the section.
6. Proofs of Probabilistic Results
The proofs establish the high-dimensional limiting behavior by controlling leapfrog energy errors, acceptance probabilities, and reversibility-related limits under the stated conditions.
- Reversibility: Time reversibility follows by combining the symmetry operator S with volume preservation and the identity H(Sz) = H(z).These transformations yield convergence of the relevant forward and reverse states.
- Energy-error analysis: The leapfrog energy error is analyzed through its first and second moments as the step-size h decreases.The analysis uses pointwise limits, fourth-order bounds, inequalities, and dominated convergence to control these quantities.
- High-dimensional limit: h = l · d^-1/4 is the scaling used to derive the high-dimensional limit in Theorem 3.6.The proof continues from the preceding asymptotic expression and applies Proposition 3.4 before invoking the Lindeberg condition.
- High-dimensional limit: The Lindeberg condition is used to establish the limiting result underlying the theorem's asymptotic acceptance analysis.The proof then evaluates the remaining expectation analytically.
- Acceptance analysis: The limiting acceptance factor is combined with a one-particle expectation using independence and dominated convergence.This factorization supplies the result stated in Equation (6.3).
7. Conclusions
The paper presents HMC as promising for high-dimensional sampling while identifying broader tuning, integrator, irreducibility, and limiting-distribution questions for future work.
- HMC is presented as a promising framework for sampling problems, especially in high dimensions.
- The overall optimization involves tuning l, T, and the mass matrix M, but this paper fixes M and T and focuses on the step-size h.
- Semi-implicit integrators may be worth studying because they have the potential to produce methods that explore state space in O(1) steps.
- The irreducibility of HMC's transition kernel remains subtle because exceptional cases can lead to nonergodic behavior.