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.

在异步集中式分布式设置中，我们考虑非凸随机优化问题，其中来自工作节点到服务器的通信时间不可忽略，并且计算和通信时间可能对所有工作节点都不同。使用一种无偏压缩技术，我们开发了一种新方法-Shadowheart SGD，可以明显改善所有之前集中式方法的时间复杂性。此外，我们还证明了在压缩通信的集中式方法族中，Shadowheart SGD的时间复杂度是最优的。我们还考虑了双向设置，其中从服务器向工作节点的广播是非可忽略的，并开发了相应的方法。

Shadowheart SGD: 面对任意计算和通信差异的分布式异步SGD的最优时间复杂度