  In federated learning (FL), the communication constraint between the remote
learners and the Parameter Server (PS) is a crucial bottleneck. For this
reason, model updates must be compressed so as to minimize the loss in accuracy
resulting from the communication constraint. This paper proposes ``\emph{${\bf
M}$-magnitude weighted $L_{\bf 2}$ distortion + $\bf 2$ degrees of freedom''}
(M22) algorithm, a rate-distortion inspired approach to gradient compression
for federated training of deep neural networks (DNNs). In particular, we
propose a family of distortion measures between the original gradient and the
reconstruction we referred to as ``$M$-magnitude weighted $L_2$'' distortion,
and we assume that gradient updates follow an i.i.d. distribution --
generalized normal or Weibull, which have two degrees of freedom. In both the
distortion measure and the gradient, there is one free parameter for each that
can be fitted as a function of the iteration number. Given a choice of gradient
distribution and distortion measure, we design the quantizer minimizing the
expected distortion in gradient reconstruction. To measure the gradient
compression performance under a communication constraint, we define the
\emph{per-bit accuracy} as the optimal improvement in accuracy that one bit of
communication brings to the centralized model over the training period. Using
this performance measure, we systematically benchmark the choice of gradient
distribution and distortion measure. We provide substantial insights on the
role of these choices and argue that significant performance improvements can
be attained using such a rate-distortion inspired compressor.
