Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation

1.1 Results

• The analysis bounds RHMC mixing using metric and function parameters, requiring smoothness and Cheeger expansion but no convexity assumptions.For Gibbs distributions induced by convex functions with convex Hessians, the paper also proves an isoperimetric inequality described as an analog of the KLS conjecture on manifolds.Source: §1.1 · pp. 3, 5
• With the log-barrier Hessian as metric, RHMC samples from a distribution very close to uniform when α=1/m.The method also applies to a general family of Gibbs distributions induced by convex functions over a polytope.Source: §1.1 · p. 4
• The volume algorithm estimates polytope volume within a 1±ε multiplicative factor and improves prior complexity by sampling a sequence of Gibbs distributions.The algorithm uses Hamiltonian Monte Carlo for that sequence.Source: §1.1 · p. 5

1.2 Approach and contributions

• Unlike straight-line random walks and the geodesic walk, RHMC avoids the expensive Metropolis filter, allowing longer steps while retaining an ODE solve per step.The geodesic walk's filter requires solving an n×n matrix ODE.Source: §1.2 · pp. 5–6
• The paper extends Gaussian cooling to manifolds, replacing the Gaussian density with e^(-αφ(x)); its speed depends on the manifold's thin-shell constant and φ's classical self-concordance.The sampling analysis uses a variant of self-concordance for the log barrier.Source: §1.2 · p. 6

1.3 Practicality

• Experiments suggest RHMC mixes in polylogarithmically many steps, while ball walk and hit-and-run appear to require n^2 steps.The authors say a direct empirical comparison of sampling algorithms remains future work.Source: §1.3 · p. 6

2 Basics of Hamiltonian Monte Carlo

• HMC generates a Markov chain from randomly generated Hamiltonian curves, defined by Hamiltonian equations for position and velocity.Source: §2 · p. 8
• The curves conserve Hamiltonian energy and make the walk time-reversible, allowing convergence to the desired distribution without a rejection step.Source: §2 · pp. 8–9
• The main analytical challenge is bounding the chain's mixing time.Source: §2 · p. 10

2.1 Hamiltonian Monte Carlo on Riemannian manifolds

• On a Riemannian manifold, the Hamiltonian map takes an initial tangent velocity along a Hamiltonian trajectory to its endpoint, and is compared with the exponential map.Source: §2.1 · pp. 11–12
• With the identity metric, curves act like stochastic gradient descent; with the Hessian metric, they act like stochastic Newton curves for f + ψ, where ψ = log det ∇2f.Source: §2.1 · p. 12

3.1 Basics of geometric Markov chains

• Conductance is bounded below by Ω(rψ) when points within metric distance r have one-step distributions with total variation distance at most 0.9.Here ψ denotes the metric-space isoperimetry parameter for the target distribution.Source: §3.1 · pp. 13–14

3.2 Overlap of one-step distributions

• The analysis uses bounded, Lipschitz auxiliary measures of path quality so that most Hamiltonian curves, rather than every curve, can be treated as well-behaved.The proposed measure jointly tracks changes in position and velocity; bounding only initial velocity would give a weaker bound.Source: §3.2 · p. 15

3.2.1 Proof Outline

• Nearby starting points are compared by bounding the Hamiltonian endpoint-map Jacobian and matching initial velocities that reach the same endpoint.The proof outline combines these steps to compare the two one-step distributions.Source: §3.2.1 · p. 15

3.2.2 Variation of Hamiltonian curve

• Hamiltonian-curve variations are represented by Jacobi fields satisfying an ODE, which the analysis uses to estimate the endpoint-map Jacobian.These variations are the tool for bounding the Jacobian determinant of the Hamiltonian map.Source: §3.2.2 · p. 16

3.2.3 Local Uniqueness of Hamiltonian Curves

• Under the stated step-size and smoothness conditions, nearby starting points admit a unique smooth matching initial velocity, with derivative norm at most 5.The matching velocity keeps the Hamiltonian endpoint fixed as the starting point varies.Source: §3.2.3 · p. 19
• For a geodesic variation of the starting point, the matching vector field remains uniquely defined and the corresponding paths retain the auxiliary-function bound ℓ0.The stated result applies under the section’s step-size and auxiliary-function conditions.Source: §3.2.3 · pp. 20–21

3.2.4 Smoothness of one-step distributions

• The one-step distribution comparison considers nearby points joined by a short geodesic and uses high-probability well-behaved paths with matched endpoints.The supplied passages do not include the completed comparison bound.Source: §3.2.4 · p. 21

3.3 Convergence bound

• The convergence bound relates HMC mixing to manifold conductance and smoothness parameters.The subsequent corollary presents a bound using two worst-case smoothness parameters; a refined bound using trajectory randomness is deferred to the next section.Source: §3.3 · pp. 23–24
• The auxiliary path-length function has ℓ0 = 10√n and ℓ1 = O(1/δ).These parameters are used with Theorem 26 to obtain the convergence bound.Source: §3.3 · p. 23
• Corollary 28 states a mixing-time bound in terms of two worst-case smoothness parameters and manifold conductance.The corollary assumes a uniform bound R0 on the norm of the drift field µ; the excerpt does not include the full bound or all parameter definitions.Source: §3.3 · pp. 23–24

4 Improved analysis of the convergence

• The improved convergence analysis targets two bottlenecks: the earlier auxiliary function and overlap bound do not fully exploit the random initial direction of each Hamiltonian curve.Theorem 29's one-step-distribution overlap result is identified as a key ingredient.Source: §4 · pp. 24–25
• The convergence theorem is stated in terms of conductance and the parameters ℓ0, ℓ1, R1, R2, and R3, under a step-size condition.A constant term from bounding bad events can be made arbitrarily small.Source: §4 · pp. 24–25

4.1 Improved one-to-one correspondence for Hamiltonian curve

• The refined correspondence analysis introduces R3 to control how the transported initial velocity changes along a Hamiltonian curve.R3 bounds the supremum of ∥Φ(t)ζ(t)∥ along the curve, refining the earlier analysis based only on R1.Source: §4.1 · p. 25

4.2 Improved smoothness of one-step distributions

• The improved smoothness analysis uses the refined curve correspondence to bound changes in the initial-velocity norm, while deferring the trace term calculation.The section also defines R2 through bounds involving curves and vector fields; the resulting one-step distributions satisfy a refined overlap estimate.Source: §4.2 · pp. 26–27

5.1 Isoperimetry for Hessian manifolds

• For convex Hessian manifolds with nonnegative directional fourth derivative, the analysis derives a general isoperimetry bound; the standard logarithmic barrier satisfies this condition.The proof uses localization to reduce the bound to a one-dimensional inequality for convex φ with convex φ′′.Source: §5.1 · pp. 29–31

5.2 Sampling with the log barrier

• With the log-barrier Hessian metric and target exp(−αφ(x)), HMC has a mixing bound, with each step given by a Hamiltonian ODE solution.The proof invokes isoperimetric-coefficient bounds and a condition from Theorem 30.Source: §5.2 · p. 31
• The Hamiltonian flow is implemented by collocation, with an algorithm for computing it in local-norm distance to additive error η.The stated running time is eO(mn^(ω−1) log^O(1)(1/η)); sampling incurs only a polylogarithmic overhead.Source: §5.2 · p. 32

6 Polytope volume computation: Gaussian cooling on manifolds

• The algorithm extends Gaussian cooling from successive Gaussian distributions to Gibbs distributions defined using a convex barrier, and estimates a telescoping product of ratios.The temperatures are chosen for the sequence, and the barrier minimizer is the center of the body.Source: §6 · p. 32

6.2 Correctness of the algorithm

• The correctness proof separates endpoint-temperature bounds from analysis of the variance of the estimator Yx.These are identified as the two parts of the algorithm-correctness proof.Source: §6.2 · p. 32

6.2.1 Initial and terminal conditions

• For a ϑ-self-concordant barrier, the analysis establishes initial and terminal temperature conditions for the cooling schedule.The supplied passages identify the conditions but do not preserve their complete formulas.Source: §6.2.1 · pp. 34–35

6.2.2 Variance of Yx

• The estimator-variance analysis uses a manifold version of a thin-shell or variance-hypothesis estimate for φ under µs.The thin-shell estimate is presented as the tool for bounding Var(Yx).Source: §6.2.2 · pp. 36–37

6.2.3 Main lemma

• The main correctness lemma states that Volume(M, ε) outputs the volume within a 1±ε multiplicative factor.The proof also relates per-phase sample counts to the target relative error.Source: §6.2.3 · p. 37

6.3 Volume computation with the log barrier

• Theorem 2 guarantees a 1±ε multiplicative estimate of polytope volume, with each HMC step solving a first-order ODE.The theorem states a total-step bound, but the supplied passage does not preserve its full expression.Source: §6.3 · p. 38

7.1 Riemannian geometry on ML (G2)

• The embedded manifold’s Euclidean-coordinate geometry is expressed through formulas for parallel transport and curvature, including Ricci curvature.These formulas provide the geometric tools used in the subsequent analysis.Source: §7.1 · p. 40

7.2 Hamiltonian walk on ML

• The specialized Hamiltonian walk is formulated as a Euclidean-coordinate ODE and implemented by collocation at complexity ˜O(mn^(ω−1)) per step.The ODE is first reduced to a first-order system; the passage attributes the collocation method to.Source: §7.2 · p. 40

7.3 Randomness of the Hamiltonian flow (ℓ0)

• The random Hamiltonian flow has bounded length ℓ0 ≤ 256, and the analysis controls its L4 behavior.The initial quantity v4 = ∥Aγγ′(0)∥4 is bounded by 2n^(1/4) with high probability.Source: §7.3 · pp. 42–44

7.4 Parameters R1, R2 and R3

• For Hamiltonian curves with bounded length, the section derives bounds for R1, R2, and R3 and for variation of parallel transport.The transport bound is stated for the parallel transport of the curve’s initial velocity; the displayed assumptions and bound are incomplete in the supplied passages.Source: §7.4 · pp. 46, 51

7.5 Stability of L2 + L4 + L∞norm (ℓ1)

• For a family of Hamiltonian curves, the section establishes stability of the L2, L4, and L∞ norms under its stated step-size conditions.The supplied lemma passage gives the stability claim’s setup but omits the resulting inequality.Source: §7.5 · p. 53
• The ℓ1 stability analysis improves an estimate using the same calculation as (7.7), then combines bounds from (7.8) and (7.9).Source: §7.5 · pp. 54–55

7.6 Mixing Time

• The logarithmic-barrier parameters satisfy M1 = n + α^2m, M2 = α, and M3 = 2α times a square-root term.The supplied passage truncates the square-root expression, so its contents cannot be specified here.Source: §7.6 · p. 55
• For a sufficiently small constant, the derived step-size choice satisfies all δ conditions required by Theorem 30.The passage states that the conditions are verified after substituting the logarithmic-barrier parameter bounds.Source: §7.6 · pp. 55–56

A Matrix ODE

• Lemmas 62 and 63 analyze matrix ODE (3.4) using bounds on Φ(t) in operator and Frobenius norms, respectively.The supplied lemma statements do not preserve the full bounds.Source: A Matrix ODE · p. 59
• The ODE analysis also uses an integral equation for a(t), which is differentiated and solved to obtain the stated result.The passages describe the proof steps without preserving the solution formula.Source: A Matrix ODE · p. 59
• For matrices E with ∥E∥2≤1/4, the determinant argument studies log det(I+tE) and uses Jacobi’s formula to express its second derivative.The derivative is given as −Tr((I+tE)−1E(I+tE)−1E).Source: A Matrix ODE · p. 60

• Lemma 65 cites [13, Ver 3, Lemma 90] for a statement applying when p ≥1.Source: B Concentration · p. 61

• The proof of Fact 48 recalls Definition 47 and indicates that its second step uses the first.Source: C Calculus · p. 61

• A Riemannian manifold equips tangent spaces with inner products, while a Hessian manifold is an open subset of R^n induced by a smooth convex function φ.Source: D Basic definitions of Riemannian… · p. 62
• The differential maps tangent directions between manifolds and acts as the Jacobian in Euclidean spaces.Source: D Basic definitions of Riemannian… · p. 62
• Curve length defines manifold distance as the infimum over connecting paths; geodesics are constant-speed locally shortest paths.Source: D Basic definitions of Riemannian… · p. 62
• The exponential map sends a tangent vector to the endpoint of its geodesic, corresponding to point-vector addition in Euclidean space.Source: D Basic definitions of Riemannian… · p. 63
• Parallel transport moves vectors along curves while preserving orthogonality to the curve’s tangent, and it extends orthonormal frames along a curve.Source: D Basic definitions of Riemannian… · p. 63
• The Levi-Civita connection defines directional derivatives using parallel transport; parallel fields have zero covariant derivative, and geodesics have zero covariant acceleration.Source: D Basic definitions of Riemannian… · p. 63

• The Riemann curvature tensor measures how a manifold’s three-dimensional parallelepipeds fail to close, while torsion-free geometry makes parallelograms close up to higher-order error.Source: §D.1 · p. 64
• Ricci curvature indicates whether nearby geodesics converge or diverge and can be expressed as an expectation over a Gaussian vector.Source: §D.1 · p. 64
• The curvature tensor can also be written as the difference between covariant derivatives taken in opposite orders along a two-parameter map.Source: §D.1 · p. 64

D.2 Hessian manifolds

• A Hessian manifold is a subset of R^n with metric entries given by the second derivatives of a smooth convex function φ.Source: §D.2 · p. 65
• Because a Hessian manifold lies in Euclidean space, its tangent spaces are identified using Euclidean coordinates.Source: §D.2 · p. 65
• Lemma 69 gives Euclidean-coordinate formulas for the Levi-Civita connection and curvature on a Hessian manifold.The lemma is stated for vector fields v, u, w, and z.Source: §D.2 · p. 65