mlsanityData to 7 Oct 2026

Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regression

arXiv 2602.18946 ↗First posted 21 Feb 2026cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

Gradient descent and stochastic gradient descent are central to modern machine learning, yet their behavior under large step sizes remains theoretically unclear. Recent work suggests that acceleration often arises near the edge of stability, where optimization trajectories become unstable and difficult to analyze. Existing results for separable logistic regression achieve faster convergence by explicitly leveraging such unstable regimes through constant or adaptive large step sizes. In this paper, we show that instability is not inherent to acceleration. We prove that gradient descent with a simple, non-adaptive increasing step-size schedule achieves exponential convergence for separable logistic regression under a margin condition, while remaining entirely within a stable optimization regime. The resulting method is anytime and does not require prior knowledge of the optimization horizon or target accuracy. We also establish exponential convergence of stochastic gradient descent using a lightweight adaptive step-size rule that avoids line search and specialized procedures, improving upon existing polynomial-rate guarantees. Together, our results demonstrate that carefully structured step-size growth alone suffices to obtain exponential acceleration for both gradient descent and stochastic gradient descent.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 18 of its 24 references that are in the map. First posted on arXiv 21 Feb 2026.

Builds on

18 of 24 references.

References · 18

  1. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  2. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 413
  3. 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 158
  4. 2022Understanding Gradient Descent on Edge of Stability in Deep Learningcited by 126
  5. 2018Convergence of Gradient Descent on Separable Datacited by 108
  6. 2022Understanding the unstable convergence of gradient descentcited by 84
  7. 2018Risk and parameter convergence of logistic regressioncited by 81
  8. 2019Adaptive Gradient Descent without Descentcited by 79
  9. 2018Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Ratecited by 63
  10. 2023Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stabilitycited by 42
  11. 2024Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiencycited by 34
  12. 2023Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimizationcited by 20
6 more
  1. 2024Increasing Both Batch Size and Learning Rate Accelerates Stochastic Gradient Descentcited by 11
  2. 2023Gradient Descent Converges Linearly for Logistic Regression on Separable Datacited by 7
  3. 2025Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regressioncited by 7
  4. 2025Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizescited by 5
  5. 2025New Results on the Polyak Stepsize: Tight Convergence Analysis and Universal Function Classescited by 4
  6. 2025Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Fastercited by 3

Built on by

Not cited yet.