Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression
Abstract
We show that gradient descent (GD) with step size η can achieve ε optimality gap on the multiclass logistic regression loss in a number of iterations T that is independent of ε. To do so, the step size η must be chosen large enough as a function of ε (and properties of the linearly separable dataset), while T is a constant that only depends on the data. The relevant properties of the data include the number of points and their margin (for T), and one additional quantity (for η) that turns out to be necessary in dimension d ≥ 3. The proofs build on the known fact that, as η→ ∞, suitably rescaled GD becomes the perceptron algorithm, and the latter finds a perfect classifier in T iterations. A similar claim was shown for two classes in dimension d = 2 using other proof techniques. This result adds to previous works that showed GD on the logistic regression loss can be accelerated by taking large step sizes. Those provoke a wild, oscillatory initial phase, followed by a stable phase. We provide results of this (qualitatively different) nature, too.
Related
- SGD in Multiclass Logistic Regression: Sequential Learning and Scaling Laws
- Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design
- Optimal Multiclass Online Regret with Arbitrary Label Spaces
- Data generation for the logistic regression model under controlled conditions
- A penalized logistic generalized regression estimator
BibTeX
@misc{musat2026gradient,
title = {{Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression}},
author = {Andreea-Alexandra Musat and Nicolas Boumal},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26748},
eprint = {2610.26748},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26748},
}
RIS
TY - UNPB
TI - Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression
AU - Andreea-Alexandra Musat
AU - Nicolas Boumal
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26748
UR - https://arxiv.org/abs/2610.26748
AB - We show that gradient descent (GD) with step size η can achieve ε optimality gap on the multiclass logistic regression loss in a number of iterations T that is independent of ε. To do so, the step size η must be chosen large enough as a function of ε (and properties of the linearly separable dataset), while T is a constant that only depends on the data. The relevant properties of the data include the number of points and their margin (for T), and one additional quantity (for η) that turns out to be necessary in dimension d ≥ 3. The proofs build on the known fact that, as η→ ∞, suitably rescaled GD becomes the perceptron algorithm, and the latter finds a perfect classifier in T iterations. A similar claim was shown for two classes in dimension d = 2 using other proof techniques. This result adds to previous works that showed GD on the logistic regression loss can be accelerated by taking large step sizes. Those provoke a wild, oscillatory initial phase, followed by a stable phase. We provide results of this (qualitatively different) nature, too.
ER -