  Communication compression, a technique aiming to reduce the information
volume to be transmitted over the air, has gained great interests in Federated
Learning (FL) for the potential of alleviating its communication overhead.
However, communication compression brings forth new challenges in FL due to the
interplay of compression-incurred information distortion and inherent
characteristics of FL such as partial participation and data heterogeneity.
Despite the recent development, the performance of compressed FL approaches has
not been fully exploited. The existing approaches either cannot accommodate
arbitrary data heterogeneity or partial participation, or require stringent
conditions on compression.
  In this paper, we revisit the seminal stochastic controlled averaging method
by proposing an equivalent but more efficient/simplified formulation with
halved uplink communication costs. Building upon this implementation, we
propose two compressed FL algorithms, SCALLION and SCAFCOM, to support unbiased
and biased compression, respectively. Both the proposed methods outperform the
existing compressed FL methods in terms of communication and computation
complexities. Moreover, SCALLION and SCAFCOM accommodates arbitrary data
heterogeneity and do not make any additional assumptions on compression errors.
Experiments show that SCALLION and SCAFCOM can match the performance of
corresponding full-precision FL approaches with substantially reduced uplink
communication, and outperform recent compressed FL methods under the same
communication budget.
