Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension

We consider the optimization problem of minimizing the logistic loss with gradient descent to train a linear model for binary classification with separable data. With a budget of $T$ iterations, it was recently shown that an accelerated $1\mathrm{/}{T}^2$ rate is possible by choosing a large step size $\eta =\mathrm{\Theta }({\gamma }^{2}T)$ (where $\gamma$ is the dataset’s margin) despite the resulting non-monotonicity of the loss. In this paper, we provide a tighter analysis of gradient descent for this problem when the data is two-dimensional: we show that GD with a sufficiently large learning rate $\eta$ finds a point with loss smaller than $\mathcal{O}(1\mathrm{/}(\eta T))$, as long as $T\ge \mathrm{\Omega }(n\mathrm{/}\gamma +1\mathrm{/}{\gamma }^2)$, where $n$ is the dataset size. Our improved rate comes from a tighter bound on the time $\tau$ that it takes for GD to transition from unstable (non-monotonic loss) to stable (monotonic loss), via a fine-grained analysis of the oscillatory dynamics of GD in the subspace orthogonal to the max-margin classifier. We also provide a lower bound of $\tau$ matching our upper bound up to logarithmic factors, showing that our analysis is tight.