  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.
