# No Free Lunch Theorem for Security and Utility in Federated Learning

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 93 references that are in the map.
- First posted on arXiv 11 Mar 2022.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [A Style-Based Generator Architecture for Generative Adversarial Networks](https://mlsanity.com/paper/1812.04948/) (2018)
- [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)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [Pre-Trained Image Processing Transformer](https://mlsanity.com/paper/2012.00364/) (2020)
- [Inverting Gradients -- How easy is it to break privacy in federated learning?](https://mlsanity.com/paper/2003.14053/) (2020)
- [Unified Language Model Pre-training for Natural Language Understanding and Generation](https://mlsanity.com/paper/1905.03197/) (2019)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [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)
- [iDLG: Improved Deep Leakage from Gradients](https://mlsanity.com/paper/2001.02610/) (2020)
- [Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning](https://mlsanity.com/paper/1702.07464/) (2017)
- [See through Gradients: Image Batch Recovery via GradInversion](https://mlsanity.com/paper/2104.07586/) (2021)
- [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)
- [Beyond Inferring Class Representatives: User-Level Privacy Leakage From Federated Learning](https://mlsanity.com/paper/1812.00535/) (2018)
- [Rethinking Lossy Compression: The Rate-Distortion-Perception Tradeoff](https://mlsanity.com/paper/1901.07821/) (2019)
- [A Hybrid Approach to Privacy-Preserving Federated Learning](https://mlsanity.com/paper/1812.03224/) (2018)
- [SecureBoost: A Lossless Federated Learning Framework](https://mlsanity.com/paper/1901.08755/) (2019)
- [On the Convergence of Local Descent Methods in Federated Learning](https://mlsanity.com/paper/1910.14425/) (2019)
- [LDP-Fed: Federated Learning with Local Differential Privacy](https://mlsanity.com/paper/2006.03637/) (2020)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Deep Learning with Gaussian Differential Privacy](https://mlsanity.com/paper/1911.11607/) (2019)
- [Local Differential Privacy based Federated Learning for Internet of Things](https://mlsanity.com/paper/2004.08856/) (2020)

## Built on by (most cited first, 30 of 39)

- [Differentially Private Diffusion Models Generate Useful Synthetic Images](https://mlsanity.com/paper/2302.13861/) (2023)
- [Federated Continual Learning via Knowledge Fusion: A Survey](https://mlsanity.com/paper/2312.16475/) (2023)
- [A Survey on Heterogeneous Federated Learning](https://mlsanity.com/paper/2210.04505/) (2022)
- [Trading Off Privacy, Utility and Efficiency in Federated Learning](https://mlsanity.com/paper/2209.00230/) (2022)
- [Grounding Foundation Models through Federated Transfer Learning: A General Framework](https://mlsanity.com/paper/2311.17431/) (2023)
- [Ten Challenging Problems in Federated Foundation Models](https://mlsanity.com/paper/2502.12176/) (2025)
- [A Survey for Federated Learning Evaluations: Goals and Measures](https://mlsanity.com/paper/2308.11841/) (2023)
- [Privacy-preserving quantum federated learning via gradient hiding](https://mlsanity.com/paper/2312.04447/) (2023)
- [Vertical Federated Learning for Effectiveness, Security, Applicability: A Survey](https://mlsanity.com/paper/2405.17495/) (2024)
- [No Free Lunch Theorem for Privacy-Preserving LLM Inference](https://mlsanity.com/paper/2405.20681/) (2024)
- [Optimizing Privacy, Utility and Efficiency in Constrained Multi-Objective Federated Learning](https://mlsanity.com/paper/2305.00312/) (2023)
- [Advances in Robust Federated Learning: A Survey with Heterogeneity Considerations](https://mlsanity.com/paper/2405.09839/) (2024)
- [FedProK: Trustworthy Federated Class-Incremental Learning via Prototypical Feature Knowledge Transfer](https://mlsanity.com/paper/2405.02685/) (2024)
- [Clients Collaborate: Flexible Differentially Private Federated Learning with Guaranteed Improvement of Utility-Privacy Trade-off](https://mlsanity.com/paper/2402.07002/) (2024)
- [Universal Adversarial Backdoor Attacks to Fool Vertical Federated Learning in Cloud-Edge Collaboration](https://mlsanity.com/paper/2304.11432/) (2023)
- [Towards Achieving Near-optimal Utility for Privacy-Preserving Federated Learning via Data Generation and Parameter Distortion](https://mlsanity.com/paper/2305.04288/) (2023)
- [Theoretically Principled Federated Learning for Balancing Privacy and Utility](https://mlsanity.com/paper/2305.15148/) (2023)
- [A Meta-learning Framework for Tuning Parameters of Protection Mechanisms in Trustworthy Federated Learning](https://mlsanity.com/paper/2305.18400/) (2023)
- [A Survey on Contribution Evaluation in Vertical Federated Learning](https://mlsanity.com/paper/2405.02364/) (2024)
- [Probably Approximately Correct Federated Learning](https://mlsanity.com/paper/2304.04641/) (2023)
- [HiFGL: A Hierarchical Framework for Cross-silo Cross-device Federated Graph Learning](https://mlsanity.com/paper/2406.10616/) (2024)
- [Federated Learning for Metaverse: A Survey](https://mlsanity.com/paper/2303.17987/) (2023)
- [Faster Convergence on Heterogeneous Federated Edge Learning: An Adaptive Clustered Data Sharing Approach](https://mlsanity.com/paper/2406.09776/) (2024)
- [A Game-theoretic Framework for Privacy-preserving Federated Learning](https://mlsanity.com/paper/2304.05836/) (2023)
- [Practical Privacy-Preserving Gaussian Process Regression via Secret Sharing](https://mlsanity.com/paper/2306.14498/) (2023)
- [Theoretical Analysis of Privacy Leakage in Trustworthy Federated Learning: A Perspective from Linear Algebra and Optimization Theory](https://mlsanity.com/paper/2407.16735/) (2024)
- [A Theoretical Analysis of Efficiency Constrained Utility-Privacy Bi-Objective Optimization in Federated Learning](https://mlsanity.com/paper/2312.16554/) (2023)
- [Bridging Privacy and Robustness for Trustworthy Machine Learning](https://mlsanity.com/paper/2403.16591/) (2024)
- [Personalized Recommendation Models in Federated Settings: A Survey](https://mlsanity.com/paper/2504.07101/) (2025)
- [Feedback Lunch: Learned Feedback Codes for Secure Communications](https://mlsanity.com/paper/2510.16620/) (2025)

## Abstract (arXiv)

In a federated learning scenario where multiple parties jointly learn a model from their respective data, there exist two conflicting goals for the choice of appropriate algorithms. On one hand, private and sensitive training data must be kept secure as much as possible in the presence of textitsemi-honest partners, while on the other hand, a certain amount of information has to be exchanged among different parties for the sake of learning utility. Such a challenge calls for the privacy-preserving federated learning solution, which maximizes the utility of the learned model and maintains a provable privacy guarantee of participating parties' private data. This article illustrates a general framework that a) formulates the trade-off between privacy loss and utility loss from a unified information-theoretic point of view, and b) delineates quantitative bounds of privacy-utility trade-off when different protection mechanisms including Randomization, Sparsity, and Homomorphic Encryption are used. It was shown that in general textitthere is no free lunch for the privacy-utility trade-off and one has to trade the preserving of privacy with a certain degree of degraded utility. The quantitative analysis illustrated in this article may serve as the guidance for the design of practical federated learning algorithms.