Gradient Coding Using the Stochastic Block Model

By Zachary B. Charles, Dimitris Papailiopoulos. 2018

26 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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

1. Virginia Smith
2. Tian Li
3. Ameet Talwalkar
4. Anit Kumar Sahu
5. Deepesh Data
6. Linqi Song
7. Suhas N. Diggavi
8. Peter Richtárik

In Computational Theory and Mathematics

1. Ameet Talwalkar
2. Tian Li
3. Suhas N. Diggavi
4. Virginia Smith
5. Deepesh Data
6. Anit Kumar Sahu
7. Linqi Song

Citations in the corpus

• Data Encoding for Byzantine-Resilient Distributed Optimization (2019, methodology): “There has been significant recent interest in using coding-theoretic techniques to mitigate the well-known straggler problem [DB13], including gradient coding [TLDK17, RTDT18, CP18, HRSH18], encoding computation [LLP + 18, DCG16], data encoding [KSDY17].”
• Federated Learning: Challenges, Methods, and Future Directions (2019, background): “For instance, in the presence of stragglers, gradient coding and its variants [11] carefully replicate data blocks (as well as the gradient computation on those data blocks) across computing nodes to obtain either an exact or inexact recovery of the true gradients.”