Gradient Coding with Iterative Block Leverage Score Sampling

arXiv:2308.03096v2 Announce Type: replace-cross
Abstract: 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 …

abstract arxiv block coding computing cs.dc cs.ir cs.it cs.lg cs.na data distributed embeddings gradient iterative math.it math.na replace sampling subsets type