# On the Complexity of Deterministic Nonsmooth and Nonconvex Optimization

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

## Key facts

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

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

- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2301.06428/) (2023)
- [A Block-Coordinate Approach of Multi-level Optimization with an Application to Physics-Informed Neural Networks](https://mlsanity.com/paper/2305.14477/) (2023)
- [Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2406.01484/) (2024)
- [Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer](https://mlsanity.com/paper/2602.08372/) (2026)
- [Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithms](https://mlsanity.com/paper/2302.12261/) (2023)

## Abstract (arXiv)

In this paper, we present several new results on minimizing a nonsmooth and nonconvex function under a Lipschitz condition. Recent work shows that while the classical notion of Clarke stationarity is computationally intractable up to some sufficiently small constant tolerance, the randomized first-order algorithms find a (δ, ε)-Goldstein stationary point with the complexity bound of tildeO(δ-1ε-3), which is independent of dimension d ≥ 1~citepZhang-2020-Complexity, Davis-2022-Gradient, Tian-2022-Finite. However, the deterministic algorithms have not been fully explored, leaving open several problems in nonsmooth nonconvex optimization. Our first contribution is to demonstrate that the randomization is textitnecessary to obtain a dimension-independent guarantee, by proving a lower bound of Omega(d) for any deterministic algorithm that has access to both 1st and 0th oracles. Furthermore, we show that the 0th oracle is textitessential to obtain a finite-time convergence guarantee, by showing that any deterministic algorithm with only the 1st oracle is not able to find an approximate Goldstein stationary point within a finite number of iterations up to sufficiently small constant parameter and tolerance. Finally, we propose a deterministic smoothing approach under the textitarithmetic circuit model where the resulting smoothness parameter is exponential in a certain parameter M > 0 (e.g., the number of nodes in the representation of the function), and design a new deterministic first-order algorithm that achieves a dimension-independent complexity bound of tildeO(Mδ-1ε-3).