  Federated learning (FL) is a challenging setting for optimization due to the
heterogeneity of the data across different clients which gives rise to the
client drift phenomenon. In fact, obtaining an algorithm for FL which is
uniformly better than simple centralized training has been a major open problem
thus far. In this work, we propose a general algorithmic framework, Mime, which
i) mitigates client drift and ii) adapts arbitrary centralized optimization
algorithms such as momentum and Adam to the cross-device federated learning
setting. Mime uses a combination of control-variates and server-level
statistics (e.g. momentum) at every client-update step to ensure that each
local update mimics that of the centralized method run on iid data. We prove a
reduction result showing that Mime can translate the convergence of a generic
algorithm in the centralized setting into convergence in the federated setting.
Further, we show that when combined with momentum based variance reduction,
Mime is provably faster than any centralized method--the first such result. We
also perform a thorough experimental exploration of Mime's performance on real
world datasets.
