The Computational Complexity of Finding Second-Order Stationary Points

Andreas Kontogiannis, Vasilis Pollatos, Sotiris Kanellopoulos, Panayotis Mertikopoulos, Aris Pagourtzis, Ioannis Panageas
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:25191-25225, 2024.

Abstract

Non-convex minimization problems are universally considered hard, and even guaranteeing that a computed solution is locally minimizing is known to be NP-hard. In this general context, our paper focuses on the problem of finding stationary points that satisfy an approximate second-order optimality condition, which serves to exclude strict saddles and other non-minimizing stationary points. Our main result is that the problem of finding approximate second-order stationary points (SOSPs) is PLS-complete, i.e., of the same complexity as the problem of finding first-order stationary points (FOSPs), thus resolving an open question in the field. In particular, our results imply that, under the widely believed complexity conjecture that PLS FNP, finding approximate SOSPs in unconstrained domains is easier than in constrained domains, which is known to be NP-hard. This comes in stark contrast with earlier results which implied that, unless PLS = CLS, finding approximate FOSPs in unconstrained domains is harder than in constrained domains.

Cite this Paper


BibTeX
@InProceedings{pmlr-v235-kontogiannis24a, title = {The Computational Complexity of Finding Second-Order Stationary Points}, author = {Kontogiannis, Andreas and Pollatos, Vasilis and Kanellopoulos, Sotiris and Mertikopoulos, Panayotis and Pagourtzis, Aris and Panageas, Ioannis}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {25191--25225}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/kontogiannis24a/kontogiannis24a.pdf}, url = {https://proceedings.mlr.press/v235/kontogiannis24a.html}, abstract = {Non-convex minimization problems are universally considered hard, and even guaranteeing that a computed solution is locally minimizing is known to be NP-hard. In this general context, our paper focuses on the problem of finding stationary points that satisfy an approximate second-order optimality condition, which serves to exclude strict saddles and other non-minimizing stationary points. Our main result is that the problem of finding approximate second-order stationary points (SOSPs) is PLS-complete, i.e., of the same complexity as the problem of finding first-order stationary points (FOSPs), thus resolving an open question in the field. In particular, our results imply that, under the widely believed complexity conjecture that PLS $\neq$ FNP, finding approximate SOSPs in unconstrained domains is easier than in constrained domains, which is known to be NP-hard. This comes in stark contrast with earlier results which implied that, unless PLS = CLS, finding approximate FOSPs in unconstrained domains is harder than in constrained domains.} }
Endnote
%0 Conference Paper %T The Computational Complexity of Finding Second-Order Stationary Points %A Andreas Kontogiannis %A Vasilis Pollatos %A Sotiris Kanellopoulos %A Panayotis Mertikopoulos %A Aris Pagourtzis %A Ioannis Panageas %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-kontogiannis24a %I PMLR %P 25191--25225 %U https://proceedings.mlr.press/v235/kontogiannis24a.html %V 235 %X Non-convex minimization problems are universally considered hard, and even guaranteeing that a computed solution is locally minimizing is known to be NP-hard. In this general context, our paper focuses on the problem of finding stationary points that satisfy an approximate second-order optimality condition, which serves to exclude strict saddles and other non-minimizing stationary points. Our main result is that the problem of finding approximate second-order stationary points (SOSPs) is PLS-complete, i.e., of the same complexity as the problem of finding first-order stationary points (FOSPs), thus resolving an open question in the field. In particular, our results imply that, under the widely believed complexity conjecture that PLS $\neq$ FNP, finding approximate SOSPs in unconstrained domains is easier than in constrained domains, which is known to be NP-hard. This comes in stark contrast with earlier results which implied that, unless PLS = CLS, finding approximate FOSPs in unconstrained domains is harder than in constrained domains.
APA
Kontogiannis, A., Pollatos, V., Kanellopoulos, S., Mertikopoulos, P., Pagourtzis, A. & Panageas, I.. (2024). The Computational Complexity of Finding Second-Order Stationary Points. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:25191-25225 Available from https://proceedings.mlr.press/v235/kontogiannis24a.html.

Related Material