Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent

Yunwen Lei; Yiming Ying

Source-linked AI summary

Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent

Yunwen Lei, Yiming Ying

arXiv:2006.08157v1Jun 15, 2020cs.LGstat.ML

TL;DR

Existing SGD stability analyses rely on restrictive bounded-gradient, smoothness, and convexity assumptions. This paper introduces on-average model stability and develops risk-sensitive bounds under relaxed conditions, including non-differentiable losses. It concludes that the resulting stability bounds can achieve minimax-optimal generalization bounds by balancing optimization and estimation errors.

Problem
Existing SGD stability analyses require restrictive assumptions on gradient boundedness, smoothness, and convexity that exclude settings such as least-squares regression and support vector machines.
Method
The paper introduces on-average model stability, whose bounds are controlled by risks of SGD iterates, and studies relaxed smoothness and convexity conditions.
Results
The analysis provides stability and generalization bounds without bounded-gradient assumptions, for non-smooth losses, and for convex objectives with non-convex losses.
Takeaways & Limitations
For the considered problems, the stability bounds can imply minimax-optimal generalization bounds by balancing optimization and estimation errors.
Takeaways & Limitations
The analysis focuses on projected stochastic gradient descent and includes a bounded-subgradient assumption in one considered setting.

Abstract

from arXiv · show

Recently there are a considerable amount of work devoted to the study of the algorithmic stability and generalization for stochastic gradient descent (SGD). However, the existing stability analysis requires to impose restrictive assumptions on the boundedness of gradients, strong smoothness and convexity of loss functions. In this paper, we provide a fine-grained analysis of stability and generalization for SGD by substantially relaxing these assumptions. Firstly, we establish stability and generalization for SGD by removing the existing bounded gradient assumptions. The key idea is the introduction of a new stability measure called on-average model stability, for which we develop novel bounds controlled by the risks of SGD iterates. This yields generalization bounds depending on the behavior of the best model, and leads to the first-ever-known fast bounds in the low-noise setting using stability approach. Secondly, the smoothness assumption is relaxed by considering loss functions with Holder continuous (sub)gradients for which we show that optimal bounds are still achieved by balancing computation and stability. To our best knowledge, this gives the first-ever-known stability and generalization bounds for SGD with even non-differentiable loss functions. Finally, we study learning problems with (strongly) convex objectives but non-convex loss functions.

1 Introduction

SGD is widely used for scalable learning, but existing stability analyses rely on restrictive gradient, smoothness, and convexity assumptions. This paper broadens stability-based generalization analysis through relaxed assumptions and a new risk-sensitive stability measure.

SGD supports large-scale learning through sequential updates with cheap per-iteration cost.Its optimization convergence has been extensively studied, alongside growing work on generalization.
Existing stability analyses assume bounded gradients and strong smoothness, which fail for least-squares regression and support vector machines.Strong convexity of each loss function also excludes problems such as least-squares regression.
The paper introduces on-average model stability to relax bounded-gradient assumptions and connect stability bounds to the risks of SGD iterates.The resulting bounds use weighted empirical risks rather than a uniform Lipschitz constant.
The analysis also relaxes smoothness and convexity requirements while retaining stability-based generalization guarantees.The paper considers relaxed smoothness, non-differentiable losses, and settings where objectives are convex but individual losses are non-convex.
The paper is organized around convex learning, relaxed convexity, relaxed strong convexity, and concluding results.

2 Related Work

Prior work developed stability and generalization analyses for SGD, including uniform and weaker stability notions, optimization-based generalization bounds, and problem-specific optimal rates. These results motivate broader analyses beyond restrictive smoothness and convexity settings.

Algorithmic Stability: Algorithmic stability provides a route to expected and high-probability generalization bounds across randomized, transfer, and privacy-preserving learning.Uniform stability is one established notion among several alternatives.
Stability of Stochastic Optimization Algorithms: Earlier SGD stability analyses used gradient co-coercivity and later weakened uniform stability to capture initial risk and stochastic-gradient variance.
Generalization Analysis of SGD: Uniform stability yielded expected SGD generalization bounds O(1/√n) for convex, strongly smooth problems.
Generalization Analysis of SGD: For convex nonsmooth learning, uniform convergence established generalization bounds O(n−1/3), while tuning passes or step sizes provided implicit regularization.
Generalization Analysis of SGD: Integral-operator analyses obtained nearly optimal excess generalization error bounds for SGD with least-squares loss.

3 Problem Formulation

The paper formulates supervised learning with empirical and population risks, studies projected SGD, and decomposes excess generalization error into estimation and optimization components. Stability is used to control estimation error, while the main analysis can also apply without projections.

Training examples are independently drawn from a distribution, and a parameterized predictor incurs loss f(w; z).The input space is a subset of R^d and outputs lie in R.
Empirical and population risks are defined from the sample loss and its expectation over the data distribution.
The target is excess generalization error F(A(S)) − F(w∗), measured against the best population-risk model w∗.
Excess error decomposes into estimation error from sampling and optimization error from minimizing the empirical objective.Stability is presented as a way to control estimation error.
The paper focuses on projected SGD, while its main Section 4 results also hold when Ω = R^d and no projections are used.
Projected Stochastic Gradient Descent: Projected SGD starts from w1 = 0, uses positive step sizes, projects onto Ω, and samples an example index uniformly at each update.The update uses a subgradient, which becomes the gradient when the loss is differentiable.

4 Stability with Convexity

The paper develops stability and generalization results for convex SGD while relaxing bounded-gradient and strong-smoothness assumptions. Its on-average model stability measure yields risk-sensitive bounds, including fast low-noise rates and results for Hölder-continuous or non-differentiable losses.

Motivation: Existing SGD stability analyses assume bounded gradients and strong smoothness, excluding least-squares regression, support vector machines, and some neural-network settings.For least squares on an unbounded parameter domain, the Lipschitz constant can be infinite; neural-network constants can also be prohibitively large.
On-average model stability: On-average model stability measures the average sensitivity of model parameters when one training example is replaced, rather than sensitivity of function values.The measure is introduced to remove bounded-gradient and strong-smoothness requirements while connecting model perturbations to generalization.
On-average model stability: The resulting generalization theory can use empirical risks of SGD iterates instead of a uniform Lipschitz constant, allowing bounds to reflect the risk of the output model.The ℓ2 form can improve dependence on the stability measure when the empirical risk is small, unlike the O(ε) dependence cited for uniform and ℓ1 stability.
Non-smooth case: For Hölder-continuous (sub)gradients, balancing computation and stability yields optimal rates, including O(n^-1/2) for α < 1/2 with T ≍ n^(1+α) and for α = 0 with T ≍ n^2.The analysis covers non-differentiable losses such as hinge loss and gives the first stability-based generalization bounds for SGD in that setting.
Non-smooth case: The framework also derives optimistic generalization bounds for non-smooth losses in low-noise cases.These results extend the low-noise benefit of risk-sensitive stability beyond the smooth setting.

5 Stability with Relaxed Convexity

The paper relaxes convexity requirements by assuming convexity of the empirical objective while allowing individual loss functions to be non-convex. It derives stability bounds under this weaker condition and applies them to AUC maximization.

5 Stability with Relaxed Convexity: The analysis assumes each empirical objective FS is convex, while individual loss functions may be non-convex.Theorem 8 and Theorem 9 use this relaxed convexity condition for SGD stability and generalization.
5 Stability with Relaxed Convexity: Theorem 8 replaces per-example convexity with the milder requirement that FS is convex.This avoids the per-example convexity needed for non-expansiveness arguments in earlier analyses.
5 Stability with Relaxed Convexity: When the relevant cumulative quantity is finite, the stability bounds become O(n^-1).The paper also states that minimax optimal generalization bounds are achievable with suitable decreasing step sizes and T ≍ n.
5 Stability with Relaxed Convexity: AUC maximization provides an application where the objective is convex although each single-example loss may be non-convex.The stochastic formulation uses one example per iteration, while the expected objective is convex.

6 Stability with Relaxed Strong Convexity

The paper studies strongly convex empirical objectives even when individual loss functions are non-convex. It obtains stability bounds and minimax-optimal generalization rates under this relaxed assumption.

6 Stability with Relaxed Strong Convexity: Theorem 10 establishes stability when the empirical objective FS is strongly convex, even if each loss function is non-convex.The required step size is ηt = 2/((t + t0)σS).
6 Stability with Relaxed Strong Convexity: The minimax-optimal generalization bound is O(1/(σn)) for strongly convex empirical objectives.The result is stated for T ≍ n under the step-size schedule in Theorem 11.
6 Stability with Relaxed Strong Convexity: The strong convexity requirement is imposed on FS rather than on every individual loss function.The paper notes that its stability bound coincides with the earlier bound up to a constant factor when t ≍ n.
6 Stability with Relaxed Strong Convexity: In the least-squares application, individual losses are non-strongly convex, but the empirical objective is strongly convex on a subspace containing the iterates.The construction uses the range of CS and applies Theorem 10 with the corresponding positive eigenvalue.

7 Conclusions

The paper broadens SGD stability analysis by removing bounded-gradient assumptions and relaxing smoothness and per-example convexity. Its bounds use on-average model stability, support low-noise rates, and can be minimax optimal.

7 Conclusions: The paper removes bounded-gradient assumptions and relaxes smoothness and the convexity requirement for each loss function.These changes broaden the applicability of stability-based generalization analysis for SGD.
7 Conclusions: On-average model stability captures SGD-iterate risks and yields fast generalization bounds in low-noise settings.The approach replaces uniform Lipschitz control with empirical-risk quantities and can exploit small output-model risk.
7 Conclusions: For the considered problems, balancing optimization and estimation errors yields minimax-optimal generalization bounds.The conclusion also states that the results extend to stochastic proximal gradient descent, high-probability bounds, and SGD without replacement.
7 Conclusions: For Holder-continuous gradients, the analysis uses self-bounding properties to control gradients through function values.The cited lemmas cover nonnegative losses with (α, L)-Holder continuous subgradients, including non-smooth cases.

C.1 Stability bounds

The stability analysis compares SGD runs on datasets differing by one example and controls their model distance under smooth, Holder-smooth, convex, and non-convex settings. These stability estimates are then converted into generalization bounds.

C.1 Stability bounds: The analysis bounds the distance between SGD iterates trained on datasets differing by one example.The construction introduces coupled sequences and uses non-expansiveness or controlled expansiveness of the update operator.
C.1 Stability bounds: For non-convex losses, Proposition C.3 establishes stability bounds without requiring per-example convexity.The result retains the other assumptions of Theorem 3 and holds for any p > 0.
C.1 Stability bounds: The resulting stability estimates are inserted into optimization-error bounds to derive generalization guarantees for SGD.The proof explicitly plugs stability inequalities into the generalization theorem and selects p = n/T in one step.

D.2 Generalization errors

This section derives generalization-error bounds for SGD by decomposing excess generalization error into estimation and optimization errors. Under convexity and Hölder-continuous subgradients, the analysis uses a proposition with polynomial step sizes and specific parameter choices.

General bound: Proposition D.4 assumes nonnegative convex losses with (α, L)-Hölder-continuous subgradients and step sizes η_t = cT^-θ.It requires θ ≥ (1 − α)/2 and n = O(T).
Theorem 7: Theorem 7 follows by verifying θ ≥ (1 − α)/2 for its parameter choices and applying Proposition D.4.Parts (a)–(c) then substitute separate choices such as θ = 1/2 and T ≍ n into the general bound.
Proof strategy: The proof separates excess generalization error into estimation error and optimization error.The estimation term is bounded through stability, while the optimization term is controlled using an auxiliary lemma.
Estimation error: The estimation analysis defines δ_j as the nonnegative expected generalization gap at iterate w_j and solves a recurrence for δ_{t+1}.The recurrence uses p = n/T and the condition n = O(T).
Optimization error: The optimization analysis applies a lemma at the comparator w* and uses concavity to obtain an optimization-error bound.This bound is combined with the estimation bound through the error decomposition.

E.1 Stability and generalization errors

This section analyzes SGD stability by comparing trajectories trained on datasets differing in one example, then combines the resulting stability bounds with optimization-error bounds to obtain generalization results. The analysis covers several polynomially decaying step-size regimes.

Stability analysis: The stability proof assumes the neighboring datasets differ in the first example and compares the corresponding SGD iterates.The update difference is decomposed according to whether the sampled index equals the changed example.
Stability analysis: When the sampled index is unchanged, smoothness controls the gradient difference; when it is changed, the exceptional event occurs with probability 1/n.These two cases yield the recurrence used to bound the iterate distance.
Stability measure: The section defines ε_stab(A, n) as the infimum ε satisfying the stability condition.The tuple (A, n) is omitted when it is clear from context.
Generalization: Theorem 9 bounds optimization error using a uniform constant for the relevant cumulative step-size quantity and then applies the stability result.The proof also uses convexity of the norm and the monotonicity of the upper bound in t.
Generalization: Theorem 8 combines the stability estimate with the error decomposition, Lemma 1, and an optimization-error bound.For η_t = η_1t^-θ with θ ∈ (1/2, 1), the proof invokes Lemma E.1 to control the resulting sums.

F Proofs on Stability with Relaxed Strong Convexity

This section proves stability bounds for settings with strongly convex empirical objectives and develops related extensions. It also identifies the range of a covariance-like matrix and notes that the SGD stability analysis extends to proximal updates.

Stability bound: Theorem 11 bounds ℓ1 on-average model stability by a quantity involving σ^-1/(Tσ_S) and ||w*||_2^2/T^2.The bound is obtained after summing the trajectory inequality and applying Lemma E.1.
Matrix characterization: Proposition F.1 states that the range of C_S is the linear span of the training vectors {x_1, …, x_n}.The proof establishes this by identifying the kernel of C_S with the orthogonal complement of that span.
Proximal extension: The SGD stability bounds extend to stochastic proximal gradient descent because proximal operators are non-expansive for convex regularizers.Projected SGD is recovered as a special case with an appropriate regularizer.

G.2 Stability bounds with high probabilities

This section extends expected stability analysis to high-probability bounds and to SGD without replacement. The high-probability result uses concentration for the number of times the changed example is sampled, while the without-replacement analysis proceeds epoch by epoch.

Generalization: High-probability generalization bounds follow by combining the stability bounds with a result relating stability and generalization in high-probability analysis.This extends the expected-stability perspective to fluctuations across random index realizations.
High-probability stability: Proposition G.1 gives a high-probability stability bound for SGD with convex losses and (α, L)-Hölder-continuous subgradients.It considers neighboring datasets, step sizes η_j = ct^-θ, and confidence parameter δ.
High-probability stability: The proof applies Chernoff’s bound to indicators recording whether SGD samples the changed example.The resulting concentration controls the cumulative contribution of those exceptional updates.
Without replacement: For SGD without replacement, training is organized into epochs whose permutations determine the sample order, with each epoch starting from the previous epoch’s last iterate.The resulting proposition establishes stability bounds for Hölder-continuous subgradients.
Without replacement: The without-replacement proof sums the per-iteration inequality within each epoch and then aggregates across epochs.Uniform random permutations make each example equally likely to occupy each position, enabling the expectation step.