A Sequential Approximation Framework for Coded Distributed Optimization
  Building on the previous work of Lee et al. and Ferdinand et al. on coded
computation, we propose a sequential approximation framework for solving
optimization problems in a distributed manner. In a distributed computation
system, latency caused by individual processors ("stragglers") usually causes a
significant delay in the overall process. The proposed method is powered by a
sequential computation scheme, which is designed specifically for systems with
stragglers. This scheme has the desirable property that the user is guaranteed
to receive useful (approximate) computation results whenever a processor
finishes its subtask, even in the presence of uncertain latency. In this paper,
we give a coding theorem for sequentially computing matrix-vector
multiplications, and the optimality of this coding scheme is also established.
As an application of the results, we demonstrate solving optimization problems
using a sequential approximation approach, which accelerates the algorithm in a
distributed system with stragglers.
