The Power of Normalization: Faster Evasion of Saddle Points

Abstract

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.

References in corpus (1)

• The Loss Surfaces of Multilayer Networks

Cited by in corpus (14)

• How to Escape Saddle Points Efficiently
• Sampling Matters in Deep Embedding Learning
• Improved Analysis of Clipping Algorithms for Non-convex Optimization
• The Geometry of Sign Gradient Descent
• Escaping Saddle Points Faster with Stochastic Momentum
• Efficiently avoiding saddle points with zero order methods: No gradients required
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• Escaping Saddle Points with the Successive Convex Approximation Algorithm
• Backward Gradient Normalization in Deep Neural Networks
• Binary Search and First Order Gradient Based Method for Stochastic Optimization
• On the Second-order Convergence Properties of Random Search Methods
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• On the Differentially Private Nature of Perturbed Gradient Descent