Research map / Learning theory and algorithms / Combinatorial and search optimization
The Computational Complexity of Finding Second-Order Stationary Points
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that finding approximate second-order stationary points (SOSPs) of unconstrained, bounded, smooth, Hessian-Lipschitz functions is PLS-complete, via a PLS membership reduction to LOCALOPT and a PLS-hardness reduction from ITER using biquintic interpolation.
Problem
Computational complexity of finding epsilon-second-order stationary points (SOSPs) in unconstrained optimization of twice-differentiable functions with Lipschitz gradient and Hessian, in the white-box model with polynomial-time Turing machines and circuits.
Approach
Shows SOSP lies in PLS by designing a LOCALOPT instance whose neighbor function alternates steepest coordinate descent and negative-curvature steps on a bounded grid, and proves PLS-hardness by embedding ITER into a C2 function built with biquintic (rather than bicubic) interpolation so that Hessian-Lipschitzness holds.
Key results
- Finding epsilon-SOSPs in unconstrained settings is in PLS (Theorem 1), so it is no harder than FOSP membership.
- Finding epsilon-SOSPs is PLS-hard even for d=2 (Theorem 2), giving PLS-completeness.
- Query lower bound Omega(1/epsilon) for deterministic algorithms computing epsilon-SOSPs (Corollary 2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an unconstrained rather than a constrained domain for finding approximate SOSPs | Finding approximate SOSPs · Optimization | computational complexity: NP-hard [31] -> PLS-complete | Helped |
| Add Hessian Lipschitzness and access to second-order oracles to the FOSP problem | Finding approximate FOSPs in unconstrained optimization · Unconstrained optimization | computational complexity | No clear effect |
| Use biquintic rather than bicubic interpolation in the hardness construction | HESSIAN-FOSP hardness reduction · Unconstrained optimization, d=2 | Hessian Lipschitzness | Helped |
Surprising findings
- Unconstrained SOSP is PLS-complete, which is presumably easier than the NP-hard constrained SOSP over polyhedra, reversing the first-order trend where unconstrained FOSP is harder than constrained.
Limitations
- The hardness and membership results are theoretical and do not yield practical algorithms.
- Membership relies on a grid-based LOCALOPT instance with exponential-size grid, not a practical method.
- Extension to third-order stationarity and relaxed second-order notions in restricted domains remain open.
Experimental setup
Baselines: Hollender & Zampetakis FOSP PLS-completeness Fearnley et al. CLS-completeness for constrained FOSP Hadley et al. NP-hardness for SOSP over polyhedra
Builds on: Hollender & Zampetakis FOSP PLS-completeness ITER (PLS-complete) Nesterov & Polyak cubic regularization Jin et al. escaping saddle points
Closest papers by meaning
- Finding Second-Order Stationary Points Efficiently in Smooth Nonconvex Linearly Constrained Optimization Problems (NeurIPS 2020 · similarity 0.92)
- Second-Order Min-Max Optimization with Lazy Hessians (ICLR 2025 · similarity 0.88)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.87)
- Barrier Algorithms for Constrained Non-Convex Optimization (ICML 2024 · similarity 0.86)
- On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.86)
- On The Complexity of First-Order Methods in Stochastic Bilevel Optimization (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.