  Federated learning encapsulates distributed learning strategies that are
managed by a central unit. Since it relies on using a selected number of agents
at each iteration, and since each agent, in turn, taps into its local data, it
is only natural to study optimal sampling policies for selecting agents and
their data in federated learning implementations. Usually, only uniform
sampling schemes are used. However, in this work, we examine the effect of
importance sampling and devise schemes for sampling agents and data
non-uniformly guided by a performance measure. We find that in schemes
involving sampling without replacement, the performance of the resulting
architecture is controlled by two factors related to data variability at each
agent, and model variability across agents. We illustrate the theoretical
findings with experiments on simulated and real data and show the improvement
in performance that results from the proposed strategies.
