# Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 40 references that are in the map.
- First posted on arXiv 7 Jan 2021.

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

- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [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)
- [Natasha 2: Faster Non-Convex Optimization Than SGD](https://mlsanity.com/paper/1708.08694/) (2017)
- [Sharp Analysis for Nonconvex SGD Escaping from Saddle Points](https://mlsanity.com/paper/1902.00247/) (2019)
- [Neon2: Finding Local Minima via First-Order Oracles](https://mlsanity.com/paper/1711.06673/) (2017)
- [First-order methods almost always avoid saddle points: the case of vanishing step-sizes](https://mlsanity.com/paper/1906.07772/) (2019)
- [On Learning Rates and Schr"odinger Operators](https://mlsanity.com/paper/2004.06977/) (2020)
- [First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time](https://mlsanity.com/paper/1711.01944/) (2017)
- [Gradient Descent Converges to Minimizers](https://mlsanity.com/paper/1602.04915/) (2016)
- [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)
- [A Generic Approach for Escaping Saddle points](https://mlsanity.com/paper/1709.01434/) (2017)
- [A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points](https://mlsanity.com/paper/1707.08028/) (2017)
- [Exit Time Analysis for Approximations of Gradient Descent Trajectories Around Saddle Points](https://mlsanity.com/paper/2006.01106/) (2020)

## Abstract (arXiv)

Gradient-related first-order methods have become the workhorse of large-scale numerical optimization problems. Many of these problems involve nonconvex objective functions with multiple saddle points, which necessitates an understanding of the behavior of discrete trajectories of first-order methods within the geometrical landscape of these functions. This paper concerns convergence of first-order discrete methods to a local minimum of nonconvex optimization problems that comprise strict-saddle points within the geometrical landscape. To this end, it focuses on analysis of discrete gradient trajectories around saddle neighborhoods, derives sufficient conditions under which these trajectories can escape strict-saddle neighborhoods in linear time, explores the contractive and expansive dynamics of these trajectories in neighborhoods of strict-saddle points that are characterized by gradients of moderate magnitude, characterizes the non-curving nature of these trajectories, and highlights the inability of these trajectories to re-enter the neighborhoods around strict-saddle points after exiting them. Based on these insights and analyses, the paper then proposes a simple variant of the vanilla gradient descent algorithm, termed Curvature Conditioned Regularized Gradient Descent (CCRGD) algorithm, which utilizes a check for an initial boundary condition to ensure its trajectories can escape strict-saddle neighborhoods in linear time. Convergence analysis of the CCRGD algorithm, which includes its rate of convergence to a local minimum, is also presented in the paper. Numerical experiments are then provided on a test function as well as a low-rank matrix factorization problem to evaluate the efficacy of the proposed algorithm.