[KongchangAI]
· 2 min read· 1,229 words

New Proof of Accelerated Convergence for Hamiltonian Monte Carlo: Dobrushin Contraction and High-Probability Mixing

New Proof of Accelerated Convergence for Hamiltonian Monte Carlo: Dobrushin Contraction and High-Probability Mixing

New coupling technique simultaneously proves dual acceleration of HMC in condition number and dimension.

This article reports an important advance in the convergence theory of Hamiltonian Monte Carlo (HMC). For the critically damped Metropolis-adjusted Langevin algorithm (with persistent uniform refresh), the authors introduce Dobrushin contraction and a new coupling technique to establish a high-probability uniform mixing bound, proving that the number of gradient evaluations required to reach ε-accuracy is 𝒪((κ^{1/2}+L_H^{1/2}m^{-3/4})d^{1/4}). This is the first result to rigorously capture acceleration in both condition number (κ^{1/2}) and dimension (d^{1/4}) simultaneously within a high-equilibrium probability region. The core technical tool is a weak-(1,1) maximal inequality derived from Hopf's maximal ergodic theorem, used to establish stability within high-probability regions and localize the analysis to fast local mixing regions. This result unifies prior independent works that separately demonstrated acceleration in condition number or dimension, providing a more rigorous mathematical foundation for HMC in high-dimensional ill-conditioned problems.

Theoretical Breakthrough: Simultaneously Capturing Two-Dimensional Acceleration

The paper considers a target measure μ(dx) ∝ e^{-U(x)}dx, where the potential function U satisfies m-strong convexity, L-gradient Lipschitz, and L_H-Frobenius Hessian Lipschitz conditions. For the critically damped Metropolis-adjusted Langevin algorithm (with persistent uniform refresh), the authors prove that the number of gradient evaluations required to reach ε-accuracy (in total variation distance) is:

𝒪((κ^{1/2} + L_H^{1/2} m^{-3/4}) d^{1/4}), ignoring logarithmic factors.

Here κ = L/m is the condition number and d is the dimension. This result holds uniformly with respect to the initial point within a high-equilibrium probability region, and also applies to warm starts. Compared with diffusion methods, the dimension dependence drops from d^{1/2} to d^{1/4}, and the condition number dependence drops from κ to κ^{1/2}, thereby demonstrating acceleration in both aspects.

Prior work (such as Bou-Rabee and Chen et al.) separately demonstrated acceleration in condition number or dimension, but failed to rigorously prove both simultaneously. The core contribution of this paper lies in integrating these two acceleration mechanisms into a unified coupling framework.

The Role of Condition Number κ and Dimension d in MCMC Convergence

In Markov chain Monte Carlo, the geometric properties of the target distribution directly determine how many steps the algorithm needs to approach equilibrium. The condition number κ = L/m characterizes the degree of "anisotropy" of the potential function U: when κ is large, the target distribution is extremely flat in some directions and extremely steep in others, and gradient-based algorithms tend to oscillate back and forth in narrow directions and crawl slowly in flat directions. Dimension d adds difficulty from another angle—volume grows exponentially in high-dimensional spaces, and the region the chain needs to explore expands dramatically. The complexity of traditional diffusion methods is typically penalized by both κ and d (e.g., on the order of κ·d^{1/2}). Therefore, whether the complexity's dependence on both κ and d can be simultaneously "reduced in order" is a core criterion for judging whether a sampling algorithm truly possesses dual acceleration. The result of this paper reduces the exponent of κ from 1 to 1/2 and the exponent of d from 1/2 to 1/4, making progress on both fronts of this criterion.

New Coupling Technique: From Fast Local Mixing to Global Stability

The paper develops a new coupling technique applicable to general Markov chains, extending an earlier framework aimed at capturing "fast local equilibration under slow global mixing." The key technical tool is a weak-(1,1) maximal inequality, derived from Hopf's maximal ergodic theorem. This inequality reveals a stability mechanism with respect to the equilibrium state within a high-probability region.

This stability enables the researchers to localize the analysis to the naturally arising fast local mixing region, and to seamlessly connect with broad local frameworks such as Dobrushin contraction, Wasserstein contraction, and the local Harris theorem. The authors specifically develop a formulation of Dobrushin contraction, providing a solid foundation for the coupling argument.

Dobrushin Contraction and Coupling Methods

The Dobrushin contraction coefficient measures the extent to which a Markov transition kernel "pulls together" any two initial distributions: if there exists ρ < 1 such that for any x, y we have W₁(δ_x P, δ_y P) ≤ ρ·dist(x, y), then the chain is said to contract in the Dobrushin sense. It is one of the most classical tools for proving geometric ergodicity, but the classical version requires globally uniform contraction, which is too stringent for algorithms like HMC that mix quickly only locally and may be slow globally. The key improvement in this paper is to localize Dobrushin contraction: contraction is verified only within the naturally arising "fast local mixing region," and then the weak-(1,1) maximal inequality is used to stitch local conclusions into a global high-probability bound. The coupling argument is the constructive means to achieve this—by designing synchronized random refreshes of two copies (persistent uniform refresh precisely provides this coupling interface), they meet at the same location with controllable probability, thereby converting total variation distance into the tail probability of the meeting time.

Hopf's Maximal Ergodic Theorem and the Weak-(1,1) Maximal Inequality

Hopf's maximal ergodic theorem originates from ergodic theory and is used to prove pointwise convergence of positive operators under semigroup action. Its core idea is to construct a "maximal operator" that characterizes the stability of the operator by comparing the supremum of functions along orbits. This paper transplants it into the analysis of Poisson equations for Markov chains, deriving a weak-(1,1) maximal inequality: this inequality provides pointwise control of the solution operator on function gradients, with control constants depending only on local geometric quantities rather than global condition numbers. This property allows researchers to assert, within a high-probability region (i.e., after excluding rare bad events), that the deviation of the chain relative to equilibrium is stably compressed, thereby strictly confining the analysis to the local mixing region and avoiding uniform requirements over the entire state space. This stands in sharp contrast to previous methods relying on global spectral gaps or global Lyapunov functions.

Cross-Validation with Multi-Source Analysis

According to prior work by Bou-Rabee and Chen et al., the acceleration properties of HMC have been separately proven under specific conditions. Through multi-source cross-validation, this paper integrates these independent results into a stronger joint guarantee. The consensus is that HMC can indeed achieve acceleration in both condition number and dimension simultaneously, but requires refined coupling constructions to handle uniformly. The divergence lies in the different emphases on the strength of assumptions across papers; for example, this paper requires Hessian Lipschitz, while some works require only gradient Lipschitz. The unique insight of this paper is the use of Hopf's maximal ergodic theorem to derive the weak-(1,1) inequality, thereby establishing stability within a high-probability region, which provides a new pathway for localization analysis.

Practical Significance and Outlook

This theoretical work provides a more rigorous mathematical foundation for the accelerated convergence of HMC, especially in high-dimensional and ill-conditioned problems. The reduction in the required number of gradient evaluations implies lower computational cost in practical sampling, although constant factors and logarithmic factors may affect actual performance. Future directions may include relaxing the Hessian Lipschitz assumption, extending to stochastic gradient versions, and studying similar coupling techniques in more general MCMC algorithms.

For practitioners, this result reinforces HMC's position as the method of choice for high-dimensional sampling and suggests that attention to details such as persistent uniform refresh in algorithm design may lead to improved theoretical guarantees.

Metropolis Adjustment and Persistent Uniform Refresh

Metropolis adjustment is the standard mechanism ensuring that MCMC algorithms are exactly invariant with respect to the target measure: at each step a candidate point is proposed, and whether to move is decided with acceptance probability min{1, e^{-ΔU}}, thereby correcting the bias introduced by discretization. For Langevin-type algorithms, this means that even if the numerical integration step size is large, the stationary distribution of the chain remains exactly μ, though the mixing speed is affected. Persistent uniform refresh, on the other hand, resets the state at each step with some probability using independently drawn auxiliary variables (such as velocity or momentum); it breaks the deterministic dependence of the trajectory and provides a "synchronization point" for the coupling construction. Together, these two designs ensure that the algorithm possesses both exact invariance and an analyzable contraction structure—the former is the bottom line of correctness, and the latter is the technical prerequisite for the high-probability mixing bound in this paper to hold.

#Hamiltonian Monte Carlo#Dobrushin contraction#high-probability mixing#MCMC convergence#coupling technique
Share:

Related articles