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
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].”
MethodVithana, S., & Ulukuş, Ş. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3292187 · Cited by 28
“33 Even though there are two types of reading and writing costs ( ), the optimization problem remains the same since the two costs are scaled versions of one another.”
BackgroundMethodResFed: Communication-Efficient Federated Learning With Deep Compressed Residuals
Song, R., Zhou, L., Lyu, L., Festag, A., & Knoll, A. (2023) · IEEE Internet of Things Journal · doi:10.1109/jiot.2023.3324079 · Cited by 30
“Note that we consider the model updates introduced by [25], [26], and [27] as special residuals, which are calculated using the stationary predictor.”
Information Compression in the AI Era: Recent Advances and Future Challenges
Chen, J., Fang, Y., Khisti, A. J., Özgür, A., & Shlezinger, N. (2025) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2025.3560359 · Cited by 42
“Common techniques include scalar and vector quantization [70], [71], sparsification [72], [73], [74], [75], projection [76], entropy encoders [77], or low-rank decomposition [78].”
Communication Cost Reduction with Partial Structure in Federated Learning
Kang, D., & Ahn, C. W. (2021) · Electronics · doi:10.3390/electronics10172081 · Cited by 17
“Such a problem of finding a trade-off between communication cost and model performance is still an open question, and various attempts are being made to solve it [27,28].”
BackgroundImproved Information Theoretic Generalization Bounds for Distributed and Federated Learning
Barnes, L. P., Dytso, A., & Poor, H. V. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834700 · Cited by 21
Self-citationPrivate Information Retrieval and Its Extensions: An Introduction, Open Problems, Future Directions
Vithana, S., Wang, Z., & Ulukuş, Ş. (2023) · IEEE BITS the Information Theory Magazine · doi:10.1109/mbits.2023.3322972 · Cited by 29
“Gradient sparsi fi cation [36], [37], [38], [39], [40], [41], [42] is a mechanism used in most learning tasks to reduce the communication overhead.”
Enabling Communication-Efficient Federated Learning via Distributed Compressed Sensing
Guan, Y., Liu, X., Ren, T., & Niu, J. (2023) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom53939.2023.10229032 · Cited by 17
“Representative schemes of sparsification such as Top-k [18], rTop-k [19], and the powerful quantization methods such as signSGD [20], QSGD [21] have been well developed in distributed training.”
MethodDynamic layer-wise sparsification for distributed deep learning
Zhang, H., Wu, T., Ma, Z., Li, F., & Liu, J. (2023) · Future Generation Computer Systems · doi:10.1016/j.future.2023.04.022 · Cited by 13
Private Federated Submodel Learning with Sparsification
Vithana, S., & Ulukuş, Ş. (2022) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw54588.2022.9965815 · Cited by 12
Neural Network Compression for Noisy Storage Devices
Isik, B., Choi, K., Zheng, X., Weissman, T., Ermon, S., Wong, H. ‐. P., & Alaghi, A. (2023) · ACM Transactions on Embedded Computing Systems · doi:10.1145/3588436 · Cited by 14
“Compression of NN parameters has a rich history starting from the early works of [15, 30], with techniques such as pruning [5, 25, 28, 29, 37, 38, 40, 45, 49, 56, 61, 63], quantization, [2, 14, 23, 43, 70] and KD [33, 57, 69] among others [18].”
Self-citationOver-the-Air Statistical Estimation
Lee, C.-Z., Barnes, L. P., & Özgür, A. (2021) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2021.3118412 · Cited by 15
Self-citationBarnes, L. P., Dytso, A., & Poor, H. V. (2022) · Entropy · doi:10.3390/e24091178 · Cited by 17
“There has been considerable interest in understanding the impact of both communication constraints [8,9] and privacy constraints [10–13] on the performance of machine learning systems, as well as designing protocols that efficiently train the systems under these constraints.”
BackgroundSelf-citationSecure Gradient Aggregation With Sparsification for Resource-Limited Federated Learning
Sami, H. U., & Güler, B. (2024) · IEEE Transactions on Communications · doi:10.1109/tcomm.2024.3403475 · Cited by 11
“Recent works have also explored the combination of two to achieve the best of both worlds [18], [45].”
Vithana, S., & Ulukuş, Ş. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3339450 · Cited by 10
Rate-Distortion Theoretic Model Compression: Successive Refinement for PruningPreprint
Isik, B., No, A., & Weissman, T. (2021) · arXiv (Cornell University) · Cited by 8
Self-citationFedLTN: Federated Learning for Sparse and Personalized Lottery Ticket Networks
Mugunthan, V., Lin, E., Gokul, V., Lau, C., Kagal, L., & Pieper, S. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-19775-8_5 · Cited by 7
“Model compression techniques [1,2,8] like quantization, pruning, and sparsification are usually taken from the classic single centralized setting and applied to FL.”
BackgroundTimely Asynchronous Hierarchical Federated Learning: Age of Convergence
Mitra, P., & Ulukuş, Ş. (2023) · International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) · doi:10.23919/wiopt58741.2023.10349820 · Cited by 9
An Efficient Asynchronous Federated Learning Protocol for Edge Devices
Li, Q. H., Gao, Z., Sun, Y., Wang, Y. L., Wang, R., & Zhu, H. (2024) · IEEE Internet of Things Journal · doi:10.1109/jiot.2024.3406634 · Cited by 4
“2) Aggregation skewness , differences in the correlation between the composition of different subsets and global model update quality due to data heterogeneity [10], [11], leading to the skewness in the aggregation direction due to instability [12], [13].”
BackgroundLee, S., & Jang, H. (2025) · IEEE Access · doi:10.1109/access.2025.3547627 · Cited by 10
“Various strategies have been proposed to reduce communication costs, including delayed updates [3], low-rank approximation [20], [21], quantization [13], [22], [23], [24], [25], [26], [27], and sparsification [28], [29], [30], [31], [32].”
Model Segmentation for Storage Efficient Private Federated Learning with Top $r$ Sparsification
Vithana, S., & Ulukuş, Ş. (2023) · Conference on Information Sciences and Systems · doi:10.1109/ciss56502.2023.10089698 · Cited by 5
“Top r sparsification [10], [11] is introduced in FL to only upload the most significant r fraction of updates to increase the efficiency of the FL process by reducing communications with insignificant impact.”
BackgroundRate-Privacy-Storage Tradeoff in Federated Learning with Top $r$ Sparsification
Vithana, S., & Ulukuş, Ş. (2023) · International Conference on Communications · doi:10.1109/icc45041.2023.10279162 · Cited by 4
“One solution to this problem is gradient sparsification [9]–[11], where the users only communicate a selected set of gradients and parameters as opposed to communicating all gradient updates and parameters.”
BackgroundMethodFedTC: Enabling Communication-Efficient Federated Learning via Transform Coding
Guan, Y., Liu, X., Niu, J., & Ren, T. (2024) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom52122.2024.10621176 · Cited by 4
Representative Kernels-Based CNN for Faster Transmission in Federated Learning
Li, W., Shen, Z., Liu, X., Wang, M., Ma, C., Ding, C., & Cao, J. (2024) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2024.3423448 · Cited by 4
“The same challenge also exists other studies which adopt top-k to perform sparsification (e.g., rTop-k [38] and Top-k SparseSecAgg [39]).”
BackgroundHa, D. T., Bac, T. P., Tran, K. D., & Tran, K. P. (2023) · Springer series in reliability engineering · doi:10.1007/978-3-031-30510-8_8 · Cited by 3
Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimation
Vithana, S., Cadambe, V. R., Calmon, F. P., & Jeong, H. (2025) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml64287.2025.00039 · Cited by 9
r Age-k: Communication-Efficient Federated Learning Using Age Factor
Mortaheb, M., Kaswan, P., & Ulukuş, Ş. (2024) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/ieeeconf60004.2024.10942626 · Cited by 2
“We take particular note of two compression strategies popular in the literature: top-k sparsification [9] and rTop-k sparsification [10].”
Evaluation of Computation Overhead of Paillier Encryption in Vertical Federated Learning
Abhinand, P., Paul, T., & Kumar, G. S. (2024) · IEEE India Council International Subsections Conference (INDISCON) · doi:10.1109/indiscon62179.2024.10744378 · Cited by 3
“…learning [11] and based on user clustering and multi task learning [12]) and for Communication-efficiency (model compression techniques [13] [14] , gradient compression techniques [15] [16], using the Lottery Ticket Hypothesis [17] [10] and others [18]) Recent developments on FL includes…”
MethodFederated Learning in Drone-based Systems
Piramuthu, O. B., & Caesar, M. (2024) · IEEE Latin-American Conference on Communications · doi:10.1109/latincom62985.2024.10770693 · Cited by 3
“…k largest magnitude gradient coordinates are sent. in the hard-threshold sparsifier [13] method, only those gradient coordinates with magnitude of at least a fixed threshold ( λ ≥ 0 ) are sent; in the rTop-k [2] method, k vectors are randomly chosen to be sent from the r largest magnitude vectors.”
Adaptive Ratio-Based-Threshold Gradient Sparsification Scheme for Federated Learning
Kong, J. M., & Sousa, E. S. (2023) · International Symposium on Networks, Computers and Communications (ISNCC) · doi:10.1109/isncc58260.2023.10323644 · Cited by 2
“A few variations of top-k have been introduced to yield improved fairness, reduced computational load, and better inference ac-2023 curacy and convergence time compared to the original method, such as FAB-top-k and rTop-k [5,6].”
MethodEfficient Unbiased Sparsification
Barnes, L. P., Chow, T., Cohen, E., Frankston, K., Howard, B., Kochman, F., Scheinerman, D., & VanderKam, J. M. (2024) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit57864.2024.10619383 · Cited by 3
“Furthermore, the works [7], [12] both show that a combination of these two strategies can outperform each one on its own separately.”
Self-citationWang, X., Shi, X., Wen, G., & Yu, X. (2025) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2025.3648495 · Cited by 1
“Among these, biased compressors such as Top-k [24], [25], 2327-4697 © 2025 IEEE.”
Age-Aware Partial Gradient Update Strategy for Federated Learning Over the Air
Du, R., Zhu, J., Li, Z., & Yang, H. H. (2026) · International Conference on Communications · doi:10.1109/icc59461.2026.11587476 · Cited by 2
“0 ); and rTop-k [15], which randomly samples k gradients from the top r by magnitude.”
Saha, R., Pilancı, M., & Goldsmith, A. J. (2021) · arXiv (Cornell University)
Over-the-Air Statistical Estimation of Sparse Models
Lee, C.-Z., Barnes, L. P., Zhan, W., & Özgür, A. (2021) · Globecom · doi:10.1109/globecom46510.2021.9685768
“We propose schemes for the sparse Gaussian location and sparse product Bernoulli models, and show that they offer drastically lower estimation error than the digital lower bounds for the same models in [4], [7].”
BackgroundMethodInfluentialSelf-citationProfessional English Translation Corpus Under the Binomial Theorem Coefficient
Zhang, J., & Jaamour, Q. (2022) · Applied Mathematics and Nonlinear Sciences · doi:10.2478/amns.2022.2.0131
Permutation mask: a combined gradient sparsification for federated learning
Zhou, S., & Zhou, Y. (2024) · Journal of nonparametric statistics · doi:10.1080/10485252.2024.2370874
Optimizing Training Performance via Omni-Block Sparsity Adaptation
Li, W. (2024) · International Conference on Communication Technology and Information Technology (ICCTIT) · doi:10.1109/icctit64404.2024.10928544
Li, X., Sun, J., Yang, Z., & Ding, K. (2025) · IEEE Internet of Things Journal · doi:10.1109/jiot.2025.3637373 · Cited by 1
“Existing sparsification methods include biased approaches, such as threshold-based [20] and top-K selection [22], [23], as well as unbiased methods like random-K [24] and hybrid variants [25], [26], many of which have established convergence guarantees [27].”
Age-Aware Edge-Blind Federated Learning via Over-the-Air Aggregation
Elshazly, A. E., & Arafa, A. M. (2026) · International Conference on Communications · doi:10.1109/icc59461.2026.11587676 · Cited by 1
“This has been mitigated in the literature by multiple approaches, such as compressive sensing (CS) methods [32], [33], random parameter selection [34], and intelligent index-selection strategies, including layer-wise sparsification, gradient segmentation, and age-based selection [35], [36].”
Ge, K., Long, W., Dong, Y., Li, D., Xie, M., 吕鹏龙, Zhang, W., & Zhang, W. (2026) · Journal of Systems Architecture · doi:10.1016/j.sysarc.2026.104047
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.