Research map / Optimization / Nonconvex and smooth optimization

Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Stochastic gradient last-iterate analysis · 0 citations (OpenAlex)

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.

Analyzes generalization error and uniform (argument) stability of GD and SGD over fixed-point grids with deterministic or stochastic rounding, showing deterministic rounding degrades GD generalization to O(T/sqrt n) and stochastic rounding can introduce dimension-dependent generalization error.

Problem

How discrete fixed-point parameter spaces with rounding affect the generalization error and algorithmic stability of gradient descent and SGD on convex, Lipschitz, smooth losses.

Approach

Treats GD/SGD iterates on the grid Z_Delta^d with deterministic (DR) or stochastic (SR) rounding and derives matching upper/lower bounds on generalization error, uniform stability, and uniform argument stability, showing qualitative differences from real-valued GD/SGD (e.g., DR-GD stability is Omega(T), DR-SGD gives O(T/n) in d=1 and O(T^2/n) in higher d).

Key results

• Deterministic-rounding GD generalization error is upper bounded by 2ηL²T/√n on binary samples and matched by a lower bound of order ΔLT/√n.
• Uniform stability of DR-GD is lower bounded by Ω(ΔLT), independent of n, so stability-based bounds are vacuous.
• DR-SGD uniform stability is bounded by (2ηL+Δ)LT/n in d=1 and tight bounds of order T²/n appear for d≥2.

Surprising findings

• Deterministic rounding makes GD generalization worse than real-valued GD, with stability-based analysis failing to capture it (stability Omega(T)).
• Stochastic rounding can make generalization error grow with dimension d, a effect absent in real-valued GD/SGD.

Limitations

• Analysis assumes exact real-valued gradient computation and ignores round-off in automatic differentiation.
• Does not cover quantization-aware training with high-precision parameters.
• Floating-point extension is only sketched for regimes with fixed exponent range.

Experimental setup

Metrics: generalization error uniform stability uniform argument stability

Baselines: GD on real-valued parameters SGD on real-valued parameters

Builds on: algorithmic stability (Hardt et al. 2016)

Closest papers by meaning

• Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm (ICML 2024 · similarity 0.91)
• Error Analysis Affected by Heavy-Tailed Gradients for Non-Convex Pairwise Stochastic Gradient Descent (AAAI 2025 · similarity 0.90)
• Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems (NeurIPS 2026 · similarity 0.90)
• Stability and Generalization Analysis of Decentralized SGD: Sharper Bounds Beyond Lipschitzness and Smoothness (ICML 2025 · similarity 0.89)
• A Precise Characterization of SGD Stability Using Loss Surface Geometry (ICLR 2024 · similarity 0.89)
• Convergence Rates for Gradient Descent on the Edge of Stability for Overparametrised Least Squares (NeurIPS 2025 · similarity 0.89)