{"ID":22918753,"CreatedAt":"2026-09-17T01:02:08.507062015Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.17780","arxiv_id":"2609.17780","title":"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.","short_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 algorithm...","url_abs":"https://arxiv.org/abs/2609.17780","url_pdf":"https://arxiv.org/pdf/2609.17780v1","authors":"[\"Guy Kornowski\"]","published":"2026-09-15T19:40:48Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}