# The cost of nonconvexity in deterministic nonsmooth optimization

arXiv: https://arxiv.org/abs/2210.00652 · HTML: https://mlsanity.com/paper/2210.00652/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Oct 2022.

## Built on by (most cited first, 9 of 9)

- [First-Order Methods for Linearly Constrained Bilevel Optimization](https://mlsanity.com/paper/2406.12771/) (2024)
- [A Block-Coordinate Approach of Multi-level Optimization with an Application to Physics-Informed Neural Networks](https://mlsanity.com/paper/2305.14477/) (2023)
- [Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2410.05880/) (2024)
- [Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithms](https://mlsanity.com/paper/2302.12261/) (2023)
- [Revisiting Frank-Wolfe for Structured Nonconvex Optimization](https://mlsanity.com/paper/2503.08921/) (2025)
- [Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective](https://mlsanity.com/paper/2403.16317/) (2024)
- [Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms](https://mlsanity.com/paper/2507.17545/) (2025)
- [Sliced Inner Product Gromov-Wasserstein Distances](https://mlsanity.com/paper/2605.08546/) (2026)
- [On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2409.10323/) (2024)

## Abstract (arXiv)

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 black-box algorithm of Zhang et al. (2020) 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. Our simple black-box deterministic version, 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, related, intriguingly, to the negative part of directional second derivatives of the objective, understood in the distributional sense.