On the Complexity of Finding Stationary Points in Stochastic $(L_0,L_1)$-Smooth Nonconvex Optimization

Abstract

We study the stochastic first-order oracle (SFO) complexity of finding $\epsilon$-stationary points of $(L_0,L_1)$-smooth nonconvex functions. Under bounded-variance noise, existing analyses of normalized and clipped stochastic gradient descent (SGD) establish optimal dependence on $\epsilon$ and $L_0$, but the jointly optimal dependence on $L_0$, $L_1$, and $\epsilon$ remains unclear. We resolve this question for an unbiased SFO whose gradient noise has a $p$th central moment bounded by ${\sigma }^p$ for some $\sigma \ge 0$, where $p\in (1,2]$.Specifically, we establish an SFO lower bound of $\Omega \left(\right({\sigma }^{\frac{p}{p-1}}{\epsilon }^{-\frac{p}{p-1}}+1)(L_0\Delta {\epsilon }^{-2}+L_1\Delta {\epsilon }^{-1}))$, where $\Delta >0$ is the initial optimality gap.This bound identifies an unavoidable contribution proportional to $L_1{\epsilon }^{-1}\Delta$. We also prove that mini-batch (smoothed) normalized SGD can attain a matching upper bound, thereby establishing the optimal SFO complexity.