The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization

Source: arxiv.org/abs/2604.02285

Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos

arXivarxiv/2604.02285Apr 2, 2026cs.CCscore 0

The complexity of finding second-order stationary points (SOSPs) in constrained settings has remained unclear and has been highlighted as an open question by the works of Hollender and Zampetakis [2023] and Kontogiannis et al. [2024]. In particular, under one established definition (SOSP1) where nonnegative curvature is required only along the null space of the active constraints [Bertsekas, 1997], the problem lies in TFNP, and algorithms with $O(poly(1/ε))$ running times have been proposed. Under another established notion of stationarity (SOSP2) checking is coNP-hard in high dimensions. We…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2604.02285
curl -X POST /api/v1/records/arxiv/2604.02285/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.02285/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'