Anytime Minibatch: Exploiting Stragglers in Online Distributed Optimization

By Nuwan S. Ferdinand, Haider Al-Lawati, Stark C. Draper, Matthew S. Nokleby. 2020

48 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, background): “Communication overhead is a major issue limiting the scaling of this approach, since ALLREDUCE must complete before every step and blocking communications are sensitive to stragglers (Dutta et al., 2018; Ferdinand et al., 2019).”
Robust and Communication-Efficient Collaborative Learning (2019, background): “The closest work to ours is (Ferdinand et al., 2019) that considers decentralized optimization for convex functions with deadline for local computations without considering communication bottlenecks and quantization as well as non-convex functions.”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “Some works propose deadlinebased approaches where all workers compute the local gradients using a variable number of samples within a fixed global cycle, which helps mitigate the impact of stragglers [16], [39].”
Privacy preservation in federated learning: An insightful survey from the GDPR perspective (2020, background): “This decentralised training approach requires a local updating scheme in which a synchronisation scheme among local nodes must be implemented [37, 100] which is not always feasible in federated settings.”
Overlap Local-SGD: An Algorithmic Approach to Hide Communication Delays in Distributed SGD (2020, background): “However, in a wireless system where the computing nodes typically have low bandwidth and poor connectivity, the high communication delay and unpredictable nodes slowdown may greatly hinder the benefits of parallel computation [5, 6, 7, 8].”