# Anytime MiniBatch: Exploiting Stragglers in Online Distributed Optimization

arXiv: https://arxiv.org/abs/2006.05752 · HTML: https://mlsanity.com/paper/2006.05752/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2020.

## Built on by (most cited first, 9 of 9)

- [Trade-offs of Local SGD at Scale: An Empirical Study](https://mlsanity.com/paper/2110.08133/) (2021)
- [FedSAE: A Novel Self-Adaptive Federated Learning Framework in Heterogeneous Systems](https://mlsanity.com/paper/2104.07515/) (2021)
- [Taming Resource Heterogeneity In Distributed ML Training With Dynamic Batching](https://mlsanity.com/paper/2305.12213/) (2023)
- [OmniLearn: A Framework for Distributed Deep Learning over Heterogeneous Clusters](https://mlsanity.com/paper/2503.17469/) (2025)
- [STSyn: Speeding Up Local SGD with Straggler-Tolerant Synchronization](https://mlsanity.com/paper/2210.03521/) (2022)
- [SignSGD with Federated Voting](https://mlsanity.com/paper/2403.16372/) (2024)
- [Decentralized optimization with non-identical sampling in presence of stragglers](https://mlsanity.com/paper/2108.11071/) (2021)
- [Lightweight Projective Derivative Codes for Compressed Asynchronous Gradient Descent](https://mlsanity.com/paper/2201.12990/) (2022)
- [AntDT: A Self-Adaptive Distributed Training Framework for Leader and Straggler Nodes](https://mlsanity.com/paper/2404.09679/) (2024)

## Abstract (arXiv)

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.