  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.
