# Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 33 references that are in the map.
- First posted on arXiv 12 Feb 2026.

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

- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability](https://mlsanity.com/paper/2103.00065/) (2021)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability](https://mlsanity.com/paper/2209.15594/) (2022)
- [Understanding Gradient Descent on Edge of Stability in Deep Learning](https://mlsanity.com/paper/2205.09745/) (2022)
- [Adaptive Gradient Methods at the Edge of Stability](https://mlsanity.com/paper/2207.14484/) (2022)
- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (2019)
- [Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate](https://mlsanity.com/paper/1806.01796/) (2018)
- [Understanding Optimization in Deep Learning with Central Flows](https://mlsanity.com/paper/2410.24206/) (2024)
- [Understanding Edge-of-Stability Training Dynamics with a Minimalist Example](https://mlsanity.com/paper/2210.03294/) (2022)
- [Learning threshold neurons via the "edge of stability"](https://mlsanity.com/paper/2212.07469/) (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)
- [(S)GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stability](https://mlsanity.com/paper/2302.08982/) (2023)
- [Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency](https://mlsanity.com/paper/2402.15926/) (2024)
- [Provably Faster Gradient Descent via Long Steps](https://mlsanity.com/paper/2307.06324/) (2023)
- [Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimization](https://mlsanity.com/paper/2309.16530/) (2023)
- [Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization](https://mlsanity.com/paper/2406.08654/) (2024)
- [Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes](https://mlsanity.com/paper/2406.05033/) (2024)
- [Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Steps](https://mlsanity.com/paper/2403.14045/) (2024)
- [Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression](https://mlsanity.com/paper/2506.02336/) (2025)
- [Anytime Acceleration of Gradient Descent](https://mlsanity.com/paper/2411.17668/) (2024)
- [From Logistic Regression to the Perceptron Algorithm: Exploring Gradient Descent with Large Step Sizes](https://mlsanity.com/paper/2412.08424/) (2024)
- [Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?](https://mlsanity.com/paper/2507.11228/) (2025)
- [The Oracle Complexity of Simplex-based Matrix Games](https://mlsanity.com/paper/2412.06990/) (2024)
- [Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression](https://mlsanity.com/paper/2501.13790/) (2025)
- [Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability](https://mlsanity.com/paper/2506.13974/) (2025)

## Built on by (most cited first, 1 of 1)

- [Improved Convergence of Large Stepsize Gradient Descent for Logistic Regression](https://mlsanity.com/paper/2610.06675/) (2026)

## 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.