PaperlayerView exact revision on arXiv

Source-linked AI summary

Data-Dependent Stability of Stochastic Gradient Descent

Ilja Kuzborskij, Christoph H. Lampert

arXiv:1703.01678v4cs.LG

TL;DR

The paper addresses the pessimism of worst-case SGD stability bounds by developing a data-dependent stability analysis. It applies this framework to convex and non-convex losses, obtaining bounds tied to initialization and curvature, tighter empirical bounds, and optimistic fast-rate results under specified conditions.

  • Problem

    Worst-case stability bounds for SGD can be too pessimistic because they ignore the data-generating process and initialization.

  • Method

    The paper establishes distribution-dependent on-average stability bounds for SGD on convex and non-convex smooth losses.

  • Results

    The bounds depend on initialization risk in convex learning and expected curvature around initialization in non-convex learning; empirically, the non-convex bound is tighter than the uniform one.

  • Takeaways & Limitations

    The analysis supports pre-screening initializations or transfer sources using stability bounds and yields optimistic fast rates when empirical risk vanishes.

  • Takeaways & Limitations

    The presented theorems assume non-negative, Lipschitz, β-smooth losses; some results additionally require convexity or Lipschitz Hessians, and SGD randomness is restricted to uniform sampling without replacement.

Abstract

from arXiv · show

We establish a data-dependent notion of algorithmic stability for Stochastic Gradient Descent (SGD), and employ it to develop novel generalization bounds. This is in contrast to previous distribution-free algorithmic stability results for SGD which depend on the worst-case constants. By virtue of the data-dependent argument, our bounds provide new insights into learning with SGD on convex and non-convex problems. In the convex case, we show that the bound on the generalization error depends on the risk at the initialization point. In the non-convex case, we prove that the expected curvature of the objective function around the initialization point has crucial influence on the generalization error. In both cases, our results suggest a simple data-driven strategy to stabilize SGD by pre-screening its initialization. As a corollary, our results allow us to show optimistic generalization bounds that exhibit fast convergence rates for SGD subject to a vanishing empirical risk and low noise of stochastic gradient.

1 Introduction

The paper replaces worst-case stability analysis of SGD with data-dependent bounds for convex and non-convex learning. These bounds connect generalization to initialization risk, curvature, and data-driven initialization selection.

  • Motivation: SGD generalization is studied through sensitivity to small training-set perturbations rather than only optimization outcomes.The motivation includes strong empirical performance even when SGD may not reach a minimum.
  • Contribution: Data-dependent algorithmic stability yields generalization bounds for both convex and non-convex learning problems.The bounds depend on the data-generating distribution and the algorithm’s initialization point.
  • Main results: For convex losses, the generalization bound is essentially multiplicative in the initialization risk when stochastic-gradient noise is not too high.
  • Main results: For non-convex losses, generalization is critically controlled by expected second-order information about the objective around initialization.The paper links lower curvature with greater SGD stability and generalization ability.
  • Main results: Empirically, the data-dependent non-convex bound is tighter than the worst-case counterpart, while optimistic bounds achieve faster rates under vanishing empirical risk.
  • Applications: The analysis supports selecting initializations or transfer sources by minimizing a data-dependent stability bound.The paper presents principled transfer-learning applications and initialization selection from random starting positions.

2 Related Work

The related-work discussion positions the paper within distribution-dependent stability and SGD generalization research. It extends data-driven stability analysis to stochastic optimization on non-convex problems and connects it to transfer learning.

  • Stability foundations: Algorithmic stability research distinguishes distribution-free uniform stability from distribution-dependent notions.Uniform stability reflects intrinsic algorithmic properties without regard to the data-generating process.
  • Stability foundations: On-average stability controls bounds through algorithm behavior under the data-generating distribution and can support optimistic risk bounds.Prior work also uses it for data-driven algorithm design, transfer, and metric learning.
  • Positioning: This paper relates SGD stability to initialization risk in convex problems rather than only to minimizers of convex ERM.
  • Positioning: For non-convex learning, the paper directly studies the connection between generalization and curvature.This differs from theoretical studies focused on neural-network objective functions more generally.
  • Positioning: Unlike much non-convex SGD optimization work, the paper targets generalization rather than convergence to stationary points or saddle avoidance.Its stability approach does not require stationary points in the analysis.
  • Transfer learning: The transfer-learning application uses stability bounds to choose initializations for improved generalization within an SGD analysis.The discussion contrasts this with literature focused mainly on ERM settings and PAC bounds.

3 Stability of Stochastic Gradient Descent

This section introduces learning-theory notation and explains how stability connects perturbation sensitivity to generalization. It motivates replacing uniform worst-case stability with a less restrictive, data-dependent analysis.

  • Setup: Training examples are drawn iid from a distribution D, and a learning algorithm maps a training set S to parameters in H.
  • Setup: Risk measures expected loss under D, empirical risk measures average training loss, and R* is the infimum population risk.
  • Stability and generalization: A stable algorithm changes little when one training example is perturbed, which supports generalization from training data to unseen data.
  • Uniform stability: Uniform stability for randomized SGD compares losses after replacing one training example and leads to expected generalization bounds.Because SGD has data and algorithmic randomness, the relevant statements are in expectation.
  • Uniform stability: Uniform-stability bounds are worst-case and ignore data-generating information that may permit faster generalization rates.The paper addresses this limitation with data-dependent bounds for convex and non-convex losses.

4 Data-dependent Stability Bounds for SGD

The paper defines stability as depending on additional parameters, especially the data-generating distribution and SGD initialization. Its on-average formulation averages over replaced examples while retaining a worst-index supremum.

  • Data-dependent stability: Data-dependent stability extends ordinary algorithmic stability by allowing bounds to depend on additional algorithm parameters θ.Here θ describes the data-generating distribution and the initialization point of SGD.
  • On-average stability: The paper studies on-average stability for randomized algorithms under training samples S drawn iid from D and a replacement example z drawn from D.
  • On-average stability: Its definition resembles prior on-average stability but takes a supremum over the index of the replaced training example.This preserves data-dependent behavior while controlling the most sensitive replacement position.

5 Main Results

The paper develops data-dependent stability bounds for SGD in convex and non-convex settings, linking generalization to initialization risk, curvature, and stochastic-gradient noise. The results also support tighter empirical bounds, optimistic convergence rates, and principled initialization or source selection.

  • Data-dependent on-average stability is established for SGD on both convex and non-convex losses.The analysis depends on the data-generating distribution and initialization point rather than only worst-case algorithmic quantities.
  • Convex losses: For convex losses, generalization depends multiplicatively on the risk at the initialization point when stochastic-gradient noise is not too high.With zero initialization risk in the deterministic case, SGD need not update in expectation and is perfectly stable; high noise removes the improvement.
  • Applications: The bounds yield a principled strategy for selecting initializations or transfer-learning sources by minimizing stability-related criteria.In non-convex settings, pre-screening can favor low Hessian spectral norm and low risk; transfer learning selects the best source of information.
  • Non-convex losses: For non-convex losses, expected curvature around initialization influences SGD stability and therefore its generalization error.Lower curvature, lower initialization risk, and lower gradient noise characterize a regime expected to yield higher stability and faster generalization.
  • Non-convex losses: When expected empirical risk vanishes and the full pass has m = O(T), the optimistic generalization error has order O(1/m).This improves on the pessimistic order O(m^(-1/(1+cγ))) under the stated conditions.
  • Non-convex losses: The data-dependent non-convex bound is empirically tighter than the worst-case counterpart on a convolutional neural network trained on MNIST.The experiment compares the data-dependent bound with the distribution-free bound of [15, Theorem 3.8] and an empirical validation-training loss gap.

6 Conclusions and Future Work

The paper concludes that data-dependent stability bounds for SGD apply to convex and non-convex smooth losses, with non-convex generalization affected by expected curvature around initialization. It also identifies optimistic fast-rate bounds and notes that adaptive step sizes remain future work.

  • Data-dependent stability bounds for SGD revisit generalization for convex and non-convex smooth loss functions.
  • Expected curvature around the initialization point heavily affects non-convex SGD generalization.
  • The data-dependent bound is empirically tighter than the uniform worst-case bound.
  • Optimistic generalization bounds exhibit fast rates when the algorithm's output has vanishing empirical risk.
  • The presented bounds have data-dependent components, but their step size cannot yet be adjusted according to the data.

A Proofs

The appendix proofs relate expected empirical and population risks through stability arguments for independently sampled training sets. The supplied proof passages mainly show proof setup, intermediate decompositions, and closure statements.

  • The appendix presents intermediate proof steps and concludes with statements that the proof is complete.
  • The proof setup considers independent training sets sampled i.i.d. from D.
  • The argument compares the algorithm's outputs on a training set and a version differing in one example.

A.1 Preliminaries

The preliminaries define SGD updates, expansiveness, and stability-related quantities, then develop tools for controlling output differences and loss differences under data perturbations. Conditional expectation over delayed perturbations is used to tighten these controls.

  • SGD is represented through gradient update operators G_t mapping the parameter space H to itself.
  • Expansiveness bounds how much a gradient update can enlarge the distance between two parameter points.
  • For convex losses, β-smoothness with α_t ≤ 2/β makes the gradient update rule 1-expansive.
  • For non-negative β-smooth losses, self-boundedness yields boundedness properties for gradient update rules.
  • A risk-to-initialization bound uses stochastic-gradient variance and does not require convexity of the loss function.
  • The perturbation analysis conditions output distance on the perturbation occurring after t_0, enabling minimization over t_0.

A.2 Convex Losses

The convex-loss analysis establishes on-average stability for SGD by combining perturbation bounds, data-dependent update control, and non-expansiveness. The proof recursively tracks output differences across whether SGD encounters the perturbed example.

  • A.2 Convex Losses: The convex analysis targets on-average stability for non-negative, β-smooth, convex loss functions.
  • A.2 Convex Losses: Theorem 5 establishes an ε(D, w_1)-on-average stability guarantee for SGD under its stated step-size assumptions.
  • A.2 Convex Losses: The proof conditions on outputs remaining identical through t_0 and recursively bounds their later expected distance.
  • A.2 Convex Losses: When SGD encounters the perturbed example, the proof uses data-dependent gradient-update boundedness; otherwise, convexity gives δ_{t+1}(S,z) ≤ δ_t(S,z).
  • A.2 Convex Losses: The stated theorem is obtained as a consequence of Theorem 5 and Lemma 4, with the proof specializing t_0 to zero.

A.3 Non-convex Losses

The section proves a data-dependent stability bound for SGD on non-convex losses. Stability reflects both diminishing step sizes and the local expansion of updates around the initialization point.

  • Stability mechanism: Stability improves because the step size has decayed by the time SGD encounters a perturbation, while subsequent updates can expand the distance between trajectories.This identifies diminishing step size and local update expansion as the two opposing factors in the argument.
  • Non-convex stability: Theorem 4 bounds SGD’s on-average stability by comparing outputs trained on a dataset and a perturbed version.The proof studies the loss difference between the two SGD outputs and unrolls a recursion for their discrepancy.
  • Expectation control: The analysis unrolls the discrepancy recursion before taking expectations, then bounds exponential terms using a Bernstein-type inequality.The expectation is taken over the data after recursion unrolling to manage dependencies among the random quantities.
  • Recursion: The proof separates the perturbed-step case from ordinary steps and combines worst-case gradient bounds with the update rule’s expansiveness.The update is at most (1 + α_tβ)-expansive, while the perturbed example is handled using bounded gradients.
  • Parameter control: The expected local expansion is bounded through μ_k ≤ min{β, E[ξ_k(S,z)]} and the second result of Lemma 6, yielding μ_k ≤ γ.This bound is then used when tuning the starting index t_0 in the stability estimate.

A.3.1 Optimistic Rates for Learning with Non-convex Loss Functions

This section develops an optimistic bound from Theorem 4 for non-convex learning. The proof combines a technical inequality with Theorem 4 and analyzes the resulting bound over initialization choices.

  • Optimistic rates: The section targets a fast convergence rate when empirical risk vanishes, building the optimistic result from Theorem 4.The argument is explicitly presented as an optimistic bound based on the preceding non-convex stability theorem.
  • Technical lemmas: Lemma 7 establishes a unique positive solution for equations formed by a leading power minus lower-order power terms and a constant.It also provides bounds on that solution, which are used in the subsequent technical argument.
  • Technical lemmas: Lemma 8 uses the function h(x) = x − ax^α − c to bound x whenever the inequality h(x) ≤ 0 holds.The proof derives this bound by applying Lemma 7 and analyzing h at zero and as x tends to infinity.
  • Optimistic-rate proof: The proof applies Theorem 4 through Lemma 8, with x identified as the expected empirical risk of the algorithm.This connects the stability bound to the optimistic-rate analysis.
  • Initialization selection: A separate argument minimizes a bound over a discrete set of source hypotheses and uses Hoeffding’s inequality followed by a union bound.The resulting source-risk terms are further bounded using empirical estimates.
Loading 1703.01678v4…