Effective communication between the server and workers plays a key role in distributed optimization. In this paper, we focus on optimizing the server-to-worker communication, uncovering inefficiencies in prevalent downlink compression approaches. Considering first the pure setup where the uplink communication costs are negligible, we introduce MARINA-P, a novel method for downlink compression, employing a collection of correlated compressors. Theoretical analyses demonstrates that MARINA-P with permutation compressors can achieve a server-to-worker communication complexity improving with the number of workers, thus being provably superior to existing algorithms. We further show that MARINA-P can serve as a starting point for extensions such as methods supporting bidirectional compression. We introduce M3, a method combining MARINA-P with uplink compression and a momentum step, achieving bidirectional compression with provable improvements in total communication complexity as the number of workers increases. Theoretical findings align closely with empirical experiments, underscoring the efficiency of the proposed algorithms.

通过提出MARINA-P方法，利用相关压缩器实现下行压缩，在纯净的上行通信成本可以忽略的情况下，从服务端到工作者的通信复杂度可以随着工作者数量而改进，这种方法在支持双向压缩的方法中有着明显的改进，理论和实验结果都证明了所提算法的高效性。

改进非凸分布式优化下函数相似性的最坏情况双向通信复杂度