# Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 71 references that are in the map.
- First posted on arXiv 6 Jun 2022.

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

- [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)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (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)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Distributed learning of deep neural network over multiple agents](https://mlsanity.com/paper/1810.06060/) (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)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [Stochastic Optimization with Importance Sampling](https://mlsanity.com/paper/1401.2753/) (2014)
- [Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks](https://mlsanity.com/paper/2111.13171/) (2021)
- [Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks](https://mlsanity.com/paper/2006.09313/) (2020)
- [What Do We Mean by Generalization in Federated Learning?](https://mlsanity.com/paper/2110.14216/) (2021)
- [Communication-Efficient Adaptive Federated Learning](https://mlsanity.com/paper/2205.02719/) (2022)
- [Federated Composite Optimization](https://mlsanity.com/paper/2011.08474/) (2020)
- [Information-theoretic generalization bounds for black-box learning algorithms](https://mlsanity.com/paper/2110.01584/) (2021)
- [Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks](https://mlsanity.com/paper/2106.03795/) (2021)
- [Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network](https://mlsanity.com/paper/1909.11274/) (2019)
- [Generalization bounds via distillation](https://mlsanity.com/paper/2104.05641/) (2021)
- [AdaComp : Adaptive Residual Gradient Compression for Data-Parallel Distributed Training](https://mlsanity.com/paper/1712.02679/) (2017)
- [Distributed Variational Representation Learning](https://mlsanity.com/paper/1807.04193/) (2018)
- [GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning](https://mlsanity.com/paper/1909.00047/) (2019)
- [Towards a Unified Information-Theoretic Framework for Generalization](https://mlsanity.com/paper/2111.05275/) (2021)
- [Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms](https://mlsanity.com/paper/2203.02474/) (2022)

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

- [Understanding Generalization of Federated Learning via Stability: Heterogeneity Matters](https://mlsanity.com/paper/2306.03824/) (2023)
- [FedSWA: Improving Generalization in Federated Learning with Highly Heterogeneous Data via Momentum-Based Stochastic Controlled Weight Averaging](https://mlsanity.com/paper/2507.20016/) (2025)
- [More Communication Does Not Result in Smaller Generalization Error in Federated Learning](https://mlsanity.com/paper/2304.12216/) (2023)
- [Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!](https://mlsanity.com/paper/2306.05862/) (2023)
- [Federated PAC-Bayesian Learning on Non-IID data](https://mlsanity.com/paper/2309.06683/) (2023)
- [Generalization in Federated Learning: A Conditional Mutual Information Framework](https://mlsanity.com/paper/2503.04091/) (2025)
- [An Information-Theoretic Analysis for Federated Learning under Concept Drift](https://mlsanity.com/paper/2506.21036/) (2025)
- [Advocating for the Silent: Enhancing Federated Generalization for Non-Participating Clients](https://mlsanity.com/paper/2310.07171/) (2023)
- [Elastic Information Bottleneck](https://mlsanity.com/paper/2311.03955/) (2023)
- [Generalization of Graph Neural Networks through the Lens of Homomorphism](https://mlsanity.com/paper/2403.06079/) (2024)
- [Heterogeneity Matters even More in Distributed Learning: Study from Generalization Perspective](https://mlsanity.com/paper/2503.01598/) (2025)
- [Generalization Bounds for Quantum Learning via R'enyi Divergences](https://mlsanity.com/paper/2505.11025/) (2025)
- [Can We Theoretically Quantify the Impacts of Local Updates on the Generalization Performance of Federated Learning?](https://mlsanity.com/paper/2409.03863/) (2024)
- [Information-Theoretic Analysis of Next-Token Prediction under Markovian Data](https://mlsanity.com/paper/2609.34731/) (2026)

## Abstract (arXiv)

In this paper, we use tools from rate-distortion theory to establish new upper bounds on the generalization error of statistical distributed learning algorithms. Specifically, there are K clients whose individually chosen models are aggregated by a central server. The bounds depend on the compressibility of each client's algorithm while keeping other clients' algorithms un-compressed, and leverage the fact that small changes in each local model change the aggregated model by a factor of only 1/K. Adopting a recently proposed approach by Sefidgaran et al., and extending it suitably to the distributed setting, this enables smaller rate-distortion terms which are shown to translate into tighter generalization bounds. The bounds are then applied to the distributed support vector machines (SVM), suggesting that the generalization error of the distributed setting decays faster than that of the centralized one with a factor of O(log(K)/√K). This finding is validated also experimentally. A similar conclusion is obtained for a multiple-round federated learning setup where each client uses stochastic gradient Langevin dynamics (SGLD).