Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 7 min ago
PreprintCC BY 4.0arXiv

On the Complexity of Finding Stationary Points in Stochastic (L0, L1)-Smooth Nonconvex Optimization

  • Yanpeng Liang
  • Luo Luo
Open at sourcePDFDOICite

Abstract

We study the stochastic first-order oracle (SFO) complexity of finding ε-stationary points of (L0,L1)-smooth nonconvex functions. Under bounded-variance noise, existing analyses of normalized and clipped stochastic gradient descent (SGD) establish optimal dependence on ε and L0, but the jointly optimal dependence on L0, L1, and ε remains unclear. We resolve this question for an unbiased SFO whose gradient noise has a pth central moment bounded by σp for some σ≥ 0, where p∈(1,2].Specifically, we establish an SFO lower bound of Ω((σp/(p−1)ε−p/(p−1)+1) (L0 Δε−2+L1Δε−1)), where Δ>0 is the initial optimality gap.This bound identifies an unavoidable contribution proportional to L1ε−1Δ. We also prove that mini-batch (smoothed) normalized SGD can attain a matching upper bound, thereby establishing the optimal SFO complexity.

Related

  1. The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
    Guy Kornowski
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  2. Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums
    Qihao Zhou
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  3. On the Complexity of Finding Stationary Points of p-th Order Hölder Smooth Functions in One Dimension
    Huanjian Zhou, Taiji Suzuki
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  4. Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
    Qihao Zhou
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  5. Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption
    Daniel Cortild, Mathias Staudigl, Juan Peypouquet +1
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{liang2026complexity,
  title = {{On the Complexity of Finding Stationary Points in Stochastic $(L_0, L_1)$-Smooth Nonconvex Optimization}},
  author = {Yanpeng Liang and Luo Luo},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.21692},
  eprint = {2610.21692},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.21692},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On the Complexity of Finding Stationary Points in Stochastic (L_0, L_1)-Smooth Nonconvex Optimization
AU  - Yanpeng Liang
AU  - Luo Luo
PY  - 2026
DA  - 2026/10/15
PB  - arXiv
DO  - 10.48550/arxiv.2610.21692
UR  - https://arxiv.org/abs/2610.21692
AB  - 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 pth central moment bounded by σ^p for some σ≥ 0, where p∈(1,2].Specifically, we establish an SFO lower bound of Ω((σ^p/(p−1)ε^−p/(p−1)+1) (L_0 Δε^−2+L_1Δε^−1)), where Δ>0 is the initial optimality gap.This bound identifies an unavoidable contribution proportional to L_1ε^−1Δ. We also prove that mini-batch (smoothed) normalized SGD can attain a matching upper bound, thereby establishing the optimal SFO complexity.
ER  -