Distributed optimization is vital in solving large-scale machine learning
problems. A widely-shared feature of distributed optimization techniques is the
requirement that all nodes complete their assigned tasks in each computational
epoch before the system can proceed to the next epoch. In such settings, slow
nodes, called stragglers, can greatly slow progress. To mitigate the impact of
stragglers, we propose an online distributed optimization method called Anytime
Minibatch. In this approach, all nodes are given a fixed time to compute the
gradients of as many data samples as possible. The result is a variable
per-node minibatch size. Workers then get a fixed communication time to average
their minibatch gradients via several rounds of consensus, which are then used
to update primal variables via dual averaging. Anytime Minibatch prevents
stragglers from holding up the system without wasting the work that stragglers
can complete. We present a convergence analysis and analyze the wall time
performance. Our numerical results show that our approach is up to 1.5 times
faster in Amazon EC2 and it is up to five times faster when there is greater
variability in compute node performance.

本研究提出了一种名为 Anytime Minibatch 的在线分布式优化方法，其通过多轮共识平均其最小批量梯度来更新主变量，以减轻节点处理速度不均导致的进度缓慢问题。数值结果表明，该方法在 Amazon EC2 上比现有方法快 1.5 倍，在计算节点性能变化较大时，可提高至五倍。