mlsanityData to 7 Oct 2026

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

arXiv 2402.15926 ↗First posted 24 Feb 2024cs.LG stat.MLcited by 34

Not on the map. Why?

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.

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

Builds on

29 of 47 references.

References · 29

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,479
  3. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  4. 2017Train longer, generalize better: closing the generalization gap in large batch training of neural networkscited by 278
  5. 2022Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stabilitycited by 151
  6. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 139
  7. 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
  8. 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
  9. 2022Understanding the unstable convergence of gradient descentcited by 84
  10. 2018Risk and parameter convergence of logistic regressioncited by 81
  11. 2022SGD with Large Step Sizes Learns Sparse Featurescited by 66
  12. 2022Analyzing Sharpness along GD Trajectory: Progressive Sharpening and Edge of Stabilitycited by 61
17 more
  1. 2022Understanding Edge-of-Stability Training Dynamics with a Minimalist Examplecited by 54
  2. 2021Large Learning Rate Tames Homogeneity: Convergence and Balancing Effectcited by 48
  3. 2022Beyond the Quadratic Approximation: the Multiscale Structure of Neural Network Loss Landscapescited by 42
  4. 2023Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stabilitycited by 42
  5. 2022Beyond the Edge of Stability via Two-step Gradient Updatescited by 38
  6. 2013Margins, Shrinkage, and Boostingcited by 35
  7. 2021Fast Margin Maximization via Dual Accelerationcited by 33
  8. 2020Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Boundcited by 31
  9. 2020Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Functioncited by 26
  10. 2023Good regularity creates large learning rate implicit biases: edge of stability, balancing, and catapultcited by 23
  11. 2023Gradient Descent Monotonically Decreases the Sharpness of Gradient Flow Solutions in Scalar Networks and Beyondcited by 20
  12. 2023Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimizationcited by 20
  13. 2020Near-Tight Margin-Based Generalization Bounds for Support Vector Machinescited by 19
  14. 2021Is Importance Weighting Incompatible with Interpolating Classifiers?cited by 19
  15. 2023From Stability to Chaos: Analyzing Gradient Descent Dynamics in Quadratic Regressioncited by 16
  16. 2021Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scalescited by 7
  17. 2019Characterizing the implicit bias via a primal-dual analysiscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 6; 2025: 15; 2026: 13.

34 papers.

Sort:

By area:

  1. 2025Implicit Bias of Spectral Descent and Muon on Multiclass Separable Datacited by 33
  2. 2024Iteration Head: A Mechanistic Study of Chain-of-Thoughtcited by 31
  3. 2024Deep linear networks for regression are implicitly regularized towards flat minimacited by 17
  4. 2024Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimizationcited by 17
  5. 2024Learning Associative Memories with Gradient Descentcited by 14
  6. 2024Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizescited by 9
  7. 2025Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regressioncited by 9
  8. 2025Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regressioncited by 7
  9. 2025Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizescited by 5
  10. 2025Gradient Descent with Large Step Sizes: Chaos and Fractal Convergence Regioncited by 5
  11. 2025Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning ratescited by 4
  12. 2026A lower bound for stepsize-based acceleration of gradient descentcited by 4
22 more
  1. 2025Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Fastercited by 3
  2. 2025Convergence Rates for Gradient Descent on the Edge of Stability in Overparametrised Least Squarescited by 3
  3. 2026Edge Flow: A Tractable and Predictive Continuous-Time Model for Gradient Descent at the Edge of Stabilitycited by 3
  4. 2025Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?cited by 2
  5. 2025Adam or Gauss-Newton? A Comparative Study In Terms of Basis Alignment and SGD Noisecited by 2
  6. 2025Basic Inequalities for First-Order Optimization with Applications to Statistical Risk Analysiscited by 2
  7. 2024Training on the Edge of Stability Is Caused by Layerwise Jacobian Alignmentcited by 1
  8. 2025Any-stepsize Gradient Descent for Separable Data under Fenchel-Young Lossescited by 1
  9. 2025Constant Stepsize Local GD for Logistic Regression: Acceleration by Instabilitycited by 1
  10. 2025Gradient Descent with Provably Tuned Learning-rate Schedulescited by 1
  11. 2026Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Designcited by 1
  12. 2026Dynamics of Gradient Descent with Large Step Size Near a Manifold of Flat Minimacited by 1
  13. 2026The Road Taken: The Role of Optimizers at the Edge of Stabilitycited by 1
  14. 2025Convergence of optimizers implies eigenvalues filtering at equilibriumcited by 0
  15. 2026Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimensioncited by 0
  16. 2026Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regressioncited by 0
  17. 2026A Mechanism Study of Delayed Loss Spikes in Batch-Normalized Linear Modelscited by 0
  18. 2026Centre manifold theorem for maps along manifolds of fixed pointscited by 0
  19. 2026Non-asymptotic implicit bias of logistic regression at early-stage gradient descent dynamicscited by 0
  20. 2026The Multiple Timescales of Gradient Descent on the Edge of Stability: A Perturbative Derivation of the Central Flowcited by 0
  21. 2026When Does Scale-Invariant Optimization Become Unstable? An Exact Schedule Law with Weight Decaycited by 0
  22. 2026Muon Sublates the Edge of Stability in LLM Pretrainingcited by 0