Gradient Coding Using the Stochastic Block Model
Abstract
Gradient descent and its many variants, including mini-batch stochastic gradient descent, form the algorithmic foundation of modern large-scale machine learning. Due to the size and scale of modern data, gradient computations are often distributed across multiple compute nodes. Unfortunately, such distributed implementations can face significant delays caused by straggler nodes, i. e., nodes that are much slower than average. Gradient coding is a new technique for mitigating the effect of stragglers via algorithmic redundancy. While effective, previously proposed gradient codes can be computationally expensive to construct, inaccurate, or susceptible to adversarial stragglers. In this work, we present the stochastic block code (SBC), a gradient code based on the stochastic block model. We show that SBCs are efficient, accurate, and that under certain settings, adversarial straggler selection becomes as hard as detecting a community structure in the multiple community, block stochastic graph model.
Integrity signals
Registry
Cites
Statistics
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?
The authors of [146] have developed tools to measure statistical heterogeneity using metrics such as local dissimilarity.
“The authors of [146] have developed tools to measure statistical heterogeneity using metrics such as local dissimilarity.”
From Challenges, Applications and Design Aspects of Federated Learning: A Survey (2021) · cites this paper as [146]
In the presence of stragglers, gradient coding and variants lead either to exact or inexact recovery of the true gradients by replicating data blocks or gradient computation across computing nodes.
“In the presence of stragglers, gradient coding, and variants [98], [99], [102], the replication of data blocks (or also the gradient computation on those data blocks) across computing nodes leads either to exact or inexact recovery of the true gradients.”
From Handling privacy-sensitive medical data with federated learning: Challenges and future directions (2023) · cites this paper as [98]
Cites
Large Scale Distributed Deep Networks
Dean, J. B., Corrado, G. S., Monga, R., Chen, K., Devin, M., Mao, M., Ranzato, M., Senior, A., Tucker, P. A., Yang, K., et al. (2012) · Cited by 3,189 · see citing works
Classical and new inequalities in analysis
MITRINOVIC, D. S., Pečarić, J. E. 1., & Fink, A. M. 1. (1993) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(93)90086-a · Cited by 1,332 · see citing works
A Probabilistic and RIPless Theory of Compressed Sensing
Candès, E. J., & Plan, Y. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2161794 · Cited by 618 · see citing works
Community Detection and Stochastic Block Models
Abbe, E. A. (2018) · now publishers, Inc. eBooks · doi:10.1561/9781680834772 · Cited by 593 · see citing works
Effective straggler mitigation: attack of the clones
Ananthanarayanan, G., Ghodsi, A., Shenker, S. J., & Stoica, I. G. (2013) · Cited by 422 · see citing works
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products
Dutta, S., Cadambe, V. R., & Grover, P. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2927558 · Cited by 362 · see citing works
Reconstruction and estimation in the planted partition model
Mossel, E., Neeman, J., & Sly, A. (2014) · Probability Theory and Related Fields · doi:10.1007/s00440-014-0576-6 · Cited by 304 · see citing works
Abbe, E. A., & Sandon, C. (2015) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2015.47 · Cited by 293 · see citing works
When Do Redundant Requests Reduce Latency?
Shah, N. B., Lee, K., & Ramchandran, K. (2015) · IEEE Transactions on Communications · doi:10.1109/tcomm.2015.2506161 · Cited by 145 · see citing works
Li, S., Maddah-Ali, M. A., & Avestimehr, A. S. (2015) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2015.7447112 · Cited by 128 · see citing works
Speeding up distributed machine learning using codes
Lee, K., Lam, M., Pedarsani, R., Papailiopoulos, D., & Ramchandran, K. (2016) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2016.7541478 · Cited by 125 · see citing works
Self-citationPaleo: A Performance Model for Deep Neural Networks
Qi, H., Sparks, E., & Talwalkar, A. (2017) · International Conference on Learning Representations · Cited by 119 · see citing works
Li, S., Maddah-Ali, M. A., & Avestimehr, A. S. (2015) · Cited by 85 · see citing works
Approximate Gradient Coding via Sparse Random GraphsPreprint
Charles, Z., Papailiopoulos, D., & Ellenberg, J. S. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1711.06771 · Cited by 46 · see citing works
Self-citationGradient Coding via the Stochastic Block ModelPreprint
Charles, Z., & Papailiopoulos, D. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.10378 · Cited by 16 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Federated learning: Challenges, methods, and future directions
Li, T., Sahu, A. K., Talwalkar, A., & Smith, V. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2975749 · Cited by 6,210 · see citing works
Handling privacy-sensitive medical data with federated learning: Challenges and future directions
Aouedi, O., Sacco, A., Piamrat, K., & Marchetto, G. (2023) · IEEE Journal of Biomedical and Health Informatics · doi:10.1109/jbhi.2022.3185673 · Cited by 165 · see citing works
Challenges, Applications and Design Aspects of Federated Learning: A Survey
Rahman, K. M. J., Ahmed, F., Akhter, N., Hasan, M., Amin, R., Aziz, K. E., Islam, A. K. M. M., Mukta, M. S. H., & Islam, A. K. M. N. (2021) · IEEE Access · doi:10.1109/access.2021.3111118 · Cited by 147 · see citing works
- Authors
- Charles, Z., & Papailiopoulos, D.
- Affiliations
- University of Wisconsin–Madison (US)
- ORCID
- Charles, Zachary
- Venue
- 2018 IEEE International Symposium on Information Theory (ISIT)
- Publisher
- IEEE
- Published
- 2018-06
- Pages
- 1998-2002
- OpenAlex
- W2935717345
- Cited by
- 23
- References
- 15
- Citations by year
- 2025: 2 · 2024: 5 · 2023: 1 · 2022: 2 · 2021: 4 · 2020: 6 · 2019: 2 · 2018: 1
- FWCI
- 1.32
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- IEEE International Symposium on Information Theory (ISIT) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed systems and fault tolerance
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Keywords
- gradient coding, stochastic block model, straggler nodes, stochastic gradient descent, mini-batch gradient descent, community detection
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
