mlsanityData to 7 Oct 2026

HOUDINI: Escaping from Moderately Constrained Saddles

arXiv 2205.13753 ↗First posted 27 May 2022cs.LG math.OC stat.MLcited by 0

Not on the map. Why?

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.

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

Builds on

26 of 50 references.

References · 26

  1. 2021Convex optimizationcited by 2,479
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2017How to Escape Saddle Points Efficientlycited by 284
  4. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  5. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  6. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
  7. 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
  8. 2018Escaping Saddles with Stochastic Gradientscited by 66
  9. 2018Stochastic Nested Variance Reduction for Nonconvex Optimizationcited by 63
  10. 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
  11. 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
  12. 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
14 more
  1. 2017Neon2: Finding Local Minima via First-Order Oraclescited by 36
  2. 2019Escaping Saddle Points with Adaptive Gradient Methodscited by 34
  3. 2017First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Timecited by 29
  4. 2016Efficient approaches for escaping higher order saddle points in non-convex optimizationcited by 23
  5. 2018Escaping Saddle Points in Constrained Optimizationcited by 14
  6. 2019Stochastic Recursive Variance-Reduced Cubic Regularization Methodscited by 12
  7. 2021Escape saddle points by a simple gradient-descent based algorithmcited by 11
  8. 2020First-Order Methods for Nonconvex Quadratic Minimizationcited by 10
  9. 2018Analysis of Krylov Subspace Solutions of Regularized Nonconvex Quadratic Problemscited by 9
  10. 2017Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundarycited by 8
  11. 2019A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guaranteescited by 7
  12. 2018Convergence to Second-Order Stationarity for Constrained Non-Convex Optimizationcited by 5
  13. 2019A Trust Region Method for Finding Second-Order Stationarity in Linearly Constrained Non-Convex Optimizationcited by 2
  14. 2013Trust Region Subproblem with a Fixed Number of Additional Linear Inequality Constraints has Polynomial Complexitycited by 1

Built on by

Not cited yet.