# Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!

arXiv: https://arxiv.org/abs/2306.05862 · HTML: https://mlsanity.com/paper/2306.05862/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 64 references that are in the map.
- First posted on arXiv 9 Jun 2023.

## Builds on (most cited first, 30 of 37)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Adaptive Federated Optimization](https://mlsanity.com/paper/2003.00295/) (2020)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Federated Learning with Differential Privacy: Algorithms and Performance Analysis](https://mlsanity.com/paper/1911.00222/) (2019)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [A Hybrid Approach to Privacy-Preserving Federated Learning](https://mlsanity.com/paper/1812.03224/) (2018)
- [Applied Federated Learning: Improving Google Keyboard Query Suggestions](https://mlsanity.com/paper/1812.02903/) (2018)
- [A Survey on Distributed Machine Learning](https://mlsanity.com/paper/1912.09789/) (2019)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Tighter risk certificates for neural networks](https://mlsanity.com/paper/2007.12911/) (2020)
- [Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization](https://mlsanity.com/paper/1910.13598/) (2019)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization](https://mlsanity.com/paper/2211.13609/) (2022)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Federated Composite Optimization](https://mlsanity.com/paper/2011.08474/) (2020)
- [Distributed Variational Representation Learning](https://mlsanity.com/paper/1807.04193/) (2018)
- [On the Information Bottleneck Problems: Models, Connections, Applications and Information Theoretic Views](https://mlsanity.com/paper/2002.00008/) (2020)
- [PAC-Bayes Information Bottleneck](https://mlsanity.com/paper/2109.14509/) (2021)
- [Why (and When) does Local SGD Generalize Better than SGD?](https://mlsanity.com/paper/2303.01215/) (2023)
- [Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms](https://mlsanity.com/paper/2203.02474/) (2022)
- [Online PAC-Bayes Learning](https://mlsanity.com/paper/2206.00024/) (2022)
- [Information-Theoretic Bounds on the Generalization Error and Privacy Leakage in Federated Learning](https://mlsanity.com/paper/2005.02503/) (2020)
- [Near-Tight Margin-Based Generalization Bounds for Support Vector Machines](https://mlsanity.com/paper/2006.02175/) (2020)
- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [Communication-Efficient Online Federated Learning Framework for Nonlinear Regression](https://mlsanity.com/paper/2110.06556/) (2021)
- [Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning](https://mlsanity.com/paper/2206.02604/) (2022)
- [Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Covers](https://mlsanity.com/paper/2209.08951/) (2022)

## Built on by (most cited first, 8 of 8)

- [Differentiated Aggregation to Improve Generalization in Federated Learning](https://mlsanity.com/paper/2404.11754/) (2024)
- [Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis](https://mlsanity.com/paper/2501.04443/) (2025)
- [Generalization in Federated Learning: A Conditional Mutual Information Framework](https://mlsanity.com/paper/2503.04091/) (2025)
- [Heterogeneity Matters even More in Distributed Learning: Study from Generalization Perspective](https://mlsanity.com/paper/2503.01598/) (2025)
- [FedFACT: A Provable Framework for Controllable Group-Fairness Calibration in Federated Learning](https://mlsanity.com/paper/2506.03777/) (2025)
- [FedSDWC: Federated Synergistic Dual-Representation Weak Causal Learning for OOD](https://mlsanity.com/paper/2511.09036/) (2025)
- [Scaling Law Analysis in Federated Learning: How to Select the Optimal Model Size?](https://mlsanity.com/paper/2511.12188/) (2025)
- [Information-Theoretic Analysis of Next-Token Prediction under Markovian Data](https://mlsanity.com/paper/2609.34731/) (2026)

## Abstract (arXiv)

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 R between K clients and a parameter server (PS), i.e., the effect on the generalization error of how often the clients' local models are aggregated at PS. In our setup, the more the clients communicate with PS the less data they use for local training in each round, such that the amount of training data per client is identical for distinct values of R. We establish PAC-Bayes and rate-distortion theoretic bounds on the generalization error that account explicitly for the effect of the number of rounds R, in addition to the number of participating devices K and individual datasets size n. The bounds, which apply to 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 derive (more) explicit bounds in this case. In particular, we show that the generalization bound of FSVM increases with R, suggesting that more frequent communication with PS diminishes the generalization power. This implies that the population risk decreases less fast with R than does the empirical risk. Moreover, our bound suggests that the generalization error of FSVM decreases faster than that of centralized learning by a factor of O(√log(K)/K). Finally, we provide experimental results obtained using neural networks (ResNet-56) which show evidence that not only may our observations for FSVM hold more generally but also that the population risk may even start to increase beyond some value of R.