PaperlayerView exact revision on arXiv

Source-linked AI summary

Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses

Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, Kunal Talwar

arXiv:2006.06914v1cs.LGmath.OCstat.ML

TL;DR

The paper studies the poorly understood uniform stability of SGD on nonsmooth convex losses. It proves sharp upper and lower bounds for GD and SGD, then uses them to obtain dimension-independent multi-pass generalization guarantees and an optimal-risk private algorithm. The results also show that nonsmooth methods may require smaller step sizes and longer runs, with quadratic iteration complexity in the privacy application.

  • Problem

    Uniform stability bounds were known for SGD on sufficiently smooth convex losses, but not for nonsmooth convex losses where generalization remains poorly understood.

  • Method

    The paper analyzes uniform argument stability for full-batch GD and multiple SGD variants using matching upper and lower bounds, including a nonsmooth hard instance.

  • Results

    The bounds yield optimal expected excess risk O(LR/√n) with T = n^2 and establish that the corresponding stability arguments are sharp up to absolute constant factors.

  • Takeaways & Limitations

    The results provide dimension-independent generalization bounds for multi-pass nonsmooth SGD and an optimal-risk differentially private noisy-SGD algorithm.

  • Takeaways & Limitations

    The privacy algorithm achieves optimal risk with n^2 steps, which is impractical for large datasets; whether quadratic time is necessary remains open.

Abstract

from arXiv · show

Uniform stability is a notion of algorithmic stability that bounds the worst case change in the model output by the algorithm when a single data point in the dataset is replaced. An influential work of Hardt et al. (2016) provides strong upper bounds on the uniform stability of the stochastic gradient descent (SGD) algorithm on sufficiently smooth convex losses. These results led to important progress in understanding of the generalization properties of SGD and several applications to differentially private convex optimization for smooth losses. Our work is the first to address uniform stability of SGD on {\em nonsmooth} convex losses. Specifically, we provide sharp upper and lower bounds for several forms of SGD and full-batch GD on arbitrary Lipschitz nonsmooth convex losses. Our lower bounds show that, in the nonsmooth case, (S)GD can be inherently less stable than in the smooth case. On the other hand, our upper bounds show that (S)GD is sufficiently stable for deriving new and useful bounds on generalization error. Most notably, we obtain the first dimension-independent generalization bounds for multi-pass SGD in the nonsmooth case. In addition, our bounds allow us to derive a new algorithm for differentially private nonsmooth stochastic convex optimization with optimal excess population risk. Our algorithm is simpler and more efficient than the best known algorithm for the nonsmooth case Feldman et al. (2020).

1 Introduction

This work establishes tight stability bounds for GD and SGD on nonsmooth convex losses, addressing a gap left by smooth-loss analyses. The bounds yield dimension-independent generalization guarantees for multi-pass SGD and an optimal-risk differentially private algorithm, while lower bounds expose inherent stability costs.

  • Motivation: Nonsmooth losses lack the nonexpansiveness used in smooth-loss analyses, leaving no previously known non-trivial uniform-stability bounds for SGD.The obstruction applies to losses such as the hinge loss.
  • Contributions: The paper establishes tight upper and lower bounds for uniform argument stability of GD and several SGD variants on arbitrary Lipschitz nonsmooth convex losses.The analysis includes high-probability upper bounds and matching expectation-based lower bounds.
  • Stability results: Nonsmooth SGD can be inherently less stable than smooth SGD, with an additional ηT term affecting stability and making the standard η = Θ(1/√n) step size vacuous.The paper shows that reducing the step size and increasing iterations can recover a near-optimal stability–empirical-risk balance.
  • Generalization: Multi-pass SGD with K passes has generalization error bounded by O((Kn + K)η), enabling excess-risk guarantees when training error is small.These are the first dimension-independent generalization bounds stated for this nonsmooth multi-pass setting.
  • Privacy application: A noisy-SGD variant for differentially private nonsmooth stochastic convex optimization attains optimal excess population risk with n^2 iterations.The approach is simpler and more efficient than the cited prior algorithm, which uses multi-phase regularized SGD and O(n^2 log(1/β)) gradient computations.

2 Notation and Preliminaries

The paper studies nonsmooth stochastic convex optimization on compact Euclidean domains and uses uniform argument stability to connect algorithm outputs to generalization and excess population risk.

  • Problem setting: The optimization setting minimizes population risk over an unknown distribution using an i.i.d. sample, with convex Lipschitz losses on a compact convex domain.The domain lies within a Euclidean ball of radius R, and the losses are bounded through their Lipschitz constant.
  • Risk decomposition: Excess population risk is analyzed through optimization, generalization, and approximation errors.The approximation error has a high-probability ˜O(LR/√n) bound, so optimization and generalization errors are the main terms to control.
  • Stability notions: Uniform argument stability measures the ℓ2 output change when neighboring datasets differ in one entry.For L-Lipschitz losses, an upper bound on output distance directly yields an upper bound on uniform stability.
  • Paper roadmap: The paper gives UAS upper and lower bounds for full-batch GD and two stochastic-gradient variants, including high-probability guarantees for sampling with replacement.The variants are full-batch GD, sampling-with-replacement SGD, and fixed-permutation SGD.
  • From stability to generalization: High-probability UAS bounds can be converted into high-probability generalization-error guarantees.The conversion uses a theorem relating UAS assumptions to εgen(A).

3 Upper Bounds on Uniform Argument Stability

The upper-bound analysis uses a common trajectory lemma to control UAS for batch GD and two SGD variants on nonsmooth convex losses. These bounds support generalization analysis but can require many iterations for optimal excess risk.

  • Common analysis: A common lemma bounds trajectory deviation by the first differing objective and subsequent subgradient discrepancies.All studied GD variants satisfy the lemma’s distance condition between subgradients.
  • Algorithmic bounds: Full-batch GD, sampling-with-replacement SGD, and fixed-permutation SGD receive UAS upper bounds under their respective update rules.The sampling-with-replacement guarantee holds with high probability, while the fixed-permutation result holds for every permutation under non-increasing step sizes.
  • Sampling-with-replacement SGD: Sampling-with-replacement SGD preserves the batch-GD stability rate with high probability despite cheaper iterations.The high-probability guarantee is at least 1 −exp(−n/2) for constant step size.
  • Fixed-permutation SGD: Fixed-permutation SGD has the same UAS bound as batch GD and sampling-with-replacement SGD, with a tighter expectation guarantee possible for a uniformly random permutation.The stated upper bound assumes a non-increasing step-size sequence.
  • Risk implications: Choosing T = n2 iterations yields expected excess risk O(LR/√n), which is optimal, while T = o(n2) cannot attain the same rate from the stability bound.For constant step size, T = ω(n2) also cannot recover the optimal excess risk.
  • Tightness: The upper stability bounds are sharp up to absolute constant factors, motivating matching lower bounds.This establishes that the high iteration requirement is not merely an artifact of loose analysis.

4 Lower Bounds on Uniform Argument Stability

The paper proves matching lower bounds for batch GD and two SGD variants, showing that the nonsmooth stability upper bounds are tight up to absolute constant factors.

  • Lower-bound framework: The lower bounds are constructed for specific first-order methods and use polyhedral objectives with adversarial extreme-point subgradients.This oracle choice is allowed because the algorithms must work for any subgradient oracle.
  • General lower bound: A general small-step-size argument also yields an Ω(LTη/n) stability lower bound for first-order methods.In the nonsmooth setting, this general lower bound is much weaker than the sharper algorithm-specific bounds.
  • Full-batch GD: For full-batch GD with constant step size, neighboring datasets can produce a lower-bounded UAS when d ≥ min{T, 1/η2}.The lower bound applies to the deterministic batch method under the stated dimensional condition.
  • Sampling-with-replacement SGD: For sampling-with-replacement SGD with constant step size, neighboring datasets can produce expected UAS of order Ω(...).The construction exploits repeated sampling of the changed data point and is analyzed through the resulting trajectory displacement.

5 Generalization Guarantees for Multi-pass SGD

The stability bounds yield non-trivial, dimension-independent generalization guarantees for multi-pass SGD on nonsmooth losses. Combined with optimization analysis, they imply optimal excess risk within n passes under an appropriate constant step size.

  • Setting: Multi-pass SGD is analyzed for K passes over n samples, with T = Kn iterations.The result addresses a commonly used practical regime for SGD on nonsmooth losses.
  • Generalization guarantees: Theorem 5.1 provides generalization-error guarantees for sampling-with-replacement SGD run for K passes with constant step size.It includes a high-probability guarantee over the sample and algorithmic randomness.
  • Proof route: The guarantees follow by converting the UAS bound into uniform stability and then applying a general stability-to-generalization theorem.The high-probability result combines the high-probability UAS guarantee with the same conversion theorem.
  • Excess risk: With appropriately chosen constant step size, multi-pass SGD is guaranteed to attain optimal excess risk of approximately LR/√n within n passes.The risk implication assumes that optimization error can be certified as small in the practical setting.

6 Implications of Our Stability Bounds

The stability bounds yield applications to nonsmooth stochastic convex optimization, including a private noisy-SGD algorithm with optimal excess population risk and nearly optimal multi-pass SGD guarantees.

  • Differentially Private Nonsmooth Stochastic Convex Optimization: n^2 gradient computations suffice for a simple noisy-SGD variant to achieve optimal excess population risk for DP-SCO.The algorithm is substantially simpler than the best previous nonsmooth-case method.
  • Differentially Private Nonsmooth Stochastic Convex Optimization: Algorithm 4, ANSGD, is (α, β)-differentially private.
  • Differentially Private Nonsmooth Stochastic Convex Optimization: ANSGD attains the same UAS bound as ArSGD because identical noise sequences cancel in the stability comparison.
  • Multi-Pass SGD: One-pass SGD has expected excess population risk O(1/√n), but this analysis does not apply to multi-pass SGD.
  • Multi-Pass SGD: Algorithms 2 and 3 recover nearly optimal high-probability excess risk bounds by making n passes over the data.

7 Discussion and Open Problems

The paper presents sharp stability results and applications while identifying open limitations concerning randomized lower bounds and the computational cost of private optimization.

  • The work provides sharp upper and lower bounds on uniform argument stability for stochastic subgradient methods in nonsmooth convex optimization.
  • Reducing the step size and running algorithms longer enables optimal population risk bounds despite inherent nonsmooth-case stability limitations.
  • Open Problems: Lower bounds are not robust to general algorithmic randomization because random initialization can prevent trajectories from reaching highly nonsmooth regions.
  • Open Problems: The privacy application achieves optimal risk in n^2 steps, which is impractical for large datasets; whether quadratic time is necessary remains open.

A Proof of Theorem 3.2

The proof analyzes neighboring-data trajectories for batch gradient descent, combining stability recurrences, risk decomposition, and optimization guarantees to relate iteration count and step size.

  • For neighboring datasets, the proof tracks the distance between batch-GD trajectories initialized at the same point.
  • Conditioning on the randomly perturbed coordinate reduces fixed-permutation SGD stability analysis to the affected data point.
  • After the differing example is processed, monotonicity of subgradients and averaging are used to control trajectory separation.
  • Risk decomposition combines a stability term with the nonsmooth optimization lower bound to constrain achievable population risk.
  • For sufficiently many iterations, the argument relates the stability growth s(T) to the constant step size η and iteration count T.

D Proof of Theorem 4.1

The lower-bound proof constructs a highly nonsmooth objective whose data-dependent drift drives orthogonal subgradient steps, producing unavoidable stability growth in sufficiently high dimension.

  • The construction requires K ≥ √D for normalization, while later steps contribute only negligible linear-drift perturbations.
  • The construction defines neighboring empirical objectives whose differing linear component affects one trajectory while the other remains at zero.
  • Sequential steps accumulate along e1, e2, and subsequent coordinate directions through the first D coordinates.
  • Averaging does not improve the lower bound in either D = T or D = 1/η^2 regimes, and an additional Ω(ηT/n) term follows.

E Proof of Theorem 4.3

The proof establishes matching lower bounds for SGD stability by comparing trajectories on neighboring datasets, showing the upper-bound analyses are tight up to absolute constants.

  • Proof strategy: Neighboring datasets differ in one entry, and the proof compares their SGD trajectories from the same initialization.The datasets are S′ = (0, 0, . . . , 0) and S = (1, 0, . . . , 0), with both trajectories initialized at zero.
  • Lower-bound behavior: Later iterations reach ∥x_t∥ = 1 − o(1) when D = 1/η^2, while the algorithm stops earlier otherwise.This trajectory behavior supplies the main lower-bound contribution.
  • Proof strategy: The differing index is tracked through the event that it has been sampled at least once by iteration t.The proof derives conditional recurrences for trajectory differences based on whether the differing index has appeared.
  • Algorithm comparison: Sampling-with-replacement and fixed-permutation SGD have uniform argument stability bounds of the same order.The proof separately analyzes the sampling event for Algorithm 2 and states the same-order conclusion for Algorithms 2 and 3.

G.0.2 Risk Bounds for Fixed-Permutation Stochastic Gradient Descent

The fixed-permutation SGD analysis yields population risk bounds even for arbitrary, nonrandom permutations, without reshuffling or other randomization.

  • Generalization consequence: Fixed-permutation SGD obtains generalization bounds for arbitrary permutations without reshuffling or any form of randomization.The result combines incremental-method optimization analysis with stability bounds that apply to arbitrary permutations.
  • Parameter setting: Algorithm 3 is analyzed with constant step size η_k ≡ η = R/[L√nK] over K = n epochs.The theorem specifies the step-size schedule and number of epochs for the fixed-permutation procedure.
  • Guarantee: For expected excess risk, the polylogarithmic factor can be removed, yielding the optimal expected-excess-risk dependence.This refinement applies when only expectation risk bounds are required.

H High-probability Bound on Optimization Error of SGD with Noisy Gradient Oracle

The appendix formulates high-probability optimization guarantees for SGD with noisy gradient oracles and supplies an optimization analysis for fixed-permutation SGD.

  • Setup: The noisy-gradient analysis assumes convex L-Lipschitz losses over X ⊆ B(0, R) and updates x_{t+1} = x_t − η · g(x, ξ_t).The oracle samples data with replacement and is analyzed through the stated stochastic-gradient recursion.
  • Oracle assumptions: The oracle is unbiased, has σ^2-sub-Gaussian gradient noise, and is independent across iterations conditional on sampled data.These are the three explicit oracle conditions used by the optimization lemma.
  • High-probability guarantee: With probability at least 1 − θ, the stochastic subgradient method’s optimization error is bounded for θ ∈ (4e^−T/32, 1).The high-probability guarantee follows by combining concentration bounds and a union bound.
  • Proof ingredients: The optimization proof combines martingale, Hoeffding, Azuma, Bernstein, and online-gradient-descent arguments.These tools bound the separate terms in the excess empirical-risk decomposition.
  • Fixed-permutation analysis: For arbitrary fixed permutations and constant step sizes within epochs, an incremental-method lemma yields optimization accuracy for fixed-permutation SGD.The appendix states the lemma and derives a corollary using convexity.
Loading 2006.06914v1…