PaperlayerView exact revision on arXiv

Source-linked AI summary

Consistency and fluctuations for stochastic gradient Langevin dynamics

Yee Whye Teh, Alexandre Thiéry, Sebastian Vollmer

arXiv:1409.0578v2stat.ML

TL;DR

Large-data MCMC can be computationally expensive because gradients and acceptance ratios require full-data processing. The paper rigorously analyzes SGLD, which uses stochastic gradients, skipped accept-reject steps, and decreasing step sizes. It establishes consistency and fluctuation results, finding that δm ≍ m^-1/3 is asymptotically optimal and gives MSE rate O(m^-1/3).

  • Problem

    Large-data MCMC requires computational work scaling with the full data set for gradients and Metropolis-Hastings acceptance ratios.

  • Method

    The paper provides a rigorous asymptotic framework for SGLD using stochastic gradients, decreasing step sizes, and weighted estimators.

  • Results

    δm ≍ m^-1/3 is asymptotically optimal and yields MSE convergence at O(m^-1/3).

  • Takeaways & Limitations

    SGLD is supported as a sound algorithm, with δm ≍ m^-1/3 recommended for asymptotic tuning.

  • Takeaways & Limitations

    The results are asymptotic and may not predict behavior under finite computational budgets; the analysis also excludes heavy-tailed and several complex target settings.

Abstract

from arXiv · show

Applying standard Markov chain Monte Carlo (MCMC) algorithms to large data sets is computationally expensive. Both the calculation of the acceptance probability and the creation of informed proposals usually require an iteration through the whole data set. The recently proposed stochastic gradient Langevin dynamics (SGLD) method circumvents this problem by generating proposals which are only based on a subset of the data, by skipping the accept-reject step and by using decreasing step-sizes sequence $(δ_m)_{m \geq 0}$. %Under appropriate Lyapunov conditions, We provide in this article a rigorous mathematical framework for analysing this algorithm. We prove that, under verifiable assumptions, the algorithm is consistent, satisfies a central limit theorem (CLT) and its asymptotic bias-variance decomposition can be characterized by an explicit functional of the step-sizes sequence $(δ_m)_{m \geq 0}$. We leverage this analysis to give practical recommendations for the notoriously difficult tuning of this algorithm: it is asymptotically optimal to use a step-size sequence of the type $δ_m \asymp m^{-1/3}$, leading to an algorithm whose mean squared error (MSE) decreases at rate $\mathcal{O}(m^{-1/3})$

1. Introduction

The paper addresses scalable Bayesian inference by studying how stochastic-gradient approximations affect SGLD, and develops asymptotic guarantees and step-size guidance.

  • Motivation: Large data sets motivate scalable Bayesian methods because available data have outpaced computational resources.
  • SGLD analysis: SGLD combines stochastic-gradient estimates with Langevin dynamics while using decreasing step sizes to control approximation effects.
  • Contributions: The paper proves SGLD consistency, a central limit theorem, bias-variance characterizations, and convergence of suitably rescaled sample paths to Langevin diffusion.
  • Step-size tuning: α⋆=1/3 is asymptotically optimal for algebraically decaying step sizes, yielding MSE convergence at O(m^-1/3).The rate is worse than standard Monte Carlo's m^-1/2 rate because of decreasing step sizes, not stochastic gradients.
  • Scope: The results are asymptotic and may not describe finite-budget behavior, where SGLD could provide computational gains.

2. Stochastic Gradient Langevin Dynamics

SGLD avoids full-data Metropolis-Hastings computation by combining Langevin discretization with unbiased stochastic gradients, then analyzes its weighted posterior estimators.

  • Langevin foundation: Langevin diffusion provides a continuous-time process whose generator and ergodicity motivate MCMC discretizations targeting π.
  • Computational motivation: In the Big Data regime, computing gradients and Metropolis-Hastings ratios costs O(N), motivating subset-based alternatives.
  • Algorithm: SGLD avoids the Metropolis-Hastings ratio and uses small-step Langevin discretization, hoping to retain an invariant distribution close to π.
  • Stochastic gradients: The stochastic gradient is unbiased and can be computed with budget O(n), where n may be much smaller than N.
  • Algorithm: SGLD updates form a non-homogeneous Markov chain using vanishing step sizes, Gaussian noise, and auxiliary random variables.
  • Estimators: Posterior expectations are approximated by step-size-weighted sums that correspond to ergodic averages over Langevin time.
  • Paper focus: The paper establishes rigorous foundations for SGLD, including consistency, fluctuation results, and explicit bias-variance analysis.

3. Assumptions and Stability Analysis

The stability analysis imposes vanishing-step-size and Lyapunov conditions that control Euler discretization and stochastic drift, enabling consistency results while limiting scope.

  • Basic assumptions: The step sizes must vanish while cumulative time diverges, with additional oscillation conditions for weighted averages.
  • Basic assumptions: Algebraic schedules δm=(m0+m)^-α satisfy the basic conditions for 0<α<1, with suitable weighted sequences.
  • Stability: Continuous-time stability does not guarantee stable Euler discretization because excessive drift magnitude can cause overshooting and divergence.
  • Stability conditions: Lyapunov conditions control both drift direction and magnitude, supporting SGLD consistency and the LLN and CLT analyses.
  • Stability results: Under the stability assumptions, moment bounds hold almost surely for specified exponents, and weighted ergodic averages satisfy analogous results.
  • Verification: The assumptions can be verified from prior and likelihood gradient growth conditions in posterior models.
  • Scope of the analysis: The analysis excludes heavy-tailed targets and generally does not cover challenging high-dimensional, multimodal, or nonparametric settings.

4. Consistency

Under step-size and stability assumptions, SGLD empirical averages converge almost surely to the target posterior, including weighted averages, establishing consistency.

  • Scope and extensions: The analysis adapts prior diminishing-step-size Euler-discretization techniques to SGLD, where the drift is available only through unbiased stochastic estimates.The weighted-average extension requires additional oscillation conditions on the weight sequence.
  • Consistency: Theorem 7 establishes almost-sure convergence of SGLD empirical averages to posterior expectations for test functions controlled by a Lyapunov function.The result also covers weighted ergodic averages under additional assumptions on the weights.
  • Consistency: The proof first establishes weak convergence of the empirical measures, then upgrades it to convergence for potentially unbounded test functions using Lyapunov moment bounds.Weak pre-compactness follows from the Lyapunov function, while truncation and extension arguments handle broader test functions.
  • Proof strategy: The consistency proof decomposes empirical averages into martingale, boundary, and discretization terms, each shown to vanish asymptotically.The discretization remainder satisfies |R_k| ≤ C δ_{k+1}^3/2, and the normalized remainder converges to zero under the step-size assumptions.

5. Fluctuations, Bias-Variance Analysis, and Central Limit Theorem

The paper decomposes SGLD estimation error into fluctuations and discretization bias, characterizes three asymptotic regimes, and identifies the step-size rate balancing them.

  • Fluctuations and CLT: Theorem 8 characterizes SGLD fluctuations through a central limit theorem under Lyapunov, step-size, and Poisson-equation regularity assumptions.The fluctuation term converges at Monte-Carlo scale to a Gaussian distribution with variance σ2(ϕ).
  • Asymptotic regimes: Three regimes arise: fluctuations dominate when B_m → 0, bias and fluctuations balance when B_m → B_∞ ∈ (0,∞), and bias dominates when B_m → ∞.The corresponding rescaled limits are centered Gaussian, non-centered Gaussian, and convergence in probability to the bias functional, respectively.
  • Bias-variance decomposition: The error decomposes into a fluctuation term, a bias term, and an asymptotically negligible remainder.The bias is determined by a step-size functional, while the fluctuation term is handled using a martingale central limit theorem.
  • Step-size tuning: For δ_m = (m_0 + m)^−α, the optimal rate occurs at α = 1/3, yielding convergence at rate m^−1/3.Fluctuations dominate for 1/3 < α ≤ 1, balance bias and fluctuations at α = 1/3, and bias dominates for 0 < α < 1/3.

6. Diffusion limit

On the appropriate inhomogeneous time scale, linearly interpolated SGLD paths converge weakly to the continuous-time Langevin diffusion under a globally Lipschitz drift condition.

  • Diffusion limit: The sample path of SGLD converges to the continuous-time Langevin diffusion when observed on the appropriate inhomogeneous time scale.This confirms the heuristic that diminishing step sizes recover the diffusion limit.
  • Proof strategy: The proof couples interpolated SGLD chains to Brownian motion and represents each path as an Itô-map image plus an asymptotically negligible error.The Brownian driving processes converge weakly to standard Brownian motion, while the error vanishes in probability under the supremum norm.
  • Discretization: The vanishing mesh of the step-size partition ensures convergence of the piecewise affine Brownian approximations and associated error terms.This mesh condition is the key discretization requirement in the stated diffusion-limit theorem.
  • Regularity condition: Global Lipschitz continuity of the drift makes the Itô map well-defined and continuous, enabling the Continuous Mapping Theorem.The limiting Itô-map image of standard Brownian motion is the Langevin diffusion.

7. Numerical Illustrations

Numerical experiments on Gaussian and logistic-regression models confirm the predicted SGLD convergence regimes and examine subsampling and comparisons with MALA. The fastest asymptotic MSE decay occurs near α = 1/3, while finite-budget experiments investigate tuning and computational efficiency.

  • Experimental setup: The experiments use a Gaussian toy model and a Bayesian logistic-regression problem to test SGLD theory under the required assumptions.The Gaussian experiment uses N = 100 observations and gradient-estimation subsets of size n = 10; the logistic-regression experiment uses d = 3 and N = 1000.
  • Comparison with MALA: The experiments investigate whether SGLD can be advantageous over MALA when the computational budget permits only a few passes through the data.The comparison limits the algorithms to 200 and 1000000 likelihood evaluations in the two SGLD tuning regimes.
  • Linear Gaussian model: The fastest theoretical and observed MSE decay is achieved at α = 1/3 for step sizes δm ≍ m−α.Estimated log-log slopes match Theorem 8, whose best decay rate is 2/3 at α = 1/3.
  • Linear Gaussian model: For α > 1/3, the MSE scales as Tm−1, whereas for α < 1/3 it decays more slowly.The MSE multiplied by Tm remains flat in the faster regime and diverges in the slower regime.
  • Subsampling: The Gaussian simulations vary subsample sizes n = 1, 5, 10, 50, 100 while measuring MSE against likelihood evaluations.This experiment examines how the subsampling scheme affects estimation at α = 0.33.
  • Comparison with MALA: In logistic regression, SGLD and MALA are compared using estimates of the posterior variance of the first component.For SGLD with n = 30, step sizes δm = (a · m + b)−0.38 are tuned using 512 independent runs and evaluated after 20 and 1000 effective iterations.

8. Conclusion

The paper establishes rigorous asymptotic foundations for SGLD, including consistency, a CLT, bias-variance characterization, and a diffusion limit. It recommends δ_m ≍ m^-1/3 for optimal asymptotic MSE decay, while emphasizing limitations of asymptotic conclusions for finite budgets.

  • 8. Conclusion: The step-size-weighted estimator is consistent, satisfies a central limit theorem, and has an explicit asymptotic bias-variance functional.The analysis also establishes a Langevin diffusion approximation on the appropriate inhomogeneous time scale.
  • 8. Conclusion: δ_m ≍ m^-1/3 is asymptotically optimal for algebraically decaying step sizes, yielding convergence at rate m^-1/3.This recommendation differs from the previously suggested δ_m ≍ m^-1/2 choice.
  • 8. Conclusion: The asymptotic rate is less efficient than standard MCMC because decreasing step sizes, rather than stochastic gradients themselves, determine the rate loss.Decreasing step sizes are required to reduce discretization bias caused by omitting Metropolis-Hastings correction.
  • 8. Conclusion: The results are asymptotic and may not describe finite-budget behavior, where SGLD could still provide computational gains over alternatives.The paper identifies non-asymptotic transient behavior as an open research direction.

Appendix A. Proof of Lemma 6

The proof of Lemma 6 reduces the required convergence statement to almost-sure finiteness of weighted sums, then invokes martingale convergence and a stated condition.

  • Appendix A. Proof of Lemma 6: Kronecker’s Lemma supplies the convergence framework for the nondecreasing positive normalization sequence b_m tending to infinity.The lemma relates convergence of a series to normalized partial sums.
  • Appendix A. Proof of Lemma 6: The required finiteness follows from Condition (16), via the L2 martingale convergence theorem, together with Condition (17).Both conditions are used to complete the summability argument.

Appendix B. Proof of Lemma 5

The proof of Lemma 5 builds moment bounds for SGLD through a discrete Lyapunov condition, then derives weighted-average and target-distribution integrability results.

  • Appendix B. Proof of Lemma 5: The multidimensional proof is analogous to the scalar presentation, whose assumptions include bounds on derivatives, gradients, and stochastic-gradient moments.The argument repeatedly invokes these regularity and growth conditions.
  • Appendix B. Proof of Lemma 5: The proof first establishes a Lyapunov-type condition for the process m ↦ V^p(θ_m).This condition is the main device used to control moments along the SGLD trajectory.
  • Appendix B. Proof of Lemma 5: Taylor expansion, drift bounds, and moment assumptions control the one-step change in V^p(θ_m).The argument bounds both the drift contribution and the Taylor-remainder term.
  • Appendix B. Proof of Lemma 5: Inductive use of the discrete Lyapunov equation yields finite expectations of V^p(θ_m) under the stated moment conditions.The proof then uses these bounds to control weighted sums and averages.
  • Appendix B. Proof of Lemma 5: The proof establishes finiteness of π(V^p) and related weighted quantities using drift conditions, Lipschitz bounds, and results for Langevin diffusion.Several auxiliary limits are obtained almost surely under the listed assumptions.
Loading 1409.0578v2…