Error Feedback Fixes SignSGD and other Gradient Compression Schemes

Abstract

Sign-based algorithms (e.g. signSGD) have been proposed as a biased gradient compression technique to alleviate the communication bottleneck in training large neural networks across multiple workers. We show simple convex counter-examples where signSGD does not converge to the optimum. Further, even when it does converge, signSGD may generalize poorly when compared with SGD. These issues arise because of the biased nature of the sign compression operator. We then show that using error-feedback, i.e. incorporating the error made by the compression operator into the next step, overcomes these issues. We prove that our algorithm EF-SGD with arbitrary compression operator achieves the same rate of convergence as SGD without any additional assumptions. Thus EF-SGD achieves gradient compression for free. Our experiments thoroughly substantiate the theory and show that error-feedback improves both convergence and generalization. Code can be found at \url{https://github.com/epfml/error-feedback-SGD}.

ICML 2019 (long talk)

Cited by in corpus (31)

• A Field Guide to Federated Optimization
• Variance Reduced Local SGD with Lower Communication Complexity
• Dynamic Model Pruning with Feedback
• SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum
• Understanding Top-k Sparsification in Distributed Deep Learning
• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• Hyper-Sphere Quantization: Communication-Efficient SGD for Federated Learning
• Distributed Learning in Wireless Networks: Recent Progress and Future Challenges
• Rethinking gradient sparsification as total error minimization
• Large Scale Private Learning via Low-rank Reparametrization
• Layer-wise Adaptive Gradient Sparsification for Distributed Deep Learning with Convergence Guarantees
• SPARQ-SGD: Event-Triggered and Compressed Communication in Decentralized Stochastic Optimization
• Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs
• Revealing and Protecting Labels in Distributed Training
• Large-Scale Deep Learning Optimizations: A Comprehensive Survey
• DeepReduce: A Sparse-tensor Communication Framework for Distributed Deep Learning
• Pufferfish: Communication-efficient Models At No Extra Cost
• Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
• Decentralized Composite Optimization with Compression
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks
• Federated Functional Gradient Boosting
• Compressing gradients by exploiting temporal correlation in momentum-SGD
• On Faster Convergence of Scaled Sign Gradient Descent
• Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization
• QuPeL: Quantized Personalization with Applications to Federated Learning
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization
• Compressed Communication for Distributed Training: Adaptive Methods and System
• CADA: Communication-Adaptive Distributed Adam
• CD-SGD: Distributed Stochastic Gradient Descent with Compression and Delay Compensation
• Rate distortion comparison of a few gradient quantizers