The DOI matches its Crossref record; 51 of the 57 references it cites were found in a registry or an index.
rTop-k: A Statistical Estimation Approach to Distributed SGD
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
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 49
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 47
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: rTop-k: A Statistical Estimation Approach to Distributed SGD. https://app.cochat.ai/papers/10.1109/jsait.2020.3042094
- The paper
- Barnes, L. P., Inan, H. A., Isik, B., & Ozgur, A. (2020). rTop-k: A Statistical Estimation Approach to Distributed SGD. IEEE Journal on Selected Areas in Information Theory. https://doi.org/10.1109/jsait.2020.3042094
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.