Understanding Generalization of Federated Learning via Stability:
  Heterogeneity Matters
Zhenyu Sun Xiaochun Niu Ermin Wei
Generalization performance is a key metric in evaluating machine learning
models when applied to real-world applications. Good generalization indicates
the model can predict unseen data correctly when trained under a limited number
of data. Federated learning (FL), which has emerged as a popular distributed
learning framework, allows multiple devices or clients to train a shared model
without violating privacy requirements. While the existing literature has
studied extensively the generalization performances of centralized machine
learning algorithms, similar analysis in the federated settings is either
absent or with very restrictive assumptions on the loss functions. In this
paper, we aim to analyze the generalization performances of federated learning
by means of algorithmic stability, which measures the change of the output
model of an algorithm when perturbing one data point. Three widely-used
algorithms are studied, including FedAvg, SCAFFOLD, and FedProx, under convex
and non-convex loss functions. Our analysis shows that the generalization
performances of models trained by these three algorithms are closely related to
the heterogeneity of clients' datasets as well as the convergence behaviors of
the algorithms. Particularly, in the i.i.d. setting, our results recover the
classical results of stochastic gradient descent (SGD).