{"id":"arxiv/2609.17780","url":"https://arxiv.org/abs/2609.17780","tags":["math.OC"],"score":0,"title":"The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization","domain":"math.OC","source":"arxiv","authors":["Guy Kornowski"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-15","reactions":{}}