Abstract
We study gradient descent (GD) with a large constant stepsize for logistic regression on linearly separable data. Existing analysis shows an accelerated rate of $\widetilde{O}(1/\sqrtε)$ 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(\ln^{p}(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.
Keywords
Subject
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Gong, X., & Li, A. (2026). Improved Convergence of Large Stepsize Gradient Descent for Logistic Regression. https://omanscience.com/en/articles/improved-convergence-of-large-stepsize-gradient-descent-for-logistic-regression
MLA 9
Gong, Xiaochuan, and Ang Li. "Improved Convergence of Large Stepsize Gradient Descent for Logistic Regression." https://omanscience.com/en/articles/improved-convergence-of-large-stepsize-gradient-descent-for-logistic-regression.
Chicago (author–date)
Gong, Xiaochuan, and Ang Li. 2026. "Improved Convergence of Large Stepsize Gradient Descent for Logistic Regression." https://omanscience.com/en/articles/improved-convergence-of-large-stepsize-gradient-descent-for-logistic-regression.
Harvard
Gong, X. and Li, A. (2026) 'Improved Convergence of Large Stepsize Gradient Descent for Logistic Regression', Available at: https://omanscience.com/en/articles/improved-convergence-of-large-stepsize-gradient-descent-for-logistic-regression.
Vancouver
Gong X, Li A. Improved Convergence of Large Stepsize Gradient Descent for Logistic Regression. https://omanscience.com/en/articles/improved-convergence-of-large-stepsize-gradient-descent-for-logistic-regression
IEEE
X. Gong, and A. Li, "Improved Convergence of Large Stepsize Gradient Descent for Logistic Regression," https://omanscience.com/en/articles/improved-convergence-of-large-stepsize-gradient-descent-for-logistic-regression.