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

arXiv:2610.26748v1 Announce Type: cross Abstract: We show that gradient descent (GD) with step size $\eta$ 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 $\eta$ 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 $\eta$) that turns out to be necessary in dimension $d \geq 3$. The proofs build on the known fact that, as $\eta \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.

Abstract:We show that gradient descent (GD) with step size $\eta$ 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 $\eta$ 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 $\eta$) that turns out to be necessary in dimension $d \geq 3$. The proofs build on the known fact that, as $\eta \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.

Optimization and Control (math.OC); Machine Learning (cs.LG)

arXiv:2610.26748 [math.OC]

(or arXiv:2610.26748v1 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2610.26748 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

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

Subiecte conexe