no. 15 · Monday 16 November 2026
Optimal Oracle Complexity for Weakly Convex Optimization
Abstract
We study the oracle complexity of finding $ε$-stationary points of $ρ$-weakly convex and $G$-Lipschitz functions, where stationarity is measured by the gradient norm of the Moreau envelope. We consider an exact first-order oracle that returns both the function value and the full subdifferential at every query point. For sufficiently small $ε>0$, we prove that every first-order algorithm, including randomized algorithms, requires $Ω({ρG^2Δ}/{ε^4})$ oracle queries to succeed with any fixed positive probability, where $f(0)-\inf f\leΔ$. This lower bound matches the best known deterministic and stochastic first-order upper bounds, up to universal constants, and establishes the optimal randomized and deterministic first-order oracle complexity. The result separates smooth nonconvex and nonsmooth weakly convex optimization: the additional $ε^{-2}$ factor is intrinsic to nonsmooth geometry rather than to stochastic oracle noise.
- comments
- 28 pages, 1 figure. This version extends the lower bound to randomized first-order algorithms and a substantially broader initial-gap regime, with revised proofs and exposition
- fields
- Optimization and Control