The Cost of Nonconvexity in Deterministic Nonsmooth Optimization
Mathematics of Operations Research · 2024-11 · 49 (4) · 2385-2401
DOI: 10.1287/moor.2022.0289 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics of Operations Research, 2024-11. Verfasst von Siyu Kong und 1 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 15 Literaturangaben.
Abstract (Originalsprache)
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 [Formula: see text] 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 [Formula: see text] for any difference-of-convex objective and [Formula: see text] 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].
Zitieren
APA
Kong, S., & Lewis, A. S. (2024). The Cost of Nonconvexity in Deterministic Nonsmooth Optimization. Mathematics of Operations Research, 49(4), 2385-2401. https://doi.org/10.1287/moor.2022.0289
Vancouver
Kong S, Lewis AS. The Cost of Nonconvexity in Deterministic Nonsmooth Optimization. Mathematics of Operations Research. 2024;49(4):2385-2401. doi:10.1287/moor.2022.0289
BibTeX
@article{Kong2024,
author = {Kong, Siyu and Lewis, A. S.},
title = {The Cost of Nonconvexity in Deterministic Nonsmooth Optimization},
journal = {Mathematics of Operations Research},
year = {2024},
volume = {49},
number = {4},
pages = {2385--2401},
doi = {10.1287/moor.2022.0289}
}
EUVIMED