# Improved Convergence of Large Stepsize Gradient Descent for Logistic Regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 50 references that are in the map.
- First posted on arXiv 5 Oct 2026.

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

- [The large learning rate phase of deep learning: the catapult mechanism](https://mlsanity.com/paper/2003.02218/) (2020)
- [Adaptive Gradient Methods at the Edge of Stability](https://mlsanity.com/paper/2207.14484/) (2022)
- [A Walk with SGD](https://mlsanity.com/paper/1802.08770/) (2018)
- [Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes](https://mlsanity.com/paper/2406.05033/) (2024)
- [Gradient Descent on Logistic Regression: Do Large Step-Sizes Work with Data on the Sphere?](https://mlsanity.com/paper/2507.11228/) (2025)
- [Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension](https://mlsanity.com/paper/2602.12471/) (2026)

## Abstract (arXiv)

We study gradient descent (GD) with a large constant stepsize for logistic regression on linearly separable data. Existing analysis shows an accelerated rate of widetildeO(1/√ε) to reach loss ε with an aggressive stepsize, although the loss may initially oscillate. Tighter control of the oscillatory dynamics has been available only for two-dimensional data. We prove a substantially faster rate in arbitrary dimension: GD with a large stepsize η=1/ε reaches loss ε within O(lnp(1/ε)) steps, where p depends only on the margin and the rank of the data. Our proof improves the bound on the transition time of GD from the oscillatory to the stable phase, after which the loss decreases monotonically. We split the oscillatory phase into recursively nested intervals. The margin and the rank bound the nesting depth, and a counting argument bounds the number of intervals at each depth, together yielding the polylogarithmic step complexity.