Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes

We study $\mathit{\text{gradient}}\mathit{\text{descent}}$ (GD) for logistic regression on linearly separable data with stepsizes that adapt to the current risk, scaled by a constant hyperparameter $\eta$. We show that after at most $1\mathrm{/}{\gamma }^2$ burn-in steps, GD achieves a risk upper bounded by $\exp (-\mathrm{\Theta }(\eta ))$, where $\gamma$ is the margin of the dataset. As $\eta$ can be arbitrarily large, GD attains an arbitrarily small risk $\mathit{\text{immediately}}\mathit{\text{after}}\mathit{\text{the}}\mathit{\text{burn-in}}\mathit{\text{steps}}$, though the risk evolution may be $\mathit{\text{non-monotonic}}$. We further construct hard datasets with margin $\gamma$, where any batch (or online) first-order method requires $\mathrm{\Omega }(1\mathrm{/}{\gamma }^2)$ steps to find a linear separator. Thus, GD with large, adaptive stepsizes is $\mathit{\text{minimax}}\mathit{\text{optimal}}$ among first-order batch methods. Notably, the classical $\mathit{\text{Perceptron}}$ (Novikoff, 1962), a first-order online method, also achieves a step complexity of $1\mathrm{/}{\gamma }^2$, matching GD even in constants. Finally, our GD analysis extends to a broad class of loss functions and certain two-layer networks.