  We consider a standard federated learning (FL) architecture where a group of
clients periodically coordinate with a central server to train a statistical
model. We develop a general algorithmic framework called FedLin to tackle some
of the key challenges intrinsic to FL, namely objective heterogeneity, systems
heterogeneity, and infrequent and imprecise communication. Our framework is
motivated by the observation that under these challenges, various existing FL
algorithms suffer from a fundamental speed-accuracy conflict: they either
guarantee linear convergence but to an incorrect point, or convergence to the
global minimum but at a sub-linear rate, i.e., fast convergence comes at the
expense of accuracy. In contrast, when the clients' local loss functions are
smooth and strongly convex, we show that FedLin guarantees linear convergence
to the global minimum, despite arbitrary objective and systems heterogeneity.
We then establish matching upper and lower bounds on the convergence rate of
FedLin that highlight the effects of intermittent communication. Finally, we
show that FedLin preserves linear convergence rates under aggressive gradient
sparsification, and quantify the effect of the compression level on the
convergence rate. Our work is the first to provide tight linear convergence
rate guarantees, and constitutes the first comprehensive analysis of gradient
sparsification in FL.
