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

Abstract

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

28 pages