Cross-Iteration Coded Computing

By Farzin Haddadpour, Yaoqing Yang, Viveck R. Cadambe, Pulkit Grover. 2018

15 citations recorded by the source corpus.

We introduce the idea of cross-iteration coded computing, an approach to reducing communication costs for a large class of distributed iterative algorithms involving linear operations, including gradient descent and accelerated gradient descent for quadratic loss functions. The state-of-the-art approach for these iterative algorithms involves performing one iteration of the algorithm per round of communication among the nodes. In contrast, our approach performs multiple iterations of the underlying algorithm in a single round of communication by incorporating some redundancy storage and computation. Our algorithm works in the master-worker setting with the workers storing carefully constructed linear transformations of input matrices and using these matrices in an iterative algorithm, with the master node inverting the effect of these linear transformations. In addition to reduced communication costs, a trivial generalization of our algorithm also includes resilience to stragglers and failures. The degree of redundancy of our algorithm can be tuned based on the amount of communication and straggler resilience required. Finally, we also describe a variant of our algorithm that can flexibly recover the results based on the degree of straggling in the worker nodes. The variant allows for the performance to degrade gracefully as the number of successful (non-straggling) workers is lowered.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, background): “For instance, reference [15] shows that by adding a controlled amount of redundancy through coding theoretic means, linear regression can be solved through one round of communication.”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, background): “Following the conference publication [1], there have been several interesting works in the coded computing community (see [21] for survey) on coded linear algebra [22]–[37], coded convolutions [47], [48], gradient coding [38]–[42], coded Fast Fourier Transforms [55], [56], performance analysis [45],”
On the Convergence of Local Descent Methods in Federated Learning (2019, neutral): “Focusing on distributed linear regression, [10] shows that by adding careful amount of redundancy via coding theoretic tools, linear regression can be solved with one-shot communication.”