Bridging Differential Privacy and Byzantine-Robustness via Model Aggregation

Heng Zhu, Qing LingIJCAI 2022 · DOI

TL;DR

This paper introduces DP-RSA, a novel federated learning algorithm that simultaneously achieves differential privacy and robustness against Byzantine attacks, even with non-i.i.d. data. It does this by decoupling privacy and robustness concerns through a unique model aggregation strategy that transmits only the signs of model differences, leading to improved communication efficiency and a clearer trade-off analysis.

What Problem Does This Paper Address?

Federated learning (FL) enables distributed model training without centralizing raw data, but it faces two major challenges: differential privacy (DP) and Byzantine robustness. DP protects user data from a curious but honest master node by adding noise, while Byzantine robustness defends against malicious workers who send faulty information to disrupt training. These two goals are often at odds. Standard DP mechanisms add noise to gradients, which can make it harder for robust aggregation methods to distinguish malicious updates from legitimate, noisy ones. This conflict is particularly pronounced when the data across workers is non-i.i.d. (not identically and independently distributed), a common scenario in real-world FL. Existing methods struggle to effectively address both issues simultaneously, especially under non-i.i.d. data, leading to a need for a unified approach that decouples these concerns.

Methods

The core innovation of DP-RSA lies in its model aggregation approach, rather than the more common gradient aggregation. Instead of sending full local models or gradients, workers compute the element-wise sign of the difference between their local model and the global model ($sign(x_k - x_0)$). This "sign-based" communication is inherently more communication-efficient and forms the basis for Byzantine robustness.

To achieve differential privacy, two novel DP mechanisms are introduced:

  • Sign-Flipping Mechanism: Randomly flips the sign of each element with a certain probability ($\gamma$).
  • Sign-Gaussian Mechanism: Adds Gaussian noise to the model difference before taking the sign.

These mechanisms are designed to perturb the uploaded signs, providing privacy guarantees. A key contribution is the theoretical analysis showing that these DP mechanisms have a decoupled and additive influence on learning performance, unlike the multiplicative influence seen in prior work. The algorithm's convergence is proven for non-convex and non-smooth cost functions using advanced techniques like Moreau envelopes and proximal point projections.

Datasets

The paper evaluates DP-RSA on two standard benchmark datasets:

  • MNIST: A dataset of handwritten digits.
  • CIFAR10: A dataset of small color images in 10 classes.

The experiments are conducted in both i.i.d. and non-i.i.d. settings to demonstrate the algorithm's effectiveness under challenging data distributions.

Key Insights and Ideas

  • Decoupling Privacy and Robustness: The paper successfully decouples DP and Byzantine robustness by focusing on model aggregation via signs, rather than gradient aggregation. This separation simplifies analysis and allows for clearer understanding of trade-offs.
  • Sign-Based Communication: Transmitting only the signs of model differences is a clever way to achieve both communication efficiency and a degree of Byzantine robustness, as the magnitude of malicious updates becomes less critical.
  • Additive Influence of DP: A significant theoretical finding is that the proposed DP mechanisms have an additive impact on learning performance, contrasting with the multiplicative impact observed in previous work. This suggests that DP can be integrated more cleanly without severely degrading robustness.
  • Novel DP Proofs: The paper presents novel proofs for the Sign-Flipping and Sign-Gaussian mechanisms satisfying $(\epsilon, \delta)$-DP, with a focus on achieving $\delta=0$ for the Sign-Flipping mechanism by leveraging properties of Gaussian CDFs.
  • Weakly Convex Convergence: The convergence analysis for non-convex and non-smooth objectives using Moreau envelopes and proximal point projections is a valuable theoretical contribution for robust FL.

Key Results

  • DP-RSA demonstrates strong performance on both MNIST and CIFAR10 datasets, outperforming baselines like SGD and SignSGD under various attacks (Gaussian, Sign-Flipping, Sample-Duplicating).
  • The algorithm shows resilience to Byzantine attacks even in non-i.i.d. settings, where other methods like SignSGD and SGD with Geometric Median struggle significantly.
  • The DP mechanisms (Sign-Flipping and Sign-Gaussian) are shown to provide privacy guarantees without excessively harming learning performance, as indicated by the experimental results where DP-RSA performs comparably to the non-private robust baseline (RSA).
  • The theoretical analysis confirms that the learning error due to Byzantine attacks is linear in the number of Byzantine workers ($b^2$), not their magnitude, and the error from DP mechanisms is additive.

Limitations and Future Work

  • Theoretical Complexity: While convergence is proven, the analysis relies on assumptions like weak convexity and bounded gradients, which are standard but might not cover all real-world scenarios.
  • Hyperparameter Tuning: The performance of DP-RSA, like most FL algorithms, is sensitive to hyperparameters such as the step size ($\alpha$), penalty parameter ($\lambda$), and DP parameters ($\epsilon, \gamma, \sigma$).
  • Future Work: The authors suggest extending the DP mechanisms to other sign-based DP algorithms and exploring more advanced composition theorems for multi-round privacy loss. Further numerical experiments with more attacks and a deeper analysis of hyperparameter influence are also mentioned. The paper also notes that the Sign-Flipping mechanism's proof can be extended to other sign-based DP mechanisms.

Summary updated

BibTeX
@inproceedings{zhu2022bridging,
  author = {Heng Zhu and Qing Ling},
  title = {{Bridging Differential Privacy and Byzantine-Robustness via Model Aggregation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/337},
}
Figure