Source-linked AI summary
Theoretical guarantees for stochastic gradient Langevin dynamics
Daniel Paulin, Peter A. Whalley
TL;DR
Full-gradient evaluations can be expensive for log-densities that sum over large datasets, motivating stochastic gradient Langevin dynamics. The paper analyzes stochastic gradient Langevin dynamics using convergence results and asymptotic bias estimates under assumptions on the gradient error. The bias bound is order h for finite fourth moment and order h^1/2 with only a second moment; no uniform order-h bound holds across fixed-variance noise laws.
Problem
Full-gradient evaluations can be expensive for log-densities that sum over large datasets, motivating stochastic gradient Langevin dynamics.
Source: §1 · p. 1Method
Results
Takeaways & Limitations
Uniform order-h bias bounds require additional tail control beyond a fixed second moment.
Source: §5 · p. 6The examples demonstrate the need for additional tail control to provide uniform first-order bias bounds.
Source: §5 · p. 6
Abstract
from arXiv · showhide
We prove asymptotic bias bounds for stochastic gradient Langevin dynamics in Wasserstein distance of order two. We assume that the negative log-density is strongly convex with a Lipschitz gradient, and that the stochastic gradient estimator is unbiased with an error satisfying a mean-square Lipschitz condition. The bounds are of order $h$ under a fourth moment assumption on the stochastic gradient error and of order $h^{1/2}$ under only a second moment assumption, where $h$ is the stepsize. A spiked-noise example shows that a second moment assumption alone is insufficient for a bound of order $h$ that is uniform over noise distributions with a fixed variance.
1 Introduction
The paper studies the Wasserstein-2 asymptotic bias of stochastic gradient Langevin dynamics and proves stepsize-dependent bounds under different moment assumptions. It also shows that second moments alone cannot guarantee a uniform order-h bound over fixed-variance noise distributions.
1 Introduction
- Unbiased stochastic gradients reduce the cost of evaluating full gradients, which can be expensive when the log-density sums over a large dataset.The scheme replaces the gradient of V with a stochastic estimator and defines its error as the estimator minus the true gradient.Source: §1 · p. 1
- Unbiasedness does not ensure that the scheme’s invariant law equals either the unadjusted Langevin invariant law or the target distribution.The paper therefore aims to quantify the asymptotic bias relative to the target in Wasserstein distance of order two.Source: §1 · p. 2
- Earlier work used weak-error expansions and non-asymptotic Wasserstein bounds; synchronous coupling gives an order h^1/2 stochastic-gradient contribution, while order h results used other assumptions [LW25; PW26a].The cited order-h approaches rely on stronger conditions, including bounded gradient errors and a warm start for, or concern a kinetic Langevin method for.Source: §1 · p. 2
- Order h bias bounds require a fourth moment of the stochastic gradient error, while a second-moment assumption gives order h^1/2; a spiked-noise example rules out uniform order h from variance alone.The paper also notes that the square-root bound can be preferable when the fourth moment is large or infinite.Source: §1 · p. 2
- The article proceeds from assumptions and convergence to invariant measure, to asymptotic bias and convergence guarantees, and then to a spiked-noise example.That example shows why a second moment alone is insufficient for a uniform order-h bias bound across fixed-variance noise distributions.Source: §1 · p. 2
2 Assumptions and convergence
This section establishes convergence of the stochastic-gradient scheme to its invariant measure under assumptions on the error and stepsize. It distinguishes that convergence from bounding the invariant measure’s bias relative to the target.
2 Assumptions and convergence
- The mean-square condition on stochastic-gradient error allows its variance to depend on position and is used to establish convergence to the invariant measure.The supplied passage states that this condition is sufficient for the proof.Source: §2 · pp. 2–3
- For the unadjusted Langevin algorithm, the cited result bounds the scaled Wasserstein-2 discretization bias by 6hβ under Assumption 1.The bound concerns π_h relative to π.Source: §2 · p. 3
- Under Assumptions 1 and 2 and the stepsize condition, the chain has a unique invariant law in P2, and its iterates converge toward that law.The proof uses contraction in Wasserstein-2 under the stated stepsize condition.Source: §2 · p. 3
- Convergence to the scheme’s invariant measure is distinct from convergence to the target; the latter also requires a bound on their Wasserstein-2 distance.The section identifies this bias bound as the focus of the subsequent section.Source: §2 · p. 3
3 Asymptotic bias bounds
The section bounds SGLD’s asymptotic bias by coupling it to the unadjusted Langevin scheme and comparing their invariant laws. The bound is O(h) with a finite fourth moment of the stochastic-gradient error and O(h^1/2) with only a second moment.
- For fixed α, β, and C_G, finite σ_4 gives an O(h) bound, while only σ_2 < ∞ gives an O(h^1/2) bound.Source: §3 · p. 3
- The proof couples the two chains and bounds their mean-square difference uniformly over iterations.Source: §3 · p. 4
- A common Gaussian vector and an optimal conditional coupling are used to couple the stepwise noise terms.Source: §3 · p. 4
- Convergence to the scheme’s invariant law lets the proof pass from a finite-iteration coupling bound to an asymptotic bias estimate.Source: §3 · p. 5
4 Iteration complexity
The section combines convergence to the scheme’s invariant law with the asymptotic bias bounds to obtain iteration guarantees. The transient term decays geometrically, while the remaining error terms depend on the available noise moments.
- The transient term decreases geometrically, while the remaining terms are O(h) for finite σ_4 and O(h^1/2) under only a second moment.Source: §4 · p. 5
- Accuracy is measured using √α W_2 as a scale-invariant quantity.Source: §4 · p. 5
- Corollary 1 specializes the combined convergence bound for ε > 0 and an initial law μ ∈ P2(R^d).Source: §4 · p. 5
5 Dependence on the noise distribution
The section shows that fixed variance alone cannot ensure a uniform first-order bias bound: rare, large gradient-error spikes can preserve variance while producing square-root-order behavior. A tensorized example further shows adverse dimension dependence for spiked noise compared with Gaussian noise of the same covariance.
5 Dependence on the noise distribution
- For pi=N(0,1), p=10^-8, and sigma=2, Figure 1 compares stationary bias with reference curves proportional to h and h^1/2.The plotted bias is computed by numerical inversion of the stationary characteristic function; the section reports a crossover from approximately square-root to linear dependence as h decreases.Source: Figure 1 · p. 6, §5 · p. 6
- Decreasing p concentrates the stochastic gradient error in rarer, larger spikes while preserving its variance.The example uses a standard Gaussian target and a spike-law stochastic gradient error.Source: §5 · pp. 5–6
- No first-order bound holds uniformly over the fixed-variance spike family, establishing the sharpness of square-root stepsize order across noise laws.For fixed p=10^-8, the bias crosses from approximately square-root to linear dependence on h as h decreases.Source: §5 · p. 6
- At h=d^-1/2, the spiked-noise bias grows as d^1/4, whereas Gaussian gradient noise with the same covariance remains bounded.The worst-case bias relative to the d-dimensional target has the same d^1/4 growth, motivating additional tail control for uniform first-order bounds.Source: §5 · p. 6
A Proof of Lemma 1
The proof works with distribution and quantile functions, uses quantile coupling to control a Wasserstein distance, and combines a limiting representation with a matching upper bound.
A Proof of Lemma 1
- The proof sets up distribution and quantile functions for the two invariant measures and uses quantile coupling, optimal for Wasserstein distance of order one, to control their difference.The setup fixes 0<h≤1 and considers the invariant measures of the stochastic and unadjusted schemes.Source: A Proof of Lemma 1 · pp. 7–8
- Dominated convergence as M→∞ yields a limiting one-dimensional representation of the Wasserstein distance.Source: A Proof of Lemma 1 · p. 8
- Coupling G_h+S_{h,p} with G_h supplies the matching upper bound.Source: A Proof of Lemma 1 · p. 8