The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization

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.