The Cost of Nonconvexity in Deterministic Nonsmooth Optimization

We study the impact of nonconvexity on the complexity of nonsmooth optimization, emphasizing objectives such as piecewise linear functions, which may not be weakly convex. We focus on a dimension-independent analysis, slightly modifying a 2020 black-box algorithm of Zhang-Lin-Jegelka-Sra-Jadbabaie that approximates an ϵ-stationary point of any directionally differentiable Lipschitz objective using $O({ϵ}^{-4})$ calls to a specialized subgradient oracle and a randomized line search. Seeking by contrast a deterministic method, we present a simple black-box version that achieves $O({ϵ}^{-5})$ for any difference-of-convex objective and $O({ϵ}^{-4})$ for the weakly convex case. Our complexity bound depends on a natural nonconvexity modulus that is related, intriguingly, to the negative part of directional second derivatives of the objective, understood in the distributional sense.

Funding: This work was supported by the National Science Foundation [Grant DMS-2006990].