The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization".
Jane: Here's the gist of the paper. The paper investigates the computational complexity of finding second-order stationary points (SOSPs) within constrained optimization problems, specifically focusing on polytope constraints, and establishes that this problem is PLS-complete.
Tom: The analysis addresses the difficulty of finding approximate SOSPs under a tractable definition, termed (Constrained-Sosp), which requires satisfying both an approximate first-order condition (g pi(x*) at most epsilon G) and an approximate second-order condition (y T grad 2f(x+) y at least-epsilon H for all y such that A'(x+) y = 0 and y = 1).
Jane: The paper proves that (Constrained-Sosp) is PLS-complete, even when the domain is restricted to the simple unit square box
0, 1: .
Tom: This hardness result holds even for the promise version of the problem.
Paper summary: Jane: So where does this leave us when we look at the title, "The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization," and who did this work? It’s Kontogiannis, Panageas, and Pollatos.
Tom: The authors are pointing out that while first-order points are traditional targets for optimization, they often lead to those undesirable strict saddle points we want to avoid.
Lu: The conclusion is that the problem of finding approximate SOSPs in constrained settings is PLS-complete, meaning it’s as hard as finding approximate unconstrained first-order stationary points.
Meng: In plain terms, this means if you are optimizing something with constraints and you need to check for stability using second-order information, you can't rely on a simple continuous search algorithm that runs quickly for all cases.
Lalam: The real implication is the barrier they’ve established: there is no known continuous algorithm with a polynomial time implementable update rule that can find an approximate SOSP under these conditions unless some major complexity classes change.
Jane: It’s about setting expectations on what we can achieve deterministically in these complex optimization landscapes. They show us where the computational limits are for finding those good, stable points.
Tom: The paper is a very strong result because it shows this hardness holds even for the promise version of the problem, which adds another layer of certainty to their claim about approximate SOSPs.
Lu: This work forces researchers to look beyond standard gradient-based approaches when dealing with constrained problems where second-order information is necessary for performance.
Meng: For those of us shipping models, this means we have to be smarter about how we structure our optimization routines, perhaps by simplifying the constraint space or changing the objective function slightly if a guaranteed fast solution is critical.
Lalam: The paper's construction using that discrete grid and biquintic interpolation is what makes this hardness concrete; it’s how they prove that every possible approximate stationary point in those regions maps back to a hard problem in Iter.
Conclusion: Tom: So we’re wrapping up on "The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization." This paper, by Kontogiannis, Panageas, and Pollatos, basically argues that finding stable points in constrained problems is really hard.
Jane: So what does that mean for someone who just wants to find the best possible solution? Like, if you’re optimizing something with rules on how big it can be or how it has to behave—the constraints—finding a point where you know you won't get stuck in a bad spot is computationally tough.
Lu: They prove that this problem is PLS-complete. That means it’s as hard as some other famous problem called Iter, even when we only look at the simple unit square box. It shows that the difficulty isn't just about having a lot of data; it’s about the structure of those constraints themselves.
Meng: So what does this mean for me in production? If I have a complex optimization problem running on my system and I need to make sure it settles into a good spot, I can't just rely on some quick, continuous algorithm that runs fast everywhere. There’s a fundamental barrier there.
Lalam: The paper shows there is no continuous algorithm with an update rule that runs in polynomial time unless some big complexity classes are actually equal. It means we can't just code our way around this difficulty easily for general constrained problems.
Jane: That sounds pretty tough for anyone trying to build robust optimization tools. So, if we look at the title again, "The Computational Complexity of Avoiding Strict Saddle Points," it really highlights that avoiding those bad points isn't a simple trick; it’s deeply rooted in the math of the problem setup.
Tom: Exactly. The authors show you need second-order information to guarantee stability under these constraints, and getting that stable information back efficiently is what they’re tackling here.
Lu: They use a reduction from Iter to show exactly how that difficulty arises, using some clever grid structures and biquintic interpolation to trap the hard instances. It’s a very specific construction showing why it’s this hard.
Meng: So for deployment purposes, we have to be very careful about how we define our search space if we want a deterministic guarantee of finding approximate stationary points without running into these complexity walls.
Lalam: I'm quite sure of the result here. The hardness is established even for the promise version of the problem, which makes their claim pretty solid. It sets a high bar for what’s possible in constrained optimization research right now.
Jane: It certainly sets a high bar, and it leads us to wonder what kind of specialized methods we might need to develop if we want to solve these kinds of problems reliably without hitting this complexity wall.
National Technical University of Athens · Archimedes, Athena Research Center, Greece · University of California, Irvine · National and Kapodistrian University of Athens
cs.CC, cs.DS, cs.GT, math.OC
Submitted: 2026-04-02
Updated: 2026-11-04
Comments: This version simplifies the group analysis and extends the results to the SOSP2 definition and nonconvex games. The abstract was shortened to meet the arXiv requirements
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 92/100
The gist: The paper investigates the computational complexity of finding second-order stationary points (SOSPs) within constrained optimization problems, specifically focusing on polytope constraints…
Key concepts
- Second-Order Stationary Points (SOSPs)
- These are points in an optimization problem where the curvature of the function, represented by the Hessian matrix, satisfies specific conditions. Finding them is crucial for determining if a point is a local minimum or maximum.
- (Constrained-Sosp)
- This is a tractable definition for finding approximate SOSPs that combines two conditions: an approximate first-order condition (related to the gradient) and an approximate second-order condition (related to the Hessian's behavior along certain directions).
- PLS-complete
- This complexity class signifies that the problem is as hard as a known difficult problem called Iter. It indicates that solving this constrained SOSP problem is computationally very difficult, suggesting no efficient general solution exists.
- Continuous Algorithm with Polynomial-Time Implementable Update Rule
- This refers to an optimization method where the steps taken at each iteration can be calculated quickly (polynomial time) and are defined by a continuous mathematical rule. The paper shows such an algorithm cannot always find approximate SOSPs.
Terminology
Summary
The paper investigates the computational complexity of finding second-order stationary points (SOSPs) within constrained optimization problems, specifically focusing on polytope constraints, and establishes that this problem is PLS-complete. p. 2 Under another well-established, relaxed definition of ϵ-approximate
second-order stationary points—where non-negative curvature is required only along the null space of
the active constraints—the problem lies in TFNP [MP91]
1
, and algorithms, such as SNAP [LRY+
20],
have been proposed that run in time O(poly(1/ϵ)). Therefore, we are naturally led to the following
important question:
Question 1: What is the computational complexity of finding SOSPs in constrained
optimization?Where the paper says it
The analysis addresses the difficulty of finding approximate SOSPs under a tractable definition, termed (Constrained-Sosp), which requires satisfying both an approximate first-order condition (|g pi(x*)| at most epsilon G) and an approximate second-order condition (y T grad 2f(x+) y at least-epsilon H for all y such that A'(x+) y = 0 and | y| = 1). The paper proves that (Constrained-Sosp) is PLS-complete, even when the domain is restricted to the simple unit square box [0, 1]. p. 0 In this paper, we settle the complexity of constrained SOSP by proving that computing an
ϵ-approximate SOSP under the tractable definition is PLS-complete. We demonstrate that our
hardness result continues to hold in domains as simple as the 2-dimensional unit square [0, 1]
2
,
and remarkably, even when promised that all stationary points are isolated at a distance of
Ω(1) away from the domain’s boundary. We note
that our results also hold for the promise version of the problem, as the hard instances we construct
inherently satisfy the required promises. Before delving into the main ideas behind our main result
in the subsequent section, we first briefly outline the main results of our paper.Where the paper says it
Where the paper says it
A key contribution involves proving that there exists no continuous algorithm with a polynomial-time implementable update rule capable of finding an approximate SOSP under these conditions, unless PLS PPAD (or equivalently PLS = CLS). p. 3 That said, we also prove the following
theorem:
Theorem (Abridged; Formally stated in Theorem 6. Unless PLS ⊆ PPAD (or equivalently PLS =
CLS), there exists no iterative algorithm with a continuous, polynomial-time implementable update
rule for finding ϵ-approximate SOSPs, even if the objective function is promised to be 1-Lipschitz,
1-smooth and 1-Hessian-Lipschitz and the domain X is fixed to be the unit square box [0, 1]
2
. 1 illustrates an example instance of the Iter problem. In this paper, we will also make use of the canonical PLS-complete problem LocalOpt [FGHS22],
which is defined as follows:
6 9 No approximate FOSPs are created on the boundary . 10 Classifying small boxes into groups .Where the paper says it
Where the paper says it
Where the paper says it
The paper meticulously details the analysis by examining specific conditions related to the minimum eigenvalue (lambda) of the Hessian across various constructed regions. For instance, for Group B, it is shown that under certain parameter assumptions (R > B + 1020), the minimal eigenvalue lambda satisfies lambda much less than-1, which precludes approximate SOSPs. Furthermore, several theorems establish bounds on terms related to the Hessian eigenvalues (e. p. 3 Unless PLS ⊆ PPAD (or equivalently PLS =
CLS), there exists no iterative algorithm with a continuous, polynomial-time implementable update
rule for finding ϵ-approximate SOSPs, even if the objective function is promised to be 1-Lipschitz,
1-smooth and 1-Hessian-Lipschitz and the domain X is fixed to be the unit square box [0, 1]
2
. Furthermore, our result implies that finding approximate SOSPs in linearly constrained optimization is as hard as in the unconstrained case, the latter of which was recently shown by Kontogiannis et
al. We demonstrate that our
hardness result continues to hold in domains as simple as the 2-dimensional unit square [0, 1]
2
,
and remarkably, even when promised that all stationary points are isolated at a distance of
Ω(1) away from the domain’s boundary. Our result establishes a fundamental barrier: unless
PLS ⊆ PPAD (which in turn would imply that PLS = CLS), no deterministic, iterative algorithm
with a computational efficient, continuous update rule can exist for finding approximate SOSPs.Where the paper says it
Where the paper says it
The complexity is contrasted with finding approximate first-order stationary points (FOSPs). p. 0 The Computational Complexity of Avoiding Strict
Saddle Points in Constrained Optimization
Andreas Kontogiannis1,2, Ioannis Panageas2,3, and Vasilis Pollatos2,4
1National Technical University of Athens
2Archimedes, Athena Research Center, Greece
3University of California, Irvine
4National and Kapodistrian University of Athens
April 3, 2026
Abstract
While first-order stationary points (FOSPs) are the traditional targets of non-convex optimization, they often correspond to undesirable strict saddle points. To circumvent this limitation,
recent attention has shifted towards finding second-order stationary points (SOSPs). While finding a FOSP
(or KKT point) in a bounded domain is known to be complete for the class CLS (Continuous
Local Search) [FGHS22]—a subclass of PLS that characterizes problems solvable by continuous,
gradient-based methods—finding a SOSP remains poorly understood and has been highlighted as an
important open question by previous recent work [HZ23, KPK+
24]. To the best of our knowledge,
the only relevant result of which we are aware showed that, for certain strict notions of stationarity,
even checking whether a point is an approximate SOSP in the presence of linear constraints is NPhard [MK87, NLR18, MOJ18]. Our result establishes a fundamental barrier: unless
PLS ⊆ PPAD (which in turn would imply that PLS = CLS), no deterministic, iterative algorithm
with a computational efficient, continuous update rule can exist for finding approximate SOSPs. This comes in stark contrast to the complexity of its constrained first-order counterpart, for
which the celebrated work of Fearnley, Goldberg, Hollender and Savani (STOC 2021, JACM 2022)
[FGHS22] showed that finding an approximate KKT point drops to CLS-complete. In doing so, we will construct a function f that satisfies the input
conditions of Interior-Sosp, while embedding an arbitrary Iter instance into a 2D discrete grid
represented within the box [0, N]
2
, which is the domain of f. Our construction will ensure that every
(ϵ0, ϵ0)-SOSP (i.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Automated determination of computational complexity for constrained optimization problems can be performed by using established hardness results, such as proving that Constrained-Sosp is PLS-complete, to determine if a deterministic iterative algorithm with a continuous update rule exists.
-
The system can rigorously verify the non-existence of continuous algorithms for finding approximate second-order stationary points in constrained settings by checking if PLS is contained within PPAD or equivalent to CLS, based on the theorem:
Unless PLS ⊆ PPAD (or equivalently PLS = CLS), there exists no iterative algorithm with a continuous, polynomial-time implementable update rule for finding epsilon-approximate SOSPs.
-
The AI system can be equipped to distinguish between different classes of stationary points by analyzing the structure of the Hessian and proximal gradient norm, specifically by classifying grid cells into groups A through G to guarantee that certain groups do not create approximate SOSPs.
-
The system can implement a proof strategy for finding an approximate SOSP in polynomial time, such as SNAP, and use this to establish complexity boundaries for constrained optimization problems by showing that the problem is PLS-hard or lies within CLS.
Abstract
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 investigate the computational landscape of finding SOSPs under polytope constraints. We prove that, even if promised that all KKT points lie a constant distance away from the domain's boundary--where SOSP1 and SOSP2 reduce to the standard unconstrained conditions--finding an approximate SOSP under either definition is PLS-hard, and the hardness continues to hold even in [0,1] squared. As a direct consequence, our result establishes a fundamental barrier on the continuity of SOSP-computing algorithms: unless PLS=CLS, no deterministic, iterative algorithm with a computationally efficient, continuous update rule can guarantee that every ε-approximate fixed point is an (ε, sqrtε) -SOSP, even under the above interior promise. We establish PLS-completeness by proving that the problem of finding approximate SOSP1 belongs to PLS in high dimensions. In addition, we prove that, for every fixed d at least 2, finding an approximate SOSP2 is also PLS-complete, escaping the coNP-hardness which appears in high dimensions. We also establish PLS-hardness and a polynomial-time search reduction to LOCALOPT for finding (r 2+γ,r) -local pure Nash equilibria, for every fixed rational γ in(0,1], in two-player nonconvex common-interest games with actions in [0,1].
Sources
- The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
- The Complexity of Min-Max Optimization with Product Constraints
- Improved Hardness Results for Min-Max Optimization with Coupled Constraints
- Quadratic Speedup for Computing Contraction Fixed Points
- CLS: New Problems and Completeness
- Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?