Gradient descent achieves fixed accuracy in constant steps on multiclass data
Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression
Machine Learning
Summary
The paper shows that gradient descent, a common method used to train classifiers, can reach any desired accuracy on a multiclass classification problem in a set number of steps that doesn’t grow as you demand better accuracy. This requires using a large enough step size that depends on some properties of the data. The authors connect this behavior to the perceptron algorithm, known for its fixed-step convergence on linearly separable data, and extend previous two-class and low-dimensional results. This helps explain how choosing large steps speeds up training under certain conditions.
What this means in practice
- •For machine learning engineers: Design training schedules with large step sizes to guarantee error targets on multiclass logistic models within a fixed iteration count.
- •For data pipeline architects: Optimize resource allocation by knowing multiclass logistic regression training can terminate after a predetermined number of updates regardless of accuracy.
A theory result. No direct application yet.
Authors
Andreea-Alexandra Musat, Nicolas Boumal
Abstract
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.