# Escaping Saddle Points in Constrained Optimization

arXiv: https://arxiv.org/abs/1809.02162 · HTML: https://mlsanity.com/paper/1809.02162/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Sep 2018.

## Built on by (most cited first, 14 of 14)

- [A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2206.08868/) (2022)
- [Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2308.07536/) (2023)
- [Escaping Saddle Points Faster with Stochastic Momentum](https://mlsanity.com/paper/2106.02985/) (2021)
- [Stochastic Gradient Langevin Dynamics with Variance Reduction](https://mlsanity.com/paper/2102.06759/) (2021)
- [Escaping strict saddle points of the Moreau envelope in nonsmooth optimization](https://mlsanity.com/paper/2106.09815/) (2021)
- [Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms](https://mlsanity.com/paper/2102.02837/) (2021)
- [MIXER: Multiattribute, Multiway Fusion of Uncertain Pairwise Affinities](https://mlsanity.com/paper/2210.08360/) (2022)
- [Greedy Pruning with Group Lasso Provably Generalizes for Matrix Sensing](https://mlsanity.com/paper/2303.11453/) (2023)
- [Avoiding strict saddle points of nonconvex regularized problems](https://mlsanity.com/paper/2401.09274/) (2024)
- [Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima](https://mlsanity.com/paper/2505.03717/) (2025)
- [Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm](https://mlsanity.com/paper/2101.02625/) (2021)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)
- [HOUDINI: Escaping from Moderately Constrained Saddles](https://mlsanity.com/paper/2205.13753/) (2022)
- [Faster Riemannian Newton-type Optimization by Subsampling and Cubic Regularization](https://mlsanity.com/paper/2302.11076/) (2023)

## Abstract (arXiv)

In this paper, we study the problem of escaping from saddle points in smooth nonconvex optimization problems subject to a convex set C. We propose a generic framework that yields convergence to a second-order stationary point of the problem, if the convex set C is simple for a quadratic objective function. Specifically, our results hold if one can find a ρ-approximate solution of a quadratic program subject to C in polynomial time, where ρ<1 is a positive constant that depends on the structure of the set C. Under this condition, we show that the sequence of iterates generated by the proposed framework reaches an (ε,γ)-second order stationary point (SOSP) in at most O(maxε-2,ρ-3γ-3) iterations. We further characterize the overall complexity of reaching an SOSP when the convex set C can be written as a set of quadratic constraints and the objective function Hessian has a specific structure over the convex set C. Finally, we extend our results to the stochastic setting and characterize the number of stochastic gradient and Hessian evaluations to reach an (ε,γ)-SOSP.