Improved Analysis for Hessian-free High-resolution Monte Carlo Sampling

Wujun Lv; Xiaoyu Wang; Yingli Wang; Lingjiong Zhu

stat.MLAug 25, 2026

Improved Analysis for Hessian-free High-resolution Monte Carlo Sampling

Authors: Wujun Lv, Xiaoyu Wang, Yingli Wang, Lingjiong Zhu

Organizations: School of Mathematics and Statistics, Donghua University, Shanghai, People’s Republic of China · Hong Kong University of Science and Technology (Guangzhou), Guangzhou, Guangdong Province, People’s Republic of China · School of Mathematical Sciences, Fudan University, Shanghai, People’s Republic of China · Department of Mathematics, Florida State University, Tallahassee, Florida, United States of America

Abstract

Hessian-free high-resolution (HFHR) dynamics augments underdamped Langevin dynamics (ULD) with reversible position diffusion for sampling problems that arise in machine learning. We establish an explicit quantitative contraction rate for HFHR dynamics under a position Poincaré inequality, weighted Hessian and Laplacian bounds, and a compact Sobolev embedding, where the potential function is not necessarily convex. An adapted time-augmented Poincaré inequality yields an explicit rate that improves upon the contraction rate of the underdamped Langevin dynamics. We also give a weak-solution construction and a self-contained spectral proof of the divergence lemma underlying the argument. For HFHR Monte Carlo (HFHRMC) algorithm, which is based on a discretization scheme of HFHR dynamics, we use a path-space Girsanov argument to obtain a non-asymptotic convergence bound and an explicit iteration complexity in total variation distance. The bounds hold for every $α\geq0$ and $γ>0$ and remain regular at the ULD endpoint. Optimizing the iteration complexity bound yields a positive, accuracy-dependent position-diffusion parameter at finite accuracy, while its leading high-accuracy order coincides with that of the optimized ULD endpoint. Our iteration complexity bound improves upon the existing work on HFHR algorithms. Numerical experiments including Bayesian learning problems on real data are provided to illustrate the effect of positive $α$ and its benefit.

Figures & tables

Panel of Figure 1 — Figure 1: Exact convergence for the anisotropic Gaussian target in $\chi^{2}$ -divergence. Every curve is evaluated analytically from the continuous-time Gaussian law.

Panel of Figure 2 — Figure 2: The number $K$ of iterations required to satisfy $B_{K}\leq\varepsilon$ for the Bayesian linear regression posterior on wine quality real data. The quantity $B_{K}$ is the analytically computed $\chi^{2}$ -divergence upper bound on joint total variation. Positive $\alpha$ is selected from the stated grid separately at each accuracy. For the corresponding sampler, $K$ is also the number of full data gradient evaluations along one trajectory. Both axes are logarithmic. We note $\gamma=2\sqrt{L}$ corresponds to [ 12 ] .

Panel of Figure 3 — Figure 3: Convergence for the real data Bayesian logistic posterior. Solid curves are independent ensemble means and shaded regions are pointwise $95\%$ confidence intervals. The horizontal axis reports $K$ iterates. The state shown at $K$ has used exactly $K$ full data gradient evaluations along each particle trajectory. We note $\gamma=2\sqrt{L}$ corresponds to [ 12 ] .

Panel of Figure 4 — Figure 4: Convergence for the Bayesian neural network with transformed physical weights and biases in $(-1.5,1.5)$ . Solid curves are independent ensemble means and shaded regions are pointwise $95\%$ confidence intervals. The horizontal axis reports $K$ iterates. The state shown at $K$ has used exactly $K$ full data gradient evaluations along each particle trajectory.

Explore similar work

Mar 2, 2026

Dimension-Independent Convergence of Underdamped Langevin Monte Carlo in KL Divergence

Underdamped Langevin dynamics (ULD) is a widely-used sampler for Gibbs distributions

π\propto e^{-V}

, and is often empirically effective in high dimensions. However, existing non-asymptotic convergence guarantees for discretized ULD typically scale polynomially with the ambient dimension

d

, leading to vacuous bounds when

d

is large. The main known dimension-free result concerns the randomized midpoint discretization in Wasserstein-2 distance (Liu et al.,2023), while dimension-independent guarantees for ULD discretizations in KL divergence have remained open. We close this gap by proving the first dimension-free KL divergence bounds for discretized ULD. Our analysis refines the KL local error framework (Altschuler et al., 2025) to a dimension-free setting and yields bounds that depend on

\mathrm{tr}(\mathbf{H})

, where

\mathbf{H}

upper bounds the Hessian of

V

, rather than on

d

. As a consequence, we obtain improved iteration complexity for underdamped Langevin Monte Carlo relative to overdamped Langevin methods in regimes where

\mathrm{tr}(\mathbf{H})\ll d

Shiyuan Zhang, Qiwei Di, Xuheng Li +1

Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Markov Chain Monte Carlo Langevin Dynamics Convergence Analysis

Ask PDF

Mar 24, 2026

Algorithmic warm starts for Hamiltonian Monte Carlo

Generating samples from a continuous probability density is a central algorithmic problem across statistics, engineering, and the sciences. For high-dimensional settings, Hamiltonian Monte Carlo (HMC) is the default algorithm across mainstream software packages. However, despite the extensive line of work on HMC and its widespread empirical success, it remains unclear how many iterations of HMC are required as a function of the dimension

d

. On one hand, a variety of results show that Metropolized HMC converges in

O(d^{1/4})

iterations from a warm start close to stationarity. On the other hand, Metropolized HMC is significantly slower without a warm start, e.g., requiring

Ω(d^{1/2})

iterations even for simple target distributions such as isotropic Gaussians. Finding a warm start is therefore the computational bottleneck for HMC. We resolve this issue for the well-studied setting of sampling from a probability distribution satisfying strong log-concavity (or isoperimetry) and third-order derivative bounds. We prove that non-Metropolized HMC generates a warm start in

\tilde{O}(d^{1/4})

iterations, after which we can exploit the warm start using Metropolized HMC. Our final complexity of

\tilde{O}(d^{1/4})

is the fastest algorithm for high-accuracy sampling under these assumptions, improving over the prior best of

\tilde{O}(d^{1/2})

. This closes the long line of work on the dimensional complexity of MHMC for such settings, and also provides a simple warm-start prescription for practical implementations.

Matthew S. Zhang, Jason M. Altschuler, Sinho Chewi

UToronto · UPenn · Yale

Markov Chain Monte Carlo Sample Complexity Log-Concave Sampling

Ask PDF

Oct 7, 2026

Reflected Anchored Langevin Algorithms

First order Langevin algorithms for constrained sampling in machine learning, such as projected Langevin Monte Carlo which are based on discretizations of reflected Langevin dynamics, require differentiable log densities that limits their applicability. This paper introduces reflected anchored Langevin dynamics (RALD), a reflected diffusion that converges to non-differentiable targets on constrained domains. The method uses a smooth anchored reference potential and multiplies the drift and noise covariance of its reflected Langevin dynamics by the same state dependent scaling factor. Its Euler-Maruyama discretization with projection gives reflected anchored Langevin Monte Carlo (RALMC) algorithm. We prove explicit convergence bounds and iteration complexity for RALMC in the 2-Wasserstein distance to the target distribution. Numerical experiments are provided to illustrate the theoretical predictions and the empirical performance of the method.

Changwei Tu, Xiaoyu Wang, Yingli Wang +2

Hong Kong University of Science and Technology (Guangzhou), Guangzhou, Guangdong Province, People’s Republic of China · School of Mathematical Sciences, Fudan University, Shanghai, People’s Republic of China · School of Mathematics and Statistics, Beijing Institute of Technology, Beijing 100081, People’s Republic of China +1

Langevin Dynamics Markov Chain Monte Carlo

Ask PDF