The Geometry of Sign Gradient Descent

Abstract

Sign-based optimization methods have become popular in machine learning due to their favorable communication cost in distributed optimization and their surprisingly good performance in neural network training. Furthermore, they are closely connected to so-called adaptive gradient methods like Adam. Recent works on signSGD have used a non-standard "separable smoothness" assumption, whereas some older works study sign gradient descent as steepest descent with respect to the ${\ell }_{\infty }$-norm. In this work, we unify these existing results by showing a close connection between separable smoothness and ${\ell }_{\infty }$-smoothness and argue that the latter is the weaker and more natural assumption. We then proceed to study the smoothness constant with respect to the ${\ell }_{\infty }$-norm and thereby isolate geometric properties of the objective function which affect the performance of sign-based methods. In short, we find sign-based methods to be preferable over gradient descent if (i) the Hessian is to some degree concentrated on its diagonal, and (ii) its maximal eigenvalue is much larger than the average eigenvalue. Both properties are common in deep networks.

References in corpus (7)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• signSGD with Majority Vote is Communication Efficient And Fault Tolerant
• Stochastic Gradient Methods with Layer-wise Adaptive Moments for Training of Deep Networks
• The Power of Normalization: Faster Evasion of Saddle Points
• The Full Spectrum of Deepnet Hessians at Scale: Dynamics with SGD Training and Sample Size
• Block-Normalized Gradient Method: An Empirical Study for Training Deep Neural Network
• Hessian based analysis of SGD for Deep Nets: Dynamics and Generalization

Cited by in corpus (4)

• Online Training of Spiking Recurrent Neural Networks with Phase-Change Memory Synapses
• Revealing and Protecting Labels in Distributed Training
• On Faster Convergence of Scaled Sign Gradient Descent
• On The Convergence of Euler Discretization of Finite-Time Convergent Gradient Flows