# Probably Approximately Correct Federated Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 97 references that are in the map.
- First posted on arXiv 10 Apr 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Federated Learning for Mobile Keyboard Prediction](https://mlsanity.com/paper/1811.03604/) (2018)
- [Differentially Private Federated Learning: A Client Level Perspective](https://mlsanity.com/paper/1712.07557/) (2017)
- [Federated Machine Learning: Concept and Applications](https://mlsanity.com/paper/1902.04885/) (2019)
- [SplitFed: When Federated Learning Meets Split Learning](https://mlsanity.com/paper/2004.12088/) (2020)
- [Distributed learning of deep neural network over multiple agents](https://mlsanity.com/paper/1810.06060/) (2018)
- [Federated Evaluation of On-device Personalization](https://mlsanity.com/paper/1910.10252/) (2019)
- [LDP-Fed: Federated Learning with Local Differential Privacy](https://mlsanity.com/paper/2006.03637/) (2020)
- [Learning the Pareto Front with Hypernetworks](https://mlsanity.com/paper/2010.04104/) (2020)
- [Adversarial Examples Make Strong Poisons](https://mlsanity.com/paper/2106.10807/) (2021)
- [R-GAP: Recursive Gradient Attack on Privacy](https://mlsanity.com/paper/2010.07733/) (2020)
- [Breaking the Communication-Privacy-Accuracy Trilemma](https://mlsanity.com/paper/2007.11707/) (2020)
- [Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization](https://mlsanity.com/paper/2006.04655/) (2020)
- [Multi-objective Evolutionary Federated Learning](https://mlsanity.com/paper/1812.07478/) (2018)
- [Towards General Deep Leakage in Federated Learning](https://mlsanity.com/paper/2110.09074/) (2021)
- [One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning](https://mlsanity.com/paper/2103.03228/) (2021)
- [No Free Lunch Theorem for Security and Utility in Federated Learning](https://mlsanity.com/paper/2203.05816/) (2022)
- [Trading Off Privacy, Utility and Efficiency in Federated Learning](https://mlsanity.com/paper/2209.00230/) (2022)
- [PAC-learning in the presence of evasion adversaries](https://mlsanity.com/paper/1806.01471/) (2018)
- [Improved Algorithms for Collaborative PAC Learning](https://mlsanity.com/paper/1805.08356/) (2018)
- [A Theory of Multiple-Source Adaptation with Limited Target Labeled Data](https://mlsanity.com/paper/2007.09762/) (2020)

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

- [Federated PAC-Bayesian Learning on Non-IID data](https://mlsanity.com/paper/2309.06683/) (2023)
- [Federated Learning with Nonvacuous Generalisation Bounds](https://mlsanity.com/paper/2310.11203/) (2023)
- [A Unified Learn-to-Distort-Data Framework for Privacy-Utility Trade-off in Trustworthy Federated Learning](https://mlsanity.com/paper/2407.04751/) (2024)
- [FedEM: A Privacy-Preserving Framework for Concurrent Utility Preservation in Federated Learning](https://mlsanity.com/paper/2503.06021/) (2025)

## Abstract (arXiv)

Federated learning (FL) is a new distributed learning paradigm, with privacy, utility, and efficiency as its primary pillars. Existing research indicates that it is unlikely to simultaneously attain infinitesimal privacy leakage, utility loss, and efficiency. Therefore, how to find an optimal trade-off solution is the key consideration when designing the FL algorithm. One common way is to cast the trade-off problem as a multi-objective optimization problem, i.e., the goal is to minimize the utility loss and efficiency reduction while constraining the privacy leakage not exceeding a predefined value. However, existing multi-objective optimization frameworks are very time-consuming, and do not guarantee the existence of the Pareto frontier, this motivates us to seek a solution to transform the multi-objective problem into a single-objective problem because it is more efficient and easier to be solved. To this end, we propose FedPAC, a unified framework that leverages PAC learning to quantify multiple objectives in terms of sample complexity, such quantification allows us to constrain the solution space of multiple objectives to a shared dimension, so that it can be solved with the help of a single-objective optimization algorithm. Specifically, we provide the results and detailed analyses of how to quantify the utility loss, privacy leakage, privacy-utility-efficiency trade-off, as well as the cost of the attacker from the PAC learning perspective.