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\geq 0$, where $p\in(1,2]$.Specifically, we establish an SFO lower bound of $\Omega\big(\big(\sigma^{\frac{p}{p-1}}\epsilon^{-\frac{p}{p-1}}+1\big) (L_0 \Delta\epsilon^{-2}+L_1\Delta\epsilon^{-1})\big)$, 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.