Gradient Coding through Iterative Block Leverage Score Sampling
Neophytos Charalambides Mert Pilanci Alfred Hero
We generalize the leverage score sampling sketch for $\ell_2$-subspace
embeddings, to accommodate sampling subsets of the transformed data, so that
the sketching approach is appropriate for distributed settings. This is then
used to derive an approximate coded computing approach for first-order methods;
known as gradient coding, to accelerate linear regression in the presence of
failures in distributed computational networks, \textit{i.e.} stragglers. We
replicate the data across the distributed network, to attain the approximation
guarantees through the induced sampling distribution. The significance and main
contribution of this work, is that it unifies randomized numerical linear
algebra with approximate coded computing, while attaining an induced
$\ell_2$-subspace embedding through uniform sampling. The transition to uniform
sampling is done without applying a random projection, as in the case of the
subsampled randomized Hadamard transform. Furthermore, by incorporating this
technique to coded computing, our scheme is an iterative sketching approach to
approximately solving linear regression. We also propose weighting when
sketching takes place through sampling with replacement, for further
compression.