# Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 47 references that are in the map.
- First posted on arXiv 24 Feb 2024.

## Builds on (most cited first, 29 of 29)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Train longer, generalize better: closing the generalization gap in large batch training of neural networks](https://mlsanity.com/paper/1705.08741/) (2017)
- [Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability](https://mlsanity.com/paper/2209.15594/) (2022)
- [Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1811.08888/) (2018)
- [Understanding the unstable convergence of gradient descent](https://mlsanity.com/paper/2204.01050/) (2022)
- [Understanding the Generalization Benefit of Normalization Layers: Sharpness Reduction](https://mlsanity.com/paper/2206.07085/) (2022)
- [Risk and parameter convergence of logistic regression](https://mlsanity.com/paper/1803.07300/) (2018)
- [How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?](https://mlsanity.com/paper/1911.12360/) (2019)
- [SGD with Large Step Sizes Learns Sparse Features](https://mlsanity.com/paper/2210.05337/) (2022)
- [Analyzing Sharpness along GD Trajectory: Progressive Sharpening and Edge of Stability](https://mlsanity.com/paper/2207.12678/) (2022)
- [Understanding Edge-of-Stability Training Dynamics with a Minimalist Example](https://mlsanity.com/paper/2210.03294/) (2022)
- [Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect](https://mlsanity.com/paper/2110.03677/) (2021)
- [Beyond the Quadratic Approximation: the Multiscale Structure of Neural Network Loss Landscapes](https://mlsanity.com/paper/2204.11326/) (2022)
- [Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability](https://mlsanity.com/paper/2305.11788/) (2023)
- [Beyond the Edge of Stability via Two-step Gradient Updates](https://mlsanity.com/paper/2206.04172/) (2022)
- [Margins, Shrinkage, and Boosting](https://mlsanity.com/paper/1303.4172/) (2013)
- [Fast Margin Maximization via Dual Acceleration](https://mlsanity.com/paper/2107.00595/) (2021)
- [Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound](https://mlsanity.com/paper/2011.04586/) (2020)
- [Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function](https://mlsanity.com/paper/2002.06189/) (2020)
- [Good regularity creates large learning rate implicit biases: edge of stability, balancing, and catapult](https://mlsanity.com/paper/2310.17087/) (2023)
- [Gradient Descent Monotonically Decreases the Sharpness of Gradient Flow Solutions in Scalar Networks and Beyond](https://mlsanity.com/paper/2305.13064/) (2023)
- [Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimization](https://mlsanity.com/paper/2309.16530/) (2023)
- [Near-Tight Margin-Based Generalization Bounds for Support Vector Machines](https://mlsanity.com/paper/2006.02175/) (2020)
- [Is Importance Weighting Incompatible with Interpolating Classifiers?](https://mlsanity.com/paper/2112.12986/) (2021)
- [From Stability to Chaos: Analyzing Gradient Descent Dynamics in Quadratic Regression](https://mlsanity.com/paper/2310.01687/) (2023)
- [Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales](https://mlsanity.com/paper/2111.03137/) (2021)
- [Characterizing the implicit bias via a primal-dual analysis](https://mlsanity.com/paper/1906.04540/) (2019)

## Built on by (most cited first, 30 of 35)

- [Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data](https://mlsanity.com/paper/2502.04664/) (2025)
- [Iteration Head: A Mechanistic Study of Chain-of-Thought](https://mlsanity.com/paper/2406.02128/) (2024)
- [Deep linear networks for regression are implicitly regularized towards flat minima](https://mlsanity.com/paper/2405.13456/) (2024)
- [Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization](https://mlsanity.com/paper/2406.08654/) (2024)
- [Learning Associative Memories with Gradient Descent](https://mlsanity.com/paper/2402.18724/) (2024)
- [Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes](https://mlsanity.com/paper/2406.05033/) (2024)
- [Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression](https://mlsanity.com/paper/2502.13283/) (2025)
- [Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression](https://mlsanity.com/paper/2506.02336/) (2025)
- [Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes](https://mlsanity.com/paper/2504.04105/) (2025)
- [Gradient Descent with Large Step Sizes: Chaos and Fractal Convergence Region](https://mlsanity.com/paper/2509.25351/) (2025)
- [Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?](https://mlsanity.com/paper/2507.11228/) (2025)
- [Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates](https://mlsanity.com/paper/2502.07141/) (2025)
- [Convergence Rates for Gradient Descent on the Edge of Stability in Overparametrised Least Squares](https://mlsanity.com/paper/2510.17506/) (2025)
- [A lower bound for stepsize-based acceleration of gradient descent](https://mlsanity.com/paper/2608.10418/) (2026)
- [Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster](https://mlsanity.com/paper/2503.00229/) (2025)
- [Edge Flow: A Tractable and Predictive Continuous-Time Model for Gradient Descent at the Edge of Stability](https://mlsanity.com/paper/2606.18080/) (2026)
- [Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability](https://mlsanity.com/paper/2506.13974/) (2025)
- [Adam or Gauss-Newton? A Comparative Study In Terms of Basis Alignment and SGD Noise](https://mlsanity.com/paper/2510.13680/) (2025)
- [Basic Inequalities for First-Order Optimization with Applications to Statistical Risk Analysis](https://mlsanity.com/paper/2512.24999/) (2025)
- [Training on the Edge of Stability Is Caused by Layerwise Jacobian Alignment](https://mlsanity.com/paper/2406.00127/) (2024)
- [Any-stepsize Gradient Descent for Separable Data under Fenchel-Young Losses](https://mlsanity.com/paper/2502.04889/) (2025)
- [Gradient Descent with Provably Tuned Learning-rate Schedules](https://mlsanity.com/paper/2512.05084/) (2025)
- [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)
- [The Road Taken: The Role of Optimizers at the Edge of Stability](https://mlsanity.com/paper/2608.18415/) (2026)
- [Convergence of optimizers implies eigenvalues filtering at equilibrium](https://mlsanity.com/paper/2510.09034/) (2025)
- [Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regression](https://mlsanity.com/paper/2602.18946/) (2026)
- [A Mechanism Study of Delayed Loss Spikes in Batch-Normalized Linear Models](https://mlsanity.com/paper/2604.16809/) (2026)
- [Centre manifold theorem for maps along manifolds of fixed points](https://mlsanity.com/paper/2604.18202/) (2026)

## Abstract (arXiv)

We consider gradient descent (GD) with a constant stepsize applied to logistic regression with linearly separable data, where the constant stepsize η is so large that the loss initially oscillates. We show that GD exits this initial oscillatory phase rapidly -- in O(η) steps -- and subsequently achieves an tildeO(1 / (η t) ) convergence rate after t additional steps. Our results imply that, given a budget of T steps, GD can achieve an accelerated loss of tildeO(1/T2) with an aggressive stepsize η:= Theta( T), without any use of momentum or variable stepsize schedulers. Our proof technique is versatile and also handles general classification loss functions (where exponential tails are needed for the tildeO(1/T2) acceleration), nonlinear predictors in the neural tangent kernel regime, and online stochastic gradient descent (SGD) with a large stepsize, under suitable separability conditions.