Accelerated Mixing Time of Randomized Hamiltonian Monte Carlo

Andre Wibisono; Siddharth Mitra; Vishwak Srinivasan; Xiuyuan Wang

Randomized Hamiltonian Monte Carlo mixes with total integration time O(α^{-1/2} log(1/ε)) for α-Talagrand log-concave targets.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-15 02:27 UTC pith:PPVQK3TG

load-bearing objection Abstract-only claim of accelerated O(α^{-1/2} log(1/ε)) total integration time for RHMC under Talagrand; real if the average-KL lemma holds, but we cannot check it yet. the 2 major comments →

arxiv 2607.12902 v1 pith:PPVQK3TG submitted 2026-07-14 stat.ML cs.DScs.LGmath.PRmath.STstat.COstat.TH

Accelerated Mixing Time of Randomized Hamiltonian Monte Carlo

Siddharth Mitra , Vishwak Srinivasan , Xiuyuan Wang , Andre Wibisono This is my paper

classification stat.ML cs.DScs.LGmath.PRmath.STstat.COstat.TH

keywords Randomized Hamiltonian Monte Carlomixing timelog-concave samplingTalagrand inequalityaccelerated samplingKL divergenceHamiltonian dynamics

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that Randomized Hamiltonian Monte Carlo (RHMC) achieves accelerated mixing guarantees when sampling from log-concave distributions. RHMC repeatedly runs continuous-time Hamiltonian dynamics for a random integration time and then resamples the velocity as an independent Gaussian. When the target is log-concave and satisfies an α-Talagrand inequality (which includes α-strongly log-concave densities), drawing the integration time from a triangular or exponential distribution whose mean is on the order of α to the power -1/2 produces exponential convergence in KL divergence; the total integration time needed to reach error ε therefore scales as O(α^{-1/2} log(1/ε)). For merely log-concave targets the same algorithm, run with a sequence of triangular times whose means grow exponentially, still reaches error ε with total integration time O(ε^{-1/2}). The argument rests on a bound for the average KL divergence along Hamiltonian trajectories, mirroring the continuous-time analysis of accelerated optimization methods. If the rates hold, they give a continuous-time explanation of how randomization of integration length alone can recover the square-root acceleration familiar from optimization.

Core claim

When the target is log-concave and satisfies an α-Talagrand inequality, RHMC with integration times drawn from the triangular or exponential distribution of mean Θ(α^{-1/2}) converges exponentially fast in KL divergence, and the total continuous-time integration cost to accuracy ε is O(α^{-1/2} log(ε^{-1})). For general log-concave targets a doubling schedule of triangular mean times yields total integration cost O(ε^{-1/2}).

What carries the argument

A bound on the average KL divergence along continuous-time Hamiltonian trajectories; combined with random integration times of mean Θ(α^{-1/2}) drawn from the triangular or exponential law, this average-KL contraction produces the claimed exponential decay of KL and the accelerated total-time rates.

Load-bearing premise

The analysis treats continuous-time Hamiltonian flow as exactly simulable and relies on a bound for average KL along those trajectories; any gap in that bound, or any discretization error that destroys continuous-time contraction, collapses the total-integration-time claims.

What would settle it

Numerically integrate RHMC with triangular random times of mean c/√α on a concrete α-strongly log-concave density (standard Gaussian or strongly log-concave logistic) and check whether total integration time grows like √(1/α) log(1/ε) or linearly before KL falls below ε; linear growth falsifies the rate.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

For α-strongly log-concave targets the continuous-time integration cost to ε-accuracy in KL is only square-root in 1/α, not linear.
Randomization of the integration length (triangular or exponential) is enough to realize the acceleration; fixed-length runs are not required.
The same average-KL contraction that underlies continuous-time accelerated optimization also controls the mixing of RHMC.
Merely log-concave targets still admit a square-root total-time guarantee via a schedule of exponentially increasing mean integration times.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Any numerical integrator that approximately preserves the average-KL contraction over intervals of length ~α^{-1/2} should inherit the same total-time scaling in discrete implementations of RHMC.
The result supplies a continuous-time bridge between acceleration in sampling and acceleration in optimization, both resting on the same Hamiltonian structure.
If the average-KL bound can be extended beyond log-concave targets, similar randomized-time acceleration may hold for broader classes of measures that still satisfy a Talagrand-type inequality.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Abstract-only claim of accelerated O(α^{-1/2} log(1/ε)) total integration time for RHMC under Talagrand; real if the average-KL lemma holds, but we cannot check it yet.

read the letter

The one thing to know: this abstract claims that Randomized HMC, with triangular or exponential random integration times of mean Θ(α^{-1/2}), mixes in total integration time O(α^{-1/2} log(1/ε)) in KL for log-concave targets that satisfy an α-Talagrand inequality, and O(ε^{-1/2}) under plain log-concavity with a schedule of growing means. That would close a gap between continuous-time underdamped Langevin rates and discrete-time MCMC, and it is the right order of magnitude for acceleration.

What looks new is the transfer of an average-KL-along-trajectory bound from accelerated Hamiltonian optimization into the RHMC setting, plus the concrete random-time schedules that make the total-time complexity work. The abstract is clean: no free parameters, no circular normalizations, and the benchmarks (KL, Talagrand constant, total integration time) are standard. If the proofs are there, this is a solid within-field advance for theoretical sampling.

The soft spot is exactly what the stress-test flags, and it is load-bearing: everything rests on that continuous-time average-KL lemma under only log-concavity + Talagrand. We have only the abstract, so we cannot verify the constants, the handling of random durations, or whether extra smoothness sneaks in. The continuous-time framing also treats the ODE as exact; any discretization that kills the contraction would leave the stated rates as continuous-time ideals rather than implementable guarantees. That is a real caveat, not a manufactured one, but it is the usual continuous-to-discrete gap rather than an obvious contradiction in the claim itself.

This is for people who care about mixing-time theory for log-concave sampling and the optimization–MCMC dictionary. A serious referee should see the full proofs; the abstract is clear enough and the result important enough that desk rejection would be wrong. I would not cite it from the abstract alone, and I would not put it in reading group until the paper is readable, but I would accept it for peer review and watch for the average-KL lemma.

Referee Report

2 major / 0 minor

Summary. The manuscript claims that Randomized Hamiltonian Monte Carlo (RHMC) achieves accelerated mixing for log-concave targets. RHMC alternates continuous-time Hamiltonian flows of random duration with independent Gaussian velocity refreshes. Under an α-Talagrand inequality (e.g., α-strong log-concavity), triangular or exponential integration times of mean Θ(α^{-1/2}) yield exponential KL contraction, so total integration time to KL error ε is O(α^{-1/2} log(ε^{-1})). Under mere log-concavity, a schedule of triangular times with exponentially growing means yields total integration time O(ε^{-1/2}). The argument rests on a continuous-time average-KL bound along Hamiltonian trajectories, inspired by accelerated Hamiltonian optimization.

Significance. If the continuous-time average-KL lemma holds under only log-concavity plus Talagrand, the paper would supply the first rigorous accelerated total-integration-time guarantees for RHMC that match known continuous-time acceleration phenomena and improve on standard Langevin/HMC rates. The parameter-free choice of mean integration time Θ(α^{-1/2}) and the explicit triangular/exponential distributions are concrete, falsifiable design recommendations. The pure log-concave O(ε^{-1/2}) schedule is likewise of independent interest. Because the work is framed entirely in continuous time, its practical impact hinges on whether the same rates survive standard symplectic discretizations; that question is left open but does not diminish the continuous-time contribution.

major comments (2)

Only the abstract is available, so the central average-KL bound along Hamiltonian trajectories cannot be inspected. That bound is load-bearing: every stated rate (both the exponential contraction under α-Talagrand and the O(ε^{-1/2}) schedule under mere log-concavity) is derived from it. Without the lemma statement, its hypotheses, and the constants that justify the mean Θ(α^{-1/2}), it is impossible to certify that the claimed total-integration-time guarantees hold under solely log-concavity + Talagrand. This is the single decisive technical gap.
The analysis treats continuous-time Hamiltonian ODEs as exactly simulable. Any subsequent discretization (leapfrog, etc.) that introduces error large enough to destroy the continuous-time KL contraction would invalidate the stated rates. The abstract does not address discretization; a major revision should either (i) prove that a standard integrator preserves the rates up to controllable error or (ii) explicitly restrict the claims to continuous time and discuss the open discretization question.

Circularity Check

0 steps flagged

No circularity found; abstract states self-contained mixing-time rates for RHMC against external benchmarks (α-Talagrand, KL error) with no fitted parameters or definitional reductions.

full rationale

Only the abstract is available. It claims exponential KL contraction for RHMC under log-concavity plus α-Talagrand when random integration times are drawn from triangular or exponential distributions of mean Θ(α^{-1/2}), yielding total integration time O(α^{-1/2} log(ε^{-1})), and an O(ε^{-1/2}) total-integration-time bound under mere log-concavity with a schedule of increasing means. These quantities are standard external complexity measures; nothing in the abstract defines a parameter from the target quantity and then re-presents it as a prediction, nor does it invoke a uniqueness theorem or ansatz solely via self-citation. The sole methodological remark is that the analysis “relies on a bound on the average KL divergence along Hamiltonian dynamics, which is inspired by an analogous result on accelerated optimization methods based on Hamiltonian dynamics.” Inspiration from a related literature is not a circular reduction. Because no equations, lemmas, or load-bearing self-citations appear in the supplied text, no step can be exhibited that reduces a claimed prediction to its own inputs by construction. The derivation chain, as stated, is therefore free of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

Abstract-only review: free parameters are essentially none (the mean Θ(α^{-1/2}) is set by the known strong-concavity/Talagrand constant, not fitted). Core axioms are standard domain assumptions of continuous-time MCMC analysis. No new physical entities are introduced.

axioms (3)

domain assumption Target distribution is log-concave (and, for the exponential rate, satisfies an α-Talagrand inequality).
Stated as the hypothesis under which the O(α^{-1/2} log(1/ε)) and O(ε^{-1/2}) rates hold.
domain assumption Continuous-time Hamiltonian dynamics can be simulated exactly for random integration times; only total integration time is counted.
Standard continuous-time idealization in HMC theory; the claimed complexity is measured in integration time, not wall-clock or leapfrog steps.
ad hoc to paper A bound on the average KL divergence along Hamiltonian trajectories holds and is strong enough to yield the stated contraction.
The abstract identifies this bound as the key analytic ingredient, inspired by accelerated optimization; its precise statement and proof are not available in the abstract.

pith-pipeline@v1.1.0-grok45 · 6150 in / 2357 out tokens · 34488 ms · 2026-07-15T02:27:45.471284+00:00 · methodology

0 comments

read the original abstract

We show the Randomized Hamiltonian Monte Carlo (RHMC) algorithm has accelerated mixing time guarantees for sampling from log-concave probability distributions. RHMC proceeds by repeatedly simulating the continuous-time Hamiltonian dynamics for some random integration times, and resetting the velocity to be an independent Gaussian random variable between each simulation. We show that when the target distribution is log-concave and satisfies an $\alpha$-Talagrand inequality (for example, if the target distribution is $\alpha$-strongly log-concave), if we use a random integration time from either the triangular or the exponential distribution with mean $\Theta(\alpha^{-1/2})$, then RHMC converges exponentially fast in KL divergence, and the total integration time to reach error $\varepsilon$ in KL divergence scales as $O(\alpha^{-1/2} \log(\varepsilon^{-1}))$. We also show that when the target distribution is log-concave, if we use a sequence of random integration times from the triangular distribution with exponentially increasing means, then the total integration time to reach error $\varepsilon$ in KL divergence scales as $O(\varepsilon^{-1/2})$. Our analysis relies on a bound on the average KL divergence along Hamiltonian dynamics, which is inspired by an analogous result on accelerated optimization methods based on Hamiltonian dynamics.

Accelerated Mixing Time of Randomized Hamiltonian Monte Carlo

Core claim

What carries the argument

Load-bearing premise

What would settle it

If this is right

Where Pith is reading between the lines

discussion (0)