The Computational Complexity of Finding Second-Order Stationary Points
Authors: Andreas Kontogiannis, Vasilis Pollatos, Sotiris Kanellopoulos, Panayotis Mertikopoulos, Aris Pagourtzis, Ioannis Panageas
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | 1National Technical University of Athens, School of Electrical and Computer Engineering, Athens, Greece. 2Archimedes/Athena RC, Greece. 3Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France. 4University of California, Irvine, USA. |
| Pseudocode | Yes | Algorithm 1: An algorithm for finding an 𝜀-SOSP on an ortho-canonical grid with step 𝛾 |
| Open Source Code | No | The paper does not provide any statement or link indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not use or reference any publicly available or open datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments, therefore, no training/validation/test dataset splits are provided. |
| Hardware Specification | No | The paper is theoretical and does not describe running experiments, therefore, no specific hardware details are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe running experiments, therefore, no specific software dependencies with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and does not describe running experiments, therefore, no specific experimental setup details such as hyperparameters or training configurations are provided. |