rTop-k: A Statistical Estimation Approach to Distributed SGD
The DOI matches its Crossref record; 51 of the 57 references it cites were found in a registry or an index.
Abstract
The large communication cost for exchanging gradients between different nodes significantly limits the scalability of distributed training for large-scale learning models. Motivated by this observation, there has been significant recent interest in techniques that reduce the communication cost of distributed Stochastic Gradient Descent (SGD), with gradient sparsification techniques such as top-k and random-k shown to be particularly effective. The same observation has also motivated a separate line of work in distributed statistical estimation theory focusing on the impact of communication constraints on the estimation efficiency of different statistical models. The primary goal of this paper is to connect these two research lines and demonstrate how statistical estimation models and their analysis can lead to new insights in the design of communication-efficient training techniques. We propose a simple statistical estimation model for the stochastic gradients which captures the sparsity and skewness of their distribution. The statistically optimal communication scheme arising from the analysis of this model leads to a new sparsification technique for SGD, which concatenates random-k and top-k, considered separately in the prior literature. We show through extensive experiments on both image and language domains with CIFAR-10, ImageNet, and Penn Treebank datasets that the concatenated application of these two sparsification methods consistently and significantly outperforms either method applied alone.
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
“Fallah et al. [181] developed a new algorithm called Personalized FedAvg by connecting MAML instead of Reptile to federated learning.”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [181]
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 · cited 4×
“In our first two experiments, we train ResNet-18 on CIFAR-10 in both distributed and federated settings and show the results in Figure 2 and Figure 3 respectively.”
MethodInfluentialImageNet: A large-scale hierarchical image database
Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., & Fei-Fei, L. (2009) · 2009 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2009.5206848 · Cited by 65,333 · cited 7×
“However, in extensive experiments on both image and language domains with CIFAR-10, ImageNet, and Penn Treebank datasets we observe that rTop-k significantly outperforms either top-k or random-k applied separately.”
MethodInfluentialLearning Multiple Layers of Features from Tiny Images
Krizhevsky, A. (2024) · doi:10.57702/zp44cu3g · Cited by 23,395
Communication-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 · cited 1×
“, one iteration over the local data adapting the federated setting in [7], [8]).”
BackgroundAdvances 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
Building a Large Annotated Corpus of English: The Penn Treebank
Marcus, M. (1993) · doi:10.21236/ada273556 · Cited by 7,405
Large-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×
“SGD methods [1], [3]–[15], as well as other fundamental contributions to distributed first-order [16]–[20] and secondorder [21]–[25] optimization procedures.”
Recurrent neural network based language model
Mikolov, T., Karafiát, M., Burget, L., Černocký, J., & Khudanpur, S. (2010) · Interspeech 2010 · doi:10.21437/interspeech.2010-343 · Cited by 5,390 · cited 1×
“We use the same train/validation/test set split and vocabulary as [48].”
MethodFederated Learning: Strategies for Improving Communication Efficiency
Konečný, J., McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. T., & Bacon, D. (2016) · arXiv · doi:10.48550/arxiv.1610.05492 · Cited by 3,766 · cited 1×
“We compare our results with the baseline setting where there is no compression, the setting proposed in [1], which uses the gradient top-k selection method, and the random-k sparsification strategy where the gradients to be communicated by each node are chosen uniformly at random [9].”
ResultIntroduction to the non-asymptotic analysis of random matrices
Vershynin, R. (2012) · Compressed Sensing · doi:10.1017/cbo9780511794308.006 · Cited by 2,150
Recurrent Neural Network Regularization
Zaremba, W., Sutskever, I., & Vinyals, O. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1409.2329 · Cited by 2,123 · cited 1×
“We use vanilla SGD with gradient May 22, 2020 DRAFT batch size) as in [34].”
MethodDistributed asynchronous deterministic and stochastic gradient optimization algorithms
Tsitsiklis, J., Bertsekas, D., & Athans, M. (1986) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1986.1104412 · Cited by 1,967
Robust 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
Federated Optimization: Distributed Machine Learning for On-Device Intelligence
Konečný, J., McMahan, H. B., Ramage, D., & Richtárik, P. (2016) · arXiv · doi:10.48550/arxiv.1610.02527 · Cited by 1,563 · cited 1×
“, one iteration over the local data adapting the federated setting in [7], [8]).”
BackgroundPegasos: primal estimated sub-gradient solver for SVM
Shalev-Shwartz, S., Singer, Y., Srebro, N., & Cotter, A. (2011) · Mathematical Programming · doi:10.1007/s10107-010-0420-4 · Cited by 1,477
Hogwild: 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 8×
“there is no compression, the setting proposed in [1], which uses the gradient top-k selection method, and the random-k sparsification strategy where the gradients to be communi-”
BackgroundMethodInfluentialQSGD: 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
Communication Efficient Distributed Machine Learning with the Parameter Server
Li, M., Andersen, D. G., Smola, A. J., & Yu, K. (2014) · neural information processing systems · Cited by 715
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
Using the Output Embedding to Improve Language Models
Press, O., & Wolf, L. (2017) · Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers · doi:10.18653/v1/e17-2025 · Cited by 596
Sparse 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 1×
“Definition 1 (Top-r Sparsification [1], [10], [26], [27]): For a parameter 1 ≤ r ≤ d, the operator topr : Rd → Rd is defined for ω ∈ Rd as ( topr(ω) ) i := { (ω)i, if i ∈ {π(1), .”
signSGD: 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 1×
“Assumption (ii) is a standard assumption in [26], [27], [38]–[41].”
BackgroundScalable distributed DNN training using commodity GPU cloud computing
Strom, N. (2015) · Interspeech 2015 · doi:10.21437/interspeech.2015-354 · Cited by 521
Stich, S. U., Cordonnier, J.-B., & Jaggi, M. (2018) · arXiv · doi:10.48550/arxiv.1809.07599 · Cited by 508
Seide, F., Fu, H., Droppo, J., Li, G., & Yu, D. (2014) · Interspeech 2014 · doi:10.21437/interspeech.2014-274 · Cited by 443
Communication-Efficient Distributed Optimization using an Approximate Newton-type Method
Shamir, O., Srebro, N., & Zhang, T. (2013) · arXiv · doi:10.48550/arxiv.1312.7853 · Cited by 424 · cited 1×
“SGD methods [1], [3]–[15], as well as other fundamental contributions to distributed first-order [16]–[20] and secondorder [21]–[25] optimization procedures.”
MethodTying Word Vectors and Word Classifiers: A Loss Framework for Language Modeling
Inan, H., Khosravi, K., & Socher, R. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.01462 · Cited by 288 · cited 1×
“architecture with 1500 hidden units per layer [46] and tie the input and the output embeddings [47].”
BackgroundSelf-citationQsparse-local-SGD: Distributed SGD with quantization, sparsification, and local computations
Basu, D., Data, D., Karakus, C., & Diggavi, S. N. (2020) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2020.2985917 · Cited by 256
Zhang, Y., Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013) · arXiv (Cornell University) · Cited by 252
Gradient 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
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
Gradient 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
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
Wang, J., Sahu, A. K., Yang, Z., Joshi, G., & Kar, S. (2019) · 2019 Sixth Indian Control Conference (ICC) · doi:10.1109/icc47138.2019.9123209 · Cited by 149 · cited 1×
“SGD methods [1], [3]–[15], as well as other fundamental contributions to distributed first-order [16]–[20] and secondorder [21]–[25] optimization procedures.”
Braverman, M., Garg, A., Ma, T., Nguyen, H. L., & Woodruff, D. P. (2016) · Proceedings of the forty-eighth annual ACM symposium on Theory of Computing · doi:10.1145/2897518.2897582 · Cited by 131 · cited 2×
“A sparse variation of the Gaussian mean estimation problem has been studied in [29], [30], [32], where = {θ ∈”
BackgroundvqSGD: Vector Quantized Stochastic Gradient Descent
Gandikota, V., Kane, D., Maity, R. K., & Mazumdar, A. (2019) · arXiv · doi:10.48550/arxiv.1911.07971 · Cited by 80
Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints
Han, Y., Özgür, A., & Weissman, T. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3108952 · Cited by 73
Stich, S. U., & Karimireddy, S. P. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.05350 · Cited by 68 · cited 3×
“Together with some form of error compensation, these methods have been shown to converge as fast as vanilla SGD in [26], [27], [37].”
BackgroundMethodInfluentialDistributed Second-Order Optimization using Kronecker-Factored Approximations
Ba, J. L., Grosse, R., & Martens, J. (2017) · International Conference on Learning Representations · Cited by 66
vqSGD: Vector Quantized Stochastic Gradient Descent
Gandikota, V., Kane, D., Maity, R. K., & Mazumdar, A. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3161620 · Cited by 62 · cited 2×
“Such convergence guarantees have been proven in [6], [15], [26], [27] for various communication efficient training techniques.”
BackgroundDINGO: Distributed Newton-Type Method for Gradient-Norm OptimizationPreprint
Crane, R., & Roosta, F. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.05134 · Cited by 49
Information-Theoretic Lower Bounds on Bayes Risk in Decentralized Estimation
Xu, A., & Raginsky, M. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2646342 · Cited by 48
On Communication Cost of Distributed Statistical Estimation and Dimensionality
Garg, A., Ma, T., & Nguyễn, H. L. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1405.1665 · Cited by 46 · cited 1×
“A sparse variation of the Gaussian mean estimation problem has been studied in [29], [30], [32], where = {θ ∈”
BackgroundLower bounds for learning distributions under communication constraints via Fisher information
Barnes, L. P., Han, Y., & Ozgur, A. (2019) · arXiv · doi:10.48550/arxiv.1902.02890 · Cited by 40
Self-citationQ-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning
Elgabli, A., Park, J., Bedi, A. S., Bennis, M., & Aggarwal, V. (2020) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp40776.2020.9054491 · Cited by 31
Inference under Information Constraints: Lower Bounds from Chi-Square Contraction
Acharya, J., Canonne, C. L., & Tyagi, H. (2019) · Cited by 24
Fisher Information for Distributed Estimation under a Blackboard Communication Protocol
Barnes, L. P., Han, Y., & Özgür, A. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849821 · Cited by 18 · cited 1×
“To prove Theorem 2, we use part of Theorem 3 from [50] (see also [36]), reproduced below, which is proved using a Fisher information argument.”
MethodSelf-citationScaling Up Quasi-newton Algorithms: Communication Efficient Distributed SR1
Jahani, M., Nazari, M., Rusakov, S., Berahas, A. S., & Takáč, M. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-64583-0_5 · Cited by 14 · cited 1×
“SGD methods [1], [3]–[15], as well as other fundamental contributions to distributed first-order [16]–[20] and secondorder [21]–[25] optimization procedures.”
Jahani, M., He, X., Ma, C., Mokhtari, A., Mudigere, D., Ribeiro, A., & Takáč, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.11507 · Cited by 13
Barnes, L. P., Han, Y., & Özgür, A. (2018) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2018.8635899 · Cited by 9 · cited 1×
“It builds on a geometric characterization of Fisher information from quantized samples, a framework introduced in [35].”
BackgroundSelf-citation
Research works printed but not linked: 2
- diakonikolas, 2017, Communication-efficient distributed learning of discrete probability distributions, Proc Adv Neural Inf Process Syst, 6394
- niu, 2011, Hogwild: A lock-free approach to parallelizing stochastic gradient, Proc NIPS, 24, 693
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
Breaking the Communication-Privacy-Accuracy Trilemma
Chen, W., Kairouz, P., & Özgür, A. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3218772 · Cited by 94
“Previous works in the mean estimation problem [8], [12], [20], [21], [22], [23] mainly focus on reducing communication cost, for instance, by random rotation [12] and sparsification [20], [21], [24], [25].”
BackgroundTimely Communication in Federated Learning
Buyukates, B., & Ulukuş, Ş. (2021) · IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS) · doi:10.1109/infocomwkshps51825.2021.9484497 · Cited by 53
Communication compression techniques in distributed deep learning: A survey
Wang, Z., Wen, M., Xu, Y., Zhou, Y., Wang, J. H., & Zhang, L. (2023) · Journal of Systems Architecture · doi:10.1016/j.sysarc.2023.102927 · Cited by 48
Wang, B., Fang, J., Li, H., & Zeng, B. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3316588 · Cited by 36
“The former includes the thresholding-based method [32] which selects the elements based on their magnitude, the Top-K method [33], [34], [35] which selects the K largest (in absolute sense) elements and variants of Top-K such as [36], [37].”
Method
Metadata
- Authors
- Barnes, L. P., Inan, H. A., Isik, B., & Ozgur, A.
- Affiliations
- Stanford University (US)
- Venue
- IEEE Journal on Selected Areas in Information Theory
- Published
- 2020-11
- Volume
- 1
- Issue
- 3
- Pages
- 897-907
- ISSN
- 2641-8770 (ISSN-L)
- OpenAlex
- W3107557773
- Cited by
- 44
- References
- 57
- Citations by year
- 2026: 3 · 2025: 5 · 2024: 10 · 2023: 14 · 2022: 6 · 2021: 6
- FWCI
- 2.55
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- Locations
- IEEE Journal on Selected Areas in Information Theory (publishedVersion)
- Funders
- NSF (CCF-1704624)
- Google Faculty Research Award
- 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
- distributed stochastic gradient descent, communication efficiency, gradient sparsification, top-k sparsification
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.