mlsanityData to 7 Oct 2026

Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning

arXiv 2206.02604 ↗First posted 6 Jun 2022stat.ML cs.IT cs.LGcited by 14

Not on the map. Why?

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).

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

Builds on

34 of 71 references.

References · 34

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2019Advances and Open Problems in Federated Learningcited by 3,021
  3. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  4. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,531
  5. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  6. 2020Adaptive Federated Optimizationcited by 1,036
  7. 2019Agnostic Federated Learningcited by 451
  8. 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
  9. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  10. 2018Distributed learning of deep neural network over multiple agentscited by 277
  11. 2018Applied Federated Learning: Improving Google Keyboard Query Suggestionscited by 202
  12. 2019A Survey on Distributed Machine Learningcited by 187
22 more
  1. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
  2. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
  3. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  4. 2014Stochastic Optimization with Importance Samplingcited by 91
  5. 2021Intrinsic Dimension, Persistent Homology and Generalization in Neural Networkscited by 70
  6. 2020Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networkscited by 62
  7. 2021What Do We Mean by Generalization in Federated Learning?cited by 62
  8. 2022Communication-Efficient Adaptive Federated Learningcited by 55
  9. 2020Federated Composite Optimizationcited by 49
  10. 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
  11. 2021Heavy Tails in SGD and Compressibility of Overparametrized Neural Networkscited by 44
  12. 2019Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural networkcited by 39
  13. 2017AdaComp : Adaptive Residual Gradient Compression for Data-Parallel Distributed Trainingcited by 33
  14. 2021Generalization bounds via distillationcited by 33
  15. 2018Distributed Variational Representation Learningcited by 32
  16. 2019GADMM: Fast and Communication Efficient Framework for Distributed Machine Learningcited by 30
  17. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 29
  18. 2022Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithmscited by 22
  19. 2020Information-Theoretic Bounds on the Generalization Error and Privacy Leakage in Federated Learningcited by 20
  20. 2020Near-Tight Margin-Based Generalization Bounds for Support Vector Machinescited by 19
  21. 2021Robustness to Pruning Predicts Generalization in Deep Neural Networkscited by 10
  22. 2021In-Network Learning: Distributed Training and Inference in Networkscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 6; 2024: 2; 2025: 5; 2026: 1.

14 papers.

Sort:

  1. 2023Understanding Generalization of Federated Learning via Stability: Heterogeneity Matterscited by 27
  2. 2025FedSWA: Improving Generalization in Federated Learning with Highly Heterogeneous Data via Momentum-Based Stochastic Controlled Weight Averagingcited by 25
  3. 2023More Communication Does Not Result in Smaller Generalization Error in Federated Learningcited by 10
  4. 2023Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!cited by 8
  5. 2023Federated PAC-Bayesian Learning on Non-IID datacited by 2
  6. 2025Generalization in Federated Learning: A Conditional Mutual Information Frameworkcited by 2
  7. 2025An Information-Theoretic Analysis for Federated Learning under Concept Driftcited by 2
  8. 2023Advocating for the Silent: Enhancing Federated Generalization for Non-Participating Clientscited by 1
  9. 2023Elastic Information Bottleneckcited by 1
  10. 2025Heterogeneity Matters even More in Distributed Learning: Study from Generalization Perspectivecited by 1
  11. 2025Generalization Bounds for Quantum Learning via R'enyi Divergencescited by 1
  12. 2024Generalization of Graph Neural Networks through the Lens of Homomorphismcited by 0
2 more
  1. 2024Can We Theoretically Quantify the Impacts of Local Updates on the Generalization Performance of Federated Learning?cited by 0
  2. 2026Information-Theoretic Analysis of Next-Token Prediction under Markovian Datacited by 0