# Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization

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

## Key facts

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

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

- [Escaping strict saddle points of the Moreau envelope in nonsmooth optimization](https://mlsanity.com/paper/2106.09815/) (2021)
- [Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima](https://mlsanity.com/paper/2505.03717/) (2025)
- [HOUDINI: Escaping from Moderately Constrained Saddles](https://mlsanity.com/paper/2205.13753/) (2022)
- [Balanced Self-Paced Learning for AUC Maximization](https://mlsanity.com/paper/2207.03650/) (2022)
- [Creating walls to avoid unwanted points in root finding and optimization](https://mlsanity.com/paper/2309.11475/) (2023)

## Abstract (arXiv)

We consider the problem of finding an approximate second-order stationary point of a constrained non-convex optimization problem. We first show that, unlike the gradient descent method for unconstrained optimization, the vanilla projected gradient descent algorithm may converge to a strict saddle point even when there is only a single linear constraint. We then provide a hardness result by showing that checking (εg,εH)-second order stationarity is NP-hard even in the presence of linear constraints. Despite our hardness result, we identify instances of the problem for which checking second order stationarity can be done efficiently. For such instances, we propose a dynamic second order Frank--Wolfe algorithm which converges to (εg, εH)-second order stationary points in O(maxεg-2, εH-3) iterations. The proposed algorithm can be used in general constrained non-convex optimization as long as the constrained quadratic sub-problem can be solved efficiently.