Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression

We study gradient descent (GD) with a constant stepsize for ℓ 2 -regularized logistic regression with linearly separable data. Classical theory suggests small stepsizes to ensure monotonic reduction of the optimization objective, achieving exponential convergence in O(κ) steps with κ being the condition number. Surprisingly, we show that this can be accelerated to O( √ κ) by simply using a large stepsize-for which the objective evolves nonmonotonically. The acceleration brought by large stepsizes extends to minimizing the population risk for separable distributions, improving on the best-known upper bounds on the number of steps to reach a nearoptimum. Finally, we characterize the largest stepsize for the local convergence of GD, which also determines the global convergence in special scenarios. Our results extend the analysis of Wu et al. ( 2024) from convex settings with minimizers at infinity to strongly convex cases with finite minimizers. * Equal contribution. † Work done while P.M. was a postdoc at EPFL, visiting the Simons Institute at UC Berkeley. 39th Conference on Neural Information Processing Systems (NeurIPS 2025).