  A widely recognized difficulty in federated learning arises from the
statistical heterogeneity among clients: local datasets often come from
different but not entirely unrelated distributions, and personalization is,
therefore, necessary to achieve optimal results from each individual's
perspective. In this paper, we show how the excess risks of personalized
federated learning with a smooth, strongly convex loss depend on data
heterogeneity from a minimax point of view. Our analysis reveals a surprising
theorem of the alternative for personalized federated learning: there exists a
threshold such that (a) if a certain measure of data heterogeneity is below
this threshold, the FedAvg algorithm [McMahan et al., 2017] is minimax optimal;
(b) when the measure of heterogeneity is above this threshold, then doing pure
local training (i.e., clients solve empirical risk minimization problems on
their local datasets without any communication) is minimax optimal. As an
implication, our results show that the presumably difficult
(infinite-dimensional) problem of adapting to client-wise heterogeneity can be
reduced to a simple binary decision problem of choosing between the two
baseline algorithms. Our analysis relies on a new notion of algorithmic
stability that takes into account the nature of federated learning.
