PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators

Changyou Chen, Nan Ding, Lawrence Carin

arXiv:1610.06665v1stat.ML

TL;DR

Large-scale Bayesian sampling needs SG-MCMC theory beyond SGLD with first-order Euler integration. The paper analyzes general SG-MCMCs with high-order integrators and their finite-time convergence and invariant measures. The proposed second-order symmetric splitting method improves convergence rates and empirical performance, while decreasing-step-size variants can share fixed-step-size rates.

  • Problem

    Finite-time convergence theory for general SG-MCMCs beyond SGLD with a first-order Euler integrator had not been explored.

  • Method

    The paper develops convergence and invariant-measure analysis for general SG-MCMCs with high-order numerical integrators and proposes an efficient second-order symmetric splitting integrator.

  • Results

    Higher-order integrators provide faster convergence rates and more accurate invariant measures; the proposed method outperforms Euler-based SGLD and SGHMC in experiments.

  • Takeaways & Limitations

    Increasing integrator order can theoretically move SG-MCMC convergence toward the standard MCMC rate, supporting effective use in real applications.

  • Takeaways & Limitations

    The asymptotic unbiasedness advantage of decreasing-step-size SG-MCMCs may not be significant when large-scale applications have not reached the asymptotic regime.

Abstract

from arXiv · show

Recent advances in Bayesian learning with large-scale data have witnessed emergence of stochastic gradient MCMC algorithms (SG-MCMC), such as stochastic gradient Langevin dynamics (SGLD), stochastic gradient Hamiltonian MCMC (SGHMC), and the stochastic gradient thermostat. While finite-time convergence properties of the SGLD with a 1st-order Euler integrator have recently been studied, corresponding theory for general SG-MCMCs has not been explored. In this paper we consider general SG-MCMCs with high-order integrators, and develop theory to analyze finite-time convergence properties and their asymptotic invariant measures. Our theoretical results show faster convergence rates and more accurate invariant measures for SG-MCMCs with higher-order integrators. For example, with the proposed efficient 2nd-order symmetric splitting integrator, the {\em mean square error} (MSE) of the posterior average for the SGHMC achieves an optimal convergence rate of $L^{-4/5}$ at $L$ iterations, compared to $L^{-2/3}$ for the SGHMC and SGLD with 1st-order Euler integrators. Furthermore, convergence results of decreasing-step-size SG-MCMCs are also developed, with the same convergence rates as their fixed-step-size counterparts for a specific decreasing sequence. Experiments on both synthetic and real datasets verify our theory, and show advantages of the proposed method in two large-scale real applications.

1 Introduction

The paper studies SG-MCMCs for scalable Bayesian sampling, focusing on how higher-order numerical integrators affect convergence and invariant-measure accuracy. It develops general theory beyond prior analyses centered on SGLD with Euler integration and introduces a practical second-order method.

  • Motivation: Exact diffusion sampling is generally infeasible because Itô diffusions are continuous-time Markov processes.
  • Scalable SG-MCMC approximations: SG-MCMC replaces continuous-time diffusion integration with numerical steps and full gradients with minibatch stochastic gradients for scalable sampling.These approximations make sampling numerically feasible for massive datasets, though they introduce convergence concerns.
  • Research gap: The paper extends convergence analysis from SGLD with a first-order Euler integrator to general SG-MCMCs using high-order integrators.
  • Main theoretical result: For a Kth-order integrator, bias scales as L^-K/(K+1) and MSE as L^-2K/(2K+1) under their respective optimal step sizes.The optimal step sizes are h ∝ L^-1/(K+1) for bias and h ∝ L^-1/(2K+1) for MSE.
  • Practical contribution: The proposed efficient second-order symmetric splitting integrator outperforms Euler-based SGLD and SGHMC on synthetic and large real datasets.

2 Preliminaries & Two Approximation Errors in SG-MCMCs

The analysis separates approximation errors from stochastic gradients and numerical integration. It uses diffusion generators and Kolmogorov operators to relate exact expectations to feasible SG-MCMC sample paths.

  • Weak-convergence framework: Weak convergence is analyzed through the evolution of expected smooth statistics rather than directly through sample paths.This motivates introducing the infinitesimal generator of the diffusion.
  • Numerical approximation: For time T = Lh, repeated numerical operators approximate the exact Kolmogorov evolution over L integration steps.The exact operator e^T L is generally infeasible to solve analytically, so a feasible local integrator is used.
  • Two approximation errors: The first approximation error comes from replacing exact diffusion evolution with a numerical integrator whose operator P_h approximates e^hL.
  • Integrator accuracy: A Kth-order local integrator satisfies P_h f = e^hL f + O(h^(K+1)) for smooth bounded test functions.
  • Two approximation errors: The second approximation error comes from replacing the full negative log-posterior gradient with a minibatch stochastic gradient.For SGHMC, the stochastic-gradient generator is written as the exact generator plus a gradient-error operator ΔV_l.

3 Convergence Analysis

The paper analyzes finite-time convergence and asymptotic invariant measures of general SG-MCMCs, including fixed and decreasing step sizes. Higher-order integrators yield faster rates, while decreasing-step-size methods can be asymptotically consistent under the stated assumptions.

  • Finite-time error analysis: The analysis separates stochastic-gradient and numerical-integrator errors and applies Kolmogorov backward-equation expansions to general SG-MCMCs.The proof avoids directly expanding a generally unavailable explicit sample-path functional and instead expands the equation for each minibatch.
  • Finite-time error analysis: A biased stochastic-gradient estimator contributes an average gradient error term that can prevent finite-time bias from converging when its growth is too fast.The term vanishes for unbiased stochastic gradients, as assumed in SGLD.
  • Finite-time error analysis: For a Kth-order integrator, bias decreases as L^(-K/(K+1)) with h ∝ L^(-1/(K+1)), while MSE decreases as L^(-2K/(2K+1)) with h ∝ L^(-1/(2K+1)).These rates improve over first-order methods when K ≥ 2.
  • Stationary invariant measures: As L approaches infinity, the sample-average mean differs from the posterior average by O(h^K), and its variance is bounded by O(h^(2K)).Thus the asymptotic sample average remains close to the true posterior average for small h.
  • Stationary invariant measures: Any invariant measure of an SG-MCMC with a Kth-order integrator is within O(h^K) of the true posterior under the stated assumptions.The result indicates that numerical approximation order, rather than stochastic-gradient approximation, determines the asymptotic invariant-measure error.
  • SG-MCMCs with decreasing step sizes: Decreasing step sizes h_l ∝ l^(-α), with 0 < α < 1, make both bias and MSE approach zero asymptotically, yielding consistent posterior averages.The optimal balances use α = 1/(K+1) for bias and α = 1/(2K+1) for MSE, matching fixed-step-size rates.

4 Practical Numerical Integrators

The paper proposes an efficient second-order symmetric splitting integrator for SGHMC by analytically splitting its local generator into solvable sub-generators. Theory shows faster bias and MSE convergence than first-order Euler integration.

  • Integrator construction: The proposed SGHMC method is a second-order symmetric splitting integrator, whereas Euler integration is first order.The scheme splits the local stochastic-gradient generator into analytically solvable sub-generators.
  • Integrator construction: The SGHMC local generator decomposes as ˜Ll = LA + LB + LOl, representing transport, damping, and stochastic-gradient force/noise components.The resulting operator uses the symmetric ABOBA composition of these sub-operators.
  • Integrator analysis: The symmetric splitting scheme is a 2nd-order local integrator with ˜Plh = eh˜Ll + O(h3).Different symmetric orders are equivalent by the Markovian property of Kolmogorov operators.
  • Convergence results: The SGHMC splitting integrator achieves MSE rate L−4/5, compared with L−2/3 for SGLD with Euler integration.The optimal MSE step size is h ∝ L−1/5, and decreasing-step-size rates agree with the fixed-step-size results.

5 Experiments

Experiments compare symmetric splitting, Euler, and SGLD methods on synthetic and large-scale machine-learning problems. The splitting method generally provides lower error, stronger predictive performance, and greater robustness than Euler SGHMC and SGLD.

  • Synthetic data: Synthetic experiments compare invariant-measure biases of SGHMC with symmetric splitting and Euler integrators across step sizes.The evaluation uses a Gaussian model with 1000 samples, minibatches of size 10, and 200 randomized runs.
  • Synthetic data: Euler SGHMC has larger invariant-measure biases and quickly explodes at large step sizes, unlike the splitting integrator.The experiments identify Euler as an unstable integrator in this setting.
  • Large-scale applications: The experiments evaluate SGLD with Euler, SGHMC with symmetric splitting, and SGHMC with Euler on large-scale applications.Applications include Wikipedia LDA and stochastic binary networks, with minibatch training and test-likelihood evaluation.
  • Large-scale applications: For LDA with 200 topics, best test perplexities are 1168 for SGHMC-S, 1180 for SGHMC-E, and 2496 for SGLD.For 500 topics, the corresponding perplexities are 1157, 1187, and 2511.
  • Large-scale applications: For SBN with 200 hidden units, negative test log-likelihoods are 98 for SGHMC-S, 100 for SGHMC-E, and 110 for SGLD.SGHMC-S is also reported as more accurate and robust than SGHMC-E because of its second-order splitting integrator.

6 Conclusion

The conclusion presents high-order integrator theory for general SG-MCMCs, covering fixed and decreasing step sizes. The proposed second-order method is theoretically faster than first-order Euler methods, and experiments validate these results.

  • Empirical behavior: In a 200-topic SGHMC experiment, the Euler integrator explodes at large step sizes.This provides an application-level illustration of the stability advantage discussed for the splitting approach.
  • Contributions: The paper develops theory for finite-time ergodic errors and asymptotic invariant measures of general SG-MCMCs with high-order integrators.The theory covers both fixed-step-size and decreasing-step-size algorithms.
  • Convergence: Fixed- and decreasing-step-size SG-MCMCs have equivalent convergence rates under the paper’s analysis.The proposed second-order integrator is faster than previous first-order Euler methods.
  • Implications: Increasing numerical-integrator order theoretically allows SG-MCMC convergence rates to approach standard MCMC convergence rates.The conclusion states that experiments on synthetic and large real datasets validate the theory.

Supplementary Material for: On the Convergence of Stochastic Gradient MCMC Algorithms

The supplementary material introduces SGLD, SGHMC, and SGNHT, then develops the operator-based framework and assumptions used to analyze stochastic-gradient and numerical-integration errors. It also records scope boundaries for verifying key assumptions.

  • Background: SGLD, SGHMC, and SGNHT are introduced as stochastic-gradient MCMC algorithms based on first-order Langevin, second-order Langevin, and Nosé–Hoover dynamics.The thermostat adaptively controls system temperature because SGHMC’s covariance is difficult to estimate under data subsampling.
  • Approximation framework: SG-MCMC approximates continuous diffusion using both a numerical integrator and a minibatch stochastic gradient.The latter replaces the full negative log-posterior gradient with a minibatch-scaled estimate.
  • Analytical framework: The analysis uses Kolmogorov backward equations and generator expansions to study expected smooth statistics of the diffusion.Bounded remainders require smoothness and growth conditions on the drift function.
  • Assumptions: The assumptions include Lyapunov stability, moment-growth bounds, and control of stochastic-gradient variability.Hypoellipticity is used to extend the framework to dynamics such as SGHMC, where noise propagates to other variables.
  • Scope: Verifying the stochastic-gradient and related assumptions is left outside the paper’s scope because one condition is extra and another is more subtle.The supplementary discussion explicitly identifies this as an unresolved verification issue.

D The Proof of Theorem 2

The proof derives finite-time bias, MSE, and invariant-measure bounds for general SG-MCMCs by expanding minibatch Kolmogorov operators and controlling approximation terms. It uses Taylor expansions, martingale bounds, and geometric ergodicity to establish the stated error estimates.

  • Operator expansion: The proof starts from a Kth-order integrator and expands the minibatch Kolmogorov operator through low-order terms.The derivation repeatedly transforms higher-order operator terms and collects the resulting expansions.
  • Bias bound: The bias bound follows after substituting the Poisson equation, dividing by Lh, and collecting low-order terms.The resulting expression is completed using finiteness and operator-norm assumptions.
  • Operator expansion: Taylor expansions of the splitting updates bound the approximation terms using bounded derivatives and operator norms.The proof treats the second-order symmetric splitting scheme through its analytically solvable A, B, and O flows.
  • MSE bound: Martingale structure and boundedness assumptions control stochastic-gradient contributions in the MSE derivation.The proof uses conditional expectations and variance decompositions to bound the relevant terms.
  • Invariant measure: Geometric ergodicity and averaging over iterates yield a bound on the distance between the integrator’s invariant measure and the target measure.The argument applies the ergodic theorem before taking the long-run average.

G The Proof of Theorem 5

The proof of Theorem 5 extends the finite-time error analysis to decreasing step sizes. It derives bias and MSE bounds from the step-size sequence and identifies conditions ensuring the error terms vanish asymptotically.

  • Proof structure: The proof separates the decreasing-step-size analysis into bias and MSE components.Each component follows analogous expansions to the fixed-step-size analysis.
  • Step-size expansion: The decreasing-step-size sequence is substituted into the operator expansions to obtain bounds for the relevant powers of the step sizes.The derivation collects low-order terms after applying the sequence-dependent expansions.
  • Bias: The bias terms converge to zero as L approaches infinity under the theorem’s assumptions.The proof states that both resulting terms vanish in the limit.
  • MSE: The MSE bound uses inequalities for sums of powers of the step sizes and variance decompositions for the remaining terms.Terms of higher order are discarded after being shown to be dominated by the principal terms.

H The Proof of Corollary 6

The proof establishes Corollary 6 by verifying the step-size assumptions for h_l proportional to l^-alpha with 0 < alpha < 1. It also reviews the Euler and symmetric splitting integrators used in SG-MCMC updates.

  • Step-size conditions: For 0 < alpha < 1, the sequence h_l proportional to l^-alpha satisfies all step-size assumptions of Theorem 5.The proof compares the relevant power sums and shows the required bounds approach zero.
  • Corollary: Because the admissible decreasing step sizes satisfy Theorem 5, the bias and MSE approach zero asymptotically.Thus the sample average is asymptotically consistent with the posterior average.
  • Euler integrator: The Euler integrator is shown to be a 1st-order local integrator for SGLD and SGHMC.The corresponding Kolmogorov operators approximate the exact minibatch evolution with O(h^2) error.
  • Symmetric splitting: SGHMC splits its stochastic-gradient generator into analytically solvable sub-generators for position, momentum damping, and stochastic-gradient noise.The split generator is written as L_A + L_B + L_O_l.
  • Symmetric splitting: The BCH expansion shows that the symmetric splitting composition is a 2nd-order local integrator.The construction uses symmetric compositions of the A, B, and O flows and controls commutator remainders.

J Mean Flow Error Analysis

The mean-flow analysis compares the exact Kolmogorov flow with the stochastic-gradient symmetric-splitting flow over a finite time horizon. It shows that the difference depends on both runtime and minibatch-gradient errors, while sample-wise convergence generally fails.

  • Mean-flow construction: The exact mean flow is the solution operator of the Kolmogorov backward equation over T = Lh.The stochastic-gradient splitting method composes L local mean-flow operators, one for each minibatch.
  • Scope of convergence: For Hamiltonian PDEs and the corresponding SDE setting, stochastic-gradient flow is generally not close to the exact flow sample by sample.The discrepancy is attributed to uncontrollable stochastic-gradient terms, whereas weak convergence remains the relevant target in applications.
  • Mean-flow error: The difference between stochastic and exact mean flows depends on the running time T and the stochastic gradients used along the trajectory.The proof composes minibatch flows with the BCH formula and bounds the resulting terms for finite T.
  • Mean-flow construction: The SGHMC splitting scheme decomposes the generator into analytically tractable components and modifies the force component with each minibatch gradient.The minibatch perturbation is represented by DeltaV_l relative to the full-gradient operator.

K.1 Synthetic data

Synthetic and application experiments compare bias and MSE across fixed and decreasing step sizes, then evaluate SGHMC and integrators on LDA and SBN.

  • Synthetic data: For smaller-than-optimal step-size exponents, bias and MSE initially decrease faster but are eventually surpassed by the theoretically optimal rates.The optimal exponents reported for Figure 5 are α = −1/3 for bias and α = −1/5 for MSE.
  • Synthetic data: SGHMC and SGLD are compared using theory-selected step-size exponents, with constants chosen by grid search and SGHMC’s parameter D selected from three values.The comparison evaluates both bias and MSE across iteration counts.
  • Synthetic data: With decreasing step sizes, SGHMC retains faster convergence than SGLD, although its advantage is smaller than with fixed step sizes.The decreasing rates are α = 1/2 and 1/3 for bias, and 1/3 and 1/5 for MSE, for SGLD and SGHMC respectively.
  • LDA & SBN: On LDA and SBN, SGHMC outperforms SGLD, while the symmetric splitting integrator outperforms the Euler integrator.The comparison table distinguishes topic count K, hidden-unit count J, and splitting (‘S’) versus Euler (‘E’) variants.
  • LDA & SBN: For the full LDA dataset, test perplexity decreases faster with the symmetric splitting integrator than with the Euler integrator.The same figure also shows a dictionary learned by SGHMC with the symmetric splitting integrator.
Loading 1610.06665v1…