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

• From Distributed Machine Learning to Federated Learning: A Survey
• Don't Use Large Mini-Batches, Use Local SGD
• A Field Guide to Federated Optimization
• PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• Variance Reduced Local SGD with Lower Communication Complexity
• Dynamic Model Pruning with Feedback
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum
• Understanding Top-k Sparsification in Distributed Deep Learning
• Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback
• Communication optimization strategies for distributed deep neural network training: A survey
• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• FedScale: Benchmarking Model and System Performance of Federated Learning at Scale
• Privacy-preserving Incremental ADMM for Decentralized Consensus Optimization
• Hyper-Sphere Quantization: Communication-Efficient SGD for Federated Learning
• Decentralized Deep Learning with Arbitrary Communication Compression
• A Double Residual Compression Algorithm for Efficient Distributed Learning
• Distributed Learning in Wireless Networks: Recent Progress and Future Challenges
• Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
• Towards Scalable Distributed Training of Deep Learning on Public Cloud Clusters
• Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks
• Communication-Efficient Robust Federated Learning with Noisy Labels
• On the Utility of Gradient Compression in Distributed Training Systems
• Rethinking gradient sparsification as total error minimization
• Adaptive Gradient Descent without Descent
• MARINA: Faster Non-Convex Distributed Learning with Compression
• Layer-wise Adaptive Gradient Sparsification for Distributed Deep Learning with Convergence Guarantees
• Large Scale Private Learning via Low-rank Reparametrization
• Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing
• SPARQ-SGD: Event-Triggered and Compressed Communication in Decentralized Stochastic Optimization
• Linear Convergent Decentralized Optimization with Compression
• FedNL: Making Newton-Type Methods Applicable to Federated Learning
• Efficient Sparse Secure Aggregation for Federated Learning
• Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs
• DRIVE: One-bit Distributed Mean Estimation
• Stochastic Sign Descent Methods: New Algorithms and Better Theory
• On Communication Compression for Distributed Optimization on Heterogeneous Data
• Large-Scale Deep Learning Optimizations: A Comprehensive Survey
• Revealing and Protecting Labels in Distributed Training
• PowerGossip: Practical Low-Rank Communication Compression in Decentralized Deep Learning
• Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descent
• DeepReduce: A Sparse-tensor Communication Framework for Distributed Deep Learning
• Communication-Efficient Distributed SGD with Error-Feedback, Revisited
• Pufferfish: Communication-efficient Models At No Extra Cost
• Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation
• QuPeD: Quantized Personalization via Distillation with Applications to Federated Learning
• NUQSGD: Provably Communication-efficient Data-parallel SGD via Nonuniform Quantization
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
• Decentralized Composite Optimization with Compression
• New Bounds For Distributed Mean Estimation and Variance Reduction
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks
• Compressing gradients by exploiting temporal correlation in momentum-SGD
• Sign Bit is Enough: A Learning Synchronization Framework for Multi-hop All-reduce with Ultimate Compression
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Federated Functional Gradient Boosting
• Step-Ahead Error Feedback for Distributed Training with Compressed Gradient
• 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
• On Faster Convergence of Scaled Sign Gradient Descent
• Quantized Adam with Error Feedback
• On The Convergence of Euler Discretization of Finite-Time Convergent Gradient Flows
• Compressed Communication for Distributed Training: Adaptive Methods and System
• CD-SGD: Distributed Stochastic Gradient Descent with Compression and Delay Compensation
• Communication-Compressed Adaptive Gradient Method for Distributed Nonconvex Optimization
• CADA: Communication-Adaptive Distributed Adam
• Towards Tight Communication Lower Bounds for Distributed Optimisation
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays
• Communication Efficient Generalized Tensor Factorization for Decentralized Healthcare Networks
• Communication-Efficient Federated Linear and Deep Generalized Canonical Correlation Analysis
• HPSGD: Hierarchical Parallel SGD With Stale Gradients Featuring
• Rate distortion comparison of a few gradient quantizers