The Computational Complexity of Finding Stationary Points in Non-Convex Optimization

Overview

• The paper investigates the computational and query complexity of finding approximate stationary points of non-convex but smooth objective functions over unrestricted domains.
• It presents several key results, including the PLS-completeness of this problem, and efficient algorithms with tight query complexity bounds for the 2D case.
• The paper also establishes a connection between finding approximate stationary points in unconstrained optimization and approximate KKT points in constrained optimization.

Plain English Explanation

In the world of optimization, finding points where the gradient (the direction of steepest change) of a function is approximately zero is a fundamental challenge, especially when the function is non-convex (not bowl-shaped) but still smooth. This problem arises in many real-world applications, such as machine learning and non-linear programming.

The paper tackles this problem from a theoretical perspective, aiming to understand the inherent computational and query complexity (the number of times the function needs to be evaluated) of finding these approximate stationary points. The key findings are:

1. The problem of finding approximate stationary points is PLS-complete, meaning it is computationally difficult and likely takes a long time to solve in the worst case.
2. For 2D problems (where the domain has only two dimensions), the paper provides an efficient algorithm that can find approximate stationary points using only a small number of function evaluations.
3. It also shows that any algorithm needs at least a certain number of function evaluations to find approximate stationary points in 2D, which matches the upper bound of the efficient algorithm, thereby characterizing the optimal query complexity for this problem.
4. For constrained optimization problems in 2D, the paper provides an algorithm to find approximate KKT points, which are a generalization of stationary points, and shows that the query complexity is optimal.
5. Finally, the paper establishes a connection between finding approximate stationary points in unconstrained optimization and approximate KKT points in constrained optimization, showing that the former is a more general problem.

Technical Explanation

The paper first shows that the problem of finding approximate stationary points of non-convex but smooth objective functions over unrestricted domains is PLS-complete. This means that the problem is computationally difficult and likely takes a long time to solve in the worst case.

Next, the paper focuses on the 2D case (where the domain has only two dimensions) and provides a zero-order algorithm (an algorithm that only requires the function values, not the gradients) that can find ε-approximate stationary points using at most O(1/ε) function evaluations. This means that as the approximation error ε gets smaller, the algorithm needs a larger number of function evaluations to find the approximate stationary point.

The paper then proves a matching lower bound, showing that any algorithm needs at least Ω(1/ε) function evaluations and/or gradient evaluations to find ε-approximate stationary points in 2D. This means that the algorithm provided is optimal in terms of the number of function evaluations required.

For constrained optimization problems in 2D, the paper provides a zero-order algorithm to find ε-KKT points, which are a generalization of stationary points that take the constraints into account. This algorithm requires at most O(1/√ε) function evaluations, matching the lower bound shown by previous work.

Finally, the paper combines its results with a recent finding to show that the problem of finding approximate KKT points in constrained optimization is reducible to the problem of finding approximate stationary points in unconstrained optimization, but not the other way around. This establishes a connection between these two fundamental problems in optimization.

Critical Analysis

The paper provides a comprehensive understanding of the computational and query complexity of finding approximate stationary points of non-convex but smooth objective functions over unrestricted domains. The PLS-completeness result highlights the inherent difficulty of this problem, while the tight complexity bounds for the 2D case offer valuable insights.

One potential limitation of the paper is that the results are primarily focused on the 2D case, and it remains to be seen how the algorithms and complexity bounds scale to higher dimensions. Additionally, the paper does not address the practical performance of the proposed algorithms, which could be an area for future research.

Furthermore, the connection between finding approximate stationary points in unconstrained optimization and approximate KKT points in constrained optimization is an interesting theoretical insight, but its practical implications for solving real-world optimization problems could be explored further.

Conclusion

This paper makes significant contributions to the field of non-convex optimization by providing a thorough analysis of the computational and query complexity of finding approximate stationary points. The key results include the PLS-completeness of the problem, tight complexity bounds for the 2D case, and the relationship between unconstrained and constrained optimization problems.

These findings advance our understanding of the inherent challenges and limitations in this fundamental area of optimization, which has important applications in machine learning, engineering, and many other fields. The insights provided by this paper can inform the design of more efficient algorithms and guide future research in this direction.