# On the Privacy-Robustness-Utility Trilemma in Distributed Learning

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 51 of its 80 references that are in the map.
- First posted on arXiv 9 Feb 2023.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Exploiting Unintended Feature Leakage in Collaborative Learning](https://mlsanity.com/paper/1805.04049/) (2018)
- [Opacus: User-Friendly Differential Privacy Library in PyTorch](https://mlsanity.com/paper/2109.12298/) (2021)
- [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)
- [A Little Is Enough: Circumventing Defenses For Distributed Learning](https://mlsanity.com/paper/1902.06156/) (2019)
- [Beyond Inferring Class Representatives: User-Level Privacy Leakage From Federated Learning](https://mlsanity.com/paper/1812.00535/) (2018)
- [Subsampled R'enyi Differential Privacy and Analytical Moments Accountant](https://mlsanity.com/paper/1808.00087/) (2018)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Practical Secure Aggregation for Federated Learning on User-Held Data](https://mlsanity.com/paper/1611.04482/) (2016)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [cpSGD: Communication-efficient and differentially-private distributed SGD](https://mlsanity.com/paper/1805.10559/) (2018)
- [RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets](https://mlsanity.com/paper/1811.03761/) (2018)
- [Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation](https://mlsanity.com/paper/1903.03936/) (2019)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing](https://mlsanity.com/paper/2006.09365/) (2020)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Differentially Private Federated Learning on Heterogeneous Data](https://mlsanity.com/paper/2111.09278/) (2021)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity](https://mlsanity.com/paper/2302.01772/) (2023)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums](https://mlsanity.com/paper/2205.12173/) (2022)

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

- [Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity](https://mlsanity.com/paper/2309.13591/) (2023)
- [The Privacy Power of Correlated Noise in Decentralized Learning](https://mlsanity.com/paper/2405.01031/) (2024)
- [Adaptive Gradient Clipping for Robust Federated Learning](https://mlsanity.com/paper/2405.14432/) (2024)
- [On the Tradeoff between Privacy Preservation and Byzantine-Robustness in Decentralized Learning](https://mlsanity.com/paper/2308.14606/) (2023)
- [Towards Trustworthy Federated Learning with Untrusted Participants](https://mlsanity.com/paper/2505.01874/) (2025)
- [Exactly Minimax-Optimal Locally Differentially Private Sampling](https://mlsanity.com/paper/2410.22699/) (2024)
- [Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers](https://mlsanity.com/paper/2312.12835/) (2023)
- [A survey on secure decentralized optimization and learning](https://mlsanity.com/paper/2408.08628/) (2024)
- [ByzFL: Research Framework for Robust Federated Learning](https://mlsanity.com/paper/2505.24802/) (2025)
- [TernaryVote: Differentially Private, Communication Efficient, and Byzantine Resilient Distributed Optimization on Heterogeneous Data](https://mlsanity.com/paper/2402.10816/) (2024)
- [On the Relevance of Byzantine Robust Optimization Against Data Poisoning](https://mlsanity.com/paper/2405.00491/) (2024)
- [Tight Stability Bounds for Robust Distributed Learning: Byzantine Failures Hurt Generalization More than Data Poisoning](https://mlsanity.com/paper/2506.18020/) (2025)
- [Balancing Privacy, Robustness, and Efficiency in Machine Learning](https://mlsanity.com/paper/2312.14712/) (2023)
- [On the Conflict of Robustness and Learning in Collaborative Machine Learning](https://mlsanity.com/paper/2402.13700/) (2024)
- [Optimized Local Updates in Federated Learning via Reinforcement Learning](https://mlsanity.com/paper/2506.06337/) (2025)
- [Perfect Privacy for Discriminator-Based Byzantine-Resilient Federated Learning](https://mlsanity.com/paper/2506.13561/) (2025)
- [SABLE: Secure And Byzantine robust LEarning](https://mlsanity.com/paper/2309.05395/) (2023)
- [LiD-FL: Towards List-Decodable Federated Learning](https://mlsanity.com/paper/2408.04963/) (2024)
- [Byzantine Outside, Curious Inside: Reconstructing Data Through Malicious Updates](https://mlsanity.com/paper/2506.11413/) (2025)
- [Beyond Trade-offs: A Unified Framework for Privacy, Robustness, and Communication Efficiency in Federated Learning](https://mlsanity.com/paper/2508.12978/) (2025)
- [The Double-Edged Nature of the Rashomon Set for Trustworthy Machine Learning](https://mlsanity.com/paper/2511.21799/) (2025)
- [A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learning](https://mlsanity.com/paper/2605.19813/) (2026)
- [Dangerous Liaisons of Convex Learning and Non-Affine Aggregation](https://mlsanity.com/paper/2606.28123/) (2026)
- [Unveiling the Non-Monotonic Effect of Privacy on Generalization under Byzantine Robustness](https://mlsanity.com/paper/2607.01492/) (2026)

## Abstract (arXiv)

The ubiquity of distributed machine learning (ML) in sensitive public domain applications calls for algorithms that protect data privacy, while being robust to faults and adversarial behaviors. Although privacy and robustness have been extensively studied independently in distributed ML, their synthesis remains poorly understood. We present the first tight analysis of the error incurred by any algorithm ensuring robustness against a fraction of adversarial machines, as well as differential privacy (DP) for honest machines' data against any other curious entity. Our analysis exhibits a fundamental trade-off between privacy, robustness, and utility. To prove our lower bound, we consider the case of mean estimation, subject to distributed DP and robustness constraints, and devise reductions to centralized estimation of one-way marginals. We prove our matching upper bound by presenting a new distributed ML algorithm using a high-dimensional robust aggregation rule. The latter amortizes the dependence on the dimension in the error (caused by adversarial workers and DP), while being agnostic to the statistical properties of the data.