The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization

arXiv:2604.02285 · cs.CC, cs.DS, cs.GT, math.OC · Submitted 2026-04-02 · Read on arXiv

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

Where the paper says it

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?

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

Where the paper says it

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.

This hardness result holds even for the promise version of the problem. p. 8
Where the paper says it

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.

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

Where the paper says it

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 .

This is achieved by demonstrating the existence of a reduction from the PLS-complete problem Iter to an Interior-Sosp instance. p. 5
Where the paper says it

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

The construction utilizes a discrete grid and biquintic interpolation, introducing seven new groups of small boxes (Groups A–G) designed to guarantee the non-existence of approximate SOSPs in these regions. p. 1
Where the paper says it

9 No approximate FOSPs are created on the boundary . 10 Classifying small boxes into groups .

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

Where the paper says it

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.

g., G y, G x) and show that these values are sufficiently negative to rule out approximate stationary points in specific sub-regions of the domain. p. 0
Where the paper says it

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.

The complexity is contrasted with finding approximate first-order stationary points (FOSPs). p. 0

Where the paper says it

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 approximate FOSPs is known to be PLS-complete in unconstrained settings, the paper shows that under linear constraints, it can be CLS-complete. p. 2
Where the paper says it

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].

The core result demonstrates that constrained SOSP finding is as hard as the unconstrained case (PLS-complete), creating a fundamental barrier against deterministic, continuous iterative methods for this problem. p. 0
Where the paper says it

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.

The construction involves mapping points onto the polytope using a recursive Ray-Shooting algorithm to define an implicit grid and potential function, ensuring that every approximate SOSP found corresponds to a solution of the Iter instance. p. 9
Where the paper says it

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.

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

  1. 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.

  2. 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.

  3. 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.

  4. 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

Related papers