Title: Straggler Mitigation in Distributed Optimization Through Data Encoding,
Abstract: Slow running or straggler tasks can significantly reduce computation speed in
distributed computation. Recently, coding-theory-inspired approaches have been
applied to mitigate the effect of straggling, through embedding redundancy in
certain linear computational steps of the optimization algorithm, thus
completing the computation without waiting for the stragglers. In this paper,
we propose an alternate approach where we embed the redundancy directly in the
data itself, and allow the computation to proceed completely oblivious to
encoding. We propose several encoding schemes, and demonstrate that popular
batch algorithms, such as gradient descent and L-BFGS, applied in a
coding-oblivious manner, deterministically achieve sample path linear
convergence to an approximate solution of the original problem, using an
arbitrarily varying subset of the nodes at each iteration. Moreover, this
approximation can be controlled by the amount of redundancy and the number of
nodes used in each iteration. We provide experimental results demonstrating the
advantage of the approach over uncoded and data replication strategies.