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 $\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.

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