The Cost of Nonconvexity in Deterministic Nonsmooth Optimization

Siyu Kong () and A. S. Lewis ()
Additional contact information
Siyu Kong: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
A. S. Lewis: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853

Mathematics of Operations Research, 2024, vol. 49, issue 4, 2385-2401

Abstract: 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.

Keywords: Primary: 90C56; 49J52; 65Y20; nonsmooth optimization; nonconvex; Goldstein subgradient; complexity; distributional derivative (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.0289 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:4:p:2385-2401

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().