Skip to content
Preprint

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

Oct 2026 · 1 citation · 48 references
Mathematics

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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.