SOURCE-LINKED INTELLIGENCE

The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization

arXiv · AI, language, vision and robotics · article · Sep 20, 2026 · UTC

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

Read original source ↗ Open in workspace

recordType

paper

region

Global