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

Andrew Lowy, Meisam Razaviyayn

TL;DR

This paper introduces a new privacy framework for federated learning called Inter-Silo Record-Level Differential Privacy (ISRL-DP). Designed for scenarios where organizations (like hospitals) want to collaborate without trusting a central server, this framework combines differential privacy with Nesterov acceleration. The authors provide the first "tight" mathematical bounds for this setting, proving that high accuracy and strong privacy are achievable even when data is messy and distributed across untrusted silos.

The Trust Gap in Federated Learning

Federated Learning (FL) was born from the idea that data should stay local. However, simply keeping data on a local device isn't enough; the model updates themselves can leak sensitive information.

Cross-silo federated learning setup with adversaries

Existing privacy solutions usually fall into two extremes:

  1. Central DP (CDP): Assumes complete trust in the central server. If the server is compromised, everyone's privacy is gone.
  2. Local DP (LDP): Assumes you trust no one, not even your own device. While highly secure, it adds so much noise that the resulting model is often uselessly inaccurate.

The authors identify a massive gap in "cross-silo" FL—imagine several hospitals collaborating to train a cancer detection model. Patients trust their own hospital, but they don't necessarily trust the other hospitals or the cloud server coordinating the training.

Trust assumptions across different privacy models

This paper formalizes this "middle ground" trust model through ISRL-DP and develops algorithms that are both private and mathematically optimal.

Methods: Acceleration and Shuffling

The researchers propose a suite of algorithms based on Noisy Distributed Minibatch SGD. Their key innovation is the use of Nesterov Acceleration within a private framework.

  • ISRL-DP Definition: They formalize a privacy notion where each silo ensures its communications are differentially private at the record level. This protects individual patients even if the server and all other hospitals are malicious eavesdroppers.
  • Acceleration: While acceleration is standard in optimization, applying it to private, heterogeneous (non-i.i.d.) data is non-trivial. The authors show that acceleration is actually required to reach optimal error rates when data distributions vary significantly between silos.
  • The Shuffle Model: They demonstrate that by using a "secure shuffler"—an intermediary that anonymizes and permutes messages—they can achieve the high accuracy of Central DP without actually needing a trusted central server.

Key Insights and Ideas

  • "Privacy for Free": The paper proves that if your dataset is large enough relative to the number of features ($d \ll n\epsilon^2$), you can achieve the same accuracy as a non-private model. Privacy doesn't always have to come at the cost of utility.
  • Acceleration is a Necessity, Not an Option: In the presence of heterogeneous data (where one hospital's patients look very different from another's), standard SGD hits a "privacy wall." Acceleration allows the algorithm to navigate this noise more effectively, reaching lower error rates in fewer communication rounds.
  • Bridging the Trust Gap: The "Shuffle Model" results are a major breakthrough. They prove that you don't need to choose between the high risk of a trusted server and the low accuracy of local privacy; a simple anonymization step (shuffling) can give you the best of both worlds.

Empirical and Theoretical Results

The authors validated their theoretical findings using three distinct tasks: MNIST (binary logistic regression across 25 silos), Health Insurance Data (linear regression to predict medical charges), and an Obesity Dataset (7-way softmax regression).

  • Theoretical Optimality: The authors provide "tight" upper and lower bounds, meaning they have mathematically proven the absolute best performance possible under these privacy constraints for convex loss functions.
  • Empirical Gains: In head-to-head tests, their ISRL-DP MB-SGD algorithm outperformed standard "Local SGD" (a common FL baseline) by 10% to 30% in accuracy across various privacy levels.
  • Communication Efficiency: By using their accelerated "One-Pass" algorithm, they achieved state-of-the-art accuracy in significantly fewer communication rounds than previous methods.

Limitations and Future Work

  • Convexity Constraints: The current mathematical proofs and optimal rates apply to convex loss functions (like logistic and linear regression). Extending these optimal bounds to non-convex deep learning models remains an open challenge.
  • Parameter Tuning: The algorithms require knowledge of the "Lipschitz constant" (a measure of how much the model changes with a small change in data) to calibrate noise. In practice, estimating this accurately without a trusted server can be difficult.
  • The Shuffler Assumption: While the shuffle model removes the need for a trusted server, it introduces the need for a secure shuffler. Finding the most practical, decentralized way to implement this shuffler is a suggested path for future engineering.

Summary updated

Abstract

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 silo $i$’s 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.
BibTeX
@inproceedings{lowy2023private,
  author = {Andrew Lowy and Meisam Razaviyayn},
  title = {{Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=TVY6GoURrw},
}
Figure