Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression
$\ell_2$-regularizationaccelerated optimizationcondition numberconstant stepsizeexponential convergenceglobal convergencegradient descentlinearly separable datalocal convergencelogistic regressionnonmonotonic evolutionpopulation risk minimizationseparable distributionsstrongly convex casesupper bounds
We study *gradient descent* (GD) with a constant stepsize for $\ell_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 $\widetilde{\mathcal{O}}(\kappa)$ steps with $\kappa$ being the condition number. Surprisingly, we show that this can be *accelerated* to $\widetilde{\mathcal{O}}(\sqrt{\kappa})$ by simply using a large stepsize