{"id":"arxiv/2609.23837","url":"https://arxiv.org/abs/2609.23837","tags":["math.OC","cs.LG"],"score":0,"title":"The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization","domain":"math.OC","source":"arxiv","authors":["Guy Kornowski"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-20","reactions":{}}