High-probability Uniform Mixing via Dobrushin Contraction and Accelerated Hamiltonian Monte Carlo

Stefan OberdörsterarXiv 2026 · arXiv

TL;DR

This paper provides the first theoretical proof that a specific variant of Hamiltonian Monte Carlo (HMC) achieves "ballistic" acceleration in both dimension and condition number simultaneously. By introducing a novel coupling framework based on Hopf’s maximal ergodic theorem, the author establishes fast mixing guarantees even for deterministic starting points, provided they lie within high-probability regions of the target distribution.

What Problem Does This Paper Address?

Sampling from high-dimensional probability distributions is a cornerstone of modern statistics and machine learning. Hamiltonian Monte Carlo (HMC) is the "gold standard" for this task because it avoids the slow, diffusive behavior of standard random walks, instead using physics-inspired dynamics to "glide" through the state space.

Theoretically, HMC is expected to show two types of acceleration:

  1. Condition Number Acceleration: Scaling with the square root of the condition number ($\kappa^{1/2}$) rather than linearly ($\kappa$).
  2. Dimension Acceleration: Scaling with $d^{1/4}$ rather than $d^{1/2}$ (as seen in the Metropolis-Adjusted Langevin Algorithm, or MALA).

While previous research had proven these accelerations separately, no single work had captured both at once under general assumptions. Furthermore, most existing proofs rely on "warm starts"—the assumption that your initial guess is already somewhat close to the target—which is often unrealistic in practice. This paper aims to bridge these gaps.

Methods

The author analyzes a specific algorithm: Metropolis-adjusted kinetic Langevin with persistent uniforms.

  • Kinetic Langevin: A version of HMC that includes "friction" (damping), which helps the sampler stay stable.
  • Persistent Uniforms: A clever trick where the random variables used for the Metropolis-Hastings "accept/reject" step are updated non-reversibly. This allows for "error telescoping," where discretization errors cancel out over multiple steps rather than accumulating linearly.

The core mathematical innovation is a new coupling technology. Instead of trying to prove that the Markov chain contracts globally (which is often impossible), the author uses local Dobrushin contraction. They prove that the chain mixes quickly within a high-probability domain $D$.

To ensure the chain doesn't simply wander out of this "good" domain before it has a chance to mix, the author derives a stability mechanism using a weak-(1,1) maximal inequality from Hopf’s maximal ergodic theorem. This allows them to prove uniform mixing from any starting point in a high-probability region, not just from warm starts.

Datasets

This is a purely theoretical paper focused on proving convergence bounds for Markov Chain Monte Carlo (MCMC) algorithms. As such, no empirical datasets were used. The results are established through rigorous mathematical proof under the assumption of $m$-strongly convex and $L$-gradient Lipschitz potentials.

Key Insights and Ideas

  • The "Aha" Moment - Ergodic Stability: The use of Hopf’s maximal ergodic theorem to provide a stability guarantee is a significant departure from standard MCMC analysis. It provides a way to "localize" the analysis to high-probability regions without needing explicit Lyapunov functions or restrictive initialization assumptions.
  • Simultaneous Scaling: By combining the "high-acceptance" regime (which handles dimension scaling) with "hypocoercivity" ideas (which handle condition number scaling), the author achieves the desired $\tilde{O}(\kappa^{1/2} d^{1/4})$ complexity.
  • Frobenius vs. Spectral Norm: The paper notes that using the Frobenius norm for Hessian Lipschitzness (rather than the spectral norm) is a key technical choice that enables the $d^{1/4}$ scaling, though it is a slightly stronger assumption.

Key Results

  • Gradient Complexity: For a target measure with an $m$-strongly convex potential, the method reaches $\varepsilon$-accuracy in total variation distance using: $$\mathcal{O}\left( \left( \kappa^{1/2} + L_H^{1/2} m^{-3/4} \right) d^{1/4} \right)$$ gradient evaluations (ignoring logarithmic factors).

  • Deterministic Initialization: The results hold uniformly over starting points in domains of high equilibrium probability. This is a major step forward from "warm start" theories, as it covers practical scenarios where a user might start the sampler at the MAP (Maximum A Posteriori) estimate.

  • Improvement over State-of-the-Art: The paper improves upon previous bounds that reported $d^{3/4}$ or $d^{1/2}$ scaling when trying to account for the condition number.

Limitations and Future Work

  • Strong Convexity: The current proof requires the target distribution to be strongly log-concave (the potential $U$ must be $m$-strongly convex). Many real-world distributions (like those in deep learning) are non-convex or only weakly convex in the tails.
  • Frobenius Assumption: The $d^{1/4}$ scaling relies on the Hessian being Lipschitz with respect to the Frobenius norm. While common, this is stricter than the spectral norm assumption used in some other works.
  • Specific Algorithm: The results are tailored to the "persistent uniform" variant of HMC. It remains to be seen if these stability mechanisms can be easily adapted to more standard HMC implementations or other advanced samplers like the No-U-Turn Sampler (NUTS).

Summary updated

Abstract

Hamiltonian Monte Carlo, since its invention and subsequent rise to widespread use, has been motivated by its ability to accelerate convergence to equilibrium compared to diffusive methods, both in terms of dependence on condition number and dimension. In the present work, we establish this acceleration simultaneously in both aspects for critically damped Metropolis-adjusted kinetic Langevin with persistent uniforms. More precisely, for target measures $μ(dx)\propto e^{-U(x)}dx$ with $m$-strongly convex, $L$-gradient Lipschitz, and $L_H$-Frobenius Hessian Lipschitz potentials, we show that the method mixes to $\varepsilon$-accuracy in total variation using $\mathcal O\bigl((κ^{1/2}+L_H^{1/2}m^{-3/4})\,d^{1/4}\bigr)$ gradient evaluations up to logarithmic factors, both uniformly over starting points in domains of high equilibrium probability and from warm starts. The proof incorporates ideas from previous studies by Bou-Rabee and Chen et al. that show either aspect of acceleration separately, into novel coupling technology. This new coupling technology for general Markov chains extends earlier frameworks aimed at capturing fast local equilibration in the presence of slow global mixing. Specifically, via a weak-$(1,1)$ maximal inequality that follows from Hopf's maximal ergodic theorem, we uncover a stability mechanism in high-probability domains with respect to equilibrium. This enables straightforward localization to naturally arising domains of fast local mixing, and seamlessly fits broad local frameworks via Dobrushin contraction, Wasserstein contraction and local Harris' theorems. We develop the Dobrushin formulation.
BibTeX
@misc{oberdorster2026high,
  author = {Stefan Oberdörster},
  title = {{High-probability Uniform Mixing via Dobrushin Contraction and Accelerated Hamiltonian Monte Carlo}},
  year = {2026},
  eprint = {2611.21305},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.21305},
}
Figure