Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization

By Jiaxiang Wu, Weidong Huang, Junzhou Huang, Tong Zhang. 2018

255 citations recorded by the source corpus.

Large-scale distributed optimization is of great importance in various applications. For data-parallel based distributed learning, the inter-node gradient communication often becomes the performance bottleneck. In this paper, we propose the error compensated quantized stochastic gradient descent algorithm to improve the training efficiency. Local gradients are quantized to reduce the communication overhead, and accumulated quantization error is utilized to speed up the convergence. Furthermore, we present theoretical analysis on the convergence behaviour, and demonstrate its advantage over competitors. Extensive experiments indicate that our algorithm can compress gradients by a factor of up to two magnitudes without performance degradation.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Computational Mechanics

In Efficiency & Compression

In Optimization & Training

Citations in the corpus

$\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, background): “Wu et al. [2018] further study an Error-Compensated SGD for quadratic optimization via adding two hyperparameters to compensate the error, but fail to theoretically verify the advantage of using error compensation.”
Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations (2019, methodology): “Reference [14] analyzed error compensation for QSGD, without Topk sparsification while focusing on quadratic functions.”
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, methodology): “Recently, Wu et al. (2018) studied an Error-Compensated SGD for quadratic optimization via adding two hyperparameters to compensate the error, but does not successfully prove the advantage of using error compensation theoretically.”
Error Feedback Fixes SignSGD and other Gradient Compression Schemes (2019, background): “[Wu et al., 2018] analyze unbiased compressors with a form of error-feedback involving two additional hyper-parameters and restricted to quadtratic functions.”
Distributed Learning over Unreliable Networks (2018, background): “To save the communication cost, some sparse based distributed learning algorithms is proposed (Shen et al., 2018b; Wu et al., 2018; Wen et al., 2017; McMahan et al., 2016; Wang et al., 2016).”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, methodology): “Mishchenko et al. (2018) consider the stochastic setting as in (1) and show convergence of SGD with unbiased quantization to a neighborhood of a stationary point for non-convex and strongly convex functions; the analysis in (Wu et al., 2018) only applies to quadratic functions.”
Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback (2019, methodology): “Error-compensated quantized SGD (ECQ-SGD) was proposed in [25], wherein a similar stochastic quantization function used in QSGD is employed, and an error bound is obtained for quadratic loss functions.”
Federated Learning in Edge Computing: A Systematic Survey (2022, methodology): “To compensate for errors in model fitting, one can use the quantization described in [170].”
3LC: Lightweight and Effective Traffic Compression for Distributed Machine Learning (2018, methodology): “the most common non-convex optimization problem used in recent work (Watcharapichat et al., 2016; Alistarh et al., 2017; Hardy et al., 2017; Hsieh et al., 2017; Wen et al., 2017; Zhang et al., 2017; Lin et al., 2018; Wu et al., 2018).”
Communication-Efficient and Distributed Learning Over Wireless Networks: Principles and Applications (2020, background): “There are many other variants of gradient quantized distributed learning algorithms, including error compensation [94], variance-reduced quantization [95], and ternary quantization [96].”
High-Dimensional Stochastic Gradient Quantization for Communication-Efficient Edge Learning (2019, methodology): “Building on QSGD, the effect of the quantization error can be further alleviated using an error-compensation scheme presented in [8].”
Stochastic Controlled Averaging for Federated Learning with Communication Compression (2023, background): “Error feedback has proven particularly effective in addressing biased compressors (Stich et al., 2018; Karimireddy et al., 2019), and it has inspired numerous subsequent distributed approaches ( e.g. , Wu et al., 2018; Alistarh et al., 2018; Li et al., 2022b).”
Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks (2019, background): “Regarding this issue, the authors of [3, 5, 6, 15, 19, 28–30] considered quantization of real-valued gradient vectors.”
Artemis: tight convergence guarantees for bidirectional compression in Federated Learning (2020, methodology): “However, most of them [16, 25, 3, 1, 20, 35] focus on compressing the message sent from the workers to the central node.”
High-Dimensional Stochastic Gradient Quantization for Communication-Efficient Edge Learning (2020, methodology): “Building on QSGD, the effect of the quantization error can be further alleviated using an error-compensation scheme presented in [11].”
Federated Learning with Compression: Unified Analysis and Sharp Guarantees (2020, methodology): “The current methodology towards reducing the size of messages is to communicate compressed local gradients or models to the central server by utilizing a quantization operator [3, 6, 48, 58, 59, 63, 65], sparsification schema [4,39,56,65], or composition of both [5].”
Gradient Compression Supercharged High-Performance Data Parallel DNN Training (2021, background): “Gradient compression algorithms have a great potential to relieve or even eliminate the above tension, since they can substantially reduce the data volume being synchronized with a negligible impact on training accuracy and convergence [4, 37, 67, 74, 76].”