PaperlayerView exact revision on arXiv

Source-linked AI summary

Underdamped Anchored Langevin Dynamics

Qi Feng, Hoang M. Nguyen, Lingjiong Zhu

arXiv:2610.36470v1cs.LGmath.PR

TL;DR

Non-differentiable and heavy-tailed targets remain challenging for Langevin methods, while prior approaches described here are overdamped. The paper proposes momentum-based UALD and its discretization, UALMC, and reports non-asymptotic guarantees with improved iteration-complexity dependence over overdamped anchored methods. It also cautions that classification accuracy need not distinguish an asymptotically unbiased sampler from a biased one.

  • Problem

    Existing approaches for non-differentiable and heavy-tailed targets are developed in the overdamped setting, while standard Langevin methods require differentiability and can face limitations on heavy-tailed targets.

    Source: §1 · pp. 2, 4

  • Method

    The paper proposes momentum-based underdamped anchored Langevin dynamics (UALD) and UALMC, which discretizes UALD using an exponential integrator that freezes state-dependent coefficients.

    Source: §1 · pp. 4–5

  • Results

    UALMC has a finite-time non-asymptotic convergence bound, and its iteration complexity improves on ALMC’s dependence on dimension and accuracy level.

    Source: §1 · p. 6

  • Takeaways & Limitations

    UALD preserves the Gibbs distribution as an invariant distribution and can sample Student’s t distributions with exponential convergence in time.

    Source: §1 · p. 6

    Classification accuracy need not distinguish an asymptotically unbiased sampler from a biased one; KLMC matches UALMC to within a point for several penalties at μ = 1/d and at every μ on Banknote.

    Source: §3.6 · p. 49

Abstract

from arXiv · show

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.

1 Introduction

The introduction presents UALD and its discretization, UALMC, as a momentum-based approach to sampling non-differentiable and heavy-tailed targets without asymptotic bias. It states invariant-distribution and non-asymptotic convergence results, including improved iteration-complexity dependence over overdamped anchored methods.

1 Introduction

  • UALD uses a smooth reference potential and multiplicative drift scaling, while UALMC discretizes UALD with an exponential integrator that freezes state-dependent coefficients.The method is introduced as an underdamped analogue of anchored Langevin dynamics.Source: §1 · pp. 4–5
  • The paper presents the first kinetic Langevin algorithm for non-differentiable targets that is free of asymptotic bias and has non-asymptotic guarantees.The introduction identifies earlier approaches for these targets as overdamped, while existing underdamped analyses assume differentiability.Source: §1 · pp. 3, 5
  • UALD preserves the Gibbs distribution as an invariant distribution and has a non-asymptotic 2-Wasserstein convergence bound; it can sample Student’s t distributions with exponential convergence in time.The convergence analysis uses synchronous coupling, perturbation control, and Lyapunov and exponential-moment bounds.Source: §1 · p. 6
  • UALMC has a finite-time non-asymptotic convergence bound, and its iteration complexity improves on ALMC’s dependence on dimension and accuracy level.The analysis accounts for frozen state-dependent speed, unbounded velocity and reference-potential gradients, and a weighted distance recursion.Source: §1 · p. 6
  • Experiments cover Laplace and heavy-tailed multivariate Student’s distributions, Bayesian logistic regression, and Bayesian neural networks on real data.The introduction reports these experiments as evidence of the proposed algorithm’s efficiency.Source: §1 · p. 6

2 Main Results

This section develops the main theoretical guarantees for UALD and UALMC, covering invariant distributions, convergence of the continuous dynamics and discrete algorithm, and sampling of polynomial-tailed targets. It also analyzes discretization error and iteration complexity under stated conditions.

2.1.1 Invariance distribution

  • The SDEs (1.6)–(1.7) preserve a Gibbs distribution as their invariant distribution.The supplied passage states this invariance result, but its displayed density formula is incomplete.Source: §2.1.1 · p. 7

2.1.2 Non-asymptotic convergence bound

  • For sufficiently small anchoring mismatch, UALD contracts in W2 at the positive rate 1/2(2κ−δ⋆).The contraction theorem gives a Lyapunov-weighted bound under Assumption 3(A)–(B); the W2 guarantee applies with finite initial Lyapunov moment.Source: §2.1.2 · pp. 15–17
  • For polynomial-tailed targets, the anchored force does not degenerate in the tails, unlike the true force, which vanishes there.The passage illustrates this distinction for a multivariate Student’s t target.Source: §2.1.2 · p. 17
  • Under Assumption 9, UALD has an explicit exponential L2 convergence guarantee for heavy-tailed targets, established through hypocoercivity, a weighted spectral gap, and weighted regularity.The weighted Poincaré inequality uses q^2 in its Dirichlet form, with confinement supplied by q^2 despite the polynomial tails.Source: §2.1.2 · pp. 18, 19, 20, 22, 23

2.2 Discrete-Time Analysis

  • The discrete analysis synchronously couples UALMC to the stationary continuous diffusion and accumulates a local discretization error of order η^2 at each step.The coupling propagates continuous contraction one step at a time.Source: §2.2 · p. 24

2.2.1 Notation and standing constants

  • Sufficiently small anchoring mismatch makes the discrete standing condition attainable and yields dimension-free mismatch and exponential-weight controls.The section states these consequences under the standing condition.Source: §2.2.1 · p. 25

2.2.2 Non-asymptotic error bounds

  • Under the standing condition and initialization assumptions, UALMC has a non-asymptotic 2-Wasserstein error bound for every iteration, with constants independent of dimension, iteration count, and stepsize.The theorem requires a sufficiently small stepsize; its local-error constant depends on the listed model and initialization parameters, but not on dimension, iteration count, or stepsize.Source: §2.2.2 · p. 26

2.2.3 Proof of Theorem 16

  • The proof of the discrete error theorem uses synchronous coupling and a continuous interpolation that recovers the scheme at step times.It couples the interpolation and a stationary copy using the same Brownian motion.Source: §2.2.3 · p. 27
  • A conditional weighted one-step contraction for the p-th power of the distance, for p in {1, 2}, controls the continuous-step term.The p = 2 case matches the weighted L4 distance used in the proof.Source: §2.2.3 · p. 29
  • Uniform polynomial moment bounds for the stationary path and iterates remove the A_j-dependence from the local error, unlike the deviation splitting used in classical KLMC.The proof bounds moments directly; the iterates have uniform bounds for p in [1, 8], and the path quantities entering the local error are bounded through order 16.Source: §2.2.3 · pp. 30, 32, 36
  • The local strong error is of order η², and after division by the contraction gap it produces the O(√d η) bias term in the recursion.The contribution to the local-error constant carrying c_F vanishes as U0 approaches U.Source: §2.2.3 · p. 38
  • Unlike classical KLMC, UALMC’s frozen state-dependent speed adds a velocity-quadratic local error, while its non-globally-Lipschitz anchored force adds an amplitude-dependent term.Both terms carry prefactor cF and vanish as U0 approaches U; controlling them requires uniform polynomial moment bounds, a weighted L4 metric, and p = 2.Source: §2.2.3 · p. 40
  • The standing condition requires ω1 = O(d^-1/2), inherited from the continuous perturbation argument, and keeps Cloc dimension-free.The dimension dependence is a caveat of the standing condition, not an effect introduced by discretization.Source: §2.2.3 · p. 41
  • UALMC improves over ALMC’s K = O~(d/ε^2) complexity by factors d in dimension and 1/ε in accuracy, while matching KLMC’s d/ε scaling.The guarantee controls W2(νK, πX) to ε; logarithmic factors and constants are suppressed in the stated complexity.Source: §2.2.3 · pp. 41–42

3 Numerical Experiments

The experiments test UALMC across synthetic Laplace and Student’s t targets, real-data logistic regression, and Bayesian neural networks. Their setups use smoothed reference potentials and compare samplers using measured Wasserstein error or classification accuracy.

3 Numerical Experiments

  • UALMC is evaluated on four tasks: synthetic Laplace sampling, Bayesian logistic regression, Bayesian neural-network inference, and synthetic heavy-tailed Student’s t sampling.The experiments use closed-form reference potentials.Source: §3 · p. 42

3.1 Setup

  • The product Laplace benchmark permits direct measurement of 2-Wasserstein distance to the target because its marginal quantile function is explicit.The reference potential is its closed-form Gaussian smoothing.Source: §3.1 · p. 43
  • Logistic-regression posteriors combine a Gaussian ridge prior with non-differentiable penalties, and the experiments compare five penalties on two UCI datasets.Runs use 20 particles and report training accuracy averaged over particles and three runs.Source: §3.1 · pp. 43–44
  • The neural-network experiments place non-differentiability in ReLU or leaky ReLU activations rather than the penalty, using smoothed activations in the reference potential.The Breast Cancer network has 992 parameters.Source: §3.1 · p. 44
  • The Student’s t experiments sweep degrees of freedom on both sides of the ν > 8 condition, while sampler comparisons include UALMC, ALMC, KLMC, and ULA.Reported discretization bias accounts for an empirical W2 sampling floor; iteration counts are medians over repetitions.Source: §3.1 · pp. 44–45

3.2 Invariance and the Anchoring Mechanism

UALD preserves the original target as its invariant distribution rather than the smoothed reference law. In the Laplace experiment, anchoring avoids the smoothing-dependent error seen in the unanchored sampler.

3.2 Invariance and the Anchoring Mechanism

  • UALD preserves π(x, v) ∝ e^(−∥v∥²/2−U(x)) as its invariant distribution, so it targets π rather than the smoothed law π0.This distinguishes it from smoothing-based methods such as [10], which converge to the smoothed target.Source: §3.2 · p. 45
  • At μ = 1, the unanchored sampler’s error to the Laplace target grows with μ, while the anchored sampler remains within sampling-floor noise.The floor is approximately 0.007 in this experiment.Source: §3.2 · p. 45
  • At μ = 1, anchoring improves W2 error by at least a factor of 30, and its error is insensitive to μ on this target.The anchored measurements at both reported μ values are within run-to-run noise of the estimator’s floor.Source: §3.2 · p. 45

3.3 Discretization Bias in the Step Size

On the product Laplace target, UALMC has lower discretization bias than ALMC at large step sizes and reaches the estimator’s resolution at larger steps. The observed W2 scaling is discussed in relation to the ALMC pathwise-error guarantee.

3.3 Discretization Bias in the Step Size

  • At d = 10 and η = 0.4, UALMC bias is 0.038 versus 0.280 for ALMC, an improvement of about 7× at the largest tested step size.For η ≤ 0.05, UALMC bias falls below the estimator’s resolution; Figure 1 plots bias against step size.Source: §3.3 · p. 45, Figure 1 · p. 46
  • At matched bias and d = 10, UALMC tolerates step sizes four to seven times larger; ALMC needs η ≈ 0.0125 to reach the same resolution.The fitted ALMC exponents are +1.14 at d = 10 and +1.04 at d = 30.Source: §3.3 · p. 46
  • The observed W2 error scaling near η^1 is compatible with ALMC’s η^(1/2) pathwise-error bound because distributional W2 error is typically one order better.The paper cautions that the theoretical bounds for both schemes may be conservative.Source: §3.3 · p. 46

3.4 Iteration Complexity in the Dimension

With friction held fixed, the measured dimension exponent approaches the predicted 1/2 as friction increases. Optimizing friction changes the scaling and trades dimensional performance against bias.

3.4 Iteration Complexity in the Dimension

  • At ε = 0.2 and γ = 5, the fitted exponent is +0.651, with Table 1 reporting iterations to W2 < 0.3 across fixed-friction runs.The table’s exponent approaches 1/2 as γ increases.Source: Table 1 · p. 47
  • At fixed γ = 5, the fitted exponent of K in d is +0.559, close to the predicted 1/2; Figure 2 shows the exponent against fixed γ.The exponent approaches 1/2 as γ grows.Source: §3.4 · p. 47, Figure 2 · p. 47
  • When γ is optimized too, the fitted exponent rises to +0.734 ± 0.027 at ε = 0.3; the observed optimal γ rises from 1 to 5 across the sweep.The reported account gives γ* ∝ d^0.3 and K ∝ d^0.8; smaller γ reduces fixed-d bias at the cost of worse dimensional scaling.Source: §3.4 · p. 47

3.5 Choice of the Smoothing Scale

The analysis requires a finite mismatch between the target and reference potentials; for separable penalties, that mismatch adds across coordinates. Although the assumption holds for every dimension and smoothing scale, keeping its constants bounded as dimension grows requires μ = O(1/d).

3.5 Choice of the Smoothing Scale

  • For separable penalties, the mismatch is additive across coordinates, and the Gaussian-smoothed ℓ1 mismatch is available exactly.The resulting mismatch bound is used in the convergence constants.Source: §3.5 · p. 48
  • Keeping the mismatch bound’s constants bounded as dimension grows requires μ = O(1/d).The finite-mismatch assumption itself holds for every dimension and every μ.Source: §3.5 · p. 48
  • At μ = 1, the median anchoring factor falls from 0.56 at d = 1 to 6.6 × 10−25 at d = 100, while at μ = 1/d it rises to 0.99.Because the position increment is multiplied by the anchoring factor, the chain is otherwise frozen; on Breast Cancer (d = 30), μ = 1 also collapses anchored accuracy to chance, unlike Banknote (d = 4).Source: §3.5 · p. 48

3.6 Non-Differentiable Regularizers

On Breast Cancer logistic regression, UALMC outperforms ALMC across five separable penalties, while the smoothing scale strongly affects results on the higher-dimensional data. Accuracy is useful for comparison, but does not by itself distinguish sampling from the target from sampling from the smoothed reference.

3.6 Non-Differentiable Regularizers

  • UALMC leads ALMC by 1.9 to 4.4 accuracy points across all five tested separable penalties on Breast Cancer.The penalties are Lasso, SCAD, MCP, elastic net, and capped ℓ1.Source: §3.6 · p. 48
  • Elastic net is the hardest tested penalty for every sampler, including KLMC and ULA, which do not use the anchoring factor.The authors attribute this drop to the target’s added ridge term, not to anchoring; smoothing adds only a constant mismatch per coordinate.Source: §3.6 · p. 49
  • At μ = 1, anchored methods collapse to chance on Breast Cancer (d = 30), while Banknote (d = 4) is insensitive to μ.The failure on Breast Cancer is consistent with exponential-in-d decay of the anchoring factor.Source: §3.6 · p. 49, Figure 4 · p. 49
  • Among scaled choices on Breast Cancer, μ = d−1/2 performs best here rather than μ = 1/d.Keeping the mismatch bound controlled motivates μ = Θ(1/d), but smaller μ sharpens the reference potential and increases its contribution to the smoothness constant.Source: §3.6 · p. 49
  • Classification accuracy need not distinguish an asymptotically unbiased sampler from a biased one: KLMC matches UALMC to within a point in several settings.This occurs at μ = 1/d for Lasso, SCAD, MCP, and capped ℓ1, and at every μ on Banknote; W2 experiments provide the discrimination.Source: §3.6 · pp. 49–50

3.7 Group Penalties

The group-lasso experiment extends the comparison to a non-differentiable penalty outside the separable piecewise-quadratic class. Its mismatch scale depends on the number of groups, and scaling μ accordingly restores strong accuracy and anchoring factors.

3.7 Group Penalties

  • The experiment uses a group-lasso penalty that is non-differentiable and outside the separable piecewise-quadratic class, with exact smoothing from Lemma 41.Coordinates are partitioned into contiguous groups, with the final group taking the remainder when group size does not divide d = 30.Source: §3.7 · p. 50
  • For fixed group size, the mismatch scale is set by the number of groups, so the requirement becomes μ = O(1/G).With equal group sizes, the mismatch expression has equality; coarser groups relieve but do not remove the pressure at fixed μ = 1.Source: §3.7 · p. 50
  • With μ = 1/G, group-lasso accuracy is 88.9–90.4% and the median anchoring factor is in [0.8, 1.0].At μ = 1, all three tested group sizes remain at chance.Source: §3.7 · p. 51

3.8 Heavy-Tailed Targets

On heavy-tailed Student’s t targets, anchoring substantially reduces bias relative to ULA on the smoothed potential, while taming trades accuracy for stability. The tamed iteration avoids divergence in the reported runs, including cases where the untamed iteration diverges.

3.8 Heavy-Tailed Targets

  • At η = 0.01, ULA on U0 has bias up to 1.90, versus at most 8.1 × 10−3 for ALMC inside the Assumption 9 range and the untamed kinetic iteration where it survives.The latter biases are at or near the estimator’s sampling floor of about 4 × 10−3; the tamed scheme has larger bias, 5 × 10−2 to 1.6 × 10−1.Source: §3.8 · p. 51
  • Figure 7 plots Student’s t bias against degrees of freedom ν at η = 0.01 for d = 3 and d = 10; the Assumption 9 threshold is ν > 8.The shaded band is below the estimator’s sampling floor; × marks untamed divergence in both runs.Source: Figure 7 · p. 52
  • The tamed scheme did not diverge in any of 80 runs, whereas the untamed iteration diverged in every run at ν = 3 and in 12 of 16 at ν = 5.Untamed runs also diverged at ν = 10 and 12 for d = 10, η = 0.05, both inside the Assumption 9 range.Source: §3.8 · p. 52
  • Taming trades accuracy for stability: where untamed runs survive, they are more accurate, but the tamed variant is the only compared iteration that never diverges.The tamed scheme’s bias is comparable to ULA at η = 0.01 and d = 10.Source: §3.8 · pp. 52–53
  • The tamed anchoring factor q/(1 + √η q) restores moment boundedness when q grows superlinearly.The authors state that explicit schemes with superlinearly growing coefficients lose moment boundedness.Source: §3.8 · p. 52

3.9 Bayesian Neural Network

On two real data sets, the anchored methods diverged at μ = 1, while scaled UALMC and KLMC remained stable. UALMC achieved 96.2–98.7% accuracy across data sets and activations, comparable to the best benchmarks.

3.9 Bayesian Neural Network

  • 96.2–98.7% accuracy across the data sets and activations; UALMC was comparable to the best benchmark on each.The experiments used a two-layer feedforward network with ReLU and leaky ReLU activations, smoothed by Corollary 39 without Monte Carlo.Source: §3.9 · p. 53
  • Under any scaled choice of μ, every UALMC and KLMC run was stable, while ALMC and ULA still diverged in some runs at η = 0.01.ULA's few divergences occurred on Breast Cancer at η = 0.01 for every μ choice.Source: §3.9 · p. 53
  • At μ = 1, anchored methods diverged within 25 iterations on both data sets and both activations, with overflow linked to a median scaling factor of 4 × 10^67 on Banknote.The factor was evaluated along the KLMC trajectory, which itself never uses it; KLMC did not diverge.Source: §3.9 · p. 53

4 Conclusion

The paper introduces UALD and its discretization, UALMC, for non-differentiable and heavy-tailed targets. It establishes non-asymptotic Wasserstein guarantees and reports better iteration-complexity dependence than overdamped anchored methods.

4 Conclusion

  • UALD and UALMC provide a momentum-based Langevin approach for non-differentiable and heavy-tailed targets that is free of asymptotic bias.The method uses a smooth reference potential and multiplicatively scales the drift in underdamped Langevin dynamics.Source: §4 · p. 53
  • The paper establishes non-asymptotic guarantees in 2-Wasserstein distance to the target distribution.Source: §4 · p. 53
  • UALMC's iteration complexity has better dependence on dimension and accuracy level than overdamped-based anchored Langevin algorithms (ALMC.Numerical experiments illustrate the theory and practical performance.Source: §4 · p. 53

A Non-Smooth Sampling

For non-smooth targets, the paper smooths the non-smooth component while retaining a smooth strongly convex component. Its assumptions and cited smoothing results bound the resulting potential and subdifferential mismatch, which can be reduced by tuning μ.

A Non-Smooth Sampling

  • Writing U as a smooth function f plus a non-smooth function g lets the underdamped anchored method use a smoothed reference potential U0.The setup assumes g is Lipschitz and weakly convex, while f is differentiable, smooth, and strongly convex.Source: A Non-Smooth Sampling · p. 60
  • Gaussian smoothing defines g0, with μ as a tunable smoothing parameter; the cited results bound the differences between U and U0 and between their subdifferentials, with mismatch reducible by choosing μ small.Source: A Non-Smooth Sampling · pp. 60–61
  • The assumptions cover examples including the ℓ1 norm, SCAD, and MCP regularizers, whose non-smooth component is weakly convex and Lipschitz.Source: A Non-Smooth Sampling · p. 60
  • For the stated composite potential, the assumptions yield a subdifferential mismatch bound that meets the dimension-dependent O(d^-1/2) requirement when μ = O(d^-2).The bound is given in the sense of the Clarke subdifferential.Source: A Non-Smooth Sampling · p. 61

B Closed-Form Gaussian Smoothing

The appendix derives closed-form Gaussian smoothings for continuous piecewise-quadratic functions and applies them to common penalties and activations. It also gives a distinct formula for group ℓ2 penalties and compares mismatch behavior for capped ℓ1 and Lasso.

B Closed-Form Gaussian Smoothing

  • For continuous piecewise-quadratic p, Gaussian smoothing and its derivative follow by partitioning at breakpoints and summing interval contributions.The formulas use breakpoint-based quantities Pj, Mj, and Qj; the lemma also covers piecewise-linear activations.Source: B Closed-Form Gaussian Smoothing · pp. 61–62
  • The appendix supplies closed-form smoothing formulas for Lasso, MCP, and SCAD, with the smoothed Lasso identified as a Huber-type function.The formulas also give smoothness information used in the method's assumptions.Source: B Closed-Form Gaussian Smoothing · pp. 62–63
  • For ReLU, Gaussian smoothing yields an explicit smoothed activation and derivative; the leaky variant reduces to ReLU at α = 0 and the identity at α = 1.Source: B Closed-Form Gaussian Smoothing · p. 64
  • Capped ℓ1 mismatch is at most λ min{θ, μ√(2/π)}, whereas Lasso mismatch grows linearly with μ as λμ√(2/π).The capped penalty's mismatch saturates with bandwidth μ, so θ varies mismatch without varying penalty scale.Source: B Closed-Form Gaussian Smoothing · pp. 64–65
  • For group penalties g(x) = λ∥x∥2, the smoothing is expressed using the mean of a noncentral χ variable, with a radial gradient obtained by differentiating the hypergeometric expression.Source: B Closed-Form Gaussian Smoothing · pp. 65–66

Related papers

Loading 2610.36470v1…