2023/10/13 by Alexandros Hollender, Hollender, Alexandros, Manolis Zampetakis +1 · 3 citations
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2310.09157
openalex publication_date 2023/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Finding approximate stationary points, i.e., points where the gradient is approximately zero, of non-convex but smooth objective functions f over unrestricted d-dimensional domains is one of the most fundamental problems in classical non-convex optimization. Nevertheless, the computational and query complexity of this problem are still not well understood when the dimension d of the problem is independent of the approximation error. In this paper, we show the following computational and query complexity results: 1. The problem of finding approximate stationary points over unrestricted domains is PLS-complete. 2. For d = 2, we provide a zero-order algorithm for finding ε-approximate stationary points that requires at most O(1/ε) value queries to the objective function. 3. We show that any algorithm needs at least Ω(1/ε) queries to the objective function and/or its gradient to find ε-approximate stationary points when d=2. Combined with the above, this characterizes the query complexity of this problem to be Θ(1/ε). 4. For d = 2, we provide a zero-order algorithm for finding ε-KKT points in constrained optimization problems that requires at most O(1/√(ε)) value queries to the objective function. This closes the gap between the works of Bubeck and Mikulincer [2020] and Vavasis [1993] and characterizes the query complexity of this problem to be Θ(1/√(ε)). 5. Combining our results with the recent result of Fearnley et al. [2022], we show that finding approximate KKT points in constrained optimization is reducible to finding approximate stationary points in unconstrained optimization but the converse is impossible.