The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization
Abstract
We study the complexity of finding (δ,ε)-Goldstein stationary points of nonsmooth nonconvex Lipschitz functions. By now, it is known that randomized first-order algorithms can solve this task with a dimension-free oracle complexity [Zhang et al., 2020], whereas deterministic algorithms cannot, as their complexity must scale at least linearly with the dimension d [Jordan et al., 2023, Tian and So, 2024]. This leaves open whether deterministic algorithms can nevertheless solve the problem with oracle complexity polynomial in d. We answer this question negatively by proving a lower bound of order (1/ε)Ω(d) for deterministic algorithm, closing the exponential gap between the previously known lower and upper bounds and resolving an open problem posed by Jordan et al. [2023]. We further discuss several extensions and implications of this result to weaker stationarity notions, finding a descent direction and deterministic smoothing. Overall, our results establish an exponential computational advantage in nonsmooth nonconvex optimization offered by randomization.
Related
- The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
- Proximal Limited-Memory Quasi-Newton Methods for Nonsmooth Nonconvex Optimization
- Variable Bregman Majorization-Minimization algorithms for nonconvex nonsmooth optimization, with application to Poisson imaging
- A sequential regularized piecewise affine algorithm for nonconvex nonsmooth multicomposite optimization in RNN training
- Projected Subgradient Methods for a Class of Nonsmooth and Nonconvex Optimization Problems
BibTeX
@misc{kornowski2026exponential,
title = {{The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization}},
author = {Guy Kornowski},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23837},
eprint = {2609.23837},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23837},
}
RIS
TY - UNPB
TI - The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization
AU - Guy Kornowski
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23837
UR - https://arxiv.org/abs/2609.23837
AB - We study the complexity of finding (δ,ε)-Goldstein stationary points of nonsmooth nonconvex Lipschitz functions. By now, it is known that randomized first-order algorithms can solve this task with a dimension-free oracle complexity [Zhang et al., 2020], whereas deterministic algorithms cannot, as their complexity must scale at least linearly with the dimension d [Jordan et al., 2023, Tian and So, 2024]. This leaves open whether deterministic algorithms can nevertheless solve the problem with oracle complexity polynomial in d. We answer this question negatively by proving a lower bound of order (1/ε)^Ω(d) for deterministic algorithm, closing the exponential gap between the previously known lower and upper bounds and resolving an open problem posed by Jordan et al. [2023]. We further discuss several extensions and implications of this result to weaker stationarity notions, finding a descent direction and deterministic smoothing. Overall, our results establish an exponential computational advantage in nonsmooth nonconvex optimization offered by randomization.
ER -