# Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Losses

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 46 references that are in the map.
- First posted on arXiv 12 Jul 2024.

## Builds on (most cited first, 29 of 29)

- [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 Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [Federated Learning for Mobile Keyboard Prediction](https://mlsanity.com/paper/1811.03604/) (2018)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Differentially Private Federated Learning: A Client Level Perspective](https://mlsanity.com/paper/1712.07557/) (2017)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Differentially Private Federated Learning on Heterogeneous Data](https://mlsanity.com/paper/2111.09278/) (2021)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Recovering Private Text in Federated Learning of Language Models](https://mlsanity.com/paper/2205.08514/) (2022)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [Scaling Federated Learning for Fine-tuning of Large Language Models](https://mlsanity.com/paper/2102.00875/) (2021)
- [On Privacy and Personalization in Cross-Silo Federated Learning](https://mlsanity.com/paper/2206.07902/) (2022)
- [Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses](https://mlsanity.com/paper/2106.09779/) (2021)
- [Private Non-Convex Federated Learning Without a Trusted Server](https://mlsanity.com/paper/2203.06735/) (2022)
- [Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization](https://mlsanity.com/paper/2206.00363/) (2022)
- [Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps](https://mlsanity.com/paper/2103.15352/) (2021)
- [Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems](https://mlsanity.com/paper/2104.02988/) (2021)
- [Stochastic Differentially Private and Fair Learning](https://mlsanity.com/paper/2210.08781/) (2022)
- [On Differentially Private Federated Linear Contextual Bandits](https://mlsanity.com/paper/2302.13945/) (2023)
- [How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2402.11173/) (2024)
- [Differentially private cross-silo federated learning](https://mlsanity.com/paper/2007.05553/) (2020)
- [On Private and Robust Bandits](https://mlsanity.com/paper/2302.02526/) (2023)
- [Differentially Private Optimization for Smooth Nonconvex ERM](https://mlsanity.com/paper/2302.04972/) (2023)

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

- [Faster Algorithms for User-Level Private Stochastic Convex Optimization](https://mlsanity.com/paper/2410.18391/) (2024)
- [Second-Order Convergence in Private Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2505.15647/) (2025)
- [On the Sample Complexity of Differentially Private Policy Optimization](https://mlsanity.com/paper/2510.21060/) (2025)
- [Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellation](https://mlsanity.com/paper/2506.02563/) (2025)
- [Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates](https://mlsanity.com/paper/2506.12994/) (2025)
- [High-Dimensional Differentially Private Quantile Regression: Distributed Estimation and Statistical Inference](https://mlsanity.com/paper/2508.05212/) (2025)
- [A Stochastic Optimization Framework for Private and Fair Learning From Decentralized Data](https://mlsanity.com/paper/2411.07889/) (2024)
- [On the Inherent Privacy of Zeroth Order Projected Gradient Descent](https://mlsanity.com/paper/2507.05610/) (2025)

## Abstract (arXiv)

We revisit the problem of federated learning (FL) with private data from people who do not trust the server or other silos/clients. In this context, every silo (e.g. hospital) has data from several people (e.g. patients) and needs to protect the privacy of each person's data (e.g. health records), even if the server and/or other silos try to uncover this data. Inter-Silo Record-Level Differential Privacy (ISRL-DP) prevents each silo's data from being leaked, by requiring that silo i's communications satisfy item-level differential privacy. Prior work arXiv:2106.09779 characterized the optimal excess risk bounds for ISRL-DP algorithms with homogeneous (i.i.d.) silo data and convex loss functions. However, two important questions were left open: (1) Can the same excess risk bounds be achieved with heterogeneous (non-i.i.d.) silo data? (2) Can the optimal risk bounds be achieved with fewer communication rounds? In this paper, we give positive answers to both questions. We provide novel ISRL-DP FL algorithms that achieve the optimal excess risk bounds in the presence of heterogeneous silo data. Moreover, our algorithms are more communication-efficient than the prior state-of-the-art. For smooth loss functions, our algorithm achieves the optimal excess risk bound and has communication complexity that matches the non-private lower bound. Additionally, our algorithms are more computationally efficient than the previous state-of-the-art.