CS Paper Radar

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

Wujun Lv, Xiaoyu Wang, Yingli Wang, Lingjiong Zhu

cs.LG stat.MLmath.APmath.PR ·submitted 2026-08-25 18:42 UTC · v1

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.

Comment
49 pages, 4 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Reflected Anchored Langevin Algorithms

cs.LG stat.MLmath.PR ·2026-10-07 ·Changwei Tu, Xiaoyu Wang, Yingli Wang, Xicheng Zhang, Lingjiong Zhu
theoryhot direction similarity 0.74
Abstract · 70 pages, 9 figures

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.

0.52

Penalized Nonreversible Langevin for Constrained Sampling

cs.LG stat.MLmath.PR ·2026-09-21 ·Pervez Ali, Weihao Dong, Xiaoyu Wang
similarity 0.73
Abstract · 68 pages, 8 figures

We propose penalized nonreversible Langevin algorithms for sampling from $π(x)\propto e^{-f(x)}\mathbf 1_{\mathcal C}(x)$, where $\mathcal C\subset\mathbb R^d$ is a compact convex set. The algorithms combine a squared distance penalty with constant or compatible state dependent skew symmetric perturbations that preserve the penalized Gibbs distribution. For smooth, possibly nonconvex $f$, we derive nonasymptotic total variation bounds for the full gradient algorithm under a log Sobolev inequality. When unbiased stochastic gradients are available, we establish $2$-Wasserstein bounds under global contraction and Lipschitz conditions on the full drift in an adapted quadratic metric. For a fixed penalty parameter, the error relative to the penalized Gibbs distribution decays exponentially to an $\mathcal{O}(\sqrtη)$ neighborhood, where $η$ is the stepsize. We also bound the discrepancy between the penalized Gibbs distribution and the constrained target. In a two dimensional quadratic model, we establish nonreversible acceleration by tuning the skew perturbation to the curvature imbalance induced by penalization. With the target accuracy and smaller curvature fixed and initial Wasserstein distances uniformly bounded, tuning the skew perturbation improves the sufficient Euler iteration bound from linear to logarithmic in the curvature ratio. Numerical experiments evaluate the algorithms on constrained Bayesian regression, classification, neural networks, and truncated sampling, and examine the acceleration mechanism in a stochastic quadratic model.

0.17

Muon meets Tamed Langevin: Momentum Preconditioning beyond Convex and gradient-Lipschitz Potentials

cs.LG math.OCmath.PRstat.ML ·2026-10-01 ·Nikolaos Makras, Sotirios Sabanis
theory similarity 0.72
Abstract · 26pages

We consider the problem of sampling from Gibbs distributions on matrix spaces whose potential energies are neither convex nor globally gradient-Lipschitz. We introduce a family of non-quadratic kinetic energies that lead to a new underdamped Langevin system with momentum preconditioning, in which the gradient of the kinetic energy acts as a smooth spectral taming of the momentum. We prove that, under these relaxed assumptions on the potential, the resulting dynamics leaves the target Gibbs measure invariant, and we establish exponential convergence to equilibrium in a weighted total variation distance. Finally, we show that the corresponding Euler-Maruyama discretization admits moment bounds that are uniform in time, without any modification of the potential gradient, which ensures the stability of the resulting sampling algorithm.

0.42

Rényi Tracking Bounds for Langevin Dynamics with Moving Targets

cs.LG stat.ML ·2026-08-25 ·Yuchen Xin, Jingxin Zhan, Zhihua Zhang
similarity 0.70
Abstract

We study Langevin diffusion and Langevin Monte Carlo (LMC) when the target distribution changes over time. Under a log-Sobolev inequality (LSI), we derive non-asymptotic Rényi-divergence guarantees for tracking the current target. The framework covers continuous-time Langevin diffusion and its discretizations. We then apply the results to nonsmooth sampling based on successive Moreau envelopes. For this scheme, we give explicit choices of the smoothing parameters and step sizes, together with corresponding complexity bounds. To our knowledge, these are the first non-asymptotic Rényi-divergence tracking bounds for Langevin dynamics with discrete target updates.

0.33

First-Order Stationarity of Reverse Diffusions

cs.LG stat.ML ·2026-09-25 ·Zhifeng Chen, Chenyang Jiang, Yazhen Wang
similarity 0.70
Abstract

Recent literature has shown a strong connection between optimization and sampling. We develop the corresponding first-order theory for diffusion models. First, the SDE-based reverse-time flows of overdamped and underdamped Langevin diffusions contract relative Fisher divergences at explicit exponential rates whenever the stationary potential of the forward process is strongly convex---a condition on the noising process one chooses, not on the data. This is a unique advantage of SDE-based reverse diffusion, absent in the reverse process based on ODEs. Second, we incorporate discretization and establish averaged first-order stationarity bounds---the sampling analog of averaged gradient-norm guarantees in nonconvex optimization---for samplers of both overdamped and underdamped diffusion models. As in nonconvex optimization, the convexity-free certificate is local: it guarantees score consistency, not global mode weights.

0.15

Gradient-Free Sampling from Generative Models via Stochastic Bounded Extremum Seeking

cs.LG stat.MLmath.OCstat.CO ·2026-10-03 ·Alexander Scheinker
theory similarity 0.69
Abstract

We introduce a sampling approach for energy- and score-based generative models that requires no gradient evaluations of the model. Replacing the drift term that would normally contain the score $\nabla_\mathbf{x} \log p_θ(\bf{x})$ with a high-frequency dithered cosine of the model's \textit{value}, $\sqrt{αω}\,\cos(ωt + k \log p_θ(\bf{x}))$, produces, in the high-frequency averaging limit, Langevin Markov chain Monte Carlo for energy-based models and the reverse-time SDE of score-based diffusion. We prove that trajectories of the dithered Itô SDE converge to those of the target SDE, driven by the same Brownian motion, uniformly on compact time intervals in probability, by an averaging argument that extends bounded extremum seeking (ES) to Itô processes, with an explicit $O(ω^{-1/2})$ mean-square rate under global bounds. The approach is not confined to smooth targets: it extends to $C^{1,1}$ energies with discontinuous curvature (without ellipticity requirement) and to Sobolev energies whose Hessians exist only off measure zero sets; for Lipschitz energies with gradient kinks the averaged limit remains well posed; the Krylov-Röckner integrability class is the boundary of provability. The approach provides a hard \textit{a priori} bound on the per-step update rate and applies to explicitly time-varying targets on finite horizons. Gradient-free pixel-space sampling is not competitive with well-tuned backpropagation-based samplers at practical evaluation budgets; the regime where the approach offers an advantage is latent-space sampling when the model is a black box and the target drifts in time. We demonstrate latent-space tracking for time-varying images on CelebA-HQ ($256{\times}256$) from limited 1D projection measurements and latent-space EBM sampling on CIFAR-10.

0.41

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

cs.LG math.PRstat.COstat.ML ·2026-11-16 ·Stefan Oberdörster
theory similarity 0.68
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.

0.15

Near-Linear Accuracy Bounds for Moreau--Yosida Unadjusted Langevin Sampling

cs.LG ·2026-09-30 ·Yuchen Xin, Zhihua Zhang
similarity 0.67
Abstract

We establish near-linear accuracy bounds for the classical Moreau--Yosida unadjusted Langevin algorithm (MYULA). The target is $π\propto e^{-f-g}$, where $f\in C^2(\mathbb{R}^d)$ is $m$-strongly convex with Lipschitz gradient and $g$ is convex and globally Lipschitz. Under an explicit parameter-dependent step-size condition, we bound the invariant-measure bias relative to the Moreau-smoothed target by $\widetilde O(h)$, with only logarithmic dependence on the inverse smoothing parameter in the error coefficient. Combining this estimate with the Moreau approximation bias and Wasserstein contraction gives $\widetilde O(\varepsilon^{-1})$ iterations to make the $N$th-iterate law $μ_N$ satisfy $\sqrt m\,W_2(μ_N,π)\le\varepsilon$, for fixed model parameters and initialization. We bound the stationary error directly, without assuming third derivatives or a Lipschitz Hessian. Each iteration uses one gradient evaluation and one exact proximal evaluation. The key idea in our analysis is to convert a second-order stationary residual into a Wasserstein bound using a Poisson-based estimate.

0.07