Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity
This work addresses efficiency challenges in distributed machine learning for scenarios with variable worker speeds, offering a theoretically optimal solution that could benefit large-scale training systems.
The paper tackles the problem of nonconvex stochastic optimization in asynchronous distributed settings with heterogeneous computation and communication times, introducing Shadowheart SGD, which achieves optimal time complexity with compressed communication, improving upon all previous centralized methods.
We consider nonconvex stochastic optimization problems in the asynchronous centralized distributed setup where the communication times from workers to a server can not be ignored, and the computation and communication times are potentially different for all workers. Using an unbiassed compression technique, we develop a new method-Shadowheart SGD-that provably improves the time complexities of all previous centralized methods. Moreover, we show that the time complexity of Shadowheart SGD is optimal in the family of centralized methods with compressed communication. We also consider the bidirectional setup, where broadcasting from the server to the workers is non-negligible, and develop a corresponding method.