Research map / Optimization / Implicit bias and generalization
A Precise Characterization of SGD Stability Using Loss Surface Geometry
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives necessary and sufficient-style characterization of linearized SGD stability at a minimum, introducing a Hessian coherence measure σ that yields a divergence condition depending on learning rate, batch size, n, and σ.
Problem
When does SGD become linearly unstable at a stationary point (a proxy for sharpness and generalization), as a function of hyperparameters and loss geometry, for general additively decomposable losses beyond MSE?
Approach
Introduces a coherence measure σ, the normalized top eigenvalue of the entry-wise square-root Gram matrix of per-sample Hessians, giving a simplified sufficient condition for divergence of linearized SGD and a near-tight matching lower-bound construction; the analysis applies to any additively decomposable twice-differentiable loss, including cross-entropy with label smoothing.
Key results
- Sufficient divergence condition: λ1(H) > (σ/η)(n/B − 1)^(-1/2) (or λ1(H) > 2/η), with σ ∈ [1, √n] in the examples.
- Lower-bound construction shows the condition is within a constant factor of optimal for σ, n/B = O(1).
- Synthetic quadratic experiments with n=100 confirm divergence boundaries predicted by the theorems as σ and B vary.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Vary Hessian coherence σ; lower σ | SGD on synthetic quadratic loss · Additively decomposable quadratic loss | stability | Hurt |
| Increase batch size B | SGD on synthetic quadratic loss · Additively decomposable quadratic loss | stability boundary accuracy | Helped |
| Use learning rate η = 0.5 rather than η = 0.8 | SGD on synthetic quadratic loss · Additively decomposable quadratic loss | lower-bound accuracy | Mixed |
| Use SGD sampling without replacement instead of Bernoulli sampling | SGD on synthetic quadratic loss · Additively decomposable quadratic loss | stability behavior | No clear effect |
| Choose parameter tuples guaranteed divergent by the theorem | SGD on synthetic quadratic loss · Additively decomposable quadratic loss | divergence | Helped |
| Choose parameter tuples guaranteed not to diverge by the theorem | SGD on synthetic quadratic loss · Additively decomposable quadratic loss | divergence | Hurt |
Surprising findings
- Hessian alignment (large σ) can cause instability even when η is small and B is on the order of n.
Limitations
- Only synthetic quadratic experiments; σ not measured for realistic neural networks.
- Sufficient condition is not tight in regime B ≪ n; gap between upper and lower bounds remains.
- Analysis based on local quadratic approximation around a minimum with PSD per-sample Hessians.
Experimental setup
Metrics: divergence of expected iterate norm
Baselines: Theorem 3.3 of Wu et al. (MSE linear stability condition)
Builds on: linear stability analysis of SGD (Wu et al.) edge of stability
Closest papers by meaning
- The alignment property of SGD noise and how it helps select flat minima: A stability analysis (NeurIPS 2022 · similarity 0.92)
- Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent (ICML 2020 · similarity 0.92)
- A Unified Stability Analysis of SAM vs SGD: Role of Data Coherence and Emergence of Simplicity Bias (NeurIPS 2025 · similarity 0.92)
- Convergence Rates for Gradient Descent on the Edge of Stability for Overparametrised Least Squares (NeurIPS 2025 · similarity 0.89)
- Error Analysis Affected by Heavy-Tailed Gradients for Non-Convex Pairwise Stochastic Gradient Descent (AAAI 2025 · similarity 0.89)
- Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters (NeurIPS 2026 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.