# Speeding Up Distributed Machine Learning Using Codes

arXiv: https://arxiv.org/abs/1512.02673 · HTML: https://mlsanity.com/paper/1512.02673/

## Key facts

- Cited by 76 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Dec 2015.

## Built on by (most cited first, 30 of 76)

- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Efficient Parallel Split Learning over Resource-constrained Wireless Edge Networks](https://mlsanity.com/paper/2303.15991/) (2023)
- [On Large-Cohort Training for Federated Learning](https://mlsanity.com/paper/2106.07820/) (2021)
- [Provably Secure Federated Learning against Malicious Clients](https://mlsanity.com/paper/2102.01854/) (2021)
- [A Survey on Vertical Federated Learning: From a Layered Perspective](https://mlsanity.com/paper/2304.01829/) (2023)
- [Efficient Device Scheduling with Multi-Job Federated Learning](https://mlsanity.com/paper/2112.05928/) (2021)
- [CodedPaddedFL and CodedSecAgg: Straggler Mitigation and Secure Aggregation in Federated Learning](https://mlsanity.com/paper/2112.08909/) (2021)
- [Multi-Job Intelligent Scheduling with Cross-Device Federated Learning](https://mlsanity.com/paper/2211.13430/) (2022)
- [Accelerating Split Federated Learning over Wireless Communication Networks](https://mlsanity.com/paper/2310.15584/) (2023)
- [HASFL: Heterogeneity-aware Split Federated Learning over Edge Computing Systems](https://mlsanity.com/paper/2506.08426/) (2025)
- [CSAFL: A Clustered Semi-Asynchronous Federated Learning Framework](https://mlsanity.com/paper/2104.08184/) (2021)
- [Stochastic Coded Federated Learning with Convergence and Privacy Guarantees](https://mlsanity.com/paper/2201.10092/) (2022)
- [Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning](https://mlsanity.com/paper/2103.01206/) (2021)
- [MOB-FL: Mobility-Aware Federated Learning for Intelligent Connected Vehicles](https://mlsanity.com/paper/2212.03519/) (2022)
- [Federated Optimization of Smooth Loss Functions](https://mlsanity.com/paper/2201.01954/) (2022)
- [Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds](https://mlsanity.com/paper/2203.09755/) (2022)
- [Stochastic Coded Federated Learning: Theoretical Analysis and Incentive Mechanism Design](https://mlsanity.com/paper/2211.04132/) (2022)
- [Joint Coding and Scheduling Optimization for Distributed Learning over Wireless Edge Networks](https://mlsanity.com/paper/2103.04303/) (2021)
- [ApproxIFER: A Model-Agnostic Approach to Resilient and Robust Prediction Serving Systems](https://mlsanity.com/paper/2109.09868/) (2021)
- [Robust Federated Learning with Connectivity Failures: A Semi-Decentralized Framework with Collaborative Relaying](https://mlsanity.com/paper/2202.11850/) (2022)
- [Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework](https://mlsanity.com/paper/2406.00300/) (2024)
- [List-Decodable Coded Computing: Breaking the Adversarial Toleration Barrier](https://mlsanity.com/paper/2101.11653/) (2021)
- [Adaptive Verifiable Coded Computing: Towards Fast, Secure and Private Distributed Machine Learning](https://mlsanity.com/paper/2107.12958/) (2021)
- [Coding for Straggler Mitigation in Federated Learning](https://mlsanity.com/paper/2109.15226/) (2021)
- [ByzSecAgg: A Byzantine-Resistant Secure Aggregation Scheme for Federated Learning Based on Coded Computing and Vector Commitment](https://mlsanity.com/paper/2302.09913/) (2023)
- [Distributed Learning based on 1-Bit Gradient Coding in the Presence of Stragglers](https://mlsanity.com/paper/2403.14716/) (2024)
- [Soft BIBD and Product Gradient Codes](https://mlsanity.com/paper/2105.05231/) (2021)
- [Straggler-Resilient Differentially-Private Decentralized Learning](https://mlsanity.com/paper/2212.03080/) (2022)
- [FedAST: Federated Asynchronous Simultaneous Training](https://mlsanity.com/paper/2406.00302/) (2024)

## Abstract (arXiv)

Codes are widely used in many engineering applications to offer robustness against noise. In large-scale systems there are several types of noise that can affect the performance of distributed machine learning algorithms -- straggler nodes, system failures, or communication bottlenecks -- but there has been little interaction cutting across codes, machine learning, and distributed systems. In this work, we provide theoretical insights on how coded solutions can achieve significant gains compared to uncoded ones. We focus on two of the most basic building blocks of distributed learning algorithms: matrix multiplication and data shuffling. For matrix multiplication, we use codes to alleviate the effect of stragglers, and show that if the number of homogeneous workers is n, and the runtime of each subtask has an exponential tail, coded computation can speed up distributed matrix multiplication by a factor of log n. For data shuffling, we use codes to reduce communication bottlenecks, exploiting the excess in storage. We show that when a constant fraction α of the data matrix can be cached at each worker, and n is the number of workers, coded shuffling reduces the communication cost by a factor of (α + frac1n)γ(n) compared to uncoded shuffling, where γ(n) is the ratio of the cost of unicasting n messages to n users to multicasting a common message (of the same size) to n users. For instance, γ(n) simeq n if multicasting a message to n users is as cheap as unicasting a message to one user. We also provide experiment results, corroborating our theoretical gains of the coded algorithms.