Optimal Deterministic Oracle Complexity for Weakly Convex Optimization

Abstract

We study the oracle complexity of finding $\epsilon$-stationary points of $\rho$-weakly convex and $G$-Lipschitz functions, where stationarity is measured by the gradient of the Moreau envelope. We consider a first-order oracle that returns both the function value and the full subdifferential at every query point. We prove that every deterministic first-order algorithm requires $\Omega (\rho G^2\Delta /{\epsilon }^4)$ oracle queries whenever $\Delta \le G^2/\rho$, where $f(\bz)-\inf f \leq Δ$. This lower bound matches the best known deterministic and stochastic first-order upper bounds, up to universal constants, and establishes the optimal deterministic oracle complexity. The result reveals a fundamental complexity separation between smooth nonconvex and nonsmooth weakly convex optimization. While smooth nonconvex minimization admits a $\Theta ({\epsilon }^{-2})$ oracle complexity, nonsmooth weakly convex optimization incurs an intrinsic additional ${\epsilon }^{-2}$ factor arising from nonsmooth geometry rather than stochasticity.