Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension
Not on the map. Why?
Abstract (arXiv)
We consider the optimization problem of minimizing the logistic loss with gradient descent to train a linear model for binary classification with separable data. With a budget of T iterations, it was recently shown that an accelerated 1/T2 rate is possible by choosing a large stepsize η = Theta(γ2 T) (where γ is the dataset's margin) despite the resulting non-monotonicity of the loss. In this paper, we provide a tighter analysis of gradient descent for this problem when the data is two-dimensional: we show that GD with a sufficiently large learning rate η finds a point with loss smaller than O(1/(η γ2 T)), as long as T ≥ Omega(n/γ + 1/γ2), where n is the dataset size. Our improved rate comes from a tighter bound on the time τ that it takes for GD to transition from unstable (non-monotonic loss) to stable (monotonic loss), via a fine-grained analysis of the oscillatory dynamics of GD in the subspace orthogonal to the max-margin classifier. We also provide a lower bound of τ matching our upper bound up to logarithmic factors, showing that our analysis is tight.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 28 of its 33 references that are in the map. First posted on arXiv 12 Feb 2026.
Builds on
28 of 33 references.
References · 28
- 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
- 2014Convex Optimization: Algorithms and Complexitycited by 569
- 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 413
- 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 259
- 2022Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stabilitycited by 151
- 2022Understanding Gradient Descent on Edge of Stability in Deep Learningcited by 126
- 2022Adaptive Gradient Methods at the Edge of Stabilitycited by 88
- 2019Adaptive Gradient Descent without Descentcited by 79
- 2018Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Ratecited by 63
- 2024Understanding Optimization in Deep Learning with Central Flowscited by 57
- 2022Understanding Edge-of-Stability Training Dynamics with a Minimalist Examplecited by 54
- 2022Learning threshold neurons via the "edge of stability"cited by 50
16 more
- 2023Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stabilitycited by 42
- 2022Beyond the Edge of Stability via Two-step Gradient Updatescited by 38
- 2023(S)GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stabilitycited by 35
- 2024Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiencycited by 34
- 2023Provably Faster Gradient Descent via Long Stepscited by 20
- 2023Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimizationcited by 20
- 2024Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimizationcited by 17
- 2024Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Stepscited by 11
- 2024Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizescited by 9
- 2024Anytime Acceleration of Gradient Descentcited by 7
- 2025Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regressioncited by 7
- 2024From Logistic Regression to the Perceptron Algorithm: Exploring Gradient Descent with Large Step Sizescited by 5
- 2024The Oracle Complexity of Simplex-based Matrix Gamescited by 4
- 2025Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regressioncited by 2
- 2025Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?cited by 2
- 2025Constant Stepsize Local GD for Logistic Regression: Acceleration by Instabilitycited by 1
Built on by
Not cited yet.