mlsanityData to 14 Oct 2026

The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization

arXiv 2609.23837 ↗First posted 20 Sep 2026math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

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/ε)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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 24 of its 42 references that are in the map. First posted on arXiv 20 Sep 2026.

Builds on

24 of 42 references.

References · 24

  1. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  2. 2017Lower Bounds for Finding Stationary Points Icited by 126
  3. 2018Stochastic subgradient method converges on tame functionscited by 124
  4. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 111
  5. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 45
  6. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 43
  7. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 39
  8. 2021A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensionscited by 39
  9. 2021On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functionscited by 31
  10. 2018Gradient Sampling Methods for Nonsmooth Optimizationcited by 23
  11. 2023An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimizationcited by 23
  12. 2024Adam with model exponential moving average is effective for nonconvex optimizationcited by 23
12 more
  1. 2024Random Scaling and Momentum for Non-smooth Non-convex Optimizationcited by 19
  2. 2023Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimizationcited by 17
  3. 2022No Dimension-Free Deterministic Algorithm Computes Approximate Stationarities of Lipschitzianscited by 16
  4. 2024General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimizationcited by 15
  5. 2026Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimizationcited by 14
  6. 2019Pathological subgradient dynamicscited by 9
  7. 2023Goldstein Stationarity in Lipschitz Constrained Optimizationcited by 6
  8. 2023Decentralized Gradient-Free Methods for Stochastic Non-Smooth Non-Convex Optimizationcited by 5
  9. 2026Muon with Finite Newton-Schulz: The Smoothing Benefit in Nonsmooth Nonconvex Optimizationcited by 5
  10. 2024Improved Sample Complexity for Private Nonsmooth Nonconvex Optimizationcited by 4
  11. 2026Nonsmooth Nonconvex-Concave Minimax Optimization: Convergence Criteria and Algorithmscited by 1
  12. 2026On computing Goldstein approximate second-order stationary points of structured nonsmooth nonconvex programscited by 1

Built on by

Not cited yet.