Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients

1. Introduction

• MCMC is widely used for sampling high-dimensional distributions, and HMC is a popular choice for smooth densities and a default in several software packages.The paper uses HMC to mean the leapfrog-integrator algorithm with Metropolis-Hastings correction.Source: §1 · pp. 1–2

1.1 Past work on HMC

• Earlier HMC analyses studied unadjusted or ODE-based variants, while existing bounds for Metropolized HMC did not establish faster mixing than MALA.Unadjusted methods can retain bias and have mixing-time bounds polynomial in 1/ϵ, unlike the logarithmic dependence typical of Metropolis-corrected methods.Source: §1.1 · pp. 2–3

1.2 Past work on mixing time dependency on initialization

• Prior work had adapted average conductance to continuous-state chains for the Ball walk, while discrete-state methods offered other approaches to reducing dependence on initialization.These approaches include log-Sobolev inequalities, evolving sets, and spectral profiles.Source: §1.2 · pp. 3–4

1.3 Our contributions

• A conductance-profile framework gives quantitative convergence guarantees for continuous-state chains and improves MRW and MALA bounds when the start is not warm.The framework is also used to establish HMC bounds.Source: §1.3 · p. 4
• With suitable step size and leapfrog-step choices, Metropolized HMC has smaller mixing-time bounds than the best known MALA bounds for log-concave distributions.The analysis concerns the leapfrog-integrator version used in practice and provides explicit hyperparameter choices.Source: §1.3 · p. 5, Table 1 · p. 5

2.1 Monte Carlo Markov chain methods

• MCMC constructs a chain with an accessible initial distribution and target stationary distribution, then asks how many steps are needed to approach that target.The sampling problem is difficult when the density is complicated and dimension is large, making direct independent sampling challenging.Source: §2.1 · p. 7

2.2 Markov chain basics

• The section defines mixing time through distributional distances and introduces warm starts and lazy chains as assumptions or settings for convergence analysis.For p=1, the defined Lp-divergence is twice total variation distance.Source: §2.2 · pp. 8–9

2.3.1 MRW and MALA algorithms

• MRW proposes a Gaussian random-walk move using function values, whereas MALA uses the gradient to shift its Gaussian proposal.The MALA proposal is an Euler-Maruyama discretization of the Langevin SDE.Source: §2.3.1 · p. 9

2.3.2 HMC sampling

• Metropolized leapfrog HMC approximates Hamiltonian dynamics for K steps and applies a Metropolis correction; K=1 is MALA after step-size reparameterization, and the analysis sets M=I.The method refreshes momentum from a standard normal distribution before the leapfrog updates.Source: §2.3.2 · pp. 10–11

3.1 Assumptions on the target distribution

• Assumption (A) requires smooth gradient and Hessian, plus a convex high-mass set with isoperimetry, and is strictly weaker than strong log-concavity in Assumption (B).Assumption (B) requires a smooth, strongly convex negative log density with Lipschitz Hessian.Source: Assumptions on the target distribution · pp. 12–13

3.2 Mixing time bounds for HMC

• For regular targets and β-warm starts, HMC has mixing bounds with warmness dependence O(log log β) under log-isoperimetry and O(log β) under isoperimetry.The theorem requires ϵ^2 ≥ 3βs; its targets have Lipschitz gradient and Hessian and a convex set containing mass 1 − s.Source: §3.2 · p. 13

3.2.1 Strongly log-concave target

• For well-conditioned strongly log-concave targets, the stated warm-start comparison gives HMC a better gradient-evaluation upper bound than MALA.The comparison assumes constant β and κ ≪ d; the cited passage summarizes rates with logarithmic terms hidden.Source: §3.2.1 · p. 15, Table 2 · p. 15
• From feasible start μ† = N(x⋆, 1/L I_d), HMC with K = κ^(3/4) uses κ^(1/4) fewer gradient evaluations than MALA when κ ≪ d^(1/2).The comparison hides logarithmic factors in ϵ, d, and κ, and assumes L_H = O(L^(3/2)).Source: §3.2.1 · pp. 15–16, Table 3 · p. 16

3.3 Mixing time bounds via conductance profile

• The paper extends conductance-profile methods to continuous-state chains, sharpening initialization dependence by using restricted rather than worst-case conductance.The restricted profile allows poor conductance in regions with very small target probability without treating it as decisive for mixing up to a suitable tolerance.Source: §3.3 · pp. 17–18
• For a convex set satisfying isoperimetry, Lemma 4 lower-bounds restricted conductance when nearby points have locally overlapping transition distributions.The local condition is dTV(Tx, Ty) ≤ 1 − ω for points within distance Δ; log-isoperimetry adds a logarithmic term.Source: §3.3 · p. 19

3.4 Improved warmness dependency for MALA and MRW

• For exponentially dimension-dependent warmness β, the sharper dependence yields an O(d log d) gain in mixing-time bounds for MALA and MRW.The section then states sharper bounds for both algorithms from the feasible start μ† = N(x⋆, 1/L I_d).Source: §3.4 · p. 20
• Theorem 5 assumes an L-smooth, m-strongly convex negative log-density and initializes both 1/2-lazy chains from µ† = N(x*, 1/L Id).The step sizes are specified in Theorem 5, but their expressions are incomplete in the supplied passages.Source: §3.4 · p. 20
• eO(dκ log (1/ϵ)) for MALA and eO(dκ^2 log (1/ϵ)) for MRW improve prior eO(d^2κ log (1/ϵ)) and eO(d^2κ^2 log (1/ϵ)) bounds, respectively.The bounds apply to mixing within ϵ total-variation distance and are smaller by a factor of d log d than the prior bounds.Source: §3.4 · pp. 20–21
• A lower bound on the mixing time of MALA and MRW remains an open question.Source: §3.4 · p. 21

4. Numerical experiments

• The experiments used Gaussian targets and compared theory-based HMC tuning with larger-step, more-leapfrog HMCagg settings; 100 independent runs and 10 repeats informed the reported averages.MALA and MRW settings followed Dwivedi et al. (2019).Source: §4 · pp. 21–22
• Convergence was measured by the least-favorable-direction 75% quantile relative error, with quantile mixing time set at the first iteration below δ=0.04.The comparison counted total function and gradient evaluations; HMC uses K gradient evaluations per outer-loop iteration.Source: §4 · p. 21
• For fixed κ=4, evaluation-count slopes were 0.80(±0.12) for HMC, 0.58(±0.15) for HMCagg, 0.93(±0.13) for MALA, and 0.96(±0.10) for MRW.The corresponding theoretical slopes were 0.92, 0.63, 1.0, and 1.0, respectively.Source: §4 · p. 22
• For κ=d^2/3, evaluation-count slopes were 1.60(±0.09) for HMC, 1.34(±0.17) for HMCagg, 1.64(±0.11) for MALA, and 2.25(±0.08) for MRW.The corresponding theoretical exponents were 1.58, 1.46, 1.67, and 2.33, respectively.Source: §4 · p. 22
• HMCagg’s aggressive tuning is well-informed only when the Hessian-Lipschitz constant L_H is small, as it is for the Gaussian targets used.For general logconcave targets, the paper recommends the more general choices in Corollary 14.Source: §4 · p. 22

5. Proofs

• HMC’s total function and gradient evaluations have smaller dimension dependence than MALA or MRW, and HMCagg uses fewer evaluations with larger step sizes and more leapfrog steps.The comparison is for Gaussian targets with condition number either constant at 4 or scaling with dimension; the HMCagg comparison is at the same quantile mixing.Source: Figure 2 · p. 23, §5 · p. 23

5.1 Overlap bounds for HMC

• Lemma 6 bounds overlap between proposals from nearby points and controls accept-reject distortion when the gradient is bounded, enabling conductance-profile analysis under its stated conditions.The bounds are used with Lemma 4 to prove Theorem 1.Source: §5.1 · pp. 23–24

5.2 Proof of Theorem 1

• Theorem 1 follows by combining Lemma 4 and Lemma 6 to lower-bound the truncated HMC conductance profile, then applying Lemma 3 on a high-probability convex set.The proof uses the set R_s with target mass at least 1 − s, where s = ϵ^2/(3β^2).Source: §5.2 · pp. 24–25

5.3.1 Properties of the HMC proposal

• The proof develops forward and inverse leapfrog proposal maps and bounds their Jacobians, establishing tools used to control distances between HMC proposals.The forward map depends on the gradient, leapfrog-step count, and step size; the inverse is defined when K^2η^2 ≤ 1/(4L).Source: §5.3.1 · p. 26

5.3.2 Proof of claim (27a) in Lemma 6

• For nearby starting points, the proof bounds proposal-distribution distance by expressing densities through a change of variables, applying Pinsker’s inequality, and bounding the resulting KL divergence.The argument uses properties of the forward map and its Jacobian, with the result applying under the stated smoothness and step-size conditions.Source: §5.3.2 · pp. 28–29

5.3.3 Proof of claim (27b) in Lemma 6

• For claim (27b), the proof compares the proposal with the post-accept-reject transition by analyzing the probability of staying at the current state and applying Markov’s inequality.The comparison excludes the lazy step.Source: §5.3.3 · p. 31
• Taylor expansion at closer points and cancellation of gradient terms yield bounds on the energy difference and residual in terms of momentum and gradient norms.The proof then uses smoothness to bound those quantities.Source: §5.3.3 · pp. 32–33
• A bounded-gradient assumption and chi-squared tail bounds control the Gaussian momentum norm, leading to a lower bound under the step-size condition, with an absolute constant c ≤ 2000.The proof uses this bound to control the acceptance ratio and then derives a total-variation bound.Source: §5.3.3 · p. 33

6. Discussion

• Appropriate step-size and leapfrog-step choices yield Metropolized HMC mixing-time bounds smaller than the best known MALA bounds for log-concave sampling.The authors describe this improvement as the benefit of using multi-step gradients.Source: §6 · p. 34
• Open questions include whether the HMC bounds are tight and whether warmness dependence can be improved to yield sublinear dimension dependence from generic initialization.The latter question is posed even for small condition number κ.Source: §6 · p. 34
• The paper improves warmness dependence in previously proved mixing rates for Metropolized random walk and Langevin algorithms.The technique is inspired by methods for improving warmness dependence in discrete-state Markov chains.Source: §6 · p. 34
• Theorem 1 can apply to general targets, including nearly log-concave distributions, although the paper focuses on strongly and weakly log-concave targets.The paper leaves explicit HMC mixing-time bounds for more general targets as an open direction.Source: §6 · p. 34

Appendix A. Proof of Lemmas 3, 4 and 6

• Appendix A collects the proofs of Lemmas 3 and 4, previously stated in Section 3.3.These lemmas are used in proving Theorem 1.Source: Appendix A · p. 35
• The appendix also provides proofs of auxiliary results concerning the HMC proposal.Those results were used in the proof of Lemma 6.Source: Appendix A · p. 35
• The stated scope of Appendix A includes the proof work supporting Theorem 1 and Lemma 6.Theorem 1 uses Lemmas 3 and 4; Lemma 6 uses the auxiliary HMC-proposal results.Source: Appendix A · p. 35

A.1 Proof of Lemma 3

• The proof adapts the spectral-profile technique to continuous state spaces and relates conductance profiles to spectral profiles.The relationship is used to prove Lemma 3.Source: §A.1 · pp. 35–36
• For a smooth chain, the transition operator maps a probability measure to another, and a distribution with a density retains a density after transition.The notation T_x denotes the transition distribution at x, namely T(δ_x).Source: §A.1 · p. 35
• The proof defines the Dirichlet form, expectation, variance, and an Ω-restricted spectral gap to set up its spectral-profile argument.The Ω-restricted profile agrees with the standard definition when Ω is the full state space X.Source: §A.1 · pp. 35–36
• Lemma 11 states an L2-mixing-time bound for a reversible, irreducible, ζ-lazy chain satisfying the smooth-chain assumption, given a β-warm start and a set Ω with sufficiently high stationary mass.The bound is stated for an error tolerance ε in (0, 1).Source: §A.1 · p. 36
• Lemma 12 relates a Markov chain’s Ω-restricted spectral profile to its Ω-restricted conductance profile.Lemma 3 follows from Lemmas 11 and 12 and the definition of the restricted conductance profile.Source: §A.1 · p. 36

A.1.1 Proof of Lemma 11

• Lemma 13 lower bounds the Dirichlet form through the Ω-restricted spectral profile under an L2 mass condition on g.Its proof extends a finite-state result of Goel et al. (2006) to continuous-state Markov chains.Source: §A.1.1 · pp. 36–37
• The density ratio hµ0,n has target expectation one, and its variance J(n) tracks the squared L2 distance between the chain distribution and the target.The proof also defines a restricted variance on Ω and reduces the mixing bound to controlling J for sets with sufficiently high target probability.Source: §A.1.1 · p. 37
• A three-step argument establishes variance existence and relates restricted variance to total variance, derives a Dirichlet-form recurrence, then integrates an extended variance bound to reach the target threshold.The proof uses a piecewise-linear extension of J to real indices in its final step.Source: §A.1.1 · pp. 37, 40
• The argument uses reversibility, stationarity, and ζ-laziness to relate the two-step chain’s Dirichlet form to the original chain’s form.The proof also establishes the Dirichlet-form identity for any transition kernel with stationary distribution Π∗.Source: §A.1.1 · pp. 38–40

A.1.2 Proof of Lemma 12

• Lemma 12’s proof reduces general functions to indicator functions via a co-area argument, then uses restricted conductance to handle continuous-state transitions in two cases.The resulting bound uses conductance flow across level sets and the non-increasing conductance and spectral profiles.Source: §A.1.2 · pp. 42–44

A.2 Proof of Lemma 4

• Lemma 4’s conductance-based proof splits into two exhaustive cases; when the relevant sets are far apart, it invokes the logarithmic isoperimetric inequality.The proof combines the bounds from both cases to obtain the claim.Source: §A.2 · pp. 45–47

A.3 Proofs related to Lemma 6

• The appendix introduces tensor notation and presents proofs of HMC-chain intermediate results—Lemmas 7, 8, 9, and 10—used in Lemma 6.The notation defines multilinear tensor operations and their vector and matrix forms.Source: §A.3 · p. 47

A.3.1 Proof of Lemma 7

• Under K^2η^2 ≤ 1/(4L), the proof of Lemma 7 uses induction to represent the mapping Jacobian with a correction matrix whose spectral norm is at most 1/8.The base cases and inductive step establish the bound for each iterate, yielding the stated result at k = K.Source: §A.3.1 · pp. 47–49

A.3.2 Proof of Lemma 8

• Lemma 8’s proof inductively bounds the derivative of the forward mapping composed with its backward mapping using correction matrices A_k and B_k, then bounds the backward-map derivative by 4/(3Kη).The intermediate bounds are ||A_k||₂ ≤ 1/6 and ||B_k||₂ ≤ 1/8.Source: §A.3.2 · pp. 49–50

A.3.3 Proof of Lemma 9

• The supplied portion of Lemma 9’s proof differentiates the mapping again and begins an induction to bound its second derivatives, with the induction steps omitted for the earlier auxiliary bound.The passage ends during the inductive step, before stating the completed bound.Source: §A.3.3 · pp. 51–52
• The Lemma 9 proof completes an induction, using multilinearity to incorporate coefficients into the tensor and applying Lemma 8 and equation (106) in its bounds.The passage then identifies k = K as a particular case and concludes the proof.Source: §A.3.3 · pp. 52–53

A.3.4 Proof of Lemma 10

• The Lemma 10 proof establishes equation (34b) by induction and obtains equation (34a) by summing k terms, using triangle inequality, L-smoothness, and K^2η^2 ≤ 1/(4L).It verifies the base case k = 0 and uses the induction hypothesis for the step from k to k + 1.Source: §A.3.4 · pp. 53–54

Appendix B. Proof of Corollary 2

• The proof obtains the two parts of Corollary 2 by choosing different initial distributions and hyperparameters in the general corollary.The proof discusses optimal step-size and leapfrog-step choices in Appendix D.1.Source: Appendix B · pp. 54–55
• Corollary 14 gives mixing-time bounds for 1/2-lazy HMC on strongly log-concave targets with a specified Gaussian initial distribution and step-size and leapfrog-step conditions.The corollary is obtained by applying Theorem 1 with choices determined by the strong-convexity parameter.Source: Appendix B · pp. 54–55

B.1 Proof of Lemma 15

• Lemma 15 places strongly log-concave targets in the general-target class used by the corollary, using the set Rs and bounds associated with that domain.The proof notes that Π∗(Rs) ≥ 1 − s and that the gradient bound follows from the bounded domain.Source: Appendix B · p. 54, §B.1 · p. 55
• The proof extends a logarithmic isoperimetric inequality to strongly log-concave distributions on Rd and provides explicit constants.It applies the inequality to the distribution restricted to Ω.Source: §B.1 · p. 55

B.2 Proof of Lemma 16

• The paper relates its proof route to localization results and logarithmic Cheeger inequalities from earlier work.It cites Lovász and Simonovits (1993), Ledoux (1999), Lee and Vempala (2018b), and Kannan et al. (2006).Source: §B.2 · p. 56
• Assuming the isoperimetric claim fails, the proof uses localization to construct a one-dimensional distribution that violates Lemma 17.The paper describes localization as reducing a high-dimensional inequality to a one-dimensional one that is easier to verify.Source: §B.2 · pp. 56–57
• The localization construction maps the partition sets S1, S2, and S3 onto sets J1, J2, and J3 along a segment between two points.The resulting density ρ is defined on [0, 1].Source: §B.2 · pp. 56–57
• The construction preserves enough mass in J1 and J2 while separating their points, yielding a contradiction with the one-dimensional inequality.The proof states ρ(J1) > Π∗(S1) − ν and ρ(J2) > Π∗(S2) − ν, then combines this with the distance bound and Lemma 17.Source: §B.2 · p. 57

B.3 Proof of Lemma 17

• The proof proceeds through three cases: constant q with interval sets, general log-concave q with interval sets, then general log-concave q with arbitrary partitions.The final case is reduced to the preceding interval case.Source: §B.3 · pp. 58–60
• For interval sets, Gaussian isoperimetry and comparisons between H and Q establish the needed inequality for general log-concave q.The proof compares the interval masses, using H(a,b) ≥ Q(a,b), H(c,d) ≥ Q(c,d), and H(b,c) ≤ Q(b,c).Source: §B.3 · pp. 58–59
• For arbitrary partitions, the proof groups J3 intervals by their surrounding sets and reduces the bound to the three-interval case.The grouping and summation argument handles the general partition using the established interval result.Source: §B.3 · pp. 60–61

Appendix C. Beyond strongly log-concave target distributions

• Appendix C extends the mixing-bound discussion to weakly log-concave targets and perturbations of log-concave targets.The appendix treats these as two settings beyond strongly log-concave targets.Source: Appendix C · p. 62

C.1 Weakly log-concave target

• Under either a fourth-moment condition or a well-behaved covariance condition, HMC improves on MALA by O(d^(1/6)) gradient evaluations.For the fourth-moment case, the chain uses a modified target and assumes a warm start relative to that target.Source: §C.1 · pp. 62–63

C.2 Non-log-concave target

• For a perturbed log-concave target, Theorem 1 applies if a gradient bound is known, but deriving explicit bounds in this setting is outside the paper's focus.The perturbation is uniformly lower-bounded, yielding an isoperimetric constant bounded below by e^(-2b)ψ0.Source: §C.2 · p. 64

Appendix D. Optimal choice for HMC hyper-parameters

• Appendix D discusses optimal leapfrog-step choices, additional convergence rates, and comparisons with unadjusted and ODE-solved HMC.Its tuning analysis trades off six terms, with the largest term determining the gradient-evaluation bound.Source: Appendix D · p. 64, §D.1 · p. 66

D.1 Optimal choices for Corollary 14

• With optimal choices of K and η, HMC's upper bound requires fewer gradient evaluations than MALA, but the choices depend delicately on κ and d.Table 4 summarizes the optimal choices for regular targets with LH = O(L).Source: §D.1 · p. 64, Table 4 · p. 65

• With a warm start and κ much smaller than d, the stated bound improves the κ exponent from 3/4 to 1/4.The passage also states that this yields a gradient-evaluation bound, but its order is incomplete in the supplied text.Source: §D.1.1 · p. 66
• With very small Hessian-Lipschitz constant and small κ, the resulting gradient-evaluation bound is of order d.This bound is discussed for a warm start; the supplied passage does not preserve the full expression.Source: §D.1.1 · p. 66
• An artificially constructed example illustrates that additional assumptions can yield faster rates, but the proof does not recover an O(1) mixing-time bound for a Gaussian target.Source: §D.1.1 · pp. 66–67
• Table 6 lists six terms in the gradient-evaluation bound for a very warm start and small Hessian-Lipschitz constant, highlighting the dominant term in red.Source: Table 6 · p. 67
• A linear transformation can improve conditioning and, when κ_h is much smaller than κ, the stated bound guarantees faster mixing on the transformed target.Samples are transformed back using the matrix M; the passage relates this transformation to a modified kinetic energy.Source: §D.1.1 · p. 67

• Table 7 summarizes gradient-evaluation guarantees for log-concave targets under shared regularity assumptions, although some methods do not require assumption (10c).Source: §D.2 · p. 67, Table 7 · p. 68
• For log-concave sampling, prior guarantees for unadjusted algorithms scale polynomially in 1/ϵ, whereas MALA and Metropolized HMC have logarithmic dependence on 1/ϵ.For well-conditioned targets, prior results have better dimension dependence than the paper's bounds.Source: §D.2 · p. 68
• The comparison translates mixing guarantees into expectation-estimation error for bounded-domain Lipschitz functions, assuming finite-sample error is negligible.The passage distinguishes Wasserstein- and total-variation-based tolerances for this comparison.Source: §D.2 · pp. 68–69
• For g(x) = ∥x∥1+ν, Metropolized HMC takes fewer gradient evaluations than ODE-based HMC for ν > 1/2 and unadjusted HMC for ν > 1.The unadjusted-HMC bounds require additional regularity conditions.Source: §D.2 · p. 69