TL;DR
This paper introduces and analyzes Inter-Silo Record-Level Differential Privacy (ISRL-DP), a realistic privacy framework for cross-silo federated learning where users trust their local organization (e.g., a hospital) but do not trust the central server or other silos. The authors provide tight upper and lower bounds for convex losses, proving that acceleration techniques can overcome data heterogeneity and that a secure shuffler can achieve optimal central DP utility without a trusted server.
What Problem Does This Paper Address?
While Federated Learning (FL) keeps data localized within silos (like hospitals or banks), simply keeping data local does not prevent privacy leaks. Adversaries can still reconstruct sensitive data via model inversion or membership inference attacks on the shared model updates.
To prevent this, researchers use Differential Privacy (DP). However, existing DP frameworks make extreme trust assumptions:
- Central DP (CDP) assumes the central server is completely trustworthy.
- Local DP (LDP) assumes no one can be trusted, forcing users to add massive amounts of noise to their data before even sharing it with their local silo, which severely destroys model utility.
This paper addresses the realistic middle ground of cross-silo FL: individuals usually trust their local silo, but the silos do not trust the central server or each other. The authors formalize this as Inter-Silo Record-Level DP (ISRL-DP), protecting individual records from adversarial servers and eavesdroppers while preserving much higher utility than LDP.
Methods
The authors develop and analyze several algorithms to achieve optimal privacy-utility tradeoffs under ISRL-DP:
- Noisy Distributed Minibatch SGD (MB-SGD): Silos compute local stochastic gradients, inject Gaussian noise calibrated to the record-level sensitivity, and send them to the server. The authors use uniform stability to prove tight generalization bounds for homogeneous (i.i.d.) data.
- One-Pass Accelerated Noisy MB-SGD: To handle heterogeneous (non-i.i.d.) data across silos, the authors introduce Nesterov-style acceleration and ensure that local data batches are sampled without replacement across iterations. This maintains gradient independence and prevents privacy degradation from data reuse.
- Multi-Stage Implementation: For strongly convex losses, a multi-stage shrinking step-size protocol is used to accelerate convergence.
- Shuffle DP Integration: The authors combine their algorithms with a secure "shuffler" that randomly permutes silo updates before they reach the server, amplifying privacy via anonymity.
Datasets
The algorithms were validated using three distinct datasets to simulate different learning tasks:
- MNIST: Used for binary logistic regression (classifying odd vs. even digits). Non-i.i.d. data was simulated by assigning specific digit pairings to each of the 25 silos.
- Health Insurance Data: Used for linear regression to predict patient medical costs. Data was split into silos based on the target cost values to create a highly heterogeneous environment.
- Obesity Dataset: Used for a 7-way multiclass softmax regression task, split into 7 heterogeneous silos based on obesity levels.
Key Insights and Ideas
- "Privacy for Free" Regime: For i.i.d. data, if the feature dimension $d$ is small relative to the local sample size ($d \le n\epsilon_0^2$), the ISRL-DP error rate matches the optimal non-private rate.
- The Power of Acceleration against Heterogeneity: Data heterogeneity usually degrades FL performance. Remarkably, this paper shows that for well-conditioned smooth losses, acceleration allows the algorithm to nearly match the optimal i.i.d. lower bounds, even with arbitrary data distributions across silos.
- Eliminating the Trusted Server: By routing updates through a secure shuffler, the framework achieves the high accuracy of Central DP under the much weaker trust assumptions of Shuffle DP.
Key Results
The paper establishes a comprehensive matrix of tight upper and lower bounds for excess risk across convex, strongly convex, i.i.d., and non-i.i.d. settings.
Empirical results backed up these theoretical findings:
- MNIST: ISRL-DP MB-SGD outperformed non-private Local SGD (FedAvg) for privacy parameters $\epsilon \ge 12$ and consistently beat the ISRL-DP Local SGD baseline.
- Health Insurance: The proposed method significantly beat the local DP baseline, particularly in strict privacy regimes ($\epsilon \le 2$).
- Obesity Data: The algorithm improved accuracy by 10% to 30% over the ISRL-DP Local SGD baseline across all tested privacy levels.
Limitations and Future Work
- Convexity Constraints: The theoretical optimality guarantees are limited to convex and strongly convex loss functions. Extending these tight bounds to non-convex landscapes (like deep neural networks) remains an open challenge.
- A Priori Knowledge: The noise calibration requires knowing the Lipschitz constant of the loss function beforehand. For unconstrained problems like linear regression, the authors had to rely on heuristic gradient clipping.
- End-to-End Privacy: Data preprocessing (like PCA) and hyperparameter tuning were not included in the DP analysis, meaning a fully practical deployment would require additional privacy accounting for those stages.
Summary updated