mlsanityData to 14 Oct 2026

Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes

arXiv 2504.04105 ↗First posted 5 Apr 2025stat.ML cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

We study textitgradient descent (GD) for logistic regression on linearly separable data with stepsizes that adapt to the current risk, scaled by a constant hyperparameter η. We show that after at most 1/γ2 burn-in steps, GD achieves a risk upper bounded by exp(-Theta(η)), where γ is the margin of the dataset. As η can be arbitrarily large, GD attains an arbitrarily small risk textitimmediately after the burn-in steps, though the risk evolution may be textitnon-monotonic. We further construct hard datasets with margin γ, where any batch (or online) first-order method requires Omega(1/γ2) steps to find a linear separator. Thus, GD with large, adaptive stepsizes is textitminimax optimal among first-order batch methods. Notably, the classical textitPerceptron (Novikoff, 1962), a first-order online method, also achieves a step complexity of 1/γ2, matching GD even in constants. Finally, our GD analysis extends to a broad class of loss functions and certain two-layer networks.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 39 of its 50 references that are in the map. First posted on arXiv 5 Apr 2025.

Builds on

39 of 50 references.

References · 39

  1. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  2. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 427
  3. 2020The large learning rate phase of deep learning: the catapult mechanismcited by 216
  4. 2022Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stabilitycited by 155
  5. 2018Convergence of Gradient Descent on Separable Datacited by 110
  6. 2022Understanding the unstable convergence of gradient descentcited by 86
  7. 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
  8. 2018Risk and parameter convergence of logistic regressioncited by 85
  9. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
  10. 2018A Walk with SGDcited by 78
  11. 2022SGD with Large Step Sizes Learns Sparse Featurescited by 68
  12. 2022Analyzing Sharpness along GD Trajectory: Progressive Sharpening and Edge of Stabilitycited by 63
27 more
  1. 2022Understanding Edge-of-Stability Training Dynamics with a Minimalist Examplecited by 56
  2. 2022Learning threshold neurons via the "edge of stability"cited by 51
  3. 2021Large Learning Rate Tames Homogeneity: Convergence and Balancing Effectcited by 50
  4. 2022Beyond the Quadratic Approximation: the Multiscale Structure of Neural Network Loss Landscapescited by 43
  5. 2023Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stabilitycited by 42
  6. 2022Beyond the Edge of Stability via Two-step Gradient Updatescited by 38
  7. 2023(S)GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stabilitycited by 36
  8. 2024Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiencycited by 35
  9. 2021Fast Margin Maximization via Dual Accelerationcited by 33
  10. 2020Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Functioncited by 26
  11. 2023Good regularity creates large learning rate implicit biases: edge of stability, balancing, and catapultcited by 25
  12. 2023Gradient Descent Monotonically Decreases the Sharpness of Gradient Flow Solutions in Scalar Networks and Beyondcited by 21
  13. 2023Provably Faster Gradient Descent via Long Stepscited by 20
  14. 2023Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimizationcited by 20
  15. 2023Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedulecited by 19
  16. 2023From Stability to Chaos: Analyzing Gradient Descent Dynamics in Quadratic Regressioncited by 17
  17. 2024Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimizationcited by 17
  18. 2024Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Stepscited by 11
  19. 2023Accelerated Gradient Descent via Long Stepscited by 9
  20. 2021Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scalescited by 7
  21. 2024Anytime Acceleration of Gradient Descentcited by 7
  22. 2022On Accelerated Perceptrons and Beyondcited by 6
  23. 2024Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedulecited by 6
  24. 2024From Logistic Regression to the Perceptron Algorithm: Exploring Gradient Descent with Large Step Sizescited by 6
  25. 2024Accelerated Gradient Descent by Concatenation of Stepsize Schedulescited by 5
  26. 2024Refined Risk Bounds for Unbounded Losses via Transductive Priorscited by 5
  27. 2024The Oracle Complexity of Simplex-based Matrix Gamescited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 5.

7 papers.

  1. 2025Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regressioncited by 9
  2. 2025Gradient Descent with Provably Tuned Learning-rate Schedulescited by 1
  3. 2026Product-Stability: Provable Convergence for Gradient Descent on the Edge of Stabilitycited by 1
  4. 2026Convergence of Steepest Descent and Adam under Non-Uniform Smoothnesscited by 1
  5. 2026Towards Understanding Momentum Acceleration in River-Valley Loss Landscapecited by 1
  6. 2026Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regressioncited by 0
  7. 2026Efficient Logistic Regression with Mixture of Sigmoidscited by 0