Source-linked AI summary
Randomized Hamiltonian Monte Carlo
Nawaf Bou-Rabee, Jesus Maria Sanz-Serna
TL;DR
HMC’s flow duration is challenging to tune because it trades computational cost against sampling quality. The paper randomizes durations exponentially in RHMC and analyzes its behavior; it proves geometric ergodicity in the exact-flow regime and finds more regular sampling-efficiency behavior than fixed-duration HMC. It also proposes variants that account for integration errors.
Problem
HMC’s flow duration trades off computational cost and sampling quality, while its sampling behavior can vary irregularly with duration.
Source: §1 · pp. 1, 3Method
Results
In the exact-flow regime, RHMC is geometrically ergodic, and its sampling metrics vary monotonically with mean duration, unlike classical HMC’s more complicated dependence on fixed duration.
Source: §7 · p. 36Takeaways & Limitations
Randomizing flow durations mitigates some artifacts of Hamiltonian dynamics, with the reported monotonicity also appearing in numerical examples for more general targets.
Source: §7 · p. 36Analyzing a discretized-flow variant requires global error bounds over arbitrarily long integration legs, and the paper leaves that analysis to future work.
Source: §6 · p. 30
Abstract
from arXiv · showhide
Tuning the durations of the Hamiltonian flow in Hamiltonian Monte Carlo (also called Hybrid Monte Carlo) (HMC) involves a tradeoff between computational cost and sampling quality, which is typically challenging to resolve in a satisfactory way. In this article we present and analyze a randomized HMC method (RHMC), in which these durations are i.i.d. exponential random variables whose mean is a free parameter. We focus on the small time step size limit, where the algorithm is rejection-free and the computational cost is proportional to the mean duration. In this limit, we prove that RHMC is geometrically ergodic under the same conditions that imply geometric ergodicity of the solution to underdamped Langevin equations. Moreover, in the context of a multi-dimensional Gaussian distribution, we prove that the sampling efficiency of RHMC, unlike that of constant duration HMC, behaves in a regular way. This regularity is also verified numerically in non-Gaussian target distributions. Finally we suggest variants of RHMC for which the time step size is not required to be small.
1. Introduction.
The introduction motivates randomizing HMC’s flow duration to address its difficult tradeoff between sampling quality and computational cost. It presents RHMC’s theoretical guarantees, more regular sampling-efficiency behavior, and practical variants.
1. Introduction.
- HMC duration is difficult to tune: longer flows increase computational cost and can increase correlation after a trajectory turns back, while some fixed durations can make HMC non-ergodic.For a univariate normal target, the flow can return the state to its starting point at particular durations.Source: §1 · pp. 3–4
- RHMC independently draws each Hamiltonian-flow duration from an exponential distribution, leaving mean duration as its free parameter in the exact-flow setting.The paper focuses on sufficiently small time steps that essentially all steps are accepted.Source: §1 · p. 4
- With exact Hamiltonian flow, RHMC is geometrically ergodic for any mean duration, using a Lyapunov and minorization argument under conditions similar to those for underdamped Langevin dynamics.The analysis also establishes invariance and uniqueness of the target measure.Source: §1 · pp. 4–5
- For multidimensional Gaussian targets, RHMC’s sampling-efficiency metrics depend simply on mean duration, unlike HMC’s complicated dependence on its fixed duration.The metrics are integrated autocorrelation time and equilibrium mean-squared displacement.Source: §1 · p. 5
- Numerical tests on a double-well potential and a pentane-molecule potential support the theoretical findings, and the reported regularity persists for more general targets.The paper also describes two variants for non-negligible integration errors: one may bias the target, while the other removes that bias using Metropolis-Hastings momentum flips.Source: §1 · p. 5
- The paper’s theoretical contributions include a Foster-Lyapunov drift condition, a martingale-problem solution, invariance and minorization results, and geometric ergodicity; it also introduces two practical implementations, including one that is unbiased.Source: §1 · p. 5
- RHMC is related to Anderson’s impulsive thermostat, and the authors state that their geometric-ergodicity proof can be modified to extend its result to an unbounded space.The cited thermostat models interaction with a heat bath through momentum-randomizing collisions at i.i.d. exponential times.Source: §1 · p. 6
2. RHMC Method.
RHMC evolves a state in an enlarged position-momentum space under Hamiltonian dynamics, with intermittent momentum randomizations. The randomization times are exponentially spaced, and a parameter controls how much momentum is retained at each jump.
2. RHMC Method.
- The infinitesimal generator combines the Hamiltonian Liouville operator with a rate-λ^-1 momentum-randomization operator.The randomization term averages the change in a test function under the momentum update map Γ.Source: §2 · pp. 6–7
- RHMC evolves the enlarged state Z=(Q,P) along Hamiltonian trajectories, interrupted by instantaneous momentum randomizations at independent exponential times with mean λ.The process is right-continuous with left limits.Source: §2 · pp. 6–7
- The Horowitz angle φ controls momentum retention at a jump: φ=π/2 gives complete randomization, while φ=0 leaves the state unchanged and is excluded because the resulting dynamics are generally non-ergodic.Source: §2 · p. 7
3. Geometric Ergodicity of RHMC.
Under Hypothesis 3.1, this section proves that RHMC has the unique invariant probability measure Π_BG and converges to it geometrically fast in total variation. The proof uses Harris’s theorem, with a Foster–Lyapunov drift condition and minorization on bounded sublevel sets of the Lyapunov function.
3.1. Overview.
- Under Hypothesis 3.1, Harris’s theorem yields that ΠBG is RHMC’s unique invariant probability measure and that RHMC is geometrically ergodic.The proof combines a Foster-Lyapunov drift condition with a minorization condition.Source: §3.1 · pp. 7–8, §3.3 · p. 10, §3.6 · p. 16
3.2. The Measure ΠBG is an Infinitesimally Invariant Measure.
- Under H1, ΠBG is infinitesimally invariant for the RHMC generator, and its Lyapunov function exists despite the absence of explicit dissipation.The section later strengthens infinitesimal invariance to invariance for the RHMC process.Source: §3.2 · pp. 9–10
3.3. Foster-Lyapunov Drift Condition.
- Momentum randomizations supply RHMC’s dissipation, establishing the Foster-Lyapunov drift condition; its rate increases with more frequent or more complete momentum randomization.The drift condition follows under Hypothesis 3.1, with γ = 2c1b for some K > 0.Source: §3.3 · pp. 10–11
3.4. Martingale Problem.
- For globally Lipschitz, continuously differentiable functions, the local martingale in Lemma 3.5 is a martingale, enabling the subsequent invariance proof.The argument uses the Lyapunov function to control the quadratic variation.Source: §3.4 · pp. 12–13
3.5. The Measure ΠBG is an Invariant Measure.
- Combining Proposition 3.1 with the martingale argument proves that ΠBG is an invariant probability measure for RHMC.The proof uses Dynkin’s formula and the fact that both Hamiltonian flow and momentum randomization preserve ΠBG.Source: §3.4 · p. 13, §3.5 · pp. 14, 16
3.6. Minorization Condition.
- For every compact set, RHMC’s transition probabilities satisfy a minorization condition, using momentum randomizations’ weak regularization transferred to positions by the Hamiltonian flow.The process need not have the strong Feller property for this minorization result.Source: §3.6 · pp. 16–17
- For every E > 0, there exist t and ϵ such that the minorization condition holds for states whose Lyapunov function values are below E.This supplies the minorization condition used with the Foster–Lyapunov drift condition in the geometric-ergodicity argument.Source: §3.6 · p. 18
3.7. Main Result: Geometric Ergodicity.
- Under Hypothesis 3.1, the process has the unique invariant probability measure Π_BG and converges to it geometrically fast in total variation.The theorem also asserts the existence of positive constants r and C.Source: §3.7 · p. 19
4. Model Problem.
On an uncorrelated multivariate Gaussian with complete momentum randomization, the paper compares randomized and fixed flow durations. RHMC’s integrated autocorrelation time declines regularly, while HMC’s oscillates; RHMC’s displacement-per-cost has a finite optimum.
4. Model Problem.
- The model comparison uses an uncorrelated multivariate Gaussian target, and assumes complete rather than partial momentum randomization.The target is described as having some components with small variances.Source: §4 · p. 19
4.1. The process.
- For fixed-duration HMC, durations at even multiples of πσ_i leave component i unchanged, while odd multiples reverse its sign; these cases are non-ergodic.Durations near integer multiples may also yield poor performance.Source: §4.1 · p. 20
4.2. Integrated Autocorrelation Time (IAC).
- RHMC’s integrated autocorrelation time decreases monotonically with duration and plateaus at one, unlike HMC’s oscillatory IAC, which can worsen as duration increases.The comparison is for estimating the target mean.Source: §4.2 · p. 21
- At the special non-ergodic durations, the considered estimator can nevertheless be exceptionally accurate in the alternating case, giving zero for an even sample count.For an odd sample count, the reported estimate is q_i(0)/(N + 1), with O(N^-1) error.Source: §4.2 · pp. 21–22
4.3. Mean Squared Displacement (MSD).
- RHMC’s mean-squared displacement increases with duration and then plateaus, while its displacement-per-cost measure peaks and declines beyond an optimal duration.The paper identifies the best duration as approximately the standard deviation of the least constrained variate; longer durations waste computational resources.Source: §4.3 · pp. 22–23
5. Numerical Testing.
Numerical tests compare HMC and RHMC on normal, double-well, and pentane targets, examining integrated autocorrelation and mean-squared displacement as functions of duration.
5.1. Standard Normal Distribution.
- For the standard normal, HMC’s IAC estimates diverge from the formula near λ=π and 3π, while RHMC’s IAC approaches one.Source: §5.1 · p. 23
5.2. Ten-Dimensional Normal Distribution.
- For ten-dimensional normals, RHMC’s MSD varies monotonically and plateaus, whereas HMC’s duration dependence is complex.Source: §5.2 · p. 23
5.3. Two-dimensional Double Well.
- For the two-dimensional double well, the tests compare IAC for 2Q1+Q2 and equilibrium MSD across HMC duration and RHMC mean duration.Source: §5.3 · p. 26
5.4. Fifteen-dimensional Pentane Molecule.
- Pentane has three potentially stable conformation types, each potentially representing multiple modes; its IAC and MSD tests show complex HMC dependence on λ.Source: §5.3 · p. 26, §5.4 · p. 28, Figure 8 · p. 28
6. Outlook.
The outlook proposes two spatially discretized variants of RHMC, then states which properties are established and which remain open. Variant #1 has a small-step drift result but does not preserve the exact invariant measure, while Variant #2 preserves infinitesimal invariance under integrator conditions but has only a geometric-ergodicity conjecture.
6. Outlook.
- The article’s main analysis assumes exact integration; long-leg global error bounds for the discretized alternative are outside its scope.That alternative uses a volume-preserving, reversible integrator, geometrically distributed step counts, and an accept-reject correction.Source: §6 · p. 30
- Both variants approximate RHMC without the exact Hamiltonian flow, using numerical integrators to approximate gradients.The authors do not compare their efficiency with standard HMC or related techniques.Source: §6 · p. 30
6.1. Variant #1.
- For sufficiently small h, Variant #1 satisfies a drift condition when the potential and integrator meet the stated hypotheses.The authors say those potential assumptions constrain target tails to be no lighter or heavier than Gaussian and may be relaxable.Source: §6.1 · p. 33
- Variant #1’s numerical integrator does not preserve the Hamiltonian exactly, so its invariant measure is not the invariant measure of the exact RHMC generator.The discrepancy is attributed to discretization error.Source: §6.1 · p. 33
6.2. Variant #2.
- Variant #2 adds momentum-flip jumps and, with a reversible, volume-preserving integrator, has the same infinitesimally invariant measure as exact RHMC.Its weights are chosen to ensure this property.Source: §6.2 · p. 34
- Geometric ergodicity of Variant #2 is conjectured, not proved; the needed analysis must control jump rates where high energy yields large integration errors.The authors defer that analysis to future work.Source: §6.2 · p. 35
7. Conclusion.
RHMC randomizes Hamiltonian-flow durations with independent exponential draws. The paper relates its stability to underdamped Langevin dynamics, reports regular sampling-metric behavior as mean duration varies, and outlines generator-based approximations.
7. Conclusion.
- RHMC draws independent exponentially distributed durations for its Hamiltonian flows, giving a generator that combines momentum randomization and the Liouville operator.The Liouville operator is differential.Source: §7 · pp. 35–36
- Under standard potential-energy hypotheses, RHMC has a stochastic Lyapunov function of the same form as underdamped Langevin dynamics, with momentum randomizations providing dissipation.The analysis required an alternative to standard approximate controllability arguments because RHMC trajectories have instantaneous momentum randomizations and are discontinuous.Source: §7 · p. 36
- In the Gaussian test problem, RHMC sampling metrics depend monotonically on mean duration, unlike classical HMC metrics, which vary more complicatedly with deterministic duration.The monotonicity also appears in numerical examples with more general targets.Source: §7 · p. 36
- The paper considers two approximations based on spatially discretizing RHMC’s infinitesimal generator and shows how to construct them to preserve the Boltzmann-Gibbs distribution.A complete analysis of these approximations is left for future work.Source: §7 · p. 36
APPENDIX A: HARRIS THEOREM
The appendix states Harris’ theorem for continuous-time Markov processes and recalls conditions sufficient for its application. A Foster-Lyapunov drift condition and a small-set condition yield a unique invariant probability measure and geometric ergodicity.
APPENDIX A: HARRIS THEOREM
- The infinitesimal generator is defined through a local-martingale condition: for suitable F, LF is the function G making the stated process a local martingale.The definition is for a Markov process on a Polish state space.Source: Appendix A · p. 37
- Harris’ theorem’s sufficient hypotheses combine a Foster-Lyapunov drift condition with a small-set condition on a sublevel set.The small-set condition applies to a sublevel set specified using the drift constants.Source: Appendix A · pp. 37–38
- Under those hypotheses, the process has a unique invariant probability measure and is geometrically ergodic.The theorem states that its positive rate and bound depend on constants in the assumptions.Source: Appendix A · p. 38