Neon2: Finding Local Minima via First-Order Oracles

By Zeyuan Allen-Zhu, Yuanzhi Li. 2017

145 citations recorded by the source corpus.

We propose a reduction for non-convex optimization that can (1) turn an stationary-point finding algorithm into an local-minimum finding one, and (2) replace the Hessian-vector product computations with only gradient computations. It works both in the stochastic and the deterministic settings, without hurting the algorithm's performance. As applications, our reduction turns Natasha2 into a first-order method without hurting its performance. It also converts SGD, GD, SCSG, and SVRG into algorithms finding approximate local minima, outperforming some best known results.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, Optimization & Training, Mathematical Optimization

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

In Optimization & Training

In Mathematical Optimization

Citations in the corpus

A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “Here, the x and y axes represent the gradient direction ∇F (Wt) and the most negatively curved direction (found by Oja’s method [2, 3]), and the z axis represents the objective value.”
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].”
Local Saddle Point Optimization: A Curvature Exploitation Approach (2018, methodology): “Finally, [2, 41] showed that ﬁrst-order information can act as a noisy Power method allowing to ﬁnd a negative curvature direction.”
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 [179]–[181].”
First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time (2017, background): “It is also worth mentioning that the field of non-convex optimization is moving so fast that similar results have appeared online after the preliminary version of this work [2].”
Natasha 2: Faster Non-Convex Optimization Than SGD (2017, methodology): “333 ) [10, 46].”
Stochastic Cubic Regularization for Fast Nonconvex Optimization (2017, methodology): “Recently, instead of using the full Hessian, Carmon and Duchi [2016] showed that using a gradient descent solver for the cubic regularization subproblem allows their algorithm to find -second-order stationary points in Õ( −2) Hessian-vector product evaluations.”
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].”
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).”
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.”
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, unknown): “Allen-Zhu & Li (2017) later extended such analysis to the rank-k case as well as the gap-free case, the latter of which serves as the pillar of the Neon method.”
Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization (2019, methodology): “We denote them by Hybrid-SGD-DL[1-3] the variants corresponding to different snapshot gradient batch-sizes of b = n, b = 0.”
Escaping Saddle Points with Adaptive Gradient Methods (2019, methodology): “Chen et al. (2018) bound the nonconvex convergence rate for a large family of Adam-like algorithms, but they essentially need to assume the effective stepsize is well-behaved (as in AMSGrad).”