Improving asynchronous machine learning optimization across varied data is hard
Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult
Machine Learning
Summary
Training machine learning models often involves many workers processing data at the same time but with different data. Theory shows it's much harder to get good training speed when workers have different data than when they share the same data. The authors found that under common assumptions, you cannot do better than existing worst-case guarantees for this harder case. They also discovered that only by combining very strong conditions can one achieve training speeds close to the simpler shared data situations.
What this means in practice
- •For distributed machine learning engineers: Designing training systems must account for fundamental limits when data across workers differs, shaping realistic performance expectations.
- •For cloud infrastructure teams: Optimize resource allocation by understanding when heterogeneity in data prevents faster asynchronous training despite added hardware.
A theory result. No direct application yet.
Authors
Alexander Tyurin
Abstract
Modern large-scale machine learning tasks often require multiple workers, devices, CPUs, or GPUs to compute stochastic gradients in parallel and asynchronously to train model weights. Theoretical results typically distinguish between two settings: (i) the homogeneous setting, where all workers have access to the same data distribution, and (ii) the heterogeneous setting, where each worker operates on different data distributions. Known optimal time complexities in these settings reveal a significant gap, with far more pessimistic guarantees in the heterogeneous case. In this work, we investigate whether these pessimistic optimal time complexities can be overcome under different assumptions. Surprisingly, we show that improvement is provably impossible under widely used first- and second-order similarity assumptions for any randomized algorithm. We then turn to the interpolation regime and demonstrate that the weak interpolation assumption alone is also insufficient. Finally, we introduce a minimal combination of irreducible assumptions, strong interpolation and the local Polyak-Lojasiewicz condition, to derive a new time complexity bound that matches the dependence on worker computation times in the best-known result in the homogeneous setting, without requiring identical data distributions.