Source-linked AI summary
On the Geometric Ergodicity of Hamiltonian Monte Carlo
Samuel Livingstone, Michael Betancourt, Simon Byrne, Mark Girolami
TL;DR
Rigorous conditions for geometric ergodicity of HMC are comparatively limited despite the method’s empirical success. This paper analyzes implementations with fixed and position-dependent integration times. Fixed times yield conditions essentially matching MALA’s, while position-dependent times permit geometric convergence for a broader class of targets.
Problem
Despite HMC’s empirical success, comparatively few rigorous results establish when its Markov chains converge geometrically.
Source: §1 · pp. 1–2Method
The paper derives conditions for geometric ergodicity under both position-independent and position-dependent HMC integration times.
Source: §1 · p. 3Results
With position-independent integration time, geometric ergodicity essentially occurs under the same tail scenarios as for MALA, while position-dependent times allow it for a much broader class of targets.
Source: §1 · p. 3Takeaways & Limitations
The idealized position-dependent-time results offer practical guidelines for choosing integration time and assessing common heuristics.
Source: §1 · p. 3The fixed-integration-time results specifically concern leapfrog HMC, though the approach may extend to other explicit symplectic integrators.
Source: §7.2 · p. 24
Abstract
from arXiv · showhide
We establish general conditions under which Markov chains produced by the Hamiltonian Monte Carlo method will and will not be geometrically ergodic. We consider implementations with both position-independent and position-dependent integration times. In the former case we find that the conditions for geometric ergodicity are essentially a gradient of the log-density which asymptotically points towards the centre of the space and grows no faster than linearly. In an idealised scenario in which the integration time is allowed to change in different regions of the space, we show that geometric ergodicity can be recovered for a much broader class of tail behaviours, leading to some guidelines for the choice of this free parameter in practice.
1. Introduction
The introduction motivates rigorous study of HMC's convergence, outlines how the method constructs proposals, and previews conditions for geometric ergodicity with fixed and position-dependent integration times. It situates the analysis among prior HMC theory and related work, then establishes notation for the paper.
1. Introduction
- HMC has shown empirical success, but comparatively few rigorous results justify its performance, motivating analysis of when its chains converge geometrically.The paper frames this question in settings such as high-dimensional posterior computation.Source: §1 · pp. 1–2
- HMC augments position with momentum, approximates Hamiltonian flow for an integration time, and uses the resulting position as a proposal.With position-independent momentum, leapfrog steps commonly set the integration time; taking one step reduces HMC to MALA.Source: §1 · pp. 2–3
- The paper establishes when common HMC implementations are or are not geometrically ergodic, with position-dependent integration times extending geometric convergence to broader target tails.For position-independent times, the conditions are essentially those for MALA; the paper also offers practical guidelines for choosing integration time.Source: §1 · pp. 2–3
1.1. Literature review
- The review distinguishes convergence-to-equilibrium theory from asymptotic-variance analyses and notes that infinite-dimensional HMC is outside this paper’s scope.Dimension-scaling behavior and tuning of expected squared jump distance are among the related performance questions discussed.Source: §1.1 · pp. 3–4
- Prior work studied geometric ergodicity for continuous-time HMC under exact integration and Gaussian-or-faster tails; this paper instead relates HMC to overdamped Langevin dynamics.Earlier work also established irreducibility under bounded-potential conditions and considered stochastic integration times.Source: §1.1 · pp. 3–4
1.2. Notation
- The paper restricts its setting to X = R^d and defines notation for target measures, transition kernels, invariance, and convergence in total variation.It notes that the convergence results can equivalently be established under the V-norm distance.Source: §1.2 · p. 4
2. Overview of Main Results
For position-independent integration times, the paper establishes geometric-ergodicity results and identifies tail regimes where it fails. An idealised position-dependent integration time extends geometric ergodicity to every tail parameter in the stated one-dimensional family, subject to an exact-flow caveat for β>2.
Position-independent integration time
- Under A1–A3, the paper states a sufficient condition for geometric ergodicity; A2 restricts tails to lighter than Laplacian but no lighter than Gaussian.A1 adds randomness to integration time, while A3 constrains the acceptance rate.Source: §2 · p. 5
Non-geometric cases
- HMC is not geometrically ergodic when the gradient of U is bounded and Eπ[e^{s∥x∥}] is infinite for every s > 0.The paper associates this condition with heavy tails, where Hamiltonian flow can be slow.Source: §2 · p. 5
Position-independent integration time
- For E(β, α) under A1, HMC is geometrically ergodic for 1 ≤ β ≤ 2, but not for β < 1 or β > 2.The β=2 case requires sufficiently small ε.Source: §2 · p. 5
- With position-independent integration time, HMC's geometric-ergodicity boundaries essentially match MALA's; extra leapfrog steps may improve speed but do not change those boundaries.The section frames this as the methods essentially coinciding in presence or absence of geometric ergodicity.Source: §2 · pp. 4, 6
Position-dependent integration time
- For the idealised one-dimensional position-dependent scheme, geometric ergodicity holds for every β > 0.The positive result for β > 2 relies on exact Hamiltonian flow and would disappear with a typical explicit numerical solver.Source: §2 · p. 6
- For β < 1, the idealised position-dependent-time findings suggest an advantage in the presence of heavy tails.The paper presents this as a suggestion, while noting the exact-flow assumption behind the β > 2 result.Source: §2 · p. 6
3. Preliminaries
The preliminaries set out drift-based and proposal-based tools for assessing geometric ergodicity. They also give criteria for establishing irreducibility and aperiodicity or ruling out geometric rates.
Drift criterion
- A Lyapunov drift inequality on a set with small level sets is presented as a criterion for geometric ergodicity.The stated drift form is PV(x) ≤ λV(x) + b1_Cω(x), with λ < 1 and finite b, ω.Source: §3 · p. 6
Metropolis–Hastings conditions
- If the stated density and proposal lower-bound conditions hold, the Metropolis–Hastings chain is π-irreducible and aperiodic, and compact sets are small.A set is small when some fixed-time transition kernel dominates a positive multiple of a measure on that set.Source: §3 · pp. 6–7
Non-geometric criteria
- For Metropolis–Hastings proposals, an essential supremum rejection probability of 1 rules out geometric ergodicity.The section also gives a necessary exponential-moment condition under a local-concentration condition on the proposal kernel.Source: §3 · p. 7
4. Hamiltonian Monte Carlo
Hamiltonian Monte Carlo augments positions with momenta and uses energy-preserving Hamiltonian flow to propose moves. The marginal-chain view makes explicit how the leapfrog proposal relates to MALA and why multiple steps add nonlinear terms.
4. Hamiltonian Monte Carlo
- Hamiltonian flow evolves position and momentum while preserving the Hamiltonian; leapfrog approximates this flow, and Metropolis–Hastings corrects the approximate proposal.The method draws momentum, advances for a chosen integration time, and accepts or rejects the resulting proposal.Source: §4 · pp. 7–8
4.1. The marginal chain
- In the marginal-chain representation, one leapfrog step gives the MALA proposal, while additional steps introduce nonlinear terms depending on the initial position and momentum.The candidate map is parameterized by the momentum, number of leapfrog steps, and step size.Source: §4.1 · pp. 8–9
5. Results for an position-independent integration time
This section examines geometric ergodicity for HMC with position-independent integration times, giving sufficient conditions and explaining the roles of inward proposals and acceptance behavior. It also identifies cases where geometric ergodicity fails, including faster-than-linear gradients and heavy tails with insufficient inward drift.
5.1. 𝝅-irreducibility
- A1 requires P𝔏[L=1] > 0 and a finite exponential moment; under A1, existing MALA results establish HMC’s π-irreducibility and ergodicity.A bounded maximum number of leapfrog steps is one sufficient way to meet the moment condition under the next subsection’s potential assumptions.Source: §5.1 · p. 9
5.2.1. Requirements for (12) to be satisfied.
- The sufficient conditions make the gradient asymptotically point inward and grow sublinearly, letting local information at the current point control global HMC moves.The Gaussian-tail boundary case is also covered under (SC1.1)–(SC1.2) when the step size is sufficiently small.Source: §5.2.1 · pp. 12, 15
5.2.2. Discussion of (13).
- The inwards-acceptance condition requires inward proposals to satisfy an asymptotic acceptance constraint; it limits tail oscillation that could otherwise undermine the geometric bound.For the exponential-family class, the paper gives a sufficient trapezium-estimate argument when 1 ≤ β < 4/3.Source: §5.2.2 · pp. 16–17
5.2. Geometric ergodicity
- A1–A3 together suffice for a geometric bound, with A2 imposing potential conditions and A3 requiring the inwards-acceptance property.A2 allows either (SC1.1)–(SC1.3), or (SC1.1)–(SC1.3b) with a sufficiently small step size.Source: §5.2.1 · p. 15, §5.2.2 · p. 17
5.2.2. Discussion of (13).
- For exponential-family tails with 1 < β < 2, inward proposals occur with probability tending to one and are accepted with probability tending to one; the β = 1 case is also geometrically ergodic.For β = 1, the proposal has an inward drift and acceptance tends to one when the zero boundary is not crossed.Source: §5.2.2 · pp. 17–18
- For (13), the coefficient is positive when (1 + 2α − α^2ε^2) sin^2(θL) > 0; for sufficiently small ε, this gives A3, and A2 completes the result.Source: §5.2.2 · p. 18
5.3.1. Light tails
- Under (17)–(19), fixed-time HMC is not geometrically ergodic: trajectories expand at least 2^L in norm, driving acceptance to zero for sublinear momentum.The conditions (18) and (19) limit tail oscillations; the acceptance result applies when ||p0|| ≤ ||x0||^δ for δ < 1.Source: §5.3.1 · pp. 18, 20
5.3.2. Heavy tails
- With bounded gradients, geometric ergodicity requires ∫e^(s||x||)π(dx) < ∞ for some s > 0; failure persists with exact integration because it is a property of the flow.When the gradient vanishes at infinity, insufficient inward drift can produce random-walk behaviour and slow convergence.Source: §5.3.2 · p. 21
6. Results for an position-dependent integration time
This section studies an idealised HMC scheme whose integration time depends on position, using longer integration to strengthen the drift in the tails. For the one-dimensional Exponential Family class, the resulting chain is geometrically ergodic for every β > 0 under the stated exact-flow assumptions.
6. Results for an position-dependent integration time
- When fixed-time DRIFT becomes negligible in the tails, increasing integration time can increase its magnitude.This motivates the position-dependent integration-time scheme considered here.Source: §6 · p. 22
- At each iteration, the scheme resamples standard Gaussian momentum and flows for a uniform time between zero and the current contour’s period.The contour is a single closed path, and the period is assumed known.Source: §6 · p. 22
- The section introduces the microcanonical expectation and invokes the Virial Theorem to relate kinetic and potential energies in its analysis.The expectation is defined along a Hamiltonian trajectory initialized at (x0, p0).Source: §6 · p. 22
- For the one-dimensional Exponential Family density class, dynamic HMC is geometrically ergodic for every β > 0.The theorem assumes the specified idealised setting with an exact integrator and known flow period.Source: §6 · pp. 22–23
- The proof establishes a drift inequality outside a sufficiently large region, yielding geometric ergodicity.It selects η < β/2 so that λ < 1 in the Lyapunov-function bound.Source: §6 · p. 23
7. Discussion
The discussion outlines implementation constraints and extensions, then gives guidance for interpreting geometric-ergodicity results and choosing HMC settings. Its practitioner advice focuses on how tail-gradient behavior relates to integration-step and integration-time choices.
7.1. Dynamic implementations
- Without an exact integrator, position-dependent integration time typically requires acceptance-probability adjustments to preserve π because the approximate flow may not be reversible.Changing L increases computation per transition; the No-U-Turn sampler uses a binary tree to preserve detailed balance when L varies.Source: §7.1 · p. 24
7.2. Extension to other integrators
- The fixed-integration-time results apply specifically to leapfrog, while implicit methods complicate the composition argument but can resolve stiffness.The authors suggest the approach may extend to other explicit symplectic integrators.Source: §7.2 · p. 24
- For the one-dimensional Exponential Family, a Hessian-based Riemannian metric is mathematically equivalent to a stated transformation that produces Gaussian tails for any β > 0.The discussion says this suggests a well-behaved sampler can be constructed.Source: §7.2 · p. 24
7.3. Honest bounds
- Geometric ergodicity gives a qualitative bound without an explicit rate; quantitative bounds are often too conservative for practical use.The cited curvature-based bounds require positive curvature in a Wasserstein distance, which in total variation is stronger than geometric ergodicity.Source: §7.3 · pp. 24–25
- The paper leaves open whether the small-step strategy shown for superlinear-tail MALA can yield similar results for HMC.It says this HMC analysis is likely possible but leaves it for future work.Source: §7.3 · p. 25
7.4. Practitioner guidelines
- For gradients that grow very rapidly or become negligible in the tails, chains may struggle to explore those tails; the paper recommends small ε for the former and sufficiently large T for the latter.It also recommends reparameterisation when available and notes corresponding Stan diagnostics: divergences and maximum tree depth warnings.Source: §7.4 · p. 25
Appendix A: Examples of 𝝅-irreducibility
The appendices give an HMC example that is not π-irreducible and connect momentum-refreshment regimes to Langevin dynamics. They also illustrate the Gaussian example’s energy contour and its projection onto position space.
Appendix A: Examples of 𝝅-irreducibility
- With a Gaussian target and L = 2, the example’s proposal kernel leaves the state unchanged, so the chain is not π-irreducible.The stated exception is the degenerate target concentrated at that point.Source: Appendix A · p. 27
- The Gaussian example’s phase-space contour is a radius-3 circle, whose projection onto position space is [−3, 3].The diagram is offered as intuition for the idealised HMC π-irreducibility argument.Source: Figure 1 · p. 28, Appendix A · p. 28
Appendix B: Connections between HMC and Langevin dynamics
- Short intervals between momentum refreshment make HMC dynamics close to an overdamped Langevin diffusion.This approximation is stated for suitably regular ∇U and small δt.Source: Appendix B · p. 28
- Longer intervals relate instead to underdamped Langevin dynamics, whose continuous OU momentum noise is connected to partial momentum refreshment in generalized HMC.The stated correspondence uses ξ := e^(−γt).Source: Appendix B · p. 29
Appendix C: Proof of inwards convergence for the Exponential family model class
The appendix provides a detailed proof case for the Exponential Family potential U(x) = α|x|^β when β lies between 1 and 2. Its calculation establishes the stated inwards-convergence result at both tails.
Appendix C: Proof of inwards convergence for the Exponential family model class
- The verbose proof treats β ∈ (1, 2) and U(x) = α|x|^β for α > 0.Source: Appendix C · p. 29
- The proof precedes its main result with a technical lemma and a direct calculation.Source: Appendix C · p. 29
- A positive L²/8 term completes the argument as x0 → ∞, with an analogous argument for x0 → −∞.Source: Appendix C · p. 31
Appendix D: Corrigendum related to Theorem 5.14 and Corollary 2.3
The corrigendum corrects a consequential typographical error in Theorem 5.14’s condition (18), provides replacement proofs, and preserves Corollary 2.3 as stated.
Appendix D: Corrigendum related to Theorem 5.14 and Corollary 2.3
- The corrigendum corrects condition (18) in Theorem 5.14 and supplies replacement proofs of Lemmas 5.15–5.17 and Theorem 5.14.For the exponential family E(β, α), the corrected condition holds for every β > 2, so Corollary 2.3 remains valid as stated.Source: Appendix D · p. 31
1. Details of the typographical error and correction
The printed condition (18) used a distance multiplier that left a gap in the β > 2 case of Corollary 2.3(ii). The corrigendum raises that multiplier from 2 to 3 and supplies replacement proofs for a separate proof-only error.
1. Details of the typographical error and correction
- For E(β, α), the printed condition’s distance multiplier of 2 guarantees the gradient bound only when β ≥ 1 + log(3)/log(2), leaving a gap for 2 < β < 1 + log(3)/log(2).The original condition required ∥y∥ ≥ 2∥x∥ ≥ C and ∥∇U(y)∥ ≥ 3∥∇U(x)∥.Source: §1 · pp. 31–32
- Condition (18) should use ∥y∥ ≥ 3∥x∥ ≥ C instead of the printed distance multiplier of 2.The conclusion of Theorem 5.14 remains unchanged.Source: §1 · p. 32
- The replacement proofs show that Lemma 5.16 requires condition (17) alone, despite the printed proof invoking condition (18).This separate typographical error is described as inconsequential.Source: §1 · p. 32
2. Replacement proofs
The replacement proof derives vanishing acceptance from the corrected conditions, establishing non-geometric ergodicity for fixed integration time and for a position-independent distribution over leapfrog-step counts.
2. Replacement proofs
- Eliminating the intermediate half-step momentum yields an exact recurrence for successive leapfrog position updates.This recurrence is part of the replacement proof’s control of the trajectory.Source: §2 · p. 32
- The corrected growth argument makes the acceptance probability tend to zero uniformly over initial momenta with ∥p₀∥ ≤ ∥x₀∥^δ.The proof uses the corrected condition (18) and the outward growth bound on leapfrog positions.Source: §2 · p. 34
- Under conditions (17), (18), and (19), HMC with any fixed integration time T > 0 does not produce a geometrically ergodic Markov chain.The proof shows the rejection probability tends to 1 as ∥x₀∥ grows, which implies non-geometric ergodicity.Source: §2 · pp. 34–35
- The non-geometric-ergodicity conclusion also holds when the number of leapfrog steps is drawn from a position-independent distribution.Conditioning on each fixed step count gives acceptance tending to zero; dominated convergence then gives the same limit unconditionally.Source: §2 · p. 35
3. Correction to Corollary 2.3
The corrected condition verifies the β > 2 case of Corollary 2.3(ii): HMC is not geometrically ergodic for every β > 2 under Assumption A1. The other stated parts of Corollary 2.3 remain unaffected.
3. Correction to Corollary 2.3
- For the exponential family E(β, α), HMC does not produce a geometrically ergodic Markov chain for every β > 2 under Assumption A1.The corrected condition (18) holds for every β > 2, and the result extends from each fixed leapfrog-step count by dominated convergence over the position-independent distribution.Source: §3 · p. 35
- The β < 1 part of Corollary 2.3(ii) and all parts of Corollary 2.3(i) are unaffected by the correction.No other changes to the results of are required.Source: §3 · p. 35