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

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