  Federated learning (FL) is a distributed machine learning architecture that
leverages a large number of workers to jointly learn a model with decentralized
data. FL has received increasing attention in recent years thanks to its data
privacy protection, communication efficiency and a linear speedup for
convergence in training (i.e., convergence performance increases linearly with
respect to the number of workers). However, existing studies on linear speedup
for convergence are only limited to the assumptions of i.i.d. datasets across
workers and/or full worker participation, both of which rarely hold in
practice. So far, it remains an open question whether or not the linear speedup
for convergence is achievable under non-i.i.d. datasets with partial worker
participation in FL. In this paper, we show that the answer is affirmative.
Specifically, we show that the federated averaging (FedAvg) algorithm (with
two-sided learning rates) on non-i.i.d. datasets in non-convex settings
achieves a convergence rate $\mathcal{O}(\frac{1}{\sqrt{mKT}} + \frac{1}{T})$
for full worker participation and a convergence rate
$\mathcal{O}(\frac{\sqrt{K}}{\sqrt{nT}} + \frac{1}{T})$ for partial worker
participation, where $K$ is the number of local steps, $T$ is the number of
total communication rounds, $m$ is the total worker number and $n$ is the
worker number in one communication round if for partial worker participation.
Our results also reveal that the local steps in FL could help the convergence
and show that the maximum number of local steps can be improved to $T/m$ in
full worker participation. We conduct extensive experiments on MNIST and
CIFAR-10 to verify our theoretical results.
