Research map / Optimization / Nonconvex and smooth optimization

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization

ICML 2025 · Optimization › Nonconvex and smooth optimization · approach: Stochastic gradient last-iterate analysis

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.

Theoretically shows that multi-pass SGD in non-smooth stochastic convex optimization can overfit rapidly after the first epoch, with population excess risk Θ(1/(ηT)+η√T), and proves matching upper and lower bounds for without- and with-replacement variants.

Problem

Whether SGD tuned to attain the minimax optimal Θ(1/√n) population rate after one pass degrades in out-of-sample (population) performance after a few additional passes in the general non-smooth stochastic convex optimization setting.

Approach

Builds a sample-dependent oracle lower-bound construction (adapting Feldman's function and Livni's 2024 constructions) showing that SGD, after memorizing the training set in its first epoch, can be steered toward a spurious empirical minimizer with large population loss; it proves tight Θ(1/(ηT)+η√T) population risk bounds for multi-pass SGD and a Ω(η√n) empirical risk lower bound for one-pass SGD

Key results

• Multi-pass SGD with step size η=Θ(1/√n) can reach population loss Ω(1) after one additional pass (lower bound Ω(min{η√T+1/(ηT),1})).
• Matching upper bound O(η√T + 1/(ηT) + ηT/n) for multi-shuffle and single-shuffle multi-pass SGD, with suffix averaging τ=Ω(T).
• One-pass SGD has empirical risk gap Ω(min{η√n,1}) in dimension d=Õ(n), improving prior quadratic-dimension constructions.

Measured effects reported in the paper

Surprising findings

• SGD achieves optimal population rate after the first pass but overfits rapidly starting from the second pass, a phase transition absent for GD.
• One-pass SGD can have Ω(1) generalization gap even with optimal step size.

Limitations

• Results are only effective from the end of the second epoch; behavior during the second pass is not precisely characterized.
• Lower bounds rely on constructed adversarial distributions and a sample-dependent oracle reduction; not shown for smooth projected SGD.
• Upper bound for with-replacement SGD requires O(n log n) steps before the lower bound applies.

Experimental setup

Metrics: population excess risk empirical risk gap

Baselines: one-pass SGD full-batch gradient descent with-replacement SGD

Builds on: Livni (2024) sample-dependent oracle lower bounds Feldman (2016) function Amir et al. (2021) Koren et al. (2022) Schliserman et al. (2024) Bassily et al. (2020) stability bounds

Closest papers by meaning

• Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime (NeurIPS 2025 · similarity 0.91)
• The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.89)
• Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.89)
• Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation (ICLR 2025 · similarity 0.88)
• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods (ICLR 2024 · similarity 0.88)
• Risk Bounds of Accelerated SGD for Overparameterized Linear Regression (ICLR 2024 · similarity 0.88)