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

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

## Key facts

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

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

- [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)
- [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)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Federated Learning with Differential Privacy: Algorithms and Performance Analysis](https://mlsanity.com/paper/1911.00222/) (2019)
- [Differentially Private Federated Learning: A Client Level Perspective](https://mlsanity.com/paper/1712.07557/) (2017)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Federated Learning for Internet of Things: A Comprehensive Survey](https://mlsanity.com/paper/2104.07914/) (2021)
- [A Hybrid Approach to Privacy-Preserving Federated Learning](https://mlsanity.com/paper/1812.03224/) (2018)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [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)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [Federated Accelerated Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08950/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [Private Selection from Private Candidates](https://mlsanity.com/paper/1811.07971/) (2018)
- [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 30)

- [On Privacy and Personalization in Cross-Silo Federated Learning](https://mlsanity.com/paper/2206.07902/) (2022)
- [Shuffle Private Linear Contextual Bandits](https://mlsanity.com/paper/2202.05567/) (2022)
- [Private Non-Convex Federated Learning Without a Trusted Server](https://mlsanity.com/paper/2203.06735/) (2022)
- [On the Privacy-Robustness-Utility Trilemma in Distributed Learning](https://mlsanity.com/paper/2302.04787/) (2023)
- [Distributed Differential Privacy in Multi-Armed Bandits](https://mlsanity.com/paper/2206.05772/) (2022)
- [On Differentially Private Federated Linear Contextual Bandits](https://mlsanity.com/paper/2302.13945/) (2023)
- [Private Multi-Task Learning: Formulation and Applications to Federated Learning](https://mlsanity.com/paper/2108.12978/) (2021)
- [How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2402.11173/) (2024)
- [ULDP-FL: Federated Learning with Across Silo User-Level Differential Privacy](https://mlsanity.com/paper/2308.12210/) (2023)
- [Cross-silo Federated Learning with Record-level Personalized Differential Privacy](https://mlsanity.com/paper/2401.16251/) (2024)
- [Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Losses](https://mlsanity.com/paper/2407.09690/) (2024)
- [Theoretically Principled Federated Learning for Balancing Privacy and Utility](https://mlsanity.com/paper/2305.15148/) (2023)
- [Federated Learning with Heterogeneous Differential Privacy](https://mlsanity.com/paper/2110.15252/) (2021)
- [Dynamic Privacy Allocation for Locally Differentially Private Federated Learning with Composite Objectives](https://mlsanity.com/paper/2308.01139/) (2023)
- [Analyzing Inference Privacy Risks Through Gradients in Machine Learning](https://mlsanity.com/paper/2408.16913/) (2024)
- [Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter](https://mlsanity.com/paper/2209.07403/) (2022)
- [Private and Federated Stochastic Convex Optimization: Efficient Strategies for Centralized Systems](https://mlsanity.com/paper/2407.12396/) (2024)
- [Second-Order Convergence in Private Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2505.15647/) (2025)
- [Research in Collaborative Learning Does Not Serve Cross-Silo Federated Learning in Practice](https://mlsanity.com/paper/2510.12595/) (2025)
- [On the Sample Complexity of Differentially Private Policy Optimization](https://mlsanity.com/paper/2510.21060/) (2025)
- [Differentially Private Federated Learning: Servers Trustworthiness, Estimation, and Statistical Inference](https://mlsanity.com/paper/2404.16287/) (2024)
- [Privacy-Preserving Split Learning with Vision Transformers using Patch-Wise Random and Noisy CutMix](https://mlsanity.com/paper/2408.01040/) (2024)
- [Federated Learning of Quantile Inference under Local Differential Privacy](https://mlsanity.com/paper/2509.21800/) (2025)
- [On the Gradient Complexity of Private Optimization with Private Oracles](https://mlsanity.com/paper/2511.13999/) (2025)
- [Federated Cubic Regularized Newton Learning with Sparsification-amplified Differential Privacy](https://mlsanity.com/paper/2408.04315/) (2024)
- [PAUSE: Low-Latency and Privacy-Aware Active User Selection for Federated Learning](https://mlsanity.com/paper/2503.13173/) (2025)
- [Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellation](https://mlsanity.com/paper/2506.02563/) (2025)
- [Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2602.00417/) (2026)
- [On the Inherent Privacy of Zeroth Order Projected Gradient Descent](https://mlsanity.com/paper/2507.05610/) (2025)
- [A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learning](https://mlsanity.com/paper/2605.19813/) (2026)

## 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.