The Power of Normalization: Faster Evasion of Saddle Points

By Kfir Yehuda Levy. 2016

115 citations recorded by the source corpus.

A commonly used heuristic in non-convex optimization is Normalized Gradient Descent (NGD) - a variant of gradient descent in which only the direction of the gradient is taken into account and its magnitude ignored. We analyze this heuristic and show that with carefully chosen parameters and noise injection, this method can provably evade saddle points. We establish the convergence of NGD to a local minimum, and demonstrate rates which improve upon the fastest known first order algorithm due to Ge e al. (2015). The effectiveness of our method is demonstrated via an application to the problem of online tensor decomposition; a task for which saddle point evasion is known to result in convergence to global minima.

Subfields: Artificial Intelligence, Computational Mathematics, Computational Mechanics

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 Mathematics

In Computational Mechanics

Citations in the corpus

AutoML-Zero: Evolving Machine Learning Algorithms From Scratch (2020, methodology): “The normalized gradient is a commonly used heuristic in non-convex optimization [29, 41], which could help with the vanishing and exploding gradient problem [98, 63].”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, methodology): “Algorithms that provably work in this setting include cubic regularization [36], trust region methods [16], approximate cubic regularization schemes [3], [12], [13], randomly initialized and perturbed (stochastic) gradients [17], [22], [22], [29], [30].”
Sampling Matters in Deep Embedding Learning (2017, background): “[12, 20] for more discussions about the benefits of using gradients of a fixed length.”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, methodology): “No spurious local minmum, i.e., all local minima are global, then perturbed (stochastic) gradient descent [Ge et al., 2015, Jin et al., 2017, Levy, 2016] or methods with second order information [Nesterov and Polyak, 2006, Curtis et al., 2014, Carmon et al., 2016, Allen-Zhu, 2017] can ﬁnd a global…”
How to Escape Saddle Points Efficiently (2017, methodology): “This was improved in Levy [2016] to O ( d 3 · poly(1 /ǫ )) using normalized gradient descent.”
BLOCK-NORMALIZED GRADIENT METHOD: AN EMPIRICAL STUDY FOR TRAINING DEEP NEURAL NETWORK (2018, methodology): “In this paper, we propose a generic framework using the mini-batch stochastic normalized gradient as the updating direction (like [Hazan et al., 2015, Levy, 2016]) and the step size is either constant or adaptive to each coordinate as in [Duchi et al., 2011, Kingma and Ba, 2014].”
A Generic Approach for Escaping Saddle points (2017, background): “Noisy variants of ﬁrst-order methods have also been shown to escape saddle points (see [13, 16, 22]), however, these methods have strong dependence on either n or d , both of which are undesirable.”
First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time (2017, background): “ct a negative curvature direction of the Hessian, which itself is stronger than just showing the objective value decrease around saddle points in existing studies (Jin et al., 2017a; Ge et al., 2015; Levy, 2016). Our main contributions are: • We provide a novel perspective of adding noise into the ﬁ”
Escaping Saddles with Stochastic Gradients (2018, methodology): “Based upon this observations, recent works prove second-order convergence of normalized GD (Levy, 2016) and perturbed GD (Jin et al., 2017a).”
Why ADAM Beats SGD for Attention Models (2019, background): “Another direction of related work is normalized gradient descent, which has been studied for quasi-convex and non-convex settings (Levy, 2016; Hazan et al., 2015; Zhang et al., 2019).”
Why Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity (2019, background): “In addition, Levy (2016) showed that normalized gradient descent may have better convergence rate in presence of injected noise.”
Why are Adaptive Methods Good for Attention Models? (2020, background): “Another direction of related work is normalized gradient descent, which has been studied for quasi-convex and non-convex settings [12, 15].”
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 classified into gradient-based (Ge et al., 2015; Levy, 2016; Xu & Yang, 2017; Allen-Zhu, 2017; Allen-Zhu & Li, 2017; Jin et al., 2017b), Hessian-vector-product-based (Carmon et al.”
ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning (2020, methodology): “For example, theoretically it has been shown that some ﬁrst order methods can only converge to an approximate second order critical point [19, 23, 26, 40].”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, background): “Levy (2016) proposed the noise-perturbed variant of NGD which yields faster evasion of saddle points than GD.”
On the Power of Over-parametrization in Neural Networks with Quadratic Activation (2018, background): “…functions satisfy the following two key properties: (1) all local minima are global and (2) all saddle points and local maxima are strict, then ﬁrst order method like gradient descent (Ge et al., 2015; Jin et al., 2017; Levy, 2016; Du et al., 2017a; Lee et al., 2016) can ﬁnd a global minimum.”
Escaping Saddle Points with Adaptive Gradient Methods (2019, background): “Reddi et al. (2018b) showed non-convergence of Adam and RMSProp in simple convex settings and provided a variant of Adam, called AMSGrad, with guaranteed convergence in the convex setting; Zhou et al. (2018) generalized this to a nonconvex first-order convergence result. Zaheer et al. (2018) showed ”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “Similar high iteration complexity holds for [176] which is based on injecting noise to normalized gradient descent.”