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

By Yi Xu, Rong Jin, Tianbao Yang. 2017

123 citations recorded by the source corpus.

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/\epsilon^{3.5})$ for finding a nearly second-order stationary point $\bf{x}$ such that $\|\nabla F(bf{x})\|\leq \epsilon$ and $\nabla^2 F(bf{x})\geq -\sqrt{\epsilon}I$ (in high probability), where $F(\cdot)$ 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.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, neutral): “5), where previously SGD variants only achieve Õ(ε−4) [6, 14, 30].”
AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization (2018, methodology): “In the noisy setting, faster rates than O ( 1/ √ N ) are also possible using accelerated SGD methods (Ghadimi and Lan, 2016; AllenZhu and Yang, 2016; Reddi et al., 2016; Allen-Zhu, 2017; Xu et al., 2018; Zhou et al., 2018; Fang et al., 2018).”
Lower bounds for non-convex stochastic optimization (2019, background): “Smoothness in higher derivatives, such as Lipschitz continuity of the Hessian, allows additional possibilities [3, 5, 25, 52].”
Escaping Saddles with Stochastic Gradients (2018, methodology): “One can even improve the convergence guarantee of SGD by using the NEON framework (Allen-Zhu & Li, 2017; Xu & Yang, 2017) but a perturbation with isotropic noise is still required.”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, methodology): “Online PCA and the NEON method In late 2017, two groups Xu et al. (2017); Allen-Zhu & Li (2018) proposed a generic saddle-point-escaping method called Neon, a Negative-CurvatureSearch method using stochastic gradients.”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “There are also several other algorithms that provably work well in the presence of stochastic / incremental first-order and / or second-order oracles [196–198].”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, background): “Other algorithms are developed for general non-convex optimization, and they can be classiﬁed into gradient-based [27, 44, 68, 4, 5, 33], Hessian-vector-product-based [12, 2, 56, 57], and Hessian-based [54, 19] methods.”
Local Saddle Point Optimization: A Curvature Exploitation Approach (2018, methodology): “Finally, [2, 41] showed that first-order information can act as a noisy Power method allowing to find a negative curvature direction.”
Neon2: Finding Local Minima via First-Order Oracles (2017, methodology): “The independent work Neon by Xu and Yang [31] is actually the first recorded theoretical result that proposed this approach.”
A Subsampling Line-Search Method with Second-Order Results (2018, background): “Noise can be used to approximate second-order information as well [32].”
Natasha 2: Faster Non-Convex Optimization Than SGD (2017, methodology): “• If one applies SGD and only escapes from saddle points using Oja’s algorithm, the convergence rate is T = (cid:101) O ( ε − 4 ) [10, 46].”
Asymmetric Valleys: Beyond Sharp and Flat Local Minima (2019, background): “For example, it is shown that they could escape saddle points or sharp local minima under reasonable assumptions (Ge et al., 2015; Jin et al., 2017; 2018a;b; Xu et al., 2018; Allen-Zhu, 2018a;b; Allen-Zhu & Li, 2018; Kleinberg et al., 2018).”