  In federated learning, communication cost is often a critical bottleneck to
scale up distributed optimization algorithms to collaboratively learn a model
from millions of devices with potentially unreliable or limited communication
and heterogeneous data distributions. Two notable trends to deal with the
communication overhead of federated algorithms are gradient compression and
local computation with periodic communication. Despite many attempts,
characterizing the relationship between these two approaches has proven
elusive. We address this by proposing a set of algorithms with periodical
compressed (quantized or sparsified) communication and analyze their
convergence properties in both homogeneous and heterogeneous local data
distribution settings. For the homogeneous setting, our analysis improves
existing bounds by providing tighter convergence rates for both strongly convex
and non-convex objective functions. To mitigate data heterogeneity, we
introduce a local gradient tracking scheme and obtain sharp convergence rates
that match the best-known communication complexities without compression for
convex, strongly convex, and nonconvex settings. We complement our theoretical
results and demonstrate the effectiveness of our proposed methods by several
experiments on real-world datasets.

Machine Learning;Distributed, Parallel, and Cluster Computing;Machine Learning