Federated Learning You May Communicate Less Often!
Milad Sefidgaran Romain Chor Abdellatif Zaidi Yijun Wan
We investigate the generalization error of statistical learning models in a
Federated Learning (FL) setting. Specifically, we study the evolution of the
generalization error with the number of communication rounds between the
clients and the parameter server, i.e., the effect on the generalization error
of how often the local models as computed by the clients are aggregated at the
parameter server. We establish PAC-Bayes and rate-distortion theoretic bounds
on the generalization error that account explicitly for the effect of the
number of rounds, say $ R \in \mathbb{N}$, in addition to the number of
participating devices $K$ and individual datasets size $n$. The bounds, which
apply in their generality for a large class of loss functions and learning
algorithms, appear to be the first of their kind for the FL setting.
Furthermore, we apply our bounds to FL-type Support Vector Machines (FSVM); and
we derive (more) explicit bounds on the generalization error in this case. In
particular, we show that the generalization error of FSVM increases with $R$,
suggesting that more frequent communication with the parameter server
diminishes the generalization power of such learning algorithms. Combined with
that the empirical risk generally decreases for larger values of $R$, this
indicates that $R$ might be a parameter to optimize in order to minimize the
population risk of FL algorithms. Moreover, specialized to the case $R=1$
(sometimes referred to as "one-shot" FL or distributed learning) our bounds
suggest that the generalization error of the FL setting decreases faster than
that of centralized learning by a factor of $\mathcal{O}(\sqrt{\log(K)/K})$,
thereby generalizing recent findings in this direction to arbitrary loss
functions and algorithms. The results of this paper are also validated on some
experiments.