PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints

Wenlong Mou, Liwei Wang, Xiyu Zhai, Kai Zheng

arXiv:1707.05947v1cs.LGmath.OCstat.ML

TL;DR

The paper addresses how to obtain algorithm-dependent generalization bounds for non-convex learning with SGLD, where existing theory is limited despite relevance to deep learning. It analyzes SGLD with stability and PAC-Bayesian methods, obtaining complementary bounds whose dependence on step sizes and trajectory gradients avoids explicit dimension and parameter-norm dependence.

  • Problem

    Non-convex stochastic-gradient generalization has limited theoretical coverage, although iteration counts and step sizes may control effective capacity in settings such as deep learning.

  • Method

    The paper derives non-asymptotic SGLD generalization bounds using uniform stability and PAC-Bayesian theory, with ℓ2 regularization for the latter.

  • Results

    The stability bound has an O(1/n) rate, while the PAC-Bayesian bound has an O(1/√n) rate with exponentially decaying contributions from earlier steps and trajectory-dependent gradient norms.

  • Takeaways & Limitations

    The bounds have no explicit dependence on parameter dimension or norms and provide an algorithm-dependent explanation for fast-training generalization in non-convex settings.

  • Takeaways & Limitations

    The stability analysis includes an author-acknowledged unsatisfactory bound, while the PAC-Bayesian theorem requires regularity conditions, appropriate initialization, and ℓ2 regularization.

Abstract

from arXiv · show

Algorithm-dependent generalization error bounds are central to statistical learning theory. A learning algorithm may use a large hypothesis space, but the limited number of iterations controls its model capacity and generalization error. The impacts of stochastic gradient methods on generalization error for non-convex learning problems not only have important theoretical consequences, but are also critical to generalization errors of deep learning. In this paper, we study the generalization errors of Stochastic Gradient Langevin Dynamics (SGLD) with non-convex objectives. Two theories are proposed with non-asymptotic discrete-time analysis, using Stability and PAC-Bayesian results respectively. The stability-based theory obtains a bound of $O\left(\frac{1}{n}L\sqrt{βT_k}\right)$, where $L$ is uniform Lipschitz parameter, $β$ is inverse temperature, and $T_k$ is aggregated step sizes. For PAC-Bayesian theory, though the bound has a slower $O(1/\sqrt{n})$ rate, the contribution of each step is shown with an exponentially decaying factor by imposing $\ell^2$ regularization, and the uniform Lipschitz constant is also replaced by actual norms of gradients along trajectory. Our bounds have no implicit dependence on dimensions, norms or other capacity measures of parameter, which elegantly characterizes the phenomenon of "Fast Training Guarantees Generalization" in non-convex settings. This is the first algorithm-dependent result with reasonable dependence on aggregated step sizes for non-convex learning, and has important implications to statistical learning aspects of stochastic gradient methods in complicated models such as deep learning.

1 Introduction

The paper studies algorithm-dependent generalization for non-convex stochastic gradient methods, where iteration counts and step sizes regulate effective capacity. It analyzes SGLD through stability and PAC-Bayesian theories, yielding complementary bounds with favorable dependence on training trajectory.

  • Motivation: Non-convex generalization remains less understood than convex stochastic-gradient generalization, despite its relevance to deep learning.Algorithm-independent capacity measures can be too large to explain why overparameterized networks generalize.
  • Problem: The paper asks how stochastic gradient methods affect generalization in non-convex risk minimization, including the multi-pass training needed in practice.Generalization error is defined as the gap between empirical and population loss, averaged over algorithmic randomness.
  • Approach: SGLD adds isotropic Gaussian noise to stochastic gradient updates and is analyzed using uniform stability and PAC-Bayesian theory.The analysis considers stochastic gradients that may be full gradients or randomly sampled single-example gradients, with Gaussian initialization.
  • Implications: The bounds avoid explicit dependence on parameter dimension and parameter norms, and depend on aggregated step sizes under Lipschitz assumptions.The two theories expose different ways SGLD controls model complexity.

2 Preliminaries

The preliminaries define the dataset, trajectory, distance, stability, and PAC-Bayesian objects used to analyze SGLD and Langevin dynamics. They also distinguish worst-case stability reasoning from algorithmic, data-dependent PAC-Bayesian reasoning.

  • Notation: Neighboring datasets differ in exactly one data point, while SGLD iterates and densities are denoted by w_k,p_k and their primed counterparts.The cumulative step size is T_k = Σ_{j=1}^k η_j, and η_k denotes the step size at iteration k.
  • Notation: The stochastic gradient decomposes as ĝ_k(w)=g_k(w)+∇R(w), with L denoting the objective's Lipschitz constant and D_H the squared Hellinger distance.The unregularized stochastic-gradient operator is g_k, while R is the regularization term.
  • Distance properties: A functional is non-expansive when applying any mapping to two random points does not increase its value.KL divergence and squared Hellinger distance are identified as non-expansive f-divergences.
  • Stability: Uniform stability compares randomized algorithm outputs on neighboring datasets and directly yields expected generalization bounds.The paper focuses on expected bounds, while high-probability extensions can add an O(1/√n) term under suitable assumptions.
  • PAC-Bayesian theory: PAC-Bayesian bounds are algorithmic and data-dependent, but commonly require bounded or sub-Gaussian losses and control KL divergence to a prior.The paper improves a prior sub-Gaussian PAC-Bayesian result to remove an additive variance-dependent term.
  • Stochastic dynamics: Langevin dynamics are represented by an SDE whose density evolves according to a Fokker-Planck equation.The SDE uses a state-dependent drift and Brownian motion, while the Fokker-Planck equation describes density evolution.

3 Ideal Case: Generalization Bounds for Langevin Equation

The ideal continuous-time analysis converts Langevin dynamics into density evolution and bounds generalization through stability distances. Gaussian convolution preserves or improves divergence behavior, while regularization supports PAC-Bayesian bounds without dimension- or norm-dependent terms.

  • Setup: SGLD is viewed as a discretization of Langevin dynamics, whose continuous-time analysis provides insight into discrete-time generalization bounds.The paper constructs continuous-time processes and corresponding PDEs to analyze the algorithm.
  • Stability analysis: Uniform stability is bounded through squared Hellinger distance between densities generated from neighboring datasets.The analysis begins with identical distributions at time zero and tracks the effects of gradient updates and Gaussian convolution.
  • Stability analysis: Non-expansive f-divergences can remain controlled even when non-convex gradient updates greatly expand parameter distance, while Gaussian convolution decreases divergence.This mechanism improves on parameter-distance stability analysis for non-convex objectives.
  • Stability result: The resulting continuous-time stability bound controls expected generalization error under the stated Lipschitz and bounded-loss assumptions.The bound is obtained by upper-bounding the Hellinger distance between the two trajectory densities.
  • PAC-Bayesian analysis: PAC-Bayesian analysis is also developed for finite-time Fokker-Planck evolution and regularized ERM.The regularization is chosen to remove dimension- or norm-dependent terms associated with the Gaussian initialization and prior comparison.
  • PAC-Bayesian analysis: The regularized analysis derives KL-divergence control using logarithmic Sobolev inequalities and Gaussian-prior calculations.The proof solves the KL evolution from an initially zero divergence and handles the prior-dependent expectation explicitly.
  • PAC-Bayesian analysis: A simpler upper bound follows by imposing uniform L-Lipschitzness on the objective.The regularized Langevin formulation is formalized in Proposition 3 before this simplification.

4 Stability of Discrete-Time SGLD

The stability analysis directly handles discrete-time SGLD by constructing stochastic processes from its updates, avoiding discretization-gap bounds with dimension dependence. It combines distance-based analyses to obtain fast generalization guarantees whose behavior depends on step sizes.

  • Discrete-time analysis: Direct SDE constructions for discrete-time updates avoid potentially dimension-dependent gaps between discrete and continuous-time Langevin analyses.The approach uses stochastic processes similar to the Langevin equation but based directly on discrete-time SGLD updates.
  • Guarantees and assumptions: The analysis assumes bounded loss and bounded differences between per-example gradients, then yields an expected generalization bound for N-round SGLD.The expectation is over the randomness of the training data or randomized algorithm as specified in the respective results.
  • Improved stability analysis: O(1/n) stability rates are obtained for SGLD by exploiting Gaussian-noise smoothing and a quadratic information-type decrease in squared Hellinger distance.The quadratic term is absent from the succinct analysis but enables the fast rate.
  • Step-size regimes: Small-step analyses use squared Hellinger distance, while larger steps are handled with an L1-distance estimate, and the two regimes are combined.The choice of estimator changes with step size because large stochastic-gradient steps can contribute more than 1/n to the succinct bound.

5 PAC-Bayesian Theory for Discrete-Time SGLD

The PAC-Bayesian analysis gives a non-asymptotic discrete-time SGLD bound by adding ℓ2 regularization and constructing data-independent, time-varying Gaussian priors. Its bound trades a slower rate for trajectory-dependent gradients and temporal decay of earlier contributions.

  • Discrete-time PAC-Bayes analysis: The PAC-Bayesian analysis directly constructs stochastic processes and PDEs from discrete-time SGLD updates instead of estimating a discretization gap.An ℓ2 regularization term R(w) = λ/2∥w∥^2 is added to avoid norm-dependent terms in the generalization bound.
  • Temporal decay: For step sizes η_k = c k^-α with α ∈ [0,1], the exponential factor yields a polynomially decaying effect for contributions from earlier rounds.The decay factor can make the resulting bound significantly smaller.
  • Assumptions: The final PAC-Bayesian results require sub-Gaussian losses under Gaussian priors and impose assumptions on Lipschitzness and algorithmic parameters.The stated theorem holds uniformly with probability 1−δ over the random draw of training data.
  • PAC-Bayesian guarantee: Theorem 10 has a slower O(1/√n) rate than stability bounds but replaces uniform Lipschitz control with expected norms of actual gradients along the optimization trajectory.The expectation is taken over the randomized algorithm rather than the data.
  • Temporal decay: The contribution of earlier gradients is suppressed by a time-decaying factor e^[-λ/2(T_N−T_k)], reducing the influence of potentially larger early gradients.With ℓ2 regularization, the bound is described as finite as T approaches infinity under the stated setting.

6 Conclusion

The paper establishes algorithm-dependent generalization bounds for non-convex regularized ERM with SGLD using uniform stability and PAC-Bayesian theory. The bounds avoid explicit dependence on dimension and parameter norms while capturing step-size and trajectory-gradient effects.

  • The paper studies non-convex regularized ERM with SGLD through uniform stability and PAC-Bayesian theory.
  • The stability-based bound attains an O(1/n) rate and depends on the Lipschitz constant and aggregated step sizes.
  • The PAC-Bayesian bound includes a time-decaying factor for contributions from earlier steps.
  • The PAC-Bayesian bound uses expected gradient norms along the optimization trajectory instead of a uniform Lipschitz constant.
  • Both bounds have no explicit dependence on parameter dimension or norms, while the PAC-Bayesian result has polynomial dependence on aggregated step sizes and objective smoothness.

Proof of theorem 4

The proof of Theorem 4 derives the PAC-Bayesian result by applying a change-of-measure inequality and controlling the resulting terms probabilistically. The argument combines a finite parameter set, union bounds, independence, and subGaussian control.

  • The proof begins with the Donsker–Varadhan change-of-measure inequality for distributions and a functional.
  • For a finite set of parameters, Markov’s inequality and a union bound yield a statement holding with probability at least 1 −δ.
  • The proof expands the right-hand side using independence and controls the resulting terms through the subGaussian property.
  • Selecting i so that 2^i ≤ D_KL(Q||P) < 2^(i+1) completes the bound.

Proof of Theorem 5

The proof of Theorem 5 analyzes full-gradient SGLD through neighboring parameter processes and their interpolated distributions. It controls their divergence using PDE arguments, Hellinger-distance estimates, and induction across steps.

  • The proof assumes bounded gradients and compares parameters initialized from neighboring datasets at each update.
  • The analysis constructs stochastic processes whose one-time distributions match the interpolated SGLD variables, then derives governing equations by differentiation.
  • The proof uses Gaussian smoothing and PDE representations to relate the interpolated processes to their density functions.
  • Squared Hellinger distance is estimated at each step, with the gradient-difference assumption controlling its change.
  • Induction over steps produces a final KL-divergence bound and then the corresponding uniform-stability bound.

Proof of Lemma 1

The proof of Lemma 1 constructs interpolated random variables for SGLD and neighboring datasets, then derives matching PDE descriptions. Independence, Gaussian noise, and induction support the resulting bounds.

  • The proof assumes distributions before the k-th step and defines density functions for the corresponding parameter variables.
  • The parameter distributions remain related because the processes apply the same gradient step and Gaussian smoothing.
  • The construction uses independent initial parameters, Gaussian noise, and uniformly sampled data indices.
  • An interpolated random-variable sequence is constructed for each step, together with an SDE having the same one-time marginals.
  • The proof defines density-based functions and derives their equations by differentiating with respect to parameters and time.
  • Lemmas controlling the interpolated equations yield bounds for sufficiently small interpolation times, after which induction completes the argument.
Loading 1707.05947v1…