# The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization

arXiv: https://arxiv.org/abs/2609.17780 · HTML: https://mlsanity.com/paper/2609.17780/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Sep 2026.

## Built on by (most cited first, 1 of 1)

- [Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints](https://mlsanity.com/paper/2610.13787/) (2026)

## Abstract (arXiv)

We prove that first-order algorithms require Omega(δ-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 Omega(λ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.