# HOUDINI: Escaping from Moderately Constrained Saddles

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 50 references that are in the map.
- First posted on arXiv 27 May 2022.

## Builds on (most cited first, 26 of 26)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Gradient Descent Can Take Exponential Time to Escape Saddle Points](https://mlsanity.com/paper/1705.10412/) (2017)
- [Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent](https://mlsanity.com/paper/1711.10456/) (2017)
- [Escaping Saddles with Stochastic Gradients](https://mlsanity.com/paper/1803.05999/) (2018)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [Natasha 2: Faster Non-Convex Optimization Than SGD](https://mlsanity.com/paper/1708.08694/) (2017)
- ["Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions](https://mlsanity.com/paper/1705.02766/) (2017)
- [Neon2: Finding Local Minima via First-Order Oracles](https://mlsanity.com/paper/1711.06673/) (2017)
- [Escaping Saddle Points with Adaptive Gradient Methods](https://mlsanity.com/paper/1901.09149/) (2019)
- [First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time](https://mlsanity.com/paper/1711.01944/) (2017)
- [Efficient approaches for escaping higher order saddle points in non-convex optimization](https://mlsanity.com/paper/1602.05908/) (2016)
- [Escaping Saddle Points in Constrained Optimization](https://mlsanity.com/paper/1809.02162/) (2018)
- [Stochastic Recursive Variance-Reduced Cubic Regularization Methods](https://mlsanity.com/paper/1901.11518/) (2019)
- [Escape saddle points by a simple gradient-descent based algorithm](https://mlsanity.com/paper/2111.14069/) (2021)
- [First-Order Methods for Nonconvex Quadratic Minimization](https://mlsanity.com/paper/2003.04546/) (2020)
- [Analysis of Krylov Subspace Solutions of Regularized Nonconvex Quadratic Problems](https://mlsanity.com/paper/1806.09222/) (2018)
- [Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary](https://mlsanity.com/paper/1702.04300/) (2017)
- [A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees](https://mlsanity.com/paper/1904.03563/) (2019)
- [Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization](https://mlsanity.com/paper/1810.02024/) (2018)
- [A Trust Region Method for Finding Second-Order Stationarity in Linearly Constrained Non-Convex Optimization](https://mlsanity.com/paper/1904.06784/) (2019)
- [Trust Region Subproblem with a Fixed Number of Additional Linear Inequality Constraints has Polynomial Complexity](https://mlsanity.com/paper/1312.1398/) (2013)

## Abstract (arXiv)

We give the first polynomial time algorithms for escaping from high-dimensional saddle points under a moderate number of constraints. Given gradient access to a smooth function f colon mathbb Rd → mathbb R we show that (noisy) gradient descent methods can escape from saddle points under a logarithmic number of inequality constraints. This constitutes the first tangible progress (without reliance on NP-oracles or altering the definitions to only account for certain constraints) on the main open question of the breakthrough work of Ge et al. who showed an analogous result for unconstrained and equality-constrained problems. Our results hold for both regular and stochastic gradient descent.