  Federated Learning (FL) refers to the paradigm where multiple worker nodes
(WNs) build a joint model by using local data. Despite extensive research, for
a generic non-convex FL problem, it is not clear, how to choose the WNs' and
the server's update directions, the minibatch sizes, and the local update
frequency, so that the WNs use the minimum number of samples and communication
rounds to achieve the desired solution. This work addresses the above question
and considers a class of stochastic algorithms where the WNs perform a few
local updates before communication. We show that when both the WN's and the
server's directions are chosen based on a stochastic momentum estimator, the
algorithm requires $\tilde{\mathcal{O}}(\epsilon^{-3/2})$ samples and
$\tilde{\mathcal{O}}(\epsilon^{-1})$ communication rounds to compute an
$\epsilon$-stationary solution. To the best of our knowledge, this is the first
FL algorithm that achieves such {\it near-optimal} sample and communication
complexities simultaneously. Further, we show that there is a trade-off curve
between local update frequencies and local minibatch sizes, on which the above
sample and communication complexities can be maintained. Finally, we show that
for the classical FedAvg (a.k.a. Local SGD, which is a momentum-less special
case of the STEM), a similar trade-off curve exists, albeit with worse sample
and communication complexities. Our insights on this trade-off provides
guidelines for choosing the four important design elements for FL algorithms,
the update frequency, directions, and minibatch sizes to achieve the best
performance.
