Gradient Coding From Cyclic MDS Codes and Expander Graphs

Netanel Raviv, Itzhak Tamo, Rashish Tandon, Alexandros G. Dimakis

Abstract

Gradient coding is a technique for straggler mitigation in distributed learning. In this paper we design novel gradient codes using tools from classical coding theory, namely, cyclic MDS codes, which compare favorably with existing solutions, both in the applicable range of parameters and in the complexity of the involved algorithms. Second, we introduce an approximate variant of the gradient coding problem, in which we settle for approximate gradient computation instead of the exact one. This approach enables graceful degradation, i.e., the $\ell_2$ error of the approximate gradient is a decreasing function of the number of stragglers. Our main result is that normalized adjacency matrices of expander graphs yield excellent approximate gradient codes, which enable significantly less computation compared to exact gradient coding, and guarantee faster convergence than trivial solutions under standard assumptions. We experimentally test our approach on Amazon EC2, and show that the generalization error of approximate gradient coding is very close to the full gradient while requiring significantly less computation from the workers.

Introduction: The Straggler Problem

In large-scale distributed learning, a "master" node divides data among many "worker" nodes. In a synchronous setup, the master must wait for every worker to finish calculating its portion of the gradient before updating the model. The entire system is only as fast as its slowest member—the straggler.

Previous solutions, like the original "Gradient Coding" framework, used redundancy to solve this: if you want to tolerate $s$ stragglers, every worker needs to store and process $d \ge s + 1$ pieces of data. This is a heavy tax. If you have 10 potential stragglers, every node does 11x the work. This paper addresses two core questions:

  1. Can we make exact reconstruction more computationally efficient?
  2. Can we settle for an approximate gradient to drastically lower that redundancy overhead?
A simple gradient coding example where the master node can reconstruct the full gradient from any two out of three workers.

Methods

The authors propose two distinct approaches to optimize this process:

1. Exact Coding via Cyclic MDS Codes

For scenarios where you need the mathematically exact gradient, the authors turn to Maximum Distance Separable (MDS) codes, specifically cyclic ones like BCH and Reed-Solomon codes.

By using the cyclic properties of these codes, they create a circulant coding matrix. This allows the master node to use Fast Fourier Transforms (FFT) and efficient interpolation to reconstruct the gradient. This reduces the decoding complexity from cubic time to nearly linear time ($O(n \log n)$), making it much more practical for systems with many workers.

2. Approximate Coding via Expander Graphs

This is the paper's most novel contribution. The authors argue that since Gradient Descent is inherently robust to noise (as seen in Stochastic Gradient Descent), we don't actually need the exact gradient every time. They use the normalized adjacency matrices of Expander Graphs to determine which worker gets which data. Expander graphs are highly connected but sparse.

In spectral graph theory, the "spectral gap" of a graph determines how well information spreads across it. The authors prove that if the coding matrix is based on a good expander, the error of the reconstructed gradient is bounded by that spectral gap. This approach breaks the $d \ge s + 1$ rule. You can tolerate many stragglers ($s$) with very low redundancy ($d$), and the error "degrades gracefully"—the more workers report back, the more accurate the gradient becomes.

Key Results and Insights

The authors evaluated their approach using synthetic data and the Amazon Employee Dataset (Kaggle) on Amazon EC2 clusters. Key findings include:

  • Efficiency: The approximate scheme (AGC) achieved nearly the same generalization error (AUC) as exact gradient coding but required significantly less computation.
  • Performance on EC2: Real-world tests showed that the expander-based approach converged much faster than the "trivial" solution of simply ignoring stragglers.
  • Deterministic vs. Randomized: While previous approximate methods relied on random graphs, this paper provides a deterministic construction using expanders, providing guaranteed error bounds.
  • Redundancy as a Spectrum: Instead of viewing straggler mitigation as a binary (either you have the gradient or you don't), the authors treat it as an approximation problem. This aligns distributed computing more closely with the "lossy" nature of modern ML.

Limitations and Future Work

While promising, some real-valued exact constructions require specific relationships between the number of nodes and stragglers (e.g., $n \equiv s \pmod 2$). Additionally, the current framework assumes a fixed coding matrix. Future work could explore adaptive coding, where the redundancy shifts in real-time based on which nodes are currently lagging, or combine coding with quantization to further reduce communication overhead.

Summary updated

Abstract

Gradient coding is a technique for straggler mitigation in distributed learning. In this paper we design novel gradient codes using tools from classical coding theory, namely, cyclic MDS codes, which compare favorably with existing solutions, both in the applicable range of parameters and in the complexity of the involved algorithms. Second, we introduce an approximate variant of the gradient coding problem, in which we settle for approximate gradient computation instead of the exact one. This approach enables graceful degradation, i.e., the $\ell_2$ error of the approximate gradient is a decreasing function of the number of stragglers. Our main result is that normalized adjacency matrices of expander graphs yield excellent approximate gradient codes, which enable significantly less computation compared to exact gradient coding, and guarantee faster convergence than trivial solutions under standard assumptions. We experimentally test our approach on Amazon EC2, and show that the generalization error of approximate gradient coding is very close to the full gradient while requiring significantly less computation from the workers.
BibTeX
@inproceedings{raviv2018gradient,
  author = {Netanel Raviv and Itzhak Tamo and Rashish Tandon and Alexandros G. Dimakis},
  title = {{Gradient Coding From Cyclic MDS Codes and Expander Graphs}},
  booktitle = {International Conference on Machine Learning},
  year = {2018},
  url = {https://openreview.net/forum?id=BJWQFs-d-B},
}
Figure