  Due to the communication bottleneck in distributed and federated learning
applications, algorithms using communication compression have attracted
significant attention and are widely used in practice. Moreover, the huge
number, high heterogeneity and limited availability of clients result in high
client-variance. This paper addresses these two issues together by proposing
compressed and client-variance reduced methods COFIG and FRECON. We prove an
$O(\frac{(1+\omega)^{3/2}\sqrt{N}}{S\epsilon^2}+\frac{(1+\omega)N^{2/3}}{S\epsilon^2})$
bound on the number of communication rounds of COFIG in the nonconvex setting,
where $N$ is the total number of clients, $S$ is the number of clients
participating in each round, $\epsilon$ is the convergence error, and $\omega$
is the variance parameter associated with the compression operator. In case of
FRECON, we prove an $O(\frac{(1+\omega)\sqrt{N}}{S\epsilon^2})$ bound on the
number of communication rounds. In the convex setting, COFIG converges within
$O(\frac{(1+\omega)\sqrt{N}}{S\epsilon})$ communication rounds, which, to the
best of our knowledge, is also the first convergence result for compression
schemes that do not communicate with all the clients in each round. We stress
that neither COFIG nor FRECON needs to communicate with all the clients, and
they enjoy the first or faster convergence results for convex and nonconvex
federated learning in the regimes considered. Experimental results point to an
empirical superiority of COFIG and FRECON over existing baselines.
