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

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 $\mathrm{\Omega }\left(\right({\sigma }^{\frac{p}{p-1}}{\epsilon }^{-\frac{p}{p-1}}+1)(L_0\mathrm{\Delta }{\epsilon }^{-2}+L_1\mathrm{\Delta }{\epsilon }^{-1}))$, where $\mathrm{\Delta }>0$ is the initial optimality gap.This bound identifies an unavoidable contribution proportional to $L_1{\epsilon }^{-1}\mathrm{\Delta }$. We also prove that mini-batch (smoothed) normalized SGD can attain a matching upper bound, thereby establishing the optimal SFO complexity.