Improving the Worst-Case Bidirectional Communication Complexity for
  Nonconvex Distributed Optimization under Function Similarity
Kaja Gruntkowska Alexander Tyurin Peter Richtárik
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.