Research map / Optimization / Implicit bias and generalization

Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression

ICML 2025 · Optimization › Implicit bias and generalization · approach: Implicit regularization of SGD · 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.

Shows that early-stopped gradient descent is calibrated and consistent for well-specified overparameterized logistic regression, while interpolating estimators (including asymptotic GD) are miscalibrated and need exponentially many samples for small zero-one error, and bounds the distance between the GD and l2-regularization paths.

Problem

Understanding the statistical benefits of early stopping in gradient descent for overparameterized, well-specified logistic regression, where interpolating (max-margin) solutions may overfit and be poorly calibrated.

Approach

Combines an implicit-bias lemma for early-stopped GD (norm and empirical-risk control via a comparator) with Rademacher/local Rademacher analysis to obtain risk bounds, and contrasts them with lower bounds for all interpolating estimators, showing that early stopping yields calibration and polynomial sample complexity whereas max-margin GD does not.

Key results

• Early-stopped GD attains vanishing excess logistic risk under well-specification with ||w*||_Sigma finite, while GD at convergence has unbounded logistic risk and calibration error bounded below by exp(-C||w*||_Sigma).
• Under a sparse setting, every interpolating estimator has excess zero-one error at least ~1/sqrt(ln(n) ln(1/delta)), whereas early-stopped GD needs only polynomially many samples.
• For any convex smooth problem, GD path and l2-regularization path differ in norm by a factor between 0.585 and 3.415 and in angle by at most pi/4.

Measured effects reported in the paper

Surprising findings

• GD at convergence (asymptotic max-margin) has unbounded logistic risk, despite converging in direction to a max-margin solution.
• The l2-distance between GD and l2-regularization paths can diverge to infinity in a simple two-point counterexample where the support vector condition fails.

Limitations

• Results are theoretical; the early-stopping time depends on oracle knowledge of the true parameter w*, so the rule is not practical.
• Bounds are not sharp; the exact bias-variance trade-off for early-stopped GD in logistic regression remains open.
• Lower bounds for zero-one error are stated for every interpolator but the maximum-margin constant lower bound is only conjectured.

Experimental setup

Metrics: excess logistic risk excess zero-one error calibration error sample complexity

Baselines: asymptotic GD maximum l2-margin solution l2-regularized ERM interpolating estimators

Builds on: implicit bias of gradient descent on separable data benign overfitting l2-regularization path

Closest papers by meaning

• Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes (ICML 2025 · similarity 0.88)
• Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification (NeurIPS 2026 · similarity 0.88)
• Risk Bounds of Accelerated SGD for Overparameterized Linear Regression (ICLR 2024 · similarity 0.87)
• Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design (NeurIPS 2026 · similarity 0.87)
• Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression (NeurIPS 2025 · similarity 0.86)
• Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regression (NeurIPS 2024 · similarity 0.85)