Abstract
This paper studies the problem of federated learning (FL) in the absence of a trustworthy server/clients. In this setting, each client needs to ensure the privacy of its own data, even if the server or other clients act adversarially. This requirement motivates the study of local differential privacy (LDP) at the client level. We provide tight (up to logarithms) upper and lower bounds for LDP convex/strongly convex federated stochastic optimization with homogeneous (i.i.d.) client data. The LDP rates match the optimal statistical rates in certain practical parameter regimes ("privacy for free"). Remarkably, we show that similar rates are attainable for smooth losses with arbitrary heterogeneous client data distributions, via a linear-time accelerated LDP algorithm. We also provide tight upper and lower bounds for LDP federated empirical risk minimization (ERM). Finally, with a secure "shuffler" to anonymize client reports (but without the presence of a trusted server), our algorithm attains the optimal central differentially private rates for stochastic convex/strongly convex optimization. Numerical experiments validate our theory and show favorable privacy-accuracy tradeoffs for our algorithm.
Introduction: The Trust Spectrum in Federated Learning
Federated Learning (FL) was designed to keep data local, but simply keeping data on a device is insufficient to prevent privacy leaks; model updates themselves can reveal sensitive information. Existing Differential Privacy (DP) solutions usually fall into two extremes: Central DP (CDP), which assumes a "trusted server," and Local DP (LDP), which assumes no one is trusted.
This paper identifies a missing middle ground: cross-silo FL. In this scenario, individuals (e.g., patients) trust their local organization (a hospital silo), but these organizations do not trust the central aggregator or each other. The authors define Inter-Silo Record-Level Differential Privacy (ISRL-DP) to address this, requiring that any communication leaving a silo must be differentially private relative to the individual records within that silo.
Methods: Bridging the Gap with Acceleration
To achieve optimal performance under ISRL-DP, the researchers propose and analyze several algorithms:
- Noisy Distributed Minibatch SGD (MB-SGD): A baseline where silos compute gradients, add Gaussian noise, and send them to the server.
- One-Pass Accelerated Noisy MB-SGD: The paper's primary algorithm. It uses Nesterov-style acceleration to speed up convergence. Crucially, this algorithm handles heterogeneous data (where different silos have different data distributions) remarkably well, nearly matching the performance of the simpler i.i.d. case.
- The Shuffler Model: The authors demonstrate that by adding a "secure shuffler" to anonymize updates, they can achieve the high accuracy of Central DP without needing a trusted central server.
Theoretical Results and Tight Bounds
A core contribution of this work is the establishment of "tight" theoretical bounds for excess risk. This means the authors have mathematically proven the fundamental limits of accuracy under these privacy constraints and developed algorithms that reach those limits.
As detailed in the table above, the researchers identify a "privacy for free" regime: if the model's dimensionality ($d$) is small relative to the data size ($n$), the privacy-protected model can achieve the same accuracy as a non-private model. Acceleration serves as the "great equalizer," maintaining accuracy even when data is heterogeneous across silos.
Empirical Validation
The theoretical findings were validated using three datasets: MNIST (binary logistic regression), Kaggle Health Insurance (linear regression), and UCI Obesity Levels (multiclass logistic regression). In experiments, the ISRL-DP MB-SGD algorithm outperformed standard Local SGD by 10% to 30% across various privacy levels. Furthermore, the accelerated methods proved significantly more communication-efficient, reaching optimal error rates in fewer rounds than previous state-of-the-art methods.
Conclusion and Future Work
While this work provides a robust framework for ISRL-DP, challenges remain. There is a small theoretical gap in the non-i.i.d. setting related to the condition number, and current bounds primarily apply to convex loss functions. Future research will aim to extend these tight bounds to non-convex deep learning and automate hyperparameter tuning in a fully private manner.
Summary updated