mlsanityData to 7 Oct 2026

Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses

arXiv 2106.09779 ↗First posted 17 Jun 2021cs.LG cs.CR math.OCcited by 30

Not on the map. Why?

Abstract (arXiv)

This paper studies federated learning (FL)--especially cross-silo FL--with data from people who do not trust the server or other silos. In this setting, each silo (e.g. hospital) has data from different people (e.g. patients) and must maintain the privacy of each person's data (e.g. medical record), even if the server or other silos act as adversarial eavesdroppers. This requirement motivates the study of Inter-Silo Record-Level Differential Privacy (ISRL-DP), which requires silos' communications to satisfy record/item-level differential privacy (DP). ISRL-DP ensures that the data of each person (e.g. patient) in silo i (e.g. hospital i) cannot be leaked. ISRL-DP is different from well-studied privacy notions. Central and user-level DP assume that people trust the server/other silos. On the other end of the spectrum, local DP assumes that people do not trust anyone at all (even their own silo). Sitting between central and local DP, ISRL-DP makes the realistic assumption (in cross-silo FL) that people trust their own silo, but not the server or other silos. In this work, we provide tight (up to logarithms) upper and lower bounds for ISRL-DP FL with convex/strongly convex loss functions and homogeneous (i.i.d.) silo data. Remarkably, we show that similar bounds are attainable for smooth losses with arbitrary heterogeneous silo data distributions, via an accelerated ISRL-DP algorithm. We also provide tight upper and lower bounds for ISRL-DP federated empirical risk minimization, and use acceleration to attain the optimal bounds in fewer rounds of communication than the state-of-the-art. Finally, with a secure "shuffler" to anonymize silo messages (but without a trusted server), our algorithm attains the optimal central DP rates under more practical trust assumptions. Numerical experiments show favorable privacy-accuracy tradeoffs for our algorithm in classification and regression tasks.

Key facts. Cited by 30 papers in the map (data through 7 Oct 2026). Builds on 43 of its 94 references that are in the map. First posted on arXiv 17 Jun 2021.

Builds on

43 of 94 references.

References · 43

  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. 2016Deep Learning with Differential Privacycited by 2,682
  4. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  5. 2019Deep Leakage from Gradientscited by 1,004
  6. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  7. 2019Federated Learning with Differential Privacy: Algorithms and Performance Analysiscited by 528
  8. 2017Differentially Private Federated Learning: A Client Level Perspectivecited by 451
  9. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  10. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  11. 2013The Composition Theorem for Differential Privacycited by 290
  12. 2021Federated Learning for Internet of Things: A Comprehensive Surveycited by 247
31 more
  1. 2018A Hybrid Approach to Privacy-Preserving Federated Learningcited by 208
  2. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  3. 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 163
  4. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  5. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  6. 2016Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphscited by 149
  7. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  8. 2020LDP-Fed: Federated Learning with Local Differential Privacycited by 129
  9. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 127
  10. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  11. 2018Distributed Differential Privacy via Shufflingcited by 115
  12. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  13. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  14. 2020Federated Accelerated Stochastic Gradient Descentcited by 85
  15. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  16. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 81
  17. 2018Private Selection from Private Candidatescited by 75
  18. 2020Local Differential Privacy based Federated Learning for Internet of Thingscited by 74
  19. 2019The Privacy Blanket of the Shuffle Modelcited by 73
  20. 2021Learning with User-Level Privacycited by 72
  21. 2017Non-convex Finite-Sum Optimization Via SCSG Methodscited by 61
  22. 2020Wireless Federated Learning with Local Differential Privacycited by 50
  23. 2019Local Differential Privacy for Deep Learningcited by 46
  24. 2018DP-ADMM: ADMM-based Distributed Learning with Differential Privacycited by 41
  25. 2020Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluationcited by 39
  26. 2020Privacy Amplification via Random Check-Inscited by 39
  27. 2020FLAME: Differentially Private Federated Learning in the Shuffle Modelcited by 27
  28. 2019The Value of Collaboration in Convex Machine Learning with Differential Privacycited by 24
  29. 2019The Role of Interactivity in Local Differential Privacycited by 15
  30. 2020Differentially Private ADMM for Convex Distributed Learning: Improved Accuracy via Multi-Step Approximationcited by 8
  31. 2018Customized Local Differential Privacy for Multi-Agent Distributed Optimizationcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 5; 2023: 5; 2024: 8; 2025: 8; 2026: 2.

30 papers.

Sort:

By area:

  1. 2022On Privacy and Personalization in Cross-Silo Federated Learningcited by 36
  2. 2022Shuffle Private Linear Contextual Banditscited by 27
  3. 2022Private Non-Convex Federated Learning Without a Trusted Servercited by 26
  4. 2023On the Privacy-Robustness-Utility Trilemma in Distributed Learningcited by 24
  5. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  6. 2023On Differentially Private Federated Linear Contextual Banditscited by 14
  7. 2021Private Multi-Task Learning: Formulation and Applications to Federated Learningcited by 11
  8. 2024How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimizationcited by 10
  9. 2023ULDP-FL: Federated Learning with Across Silo User-Level Differential Privacycited by 9
  10. 2024Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Lossescited by 8
  11. 2024Cross-silo Federated Learning with Record-level Personalized Differential Privacycited by 7
  12. 2023Theoretically Principled Federated Learning for Balancing Privacy and Utilitycited by 6
18 more
  1. 2021Federated Learning with Heterogeneous Differential Privacycited by 5
  2. 2023Dynamic Privacy Allocation for Locally Differentially Private Federated Learning with Composite Objectivescited by 4
  3. 2024Analyzing Inference Privacy Risks Through Gradients in Machine Learningcited by 4
  4. 2022Private Stochastic Optimization With Large Worst-Case Lipschitz Parametercited by 3
  5. 2024Private and Federated Stochastic Convex Optimization: Efficient Strategies for Centralized Systemscited by 3
  6. 2025Second-Order Convergence in Private Stochastic Non-Convex Optimizationcited by 3
  7. 2025Research in Collaborative Learning Does Not Serve Cross-Silo Federated Learning in Practicecited by 3
  8. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  9. 2024Differentially Private Federated Learning: Servers Trustworthiness, Estimation, and Statistical Inferencecited by 2
  10. 2024Privacy-Preserving Split Learning with Vision Transformers using Patch-Wise Random and Noisy CutMixcited by 2
  11. 2025Federated Learning of Quantile Inference under Local Differential Privacycited by 2
  12. 2025On the Gradient Complexity of Private Optimization with Private Oraclescited by 2
  13. 2024Federated Cubic Regularized Newton Learning with Sparsification-amplified Differential Privacycited by 1
  14. 2025PAUSE: Low-Latency and Privacy-Aware Active User Selection for Federated Learningcited by 1
  15. 2025Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellationcited by 1
  16. 2025On the Inherent Privacy of Zeroth Order Projected Gradient Descentcited by 0
  17. 2026Shuffle and Joint Differential Privacy for Generalized Linear Contextual Banditscited by 0
  18. 2026A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learningcited by 0