Stochastic Sign Descent Methods: New Algorithms and Better Theory

Abstract

Various gradient compression schemes have been proposed to mitigate the communication cost in distributed training of large scale machine learning models. Sign-based methods, such as signSGD, have recently been gaining popularity because of their simple compression rule and connection to adaptive gradient methods, like ADAM. In this paper, we analyze sign-based methods for non-convex optimization in three key settings: (i) standard single node, (ii) parallel with shared data and (iii) distributed with partitioned data. For single machine case, we generalize the previous analysis of signSGD relying on intuitive bounds on success probabilities and allowing even biased estimators. Furthermore, we extend the analysis to parallel setting within a parameter server framework, where exponentially fast noise reduction is guaranteed with respect to number of nodes, maintaining $1$-bit compression in both directions and using small mini-batch sizes. Next, we identify a fundamental issue with signSGD to converge in distributed environment. To resolve this issue, we propose a new sign-based method, {\em Stochastic Sign Descent with Momentum (SSDM)}, which converges under standard bounded variance assumption with the optimal asymptotic rate. We validate several aspects of our theoretical findings with numerical experiments.

33 pages, 8 figures, 1 table, ICML 2021 (v6: post-publication correction)

References in corpus (15)

• Deep Learning in Neural Networks: An Overview
• ADADELTA: An Adaptive Learning Rate Method
• On the Convergence of Adam and Beyond
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• ATOMO: Communication-efficient Learning via Atomic Sparsification
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization
• signSGD with Majority Vote is Communication Efficient And Fault Tolerant
• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
• Distributed Learning with Compressed Gradient Differences
• On the absolute constants in the Berry-Esseen type inequalities for identically distributed summands
• Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition
• Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients
• Distributed learning with compressed gradients

Cited by in corpus (4)

• Sign Bit is Enough: A Learning Synchronization Framework for Multi-hop All-reduce with Ultimate Compression
• Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques
• Federated Learning via Plurality Vote
• On The Convergence of Euler Discretization of Finite-Time Convergent Gradient Flows