A. Kontogiannis, V. Pollatos, S. Kanellopoulos, P. Mertikopoulos, A. Pagourtzis, and I. Panageas. In ICML '24: Proceedings of the 41st International Conference on Machine Learning, 2024.
The problem of computing approximate stationary points of non-convex landscapes has received extensive scrutiny in optimization and machine learning. It was established quite recently that finding approximate stationary points for non-convex, smooth, bounded functions defined in unrestricted domains is complete for the class PLS. Nevertheless, a major obstacle in non-convex optimization is the avoidance of saddle points, i.e., stationary points of negative curvature which can outnumber the number of local minima. In this paper, we focus on the problem of finding approximate stationary points that are not strict saddles, i.e., second-order stationary points. We show that the aforementioned problem is also complete for the class PLS, answering an open question in the field. Our results imply that, unless PLS = NP, finding approximate second- order stationary points in unrestricted domains is easier than in (restricted) linear constrained domains, which is known to be NP-hard. This comes in stark contrast with previous results showing that, unless PLS = CLS, finding approximate stationary points in unrestricted domains is harder than in (restricted) linear constrained domains.