# MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 33 references that are in the map.
- First posted on arXiv 5 Oct 2024.

## Builds on (most cited first, 23 of 23)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Revisiting Distributed Synchronous SGD](https://mlsanity.com/paper/1702.05800/) (2017)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD](https://mlsanity.com/paper/1803.01113/) (2018)
- [Perturbed Iterate Analysis for Asynchronous Stochastic Optimization](https://mlsanity.com/paper/1507.06970/) (2015)
- [Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays](https://mlsanity.com/paper/2206.07638/) (2022)
- [A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates](https://mlsanity.com/paper/1806.10188/) (2018)
- [An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization](https://mlsanity.com/paper/1505.04824/) (2015)
- [Asynchronous Stochastic Optimization Robust to Arbitrary Delays](https://mlsanity.com/paper/2106.11879/) (2021)
- [Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model](https://mlsanity.com/paper/2305.12387/) (2023)
- [AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms](https://mlsanity.com/paper/2310.20452/) (2023)
- [Delay-adaptive step-sizes for asynchronous learning](https://mlsanity.com/paper/2202.08550/) (2022)
- [Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server](https://mlsanity.com/paper/1610.05507/) (2016)
- [Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglers](https://mlsanity.com/paper/2002.11005/) (2020)
- [Adaptive Stochastic Gradient Descent for Fast and Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2208.03134/) (2022)

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

- [Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity](https://mlsanity.com/paper/2501.16168/) (2025)
- [ATA: Adaptive Task Allocation for Efficient Resource Management in Distributed Machine Learning](https://mlsanity.com/paper/2502.00775/) (2025)
- [Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity](https://mlsanity.com/paper/2509.22860/) (2025)
- [BurTorch: Revisiting Training from First Principles by Coupling Autodiff, Math Optimization, and Systems](https://mlsanity.com/paper/2503.13795/) (2025)
- [Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods](https://mlsanity.com/paper/2602.03802/) (2026)
- [Optimization Trade-offs in Asynchronous Federated Learning: A Stochastic Networks Approach](https://mlsanity.com/paper/2603.26231/) (2026)

## Abstract (arXiv)

We investigate the problem of minimizing the expectation of smooth nonconvex functions in a distributed setting with multiple parallel workers that are able to compute stochastic gradients. A significant challenge in this context is the presence of arbitrarily heterogeneous and stochastic compute times among workers, which can severely degrade the performance of existing parallel stochastic gradient descent (SGD) methods. While some parallel SGD algorithms achieve optimal performance under deterministic but heterogeneous delays, their effectiveness diminishes when compute times are random - a scenario not explicitly addressed in their design. To bridge this gap, we introduce MindFlayer SGD, a novel parallel SGD method specifically designed to handle stochastic and heterogeneous compute times. Through theoretical analysis and empirical evaluation, we demonstrate that MindFlayer SGD consistently outperforms existing baselines, particularly in environments with heavy-tailed noise. Our results highlight its robustness and scalability, making it a compelling choice for large-scale distributed learning tasks.