A Sequential Approximation Framework for Coded Distributed Optimization
This addresses latency issues in distributed computation systems, particularly for optimization tasks, but appears incremental as it builds on prior coded computation work.
The paper tackles the problem of stragglers causing delays in distributed optimization by proposing a sequential approximation framework that guarantees useful approximate results as processors finish, with a coding theorem for matrix-vector multiplications and proven optimality.
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.