On the Complexity of Deterministic Nonsmooth and Nonconvex Optimization
share
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 Õ(δ^-1ϵ^-3), which is independent of dimension d ≥ 1 <cit.>. 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 necessary to obtain a dimension-independent guarantee, by proving a lower bound of Ω(d) for any deterministic algorithm that has access to both 1^st and 0^th oracles. Furthermore, we show that the 0^th oracle is essential to obtain a finite-time convergence guarantee, by showing that any deterministic algorithm with only the 1^st 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 arithmetic 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 Õ(Mδ^-1ϵ^-3).
READ FULL TEXT