Reimaging Gradient Descent: Large Stepsize, Oscillation, and Acceleration

Gradient descent (GD) and its variants are pivotal in machine learning. Conventional wisdom suggests smaller stepsizes for stability, yet in practice, larger stepsizes often yield faster convergence, despite initial instability. In this talk, I will explain how large stepsizes provably accelerate GD for logistic regression on separable data in three settings.

• We start with logistic regression, a convex but non-strongly convex problem. We show that GD with a large stepsize attains an $ϵ$-risk in $O(1/\sqrt{ϵ})$ steps. This matches the accelerated step complexity of Nesterov momentum and improves the classical $O(1/ϵ)$ step complexity for GD with a small stepsize.
• We then consider ${\ell }_2$-regularized logistic regression with regularization strength $\lambda$, a strongly convex problem with condition number $\mathrm{\Theta }(1/\lambda )$. We show GD with a large stepsize attains an $ϵ$-excess risk in $O(1/\sqrt{\lambda }\ln (1/ϵ))$ steps. This, again, matches Nesterov momentum and improves the $O(1/\lambda \ln (1/ϵ))$ step complexity for GD with a small stepsize.
• Finally, we consider the task of finding a linear separator of a linearly separable dataset with margin $\gamma$. We show that, with large and adaptive stepsizes, GD solves this task in $1/{\gamma }^2$ steps by minimizing the logistic risk. We further show this step complexity is minimax optimal for all first-order methods, and cannot be achieved by GD with small stepsizes.