Tradeoffs for task parallelization in distributed optimization

We consider the problem of solving multiple optimization tasks on the same data in a distributed setting. We focus on consensus-based and incremental optimization strategies. Consensus-based distributed optimizers converge in fewer iterations, but the multiple tasks must be run serially. Incremental optimization algorithms, where the iterate is passed from node to node, have slower convergence guarantees but they can be parallelized to work on multiple tasks concurrently. When there are many tasks to solve, this approach can suffer from queuing delay. We provide an analysis of this delay which suggests that incremental algorithms may have superior performance for a moderate number of tasks. The main factor that controls this effect is the communication time. We show experimentally that there is a regime in which parallel instances of incremental algorithms can outperform serial instances of consensus-based algorithms.