mlsanityData to 14 Oct 2026

Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression

arXiv 2506.02336 ↗First posted 3 Jun 2025stat.ML cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

We study gradient descent (GD) with a constant stepsize for ℓ2-regularized logistic regression with linearly separable data. Classical theory suggests small stepsizes to ensure monotonic reduction of the optimization objective, achieving exponential convergence in widetildeO(kappa) steps with kappa being the condition number. Surprisingly, we show that this can be accelerated to widetildeO(√kappa) by simply using a large stepsize -- for which the objective evolves nonmonotonically. The acceleration brought by large stepsizes extends to minimizing the population risk for separable distributions, improving on the best-known upper bounds on the number of steps to reach a near-optimum. Finally, we characterize the largest stepsize for the local convergence of GD, which also determines the global convergence in special scenarios. Our results extend the analysis of Wu et al. (2024) from convex settings with minimizers at infinity to strongly convex cases with finite minimizers.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 22 of its 40 references that are in the map. First posted on arXiv 3 Jun 2025.

Builds on

22 of 40 references.

References · 22

  1. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  2. 2019Benign Overfitting in Linear Regressioncited by 549
  3. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 427
  4. 2022Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stabilitycited by 155
  5. 2022Understanding Gradient Descent on Edge of Stability in Deep Learningcited by 128
  6. 2018Risk and parameter convergence of logistic regressioncited by 85
  7. 2024Understanding Optimization in Deep Learning with Central Flowscited by 64
  8. 2022Understanding Edge-of-Stability Training Dynamics with a Minimalist Examplecited by 56
  9. 2023Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stabilitycited by 42
  10. 2024Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiencycited by 35
  11. 2020On the proliferation of support vectors in high dimensionscited by 32
  12. 2020Gradient Methods Never Overfit On Separable Datacited by 29
10 more
  1. 2023Provably Faster Gradient Descent via Long Stepscited by 20
  2. 2023Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedulecited by 19
  3. 2024Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimizationcited by 17
  4. 2025Taking a Big Step: Large Learning Rates in Denoising Score Matching Prevent Memorizationcited by 17
  5. 2024Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizescited by 14
  6. 2024Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizescited by 12
  7. 2025Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regressioncited by 9
  8. 2023Tight Risk Bounds for Gradient Descent on Separable Datacited by 7
  9. 2024Anytime Acceleration of Gradient Descentcited by 7
  10. 2025Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizescited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 9.

9 papers.

  1. 2026Edge Flow: A Tractable and Predictive Continuous-Time Model for Gradient Descent at the Edge of Stabilitycited by 3
  2. 2026SGD at the Edge of Stability: Stochastic Stabilization with Large Learning Ratescited by 2
  3. 2026Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimensioncited by 1
  4. 2026Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Designcited by 1
  5. 2026Dynamics of Gradient Descent with Large Step Size Near a Manifold of Flat Minimacited by 1
  6. 2026Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regressioncited by 0
  7. 2026The Multiple Timescales of Gradient Descent on the Edge of Stability: A Perturbative Derivation of the Central Flowcited by 0
  8. 2026When Does Scale-Invariant Optimization Become Unstable? An Exact Schedule Law with Weight Decaycited by 0
  9. 2026Large Stepsizes Federated Learning on Logistic Regression with Linearly Separable Data: The Case of Heterogeneous Devicescited by 0