The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
summary
The gist
The paper investigates the computational complexity of finding second-order stationary points (SOSPs) within constrained optimization problems, specifically focusing on polytope constraints…
In short
The paper investigates finding second-order stationary points (SOSPs) within constrained optimization problems, specifically those defined by polytope constraints. It proves that finding approximate SOSPs is PLS-complete, even on simple domains like a unit square. This means no continuous algorithm with a polynomial-time update rule can reliably find such points unless the complexity class PLS equals PPAD.
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 used across episodes
This episode discusses
- The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization · Paper Radio
- 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
The paper
The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization · Read on arXiv
National Technical University of Athens · Archimedes, Athena Research Center, Greece · University of California, Irvine · National and Kapodistrian University of Athens
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].
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.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game