# Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression

arXiv: https://arxiv.org/abs/2506.02336 · HTML: https://mlsanity.com/paper/2506.02336/

## 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 (most cited first, 22 of 22)

- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability](https://mlsanity.com/paper/2103.00065/) (2021)
- [Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability](https://mlsanity.com/paper/2209.15594/) (2022)
- [Understanding Gradient Descent on Edge of Stability in Deep Learning](https://mlsanity.com/paper/2205.09745/) (2022)
- [Risk and parameter convergence of logistic regression](https://mlsanity.com/paper/1803.07300/) (2018)
- [Understanding Optimization in Deep Learning with Central Flows](https://mlsanity.com/paper/2410.24206/) (2024)
- [Understanding Edge-of-Stability Training Dynamics with a Minimalist Example](https://mlsanity.com/paper/2210.03294/) (2022)
- [Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability](https://mlsanity.com/paper/2305.11788/) (2023)
- [Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency](https://mlsanity.com/paper/2402.15926/) (2024)
- [On the proliferation of support vectors in high dimensions](https://mlsanity.com/paper/2009.10670/) (2020)
- [Gradient Methods Never Overfit On Separable Data](https://mlsanity.com/paper/2007.00028/) (2020)
- [Provably Faster Gradient Descent via Long Steps](https://mlsanity.com/paper/2307.06324/) (2023)
- [Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule](https://mlsanity.com/paper/2309.07879/) (2023)
- [Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization](https://mlsanity.com/paper/2406.08654/) (2024)
- [Taking a Big Step: Large Learning Rates in Denoising Score Matching Prevent Memorization](https://mlsanity.com/paper/2502.03435/) (2025)
- [Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes](https://mlsanity.com/paper/2406.05033/) (2024)
- [Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes](https://mlsanity.com/paper/2406.06838/) (2024)
- [Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression](https://mlsanity.com/paper/2502.13283/) (2025)
- [Tight Risk Bounds for Gradient Descent on Separable Data](https://mlsanity.com/paper/2303.01135/) (2023)
- [Anytime Acceleration of Gradient Descent](https://mlsanity.com/paper/2411.17668/) (2024)
- [Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes](https://mlsanity.com/paper/2504.04105/) (2025)

## Built on by (most cited first, 9 of 9)

- [Edge Flow: A Tractable and Predictive Continuous-Time Model for Gradient Descent at the Edge of Stability](https://mlsanity.com/paper/2606.18080/) (2026)
- [SGD at the Edge of Stability: Stochastic Stabilization with Large Learning Rates](https://mlsanity.com/paper/2606.30930/) (2026)
- [Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension](https://mlsanity.com/paper/2602.12471/) (2026)
- [Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design](https://mlsanity.com/paper/2606.21683/) (2026)
- [Dynamics of Gradient Descent with Large Step Size Near a Manifold of Flat Minima](https://mlsanity.com/paper/2607.08380/) (2026)
- [Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regression](https://mlsanity.com/paper/2602.18946/) (2026)
- [The Multiple Timescales of Gradient Descent on the Edge of Stability: A Perturbative Derivation of the Central Flow](https://mlsanity.com/paper/2609.01034/) (2026)
- [When Does Scale-Invariant Optimization Become Unstable? An Exact Schedule Law with Weight Decay](https://mlsanity.com/paper/2609.09116/) (2026)
- [Large Stepsizes Federated Learning on Logistic Regression with Linearly Separable Data: The Case of Heterogeneous Devices](https://mlsanity.com/paper/2610.05915/) (2026)

## 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.