  Federated learning is a powerful paradigm for large-scale machine learning,
but it faces significant challenges due to unreliable network connections, slow
communication, and substantial data heterogeneity across clients. FedAvg and
SCAFFOLD are two prominent algorithms to address these challenges. In
particular, FedAvg employs multiple local updates before communicating with a
central server, while SCAFFOLD maintains a control variable on each client to
compensate for ``client drift'' in its local updates. Various methods have been
proposed to enhance the convergence of these two algorithms, but they either
make impractical adjustments to the algorithmic structure or rely on the
assumption of bounded data heterogeneity.
  This paper explores the utilization of momentum to enhance the performance of
FedAvg and SCAFFOLD. When all clients participate in the training process, we
demonstrate that incorporating momentum allows FedAvg to converge without
relying on the assumption of bounded data heterogeneity even using a constant
local learning rate. This is novel and fairly surprising as existing analyses
for FedAvg require bounded data heterogeneity even with diminishing local
learning rates. In partial client participation, we show that momentum enables
SCAFFOLD to converge provably faster without imposing any additional
assumptions. Furthermore, we use momentum to develop new variance-reduced
extensions of FedAvg and SCAFFOLD, which exhibit state-of-the-art convergence
rates. Our experimental results support all theoretical findings.
