On the Complexity of Deterministic Nonsmooth and Nonconvex Optimization

In this paper, we present several new results on minimizing a nonsmooth and nonconvex function under a Lipschitz condition. Recent work shows that while the classical notion of Clarke stationarity is computationally intractable up to some sufficiently small constant tolerance, the randomized first-order algorithms find a (δ, ε)-Goldstein stationary point with the complexity bound of tildeO(δ-1ε-3), which is independent of dimension d ≥ 1~citepZhang-2020-Complexity, Davis-2022-Gradient, Tian-2022-Finite. However, the deterministic algorithms have not been fully explored, leaving open several problems in nonsmooth nonconvex optimization. Our first contribution is to demonstrate that the randomization is textitnecessary to obtain a dimension-independent guarantee, by proving a lower bound of Omega(d) for any deterministic algorithm that has access to both 1st and 0th oracles. Furthermore, we show that the 0th oracle is textitessential to obtain a finite-time convergence guarantee, by showing that any deterministic algorithm with only the 1st oracle is not able to find an approximate Goldstein stationary point within a finite number of iterations up to sufficiently small constant parameter and tolerance. Finally, we propose a deterministic smoothing approach under the textitarithmetic circuit model where the resulting smoothness parameter is exponential in a certain parameter M > 0 (e.g., the number of nodes in the representation of the function), and design a new deterministic first-order algorithm that achieves a dimension-independent complexity bound of tildeO(Mδ-1ε-3).