The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization

arXiv:2609.23837v1 Announce Type: cross Abstract: We study the complexity of finding (elta,epsilon)-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/epsilon)^{Omega(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.

Source: arXiv cs.LG | 2026-09-22