The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
Abstract
We prove that first-order algorithms require Ω(δ−1ε−3) gradient queries (in the worst case) to find a (δ,ε)-Goldstein stationary point of a Lipschitz function, at which there is a convex combination of gradients within distance δ whose norm is at most ε. This lower bound is tight, matching known algorithms up to absolute constants, therefore resolving the complexity of convergence to stationarity in nonsmooth nonconvex optimization. We further prove a tight lower bound of Ω(λ1/2ε−7/2) for finding points satisfying the recently proposed relaxed notion of (λ,ε)-stationarity, which allows combining further-away gradients. Our results reveal that convergence rates to nonsmooth stationarity are not affected by gradient stochasticity, in sharp contrast to smooth optimization.
Related
- On the Complexity of Finding Stationary Points in Stochastic (L0, L1)-Smooth Nonconvex Optimization
- Deterministic Oracle Complexity for Goldstein Stationarity in Nonsmooth Nonconvex Optimization with Constraints
- Proximal Limited-Memory Quasi-Newton Methods for Nonsmooth Nonconvex Optimization
- Variable Bregman Majorization-Minimization algorithms for nonconvex nonsmooth optimization, with application to Poisson imaging
- Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums
BibTeX
@misc{kornowski2026complexity,
title = {{The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization}},
author = {Guy Kornowski},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17780},
eprint = {2609.17780},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17780},
}
RIS
TY - UNPB
TI - The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
AU - Guy Kornowski
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17780
UR - https://arxiv.org/abs/2609.17780
AB - We prove that first-order algorithms require Ω(δ^−1ε^−3) gradient queries (in the worst case) to find a (δ,ε)-Goldstein stationary point of a Lipschitz function, at which there is a convex combination of gradients within distance δ whose norm is at most ε. This lower bound is tight, matching known algorithms up to absolute constants, therefore resolving the complexity of convergence to stationarity in nonsmooth nonconvex optimization. We further prove a tight lower bound of Ω(λ^1/2ε^−7/2) for finding points satisfying the recently proposed relaxed notion of (λ,ε)-stationarity, which allows combining further-away gradients. Our results reveal that convergence rates to nonsmooth stationarity are not affected by gradient stochasticity, in sharp contrast to smooth optimization.
ER -