论文标题
EF21-P和朋友：通过双向压缩提高了理论沟通复杂性，以进行分布式优化
EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compression
论文作者
论文摘要
在这项工作中，我们将注意力集中在分布式优化问题上，因为服务器与工人之间的通信时间不可忽略。我们获得了支持双向压缩的新颖方法（包括从服务器到工人，反之亦然），这些方法享有凸和非凸问题的最新理论通信复杂性。我们的界限是第一个设法将来自工人到服务器和服务器对工人压缩的差异/错误的差异，从而将乘法依赖转换为加成层。此外，在凸状态下，我们获得了与梯度下降的理论通信复杂性相匹配的第一界。即使在这个凸制度中，我们的算法也与有偏梯度估计器一起使用，这是非标准的，需要可能具有独立关注的新证明技术。最后，我们的理论结果通过合适的实验得到了证实。
In this work we focus our attention on distributed optimization problems in the context where the communication time between the server and the workers is non-negligible. We obtain novel methods supporting bidirectional compression (both from the server to the workers and vice versa) that enjoy new state-of-the-art theoretical communication complexity for convex and nonconvex problems. Our bounds are the first that manage to decouple the variance/error coming from the workers-to-server and server-to-workers compression, transforming a multiplicative dependence to an additive one. Moreover, in the convex regime, we obtain the first bounds that match the theoretical communication complexity of gradient descent. Even in this convex regime, our algorithms work with biased gradient estimators, which is non-standard and requires new proof techniques that may be of independent interest. Finally, our theoretical results are corroborated through suitable experiments.
