The Cost of Nonconvexity in Deterministic Nonsmooth Optimization
成果类型：
Article
署名作者：
Kong, Siyu; Lewis, A. S.
署名单位：
Cornell University
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2022.0289
发表日期：
2024
页码：
2385-2401
关键词：
摘要：
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 e-stationary point of any directionally differentiable Lipschitz objective using O(e-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(e-5) for any difference-ofconvex objective and O(e-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.