  Federated learning involves a mixture of centralized and decentralized
processing tasks, where a server regularly selects a sample of the agents and
these in turn sample their local data to compute stochastic gradients for their
learning updates. This process runs continually. The sampling of both agents
and data is generally uniform; however, in this work we consider non-uniform
sampling. We derive optimal importance sampling strategies for both agent and
data selection and show that non-uniform sampling without replacement improves
the performance of the original FedAvg algorithm. We run experiments on a
regression and classification problem to illustrate the theoretical results.
