📖
Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression
Andreea-Alexandra Musat, Nicolas Boumal

Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression

Science & Mathematics Published 2026 Verification Pending

Overview & Synopsis

We show that gradient descent (GD) with step size $η$ can achieve $\varepsilon$ optimality gap on the multiclass logistic regression loss in a number of iterations $T$ that is independent of $\varepsilon$. To do so, the step size $η$ must be chosen large enough as a function of $\varepsilon$ (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 \geq 3$. The proofs build on the known fact that, as $η\to \infty$, 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.

Indexed from repository: arXiv (arxiv.org)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression
Author / Organization Andreea-Alexandra Musat, Nicolas Boumal
Subject & Discipline math.OC
Categories Science & Mathematics
Publication Year 2026
License / Rights arXiv Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website arXiv (arxiv.org)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-272245
Original Source Link Visit Source Page on arxiv.org »