Classical Langevin Monte Carlo algorithms, such as the unadjusted Langevin algorithm (ULA), are based on discretization schemes of the overdamped Langevin dynamics and are widely used for sampling in machine learning because they scale to high dimensions and large datasets. However, they require differentiable log-densities, and are less efficient for sampling heavy-tailed distributions. Although various approaches have been proposed in the literature for sampling non-differentiable and heavy-tailed targets, all of them are developed in the overdamped setting only. We propose a novel momentum-based underdamped anchored Langevin dynamics (UALD), and underdamped anchored Langevin Monte Carlo (UALMC) algorithm based on a discretization scheme of UALD. Our paper is the first to provide a kinetic (momentum-based) Langevin algorithm for non-differentiable and heavy-tailed targets that is free of asymptotic bias. The method replaces the original potential with a smooth reference potential and modifies the underdamped Langevin dynamics via multiplicative scaling in the drift term. We establish non-asymptotic guarantees in the 2-Wasserstein distance to the target distribution and show that the resulting iteration complexity has better dependence on dimension and accuracy level compared to overdamped-based anchored Langevin algorithms. We provide numerical experiments to illustrate the theory and practical performance of our proposed approach.
Figures & tables
Figure 1: Discretization bias against step size on the product Laplace target, μ=1/d , after T=300 of simulated time, for UALMC ( 1.8 ) with γ=1.5L and ALMC [ 39 ] ; one run per step size. Dotted: the estimator’s sampling floor; points whose measured W2 does not exceed the floor are omitted.
Figure 2: Fitted exponent of K in d , with γ held fixed across the sweep as in Corollary 25 , against the value at which it is held. Dashed: the exponent 1/2 of Corollary 25 .
γ
d=1
2
5
10
20
50
100
exponent
1
10
20
75
100
132
352
412
+0.811
2
15
20
50
105
140
415
452
+0.803
3
15
25
35
70
160
218
525
+0.760
5
25
35
45
62
108
255
280
+0.559
Table 1: Iterations to W2<0.3 on the product Laplace target, μ=1/d , minimized over the step size with γ held fixed, medians over four repetitions. The exponent approaches the 1/2 of Corollary 25 as γ grows; at ε=0.2 the value at γ=5 is +0.651 .
Figure 3: Left: median anchoring factor ak=eU−U0 at draws from the target. Right: bias against friction at d=5 , η=0.02 ; dashed: γ=L , the threshold of Proposition 2 .
Figure 4: Bayesian logistic regression with the ℓ1 penalty and exact Gaussian smoothing, final accuracy against the choice of μ , for both data sets and all four samplers. Dotted: chance level. The anchored methods fail at μ=1 on Breast Cancer ( d=30 ) and are unaffected on Banknote ( d=4 ), as ( 3.10 ) predicts.
Figure 5: Bayesian logistic regression on Breast Cancer ( n=569 , d=30 ) with mixed penalty U=f+m0∥x∥2+g , exact Gaussian smoothing, μ=1/d .
Figure 6: Group-lasso logistic regression on Breast Cancer, UALMC. Left: accuracy. Right: median anchoring factor. Dotted: chance level.
Figure 7: Student’s t target ( 3.9 ), bias against degrees of freedom ν at η=0.01 for d=3 (left) and d=10 (right), mean of two runs. The shaded band lies below the estimator’s sampling floor; an open marker on its edge means the bias is not resolvable in both runs. × : the untamed iteration diverged in both runs. Where it survives, its bias cannot be told apart from that of ALMC (the two runs overlap, or the bias is not resolvable), so it is not drawn separately. Assumption 9 requires ν>8 .
Markov Chain Monte Carlo uses Markov chains designed to have a target distribution as their stationary law, enabling sampling and statistical estimation.
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
Anchored Langevin dynamics (ALD) is useful for non-smooth sampling where the density of the target distribution is possibly non-differentiable and heavy-tailed; reflected anchored Langevin dynamics (RALD) can sample possibly non-differentiable target density on a constrained domain. In this paper, we propose and study non-reversible anchored Langevin dynamics (NALD) for sampling possibly non-differentiable and heavy-tailed target density in the Euclidean space and the non-reversible reflected anchored Langevin dynamics (NRALD) for sampling possibly non-differentiable target density in the constrained space. Our construction adds a circulation drift generated by a possibly state-dependent divergence-free skew-symmetric matrix field and a stream potential. It preserves the target distribution without requiring derivatives of target density, admits a random-time-change representation, and applies both on the whole Euclidean space and on bounded domains with normal reflection. By breaking reversibility, we show that NALD and NRALD can converge to their target distributions faster than their reversible counterparts via finite-time non-asymptotic convergence analysis, a large deviations analysis and asymptotic variance reduction. Numerical experiments demonstrate the efficiency of the proposed algorithms.
Pervez Ali, Xiaoyu Wang, Yingli Wang +1
Department of Mathematics, Florida State University, Tallahassee, Florida, United States of America · Fintech Thrust, 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
Underdamped Langevin dynamics (ULD) is a widely-used sampler for Gibbs distributions π∝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 tr(H), where 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 tr(H)≪d.
Shiyuan Zhang, Qiwei Di, Xuheng Li +1
Department of Computer Science, University of California, Los Angeles, CA 90095, USA