mlsanityData to 7 Oct 2026

On the Privacy-Robustness-Utility Trilemma in Distributed Learning

arXiv 2302.04787 ↗First posted 9 Feb 2023cs.LG cs.CR cs.DCcited by 24

Not on the map. Why?

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.

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

Builds on

51 of 80 references.

References · 51

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2016Deep Learning with Differential Privacycited by 2,682
  3. 2016Membership Inference Attacks against Machine Learning Modelscited by 2,221
  4. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  5. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 698
  6. 2017Renyi Differential Privacycited by 643
  7. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  8. 2018Exploiting Unintended Feature Leakage in Collaborative Learningcited by 509
  9. 2021Opacus: User-Friendly Differential Privacy Library in PyTorchcited by 375
  10. 2020iDLG: Improved Deep Leakage from Gradientscited by 367
  11. 2017Deep Models Under the GAN: Information Leakage from Collaborative Deep Learningcited by 326
  12. 2019A Little Is Enough: Circumventing Defenses For Distributed Learningcited by 285
38 more
  1. 2018Beyond Inferring Class Representatives: User-Level Privacy Leakage From Federated Learningcited by 242
  2. 2018Subsampled R'enyi Differential Privacy and Analytical Moments Accountantcited by 234
  3. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  4. 2016Practical Secure Aggregation for Federated Learning on User-Held Datacited by 178
  5. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  6. 2018cpSGD: Communication-efficient and differentially-private distributed SGDcited by 157
  7. 2018RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasetscited by 148
  8. 2020Learning from History for Byzantine Robust Optimizationcited by 137
  9. 2019Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulationcited by 136
  10. 2020Byzantine-Robust Learning on Heterogeneous Datasets via Bucketingcited by 125
  11. 2014Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Boundscited by 104
  12. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  13. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 81
  14. 2021Differentially Private Federated Learning on Heterogeneous Datacited by 74
  15. 2021Robust and Differentially Private Mean Estimationcited by 66
  16. 2021Differential privacy and robust statistics in high dimensionscited by 64
  17. 2023Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneitycited by 64
  18. 2022Byzantine Machine Learning Made Easy by Resilient Averaging of Momentumscited by 63
  19. 2020Byzantine-Resilient Non-Convex Stochastic Gradient Descentcited by 56
  20. 2015Between Pure and Approximate Differential Privacycited by 55
  21. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  22. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  23. 2019Differential Privacy-enabled Federated Learning for Sensitive Health Datacited by 44
  24. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  25. 2016Stochastic Heavy Ballcited by 40
  26. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  27. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  28. 2021Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Lossescited by 30
  29. 2020Byzantine-Resilient High-Dimensional Federated Learningcited by 27
  30. 2021Approximate Byzantine Fault-Tolerance in Distributed Optimizationcited by 27
  31. 2022Private Non-Convex Federated Learning Without a Trusted Servercited by 26
  32. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  33. 2019Manipulation Attacks in Local Differential Privacycited by 23
  34. 2020Robust estimation via generalized quasi-gradientscited by 19
  35. 2021Differential Privacy and Byzantine Resilience in SGD: Do They Add Up?cited by 17
  36. 2022On robustness and local differential privacycited by 15
  37. 2022Bridging Differential Privacy and Byzantine-Robustness via Model Aggregationcited by 12
  38. 2021Robust Testing and Estimation under Manipulation Attackscited by 5

50 most cited of 51 All 51 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 8; 2025: 8; 2026: 3.

24 papers.

Sort:

By area:

  1. 2023Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneitycited by 25
  2. 2024The Privacy Power of Correlated Noise in Decentralized Learningcited by 17
  3. 2024Adaptive Gradient Clipping for Robust Federated Learningcited by 10
  4. 2023On the Tradeoff between Privacy Preservation and Byzantine-Robustness in Decentralized Learningcited by 8
  5. 2025Towards Trustworthy Federated Learning with Untrusted Participantscited by 8
  6. 2024Exactly Minimax-Optimal Locally Differentially Private Samplingcited by 5
  7. 2023Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outlierscited by 4
  8. 2024A survey on secure decentralized optimization and learningcited by 4
  9. 2025ByzFL: Research Framework for Robust Federated Learningcited by 3
  10. 2024TernaryVote: Differentially Private, Communication Efficient, and Byzantine Resilient Distributed Optimization on Heterogeneous Datacited by 2
  11. 2024On the Relevance of Byzantine Robust Optimization Against Data Poisoningcited by 2
  12. 2025Tight Stability Bounds for Robust Distributed Learning: Byzantine Failures Hurt Generalization More than Data Poisoningcited by 2
12 more
  1. 2023Balancing Privacy, Robustness, and Efficiency in Machine Learningcited by 1
  2. 2024On the Conflict of Robustness and Learning in Collaborative Machine Learningcited by 1
  3. 2025Optimized Local Updates in Federated Learning via Reinforcement Learningcited by 1
  4. 2023SABLE: Secure And Byzantine robust LEarningcited by 0
  5. 2024LiD-FL: Towards List-Decodable Federated Learningcited by 0
  6. 2025Byzantine Outside, Curious Inside: Reconstructing Data Through Malicious Updatescited by 0
  7. 2025Perfect Privacy for Discriminator-Based Byzantine-Resilient Federated Learningcited by 0
  8. 2025Beyond Trade-offs: A Unified Framework for Privacy, Robustness, and Communication Efficiency in Federated Learningcited by 0
  9. 2025The Double-Edged Nature of the Rashomon Set for Trustworthy Machine Learningcited by 0
  10. 2026A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learningcited by 0
  11. 2026Dangerous Liaisons of Convex Learning and Non-Affine Aggregationcited by 0
  12. 2026Unveiling the Non-Monotonic Effect of Privacy on Generalization under Byzantine Robustnesscited by 0