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 $ε$-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 $ε$ and $L_0$, but the jointly optimal dependence on $L_0$, $L_1$, and $ε$ remains unclear. We resolve this question for an unbiased SFO whose gradient noise has a $p$th central moment bounded by $σ^p$ for some $σ\geq 0$, where $p\in(1,2]$.Specifically, we establish an SFO lower bound of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.21692
curl -X POST /api/v1/records/arxiv/2610.21692/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.21692/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'