Error Feedback Fixes SignSGD and other Gradient Compression Schemes

By Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U. Stich, Martin Jaggi. 2019

655 citations recorded by the source corpus.

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{this https URL}.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Efficiency & Compression, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Efficiency & Compression

In Optimization & Training

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “Consequently, a wider set of ideas related to error-correction such as [272, 346, 396, 380, 228, 371] are relevant in this setting, many of which could address both (a) and (b).”
Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, methodology): “…communication overhead of distributed SGD, such as quantization (Seide et al., 2014; Strom, 2015; Wen et al., 2017; Alistarh et al., 2016; Bernstein et al., 2018; Karimireddy et al., 2019; Zheng et al., 2019) and sparsification (Aji and Heafield, 2017; Stich et al., 2018; Jiang and Agrawal, 2018).”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, background): “That includes the design of more eﬃcient communication strategies (Konečn`y et al., 2016b,a; Suresh et al., 2017; Stich et al., 2018; Karimireddy et al., 2019; Basu et al., 2019), the study of lower bounds for parallel stochastic optimization with a dependency graph (Woodworth et al., 2018b),…”
SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, background): “Note that various approaches to gradient compression have been proposed to reduce the communication overhead for ALLREDUCE and decentralized learning methods (Alistarh et al., 2007; Wen et al., 2007; Bernstein et al., 2019; Karimireddy et al., 2019; Koloskova et al., 2019b; Vogels et al., 2019).”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, background): “Schemes with error correction work often best in practice and give the best theoretical gurantees (Lin et al., 2018b; Alistarh et al., 2018; Stich et al., 2018; Karimireddy et al., 2019).”
Natural Compression for Distributed Deep Learning (2019, background): “several state-of-the-art compressors (Karimireddy et al., 2019; Zheng et al., 2019; Bernstein et al., 2018; Vogels et al., 2019) by setting K so that the transmission amount are the same.”
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, background): “Recent work (Karimireddy et al., 2019) considers a non-convex loss non-parallel function, and proves that the error-compensate strategy could greatly reduce the overhead caused by compression.”
PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization (2019, methodology): “Secondly, EF-SGD improves convergence and obtains better test accuracy (Karimireddy et al., 2019).”
Don't Use Large Mini-Batches, Use Local SGD (2018, methodology): “We extend the single-worker EF-signSGD algorithm of Karim-ireddy et al. (2019) (i.e. their Algorithm 1) to multiple-workers case by empirically investigating different algorithmic design choices.”
Dynamic Model Pruning with Feedback (2020, methodology): “Lastly, we give the proof of Theorem 4.2, following Karimireddy et al. (2019).”
Variance Reduced Local SGD with Lower Communication Complexity (2019, methodology): “…methods are proposed, such as lossy compression methods [Alistarh et al., 2017, Aji and Heaﬁeld, 2017, Bernstein et al., 2019, Lin et al., 2018b, Karimireddy et al., 2019, Tang et al., 2019], which use inexact approximations or partial data to represent the gradients, and methods [Stich, 2019,…”
FedBoost: Communication-Efficient Algorithms for Federated Learning (2020, neutral): “, 2018) and in other distributed settings (Stich et al., 2018; Karimireddy et al., 2019; Basu et al., 2019).”
From distributed machine learning to federated learning: a survey (2021, background): “Sketched updates are proposed for gradient compression to accelerate the data transfer during the distributed training within a single data center [75,76,82,159].”
CSER: Communication-efficient SGD with Error Reset (2020, methodology): “EF-SGD However, different from EF-SGD We name this special case “communication-efﬁcient SGD with error assimilation” (CSEA).”