Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations
Open accessThe DOI matches its Crossref record; 51 of the 56 references it cites were found in a registry or an index.
Abstract
Communication bottleneck has been identified as a significant issue in distributed optimization of large-scale learning models. Recently, several approaches to mitigate this problem have been proposed, including different forms of gradient compression or computing local models and mixing them iteratively. In this paper, we propose Qsparse-local-SGD algorithm, which combines aggressive sparsification with quantization and local computation along with error compensation, by keeping track of the difference between the true and compressed gradients. We propose both synchronous and asynchronous implementations of Qsparse-local-SGD. We analyze convergence for Qsparse-local-SGD in the distributed setting for smooth non-convex and convex objective functions. We demonstrate that Qsparse-local-SGD converges at the same rate as vanilla distributed SGD for many important classes of sparsifiers and quantizers. We use Qsparse-local-SGD to train ResNet-50 on ImageNet and show that it results in significant savings over the state-of-the-art, in the number of bits transmitted to reach target accuracy.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“This 'privacy amplification via iteration' setting has been recently studied by Feldman et al. [185] for convex optimization problems.”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [185]
Citations
Cites
Deep Residual Learning for Image Recognition
He, K., Zhang, X., Ren, S., & Sun, J. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.90 · Cited by 235,474
Adam: A Method for Stochastic Optimization
Kingma, D. P., & Ba, J. (2014) · arXiv · doi:10.48550/arxiv.1412.6980 · Cited by 98,946 · cited 1×
“This further inspired optimizers, such as RMSPROP [37], ADAM [38], which incorporate appropriate adaptive scaling with momentum acceleration and have demonstrated empirical superiority in non-convex applications.”
MethodBERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
Devlin, J., Chang, M.-W., Lee, K., & Toutanova, K. (2018) · arXiv · doi:10.48550/arxiv.1810.04805 · Cited by 73,173 · cited 1×
“For example, consider training the BERT architecture for language models [9] which has about 340 million parameters, implying that each full precision exchange between workers is over 1.”
BackgroundGradient-based learning applied to document recognition
Lecun, Y., Bottou, L., Bengio, Y., & Haffner, P. (1998) · Proceedings of the IEEE · doi:10.1109/5.726791 · Cited by 58,805 · cited 4×
“The experiments in Figure 2a-2c are in a synchronous distributed setting with 15 worker nodes, each processing a mini-batch size of 8 samples per iteration using the MNIST [LBBH98] hand-written digits data set.”
MethodInfluentialBERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
Devlin, J., Chang, M.-W., Lee, K., & Toutanova, K. (2019) · Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers) · doi:10.18653/v1/n19-1423 · Cited by 54,325 · cited 1×
“For example, consider training the BERT architecture for language models [9] which has about 340 million parameters, implying that each full precision exchange between workers is over 1.”
BackgroundCommunication-Efficient Learning of Deep Networks from Decentralized Data
McMahan, H. B., Moore, E., Ramage, D., Hampson, S., & Arcas, B. A. Y. (2016) · arXiv · doi:10.48550/arxiv.1602.05629 · Cited by 14,215
TensorFlow: A system for large-scale machine learning
Abadi, M., Barham, P., Chen, J., Chen, Z., Davis, A., Dean, J., Devin, M., Ghemawat, S., Irving, G., Isard, M., et al. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.08695 · Cited by 11,822
A Stochastic Approximation Method
Robbins, H., & Monro, S. (1951) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729586 · Cited by 9,643 · cited 1×
“STOCHASTIC Gradient Descent (SGD) [2] and its many variants have become the workhorse for modern largescale optimization as applied to machine learning [3], [4].”
BackgroundLarge-Scale Machine Learning with Stochastic Gradient Descent
Bottou, L. (2010) · Proceedings of COMPSTAT'2010 · doi:10.1007/978-3-7908-2604-3_16 · Cited by 5,795 · cited 1×
“STOCHASTIC Gradient Descent (SGD) [2] and its many variants have become the workhorse for modern largescale optimization as applied to machine learning [3], [4].”
BackgroundA direct adaptive method for faster backpropagation learning: the RPROP algorithm
Riedmiller, M., & Braun, H. (2002) · IEEE International Conference on Neural Networks · doi:10.1109/icnn.1993.298623 · Cited by 3,917 · cited 1×
“Such methods drew interest since RPROP [36], which only used the temporal behavior of the sign of the gradient.”
MethodRobust Stochastic Approximation Approach to Stochastic Programming
Nemirovski, A., Juditsky, A., Lan, G., & Shapiro, A. (2009) · SIAM Journal on Optimization · doi:10.1137/070704277 · Cited by 1,945 · cited 1×
“This is a standard assumption in [SSS07, NJLS09, RRWN11, HK14, RSS12, SCJ18, Sti19, YYZ18, KSJ19, AHJ + 18].”
Horovod: fast and easy distributed deep learning in TensorFlow
Sergeev, A., & Del Balso, M. (2018) · arXiv · doi:10.48550/arxiv.1802.05799 · Cited by 1,620 · cited 1×
“We build our compression scheme into the Horovod framework [SB18].”
MethodHogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
Niu, F., Recht, B., Re, C., & Wright, S. J. (2011) · arXiv · doi:10.48550/arxiv.1106.5730 · Cited by 1,211
Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
Lin, Y., Han, S., Mao, H., Wang, Y., & Dally, W. J. (2017) · arXiv · doi:10.48550/arxiv.1712.01887 · Cited by 1,134 · cited 3×
“, where nodes locally select Topk values of the gradient in absolute value and transmit these at full precision [5], [14], [16]–[19], while maintaining errors in local nodes for later compensation.”
BackgroundMethodPegasos: Primal Estimated sub-GrAdient SOlver for SVM
Shalev-Shwartz, S., Singer, Y., & Srebro, N. (2007) · Proceedings of the 24th international conference on Machine learning · doi:10.1145/1273496.1273598 · Cited by 973 · cited 1×
“tion in [5], [18], [20], [23], [33], [39]–[43].”
QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
Alistarh, D., Grubic, D., Li, J., Tomioka, R., & Vojnović, M. (2016) · London School of Economics and Political Science Research Online (London School of Economics and Political Science) · doi:10.48550/arxiv.1610.02132 · Cited by 859
TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
Wen, W., Xu, C., Yan, F., Wu, C., Wang, Y., Chen, Y., & Li, H. H. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.07878 · Cited by 622 · cited 7×
“Theoretically justified gradient compression using unbiased stochastic quantizers has been proposed and analyzed in [6], [8], [13], [15].”
BackgroundMethodInfluentialSparse Communication for Distributed Gradient Descent
Aji, A. F., & Heafield, K. (2017) · Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing · doi:10.18653/v1/d17-1045 · Cited by 585 · cited 2×
“, k < 1%, has been proposed [2, 4, 20, 30, 32], combined with error compensation to ensure that all co-ordinates do get eventually updated as needed.”
BackgroundsignSGD: Compressed Optimisation for Non-Convex Problems
Bernstein, J., Wang, Y.-X., Azizzadenesheli, K., & Anandkumar, A. (2018) · arXiv · doi:10.48550/arxiv.1802.04434 · Cited by 541
The Convergence of Sparsified Gradient MethodsPreprint
Alistarh, D., Hoefler, T., Johansson, M., Khirirat, S., Konstantinov, N., & Renggli, C. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1809.10505 · Cited by 525 · cited 9×
“The analysis for the centralized Topk (among other sparsifiers) was considered in [18], and [5] analyzed a distributed version with the assumption of closeness of the aggregated Topk gradients to the centralized Topk case, see Assumption 1 in [5].”
BackgroundMethodResultInfluentialScalable distributed DNN training using commodity GPU cloud computing
Strom, N. (2015) · Interspeech 2015 · doi:10.21437/interspeech.2015-354 · Cited by 521 · cited 4×
“, where nodes locally select Topk values of the gradient in absolute value and transmit these at full precision [5], [14], [16]–[19], while maintaining errors in local nodes for later compensation.”
BackgroundMethodInfluentialStich, S. U., Cordonnier, J.-B., & Jaggi, M. (2018) · arXiv · doi:10.48550/arxiv.1809.07599 · Cited by 508 · cited 10×
“The analysis for the centralized Topk (among other sparsifiers) was considered in [18], and [5] analyzed a distributed version with the assumption of closeness of the aggregated Topk gradients to the centralized Topk case, see Assumption 1 in [5].”
BackgroundMethodResultInfluentialYu, H., Yang, S., & Zhu, S. (2019) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v33i01.33015693 · Cited by 497 · cited 7×
“Figure 1(i)–1(l) demonstrate the performance of our scheme in comparison with EF-SIGNSGD [32], TopK-SGD [5], [18] and local SGD [20], [23].”
BackgroundResultInfluentialMaking Gradient Descent Optimal for Strongly Convex Stochastic Optimization
Rakhlin, A., Shamir, O., & Sridharan, K. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1109.5647 · Cited by 492 · cited 1×
“tion in [5], [18], [20], [23], [33], [39]–[43].”
Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning
Bach, F., & Moulines, É. (2011) · Cited by 488
Seide, F., Fu, H., Droppo, J., Li, G., & Yu, D. (2014) · Interspeech 2014 · doi:10.21437/interspeech.2014-274 · Cited by 443 · cited 1×
“ent methods has decades rich history [26] and its recent use in training deep neural networks [16], [27] has re-ignited interest.”
BackgroundBeyond the regret minimization barrier
Hazan, E., & Kale, S. (2014) · Journal of Machine Learning Research · doi:10.5555/2627435.2670328 · Cited by 334 · cited 1×
“This is a standard assumption in [SSS07, NJLS09, RRWN11, HK14, RSS12, SCJ18, Sti19, YYZ18, KSJ19, AHJ + 18].”
Communication-efficient algorithms for statistical optimization
Zhang, Y., Duchi, J. C., & Wainwright, M. J. (2012) · 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2012.6426691 · Cited by 283
Zhang, Y., Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013) · arXiv (Cornell University) · Cited by 252
Yu, H., Jin, R., & Yang, S. (2019) · arXiv · doi:10.48550/arxiv.1905.03817 · Cited by 244 · cited 1×
“Our numerics also incorporate momentum acceleration, whose analysis is a topic for future research, for example incorporating ideas from [42].”
MethodCommunication Compression for Decentralized Training
Tang, H., Gan, S., Zhang, C., Zhang, T., & Liu, J. (2018) · arXiv · doi:10.48550/arxiv.1803.06443 · Cited by 206
SGD and Hogwild! Convergence Without the Bounded Gradients AssumptionPreprint
Nguyen, L. M., Nguyen, P. H., van Dijk, M., Richtárik, P., Scheinberg, K., & Takáč, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.03801 · Cited by 198 · cited 1×
“of the uniform boundedness of the gradient allowing arbitrarily different gradients of local functions in heterogenous settings as done for SGD in [25], [44] is”
BackgroundGradient Sparsification for Communication-Efficient Distributed Optimization
Wangni, J., Wang, J., Ji, L. H., & Zhang, T. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1710.09854 · Cited by 198 · cited 1×
“Though methods in [28], [29] use induced sparsity in the quantized gradients, explicitly sparsifying the gradients more aggressively by retaining Topk components, e.”
MethodCommunication-efficient algorithms for statistical optimization
(2013) · Journal of Machine Learning Research · doi:10.5555/2567709.2567769 · Cited by 195 · cited 1×
“Skipping communication rounds , whereby nodes average their models after locally updating their models for several steps [YYZ18,Cop15,ZDW13,Sti19,CH16,WJ18].”
MethodError Compensated Quantized SGD and its Applications to Large-scale Distributed OptimizationPreprint
Wu, J., Huang, W., Huang, J., & Zhang, T. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.08054 · Cited by 193 · cited 2×
“Reference [14] analyzed error compensation for QSGD, without Topk sparsification while focusing on quadratic functions.”
BackgroundMethodLocal SGD Converges Fast and Communicates Little
Stich, S. U. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.09767 · Cited by 191
ATOMO: Communication-efficient Learning via Atomic Sparsification
Wang, H., Sievert, S., Charles, Z., Liu, S., Wright, S. J., & Papailiopoulos, D. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.04090 · Cited by 189 · cited 1×
“Though methods in [28], [29] use induced sparsity in the quantized gradients, explicitly sparsifying the gradients more aggressively by retaining Topk components, e.”
MethodGradient Sparsification for Communication-Efficient Distributed Optimization
Wangni, J., Wang, J., Liu, J., & Zhang, T. (2018) · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · Cited by 166
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
Koloskova, A., Stich, S. U., & Jaggi, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.00340 · Cited by 163 · cited 3×
“Another recent work in [33] studies the decentralized case with sparsification for strongly convex functions.”
BackgroundMethodPerturbed Iterate Analysis for Asynchronous Stochastic Optimization
Mania, H., Pan, X., Papailiopoulos, D., Recht, B., Ramchandran, K., & Jordan, M. I. (2017) · SIAM Journal on Optimization · doi:10.1137/16m1057000 · Cited by 154 · cited 2×
“We prove convergence for the distributed sparsification and error compensation algorithm, without the assumption of [5], by using the perturbed iterate methods [18], [31].”
MethodChen, K., & Huo, Q. (2016) · 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) · doi:10.1109/icassp.2016.7472805 · Cited by 147
Wang, J., & Joshi, G. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1808.07576 · Cited by 146 · cited 2×
“Relaxation of the uniform boundedness of the gradient allowing arbitrarily different gradients of local functions in heterogenous settings as done for SGD in [24, 37] is left as future work.”
BackgroundError Feedback Fixes SignSGD and other Gradient Compression Schemes
Karimireddy, S. P., Rebjock, Q., Stich, S. U., & Jaggi, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.09847 · Cited by 137
Distributed Mean Estimation with Limited Communication
Suresh, A. T., Yu, F. X., Kumar, S., & McMahan, H. B. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.00429 · Cited by 135 · cited 7×
“Theoretically justified gradient compression using unbiased stochastic quantizers has been proposed and analyzed in [6], [8], [13], [15].”
BackgroundMethodInfluentialOn the design of gradient algorithms for digitally implemented adaptive filters
Gitlin, R. D., Mazo, J. E., & Taylor, M. (1973) · IEEE Transactions on Circuit Theory · doi:10.1109/tct.1973.1083627 · Cited by 132 · cited 1×
“The use of quantization for communication efficient gradient methods has decades rich history [GMT73] and its recent use in training deep neural networks [SFD + 14, Str15] has re-ignited interest.”
MethodTraining Quantized Nets: A Deeper Understanding
Li, H., De, S., Xu, Z., Studer, C., Samet, H., & Goldstein, T. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.02379 · Cited by 130 · cited 1×
“Theoretically justified gradient compression using unbiased stochastic quantizers has been proposed and analyzed in [6], [8], [13], [15].”
BackgroundDecentralized Consensus Optimization With Asynchrony and Delays
Wu, T., Yuan, K., Ling, Q., Yin, W., & Sayed, A. H. (2018) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2017.2695121 · Cited by 99
Parallel SGD: When does averaging help?
Zhang, J., De, C., Mitliagkas, I., & Ré, C. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1606.07365 · Cited by 73
Top-k Multiclass SVMPreprint
Lapin, M., Hein, M., & Schiele, B. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.06683 · Cited by 48
Stochastic, Distributed and Federated Optimization for Machine LearningPreprint
Konečný, J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1707.01155 · Cited by 44
Coppola, G. (2015) · ERA · Cited by 23
Research works printed but not linked: 2
- tieleman, 2012, Lecture 6.5-RMSprop: Divide the gradient by a running average of its recent magnitude, COURSERA Neural Netw Mach Learn, 4, 26
- basu, 2019, QSparse-local-SGD: Distributed SGD with quantization, sparsification and local computations, Proc Neural Inf Process Syst, 14668
Cited by
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
Wang, J., Liu, Q., Liang, H., Joshi, G., & Poor, H. V. (2020) · arXiv · doi:10.48550/arxiv.2007.07481 · Cited by 927
Decentralized federated learning: Fundamentals, state of the art, frameworks, trends, and challenges
Martínez Beltrán, E. T., Pérez, M. Q., Sánchez, P. M. S., Bernal, S. L., Bovet, G., Pérez, M. G., Pérez, G. M., & Celdrán, A. H. (2023) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2023.3315746 · Cited by 625
“Many DFL studies are based on Stochastic Gradient Descent (SGD), which can be used to train NNs [110], [113].”
BackgroundMethodInfluentialDistributed Artificial Intelligence Empowered by End-Edge-Cloud Computing: A Survey
Duan, S., Wang, D., Ren, J., Lyu, F., Zhang, Y., Wu, H., & Shen, X. (2023) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2022.3218527 · Cited by 408
Adaptive Gradient Sparsification for Efficient Federated Learning: An Online Learning Approach
Han, P., Wang, S., & Leung, K. K. (2020) · 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs47774.2020.00026 · Cited by 181
“In periodic averaging GS [8], [20], [21], a random subset of gradient elements are transmitted and aggregated in each round, so that after a finite number of rounds, all elements of the full gradient vector are aggregated at least once.”
Background
Metadata
- Authors
- Basu, D., Data, D., Karakus, C., & Diggavi, S. N.
- Affiliations
- Adobe Systems (United States) (US)
- University of California, Los Angeles (US)
- Amazon (United States) (US)
- Venue
- IEEE Journal on Selected Areas in Information Theory
- Published
- 2020-05
- Volume
- 1
- Issue
- 1
- Pages
- 217-226
- ISSN
- 2641-8770 (ISSN-L)
- OpenAlex
- W2948092338
- Cited by
- 256
- References
- 56
- Citations by year
- 2026: 10 · 2025: 26 · 2024: 67 · 2023: 67 · 2022: 36 · 2021: 35 · 2020: 15
- FWCI
- 15.03
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- IEEE Journal on Selected Areas in Information Theory (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- neural information processing systems
- Funders
- NSF (1514531)
- UC-NL (LFR-18-548554)
- Army Research Laboratory under Cooperative Agreement (W911NF-17-2-0196)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Keywords
- gradient quantization, gradient sparsification, local computation, error compensation, communication efficiency, asynchronous SGD, convergence analysis, non-convex optimization, convex optimization, ImageNet
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.