2022/09/26 by Jordan, Michael I., Lin, Tianyi, Zampetakis, Manolis
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2209.12463
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 O(δ-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 necessary to obtain a dimension-independent guarantee, by proving a lower bound of Ω(d) for any deterministic algorithm that has access to both 1st and 0th oracles. Furthermore, we show that the 0th oracle is essential 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 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 O(Mδ-1ε-3).