Gradient Coding With Iterative Block Leverage Score Sampling

Gradient coding is a method for mitigating straggling servers in a centralized computing network that uses erasure-coding techniques to distributively carry out first-order optimization methods. Randomized numerical linear algebra uses randomization to develop improved algorithms for large-scale linear algebra computations. In this study, we propose a method for distributed optimization that combines gradient coding and randomized numerical linear algebra. The proposed method uses a randomized ℓ₂-subspace embedding and a gradient coding technique to distribute blocks of data to the computational nodes of a centralized network, and at each iteration the central server only requires a small number of computations to obtain the steepest descent update. The novelty of our approach is that the data is replicated according to importance scores, called block leverage scores, in contrast to most gradient coding approaches that uniformly replicate the data blocks. Furthermore, we do not require a decoding step at each iteration, avoiding a bottleneck in previous gradient coding schemes. We show that our approach results in a valid ℓ₂-subspace embedding, and that our resulting approximation converges to the optimal solution.. Authors: Charalambides, Neophytos [University of Michigan, Ann Arbor, MI (United States); University of California, San Diego, CA (United States)] (ORCID:0000000285281467); Pilanci, Mert [Stanford University, CA (United States)] (ORCID:0000000208709992); Hero, Alfred O. [University of Michigan, Ann Arbor, MI (United States)] (ORCID:0000000225319670). DOE Contract: NA0003921. Subjects: 97 MATHEMATICS AND COMPUTING; Low-rank approximations; coded computing; erasure-coding; least-squares regression; randomized algorithms; randomized numerical linear algebra; replication-coding; stragglers