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 (5)

• The Loss Surfaces of Multilayer Networks
• Matrix Completion has No Spurious Local Minimum
• Variance Reduction for Faster Non-Convex Optimization
• Beyond Convexity: Stochastic Quasi-Convex Optimization
• Complete Dictionary Recovery over the Sphere

Cited by in corpus (40)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• How to Escape Saddle Points Efficiently
• AutoML-Zero: Evolving Machine Learning Algorithms From Scratch
• Sampling Matters in Deep Embedding Learning
• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• Escaping Saddles with Stochastic Gradients
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Progress toward favorable landscapes in quantum combinatorial optimization
• Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study
• Efficiently escaping saddle points on manifolds
• Inexact Non-Convex Newton-Type Methods
• Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
• Robust Distributed Optimization With Randomly Corrupted Gradients
• Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• Finding Local Minima via Stochastic Nested Variance Reduction
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping
• A One-bit, Comparison-Based Gradient Estimator
• Improved Analysis of Clipping Algorithms for Non-convex Optimization
• On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Stationary Points of Shallow Neural Networks with Quadratic Activation Function
• The Geometry of Sign Gradient Descent
• Efficiently avoiding saddle points with zero order methods: No gradients required
• Escaping Saddle Points Faster with Stochastic Momentum
• 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
• Adaptive Stochastic Gradient Langevin Dynamics: Taming Convergence and Saddle Point Escape Time
• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
• On the global convergence of randomized coordinate gradient descent for non-convex optimization
• Backward Gradient Normalization in Deep Neural Networks
• On Assessing the Quantum Advantage for MaxCut Provided by Quantum Neural Network Ansätze
• On the Differentially Private Nature of Perturbed Gradient Descent
• Binary Search and First Order Gradient Based Method for Stochastic Optimization
• A Deterministic Gradient-Based Approach to Avoid Saddle Points
• On the Second-order Convergence Properties of Random Search Methods
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum