# Communication-Computation Efficient Gradient Coding

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2018.

## Built on by (most cited first, 27 of 27)

- [1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed](https://mlsanity.com/paper/2102.02888/) (2021)
- [Recent Advances on Federated Learning: A Systematic Survey](https://mlsanity.com/paper/2301.01299/) (2023)
- [1-bit LAMB: Communication Efficient Large-Scale Large-Batch Training with LAMB's Convergence Speed](https://mlsanity.com/paper/2104.06069/) (2021)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [Joint Optimization of Communications and Federated Learning Over the Air](https://mlsanity.com/paper/2104.03490/) (2021)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [Communication-Efficient Distributed Optimization with Quantized Preconditioners](https://mlsanity.com/paper/2102.07214/) (2021)
- [Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning](https://mlsanity.com/paper/2103.01206/) (2021)
- [Fundamental Limits of Hierarchical Secure Aggregation with Cyclic User Association](https://mlsanity.com/paper/2503.04564/) (2025)
- [ApproxIFER: A Model-Agnostic Approach to Resilient and Robust Prediction Serving Systems](https://mlsanity.com/paper/2109.09868/) (2021)
- [Optimal Communication-Computation Trade-Off in Heterogeneous Gradient Coding](https://mlsanity.com/paper/2103.01589/) (2021)
- [Adaptive Stochastic Gradient Descent for Fast and Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2208.03134/) (2022)
- [Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping](https://mlsanity.com/paper/2111.02949/) (2021)
- [Lightweight Projective Derivative Codes for Compressed Asynchronous Gradient Descent](https://mlsanity.com/paper/2201.12990/) (2022)
- [Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning](https://mlsanity.com/paper/2206.02450/) (2022)
- [Sequential Gradient Coding For Straggler Mitigation](https://mlsanity.com/paper/2211.13802/) (2022)
- [Solon: Communication-efficient Byzantine-resilient Distributed Training via Redundant Gradients](https://mlsanity.com/paper/2110.01595/) (2021)
- [Adaptive Worker Grouping For Communication-Efficient and Straggler-Tolerant Distributed SGD](https://mlsanity.com/paper/2201.04301/) (2022)
- [Cost-Efficient Distributed Learning via Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2202.08302/) (2022)
- [Fast and Straggler-Tolerant Distributed SGD with Reduced Computation Load](https://mlsanity.com/paper/2304.08589/) (2023)
- [Iterative Sketching for Secure Coded Regression](https://mlsanity.com/paper/2308.04185/) (2023)
- [Approximate Gradient Coding for Privacy-Flexible Federated Learning with Non-IID Data](https://mlsanity.com/paper/2404.03524/) (2024)
- [Design and Optimization of Hierarchical Gradient Coding for Distributed Learning at Edge Devices](https://mlsanity.com/paper/2406.10831/) (2024)
- [Approximate Gradient Coding for Distributed Learning with Heterogeneous Stragglers](https://mlsanity.com/paper/2510.22539/) (2025)
- [Coding-Enforced Resilient and Secure Aggregation for Hierarchical Federated Learning](https://mlsanity.com/paper/2601.17995/) (2026)
- [Pipelined Gradient Coding](https://mlsanity.com/paper/2607.20739/) (2026)

## Abstract (arXiv)

This paper develops coding techniques to reduce the running time of distributed learning tasks. It characterizes the fundamental tradeoff to compute gradients (and more generally vector summations) in terms of three parameters: computation load, straggler tolerance and communication cost. It further gives an explicit coding scheme that achieves the optimal tradeoff based on recursive polynomial constructions, coding both across data subsets and vector components. As a result, the proposed scheme allows to minimize the running time for gradient computations. Implementations are made on Amazon EC2 clusters using Python with mpi4py package. Results show that the proposed scheme maintains the same generalization error while reducing the running time by 32% compared to uncoded schemes and 23% compared to prior coded schemes focusing only on stragglers (Tandon et al., ICML 2017).