# First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2017.

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

- [Gradient Norm Aware Minimization Seeks First-Order Flatness and Improves Generalization](https://mlsanity.com/paper/2303.03108/) (2023)
- [Flatness-Aware Minimization for Domain Generalization](https://mlsanity.com/paper/2307.11108/) (2023)
- [Efficiently Escaping Saddle Points in Bilevel Optimization](https://mlsanity.com/paper/2202.03684/) (2022)
- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case](https://mlsanity.com/paper/2307.11782/) (2023)
- [A Global Geometric Analysis of Maximal Coding Rate Reduction](https://mlsanity.com/paper/2406.01909/) (2024)
- [Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks](https://mlsanity.com/paper/2302.09699/) (2023)
- [Escape saddle points by a simple gradient-descent based algorithm](https://mlsanity.com/paper/2111.14069/) (2021)
- [Escaping Saddle Points Faster with Stochastic Momentum](https://mlsanity.com/paper/2106.02985/) (2021)
- [Memory Augmented Optimizers for Deep Learning](https://mlsanity.com/paper/2106.10708/) (2021)
- [On the Second-order Convergence Properties of Random Search Methods](https://mlsanity.com/paper/2110.13265/) (2021)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)
- [Efficient displacement convex optimization with particle gradient descent](https://mlsanity.com/paper/2302.04753/) (2023)
- [Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance](https://mlsanity.com/paper/2604.16620/) (2026)
- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)
- [Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience](https://mlsanity.com/paper/2103.09424/) (2021)
- [Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning](https://mlsanity.com/paper/2202.06083/) (2022)
- [Tackling benign nonconvexity with smoothing and stochastic gradients](https://mlsanity.com/paper/2202.09052/) (2022)
- [Variance-Reduced Conservative Policy Iteration](https://mlsanity.com/paper/2212.06283/) (2022)
- [Escaping Saddle Points with Compressed SGD](https://mlsanity.com/paper/2105.10090/) (2021)
- [Faster Perturbed Stochastic Gradient Methods for Finding Local Minima](https://mlsanity.com/paper/2110.13144/) (2021)
- [SiGeo: Sub-One-Shot NAS via Information Theory and Geometry of Loss Landscape](https://mlsanity.com/paper/2311.13169/) (2023)
- [Noise is All You Need: Private Second-Order Convergence of Noisy SGD](https://mlsanity.com/paper/2410.06878/) (2024)
- [Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimization](https://mlsanity.com/paper/2509.02937/) (2025)
- [Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization](https://mlsanity.com/paper/2606.05438/) (2026)
- [Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm](https://mlsanity.com/paper/2101.02625/) (2021)
- [Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods](https://mlsanity.com/paper/2103.04413/) (2021)
- [HOUDINI: Escaping from Moderately Constrained Saddles](https://mlsanity.com/paper/2205.13753/) (2022)

## Abstract (arXiv)

Two classes of methods have been proposed for escaping from saddle points with one using the second-order information carried by the Hessian and the other adding the noise into the first-order information. The existing analysis for algorithms using noise in the first-order information is quite involved and hides the essence of added noise, which hinder further improvements of these algorithms. In this paper, we present a novel perspective of noise-adding technique, i.e., adding the noise into the first-order information can help extract the negative curvature from the Hessian matrix, and provide a formal reasoning of this perspective by analyzing a simple first-order procedure. More importantly, the proposed procedure enables one to design purely first-order stochastic algorithms for escaping from non-degenerate saddle points with a much better time complexity (almost linear time in terms of the problem's dimensionality). In particular, we develop a bf first-order stochastic algorithm based on our new technique and an existing algorithm that only converges to a first-order stationary point to enjoy a time complexity of widetilde O(d/ε3.5) for finding a nearly second-order stationary point bfx such that |nabla F(bfx)|≤ ε and nabla2 F(bfx)≥ -√εI (in high probability), where F(·) denotes the objective function and d is the dimensionality of the problem. To the best of our knowledge, this is the best theoretical result of first-order algorithms for stochastic non-convex optimization, which is even competitive with if not better than existing stochastic algorithms hinging on the second-order information.