Byzantine-Robust Learning on Heterogeneous Data via Gradient Splitting

Yuchen Liu, Chen Chen, Lingjuan Lyu, Fangzhao Wu, Sai Wu

TL;DR

This paper introduces GAS, a novel Gradient Splitting approach to make Federated Learning (FL) robust against Byzantine attacks, even when client data is highly heterogeneous (non-IID). GAS effectively tackles the dual challenges of high-dimensional gradients and data heterogeneity, significantly improving the performance of existing robust aggregation methods in realistic FL scenarios.

What Problem Does This Paper Address?

Federated Learning (FL) allows multiple clients to collaboratively train a machine learning model without sharing their raw data. However, this distributed nature makes FL vulnerable to "Byzantine attacks," where malicious clients send corrupted gradients to the central server, aiming to sabotage the training process and degrade the global model's performance. While many robust aggregation rules (AGRs) have been proposed to defend against these attacks, they often falter in real-world FL settings where client data is not identically and independently distributed (non-IID). This non-IID nature introduces two major challenges:

  1. Curse of Dimensionality: In high-dimensional spaces, Byzantine gradients can be crafted to subtly manipulate the aggregation process, even fooling robust AGRs that try to include all honest gradients.
  2. Gradient Heterogeneity: When client data is non-IID, honest clients' gradients can naturally differ significantly. Robust AGRs that aggressively filter out potential outliers (to avoid Byzantine gradients) might inadvertently discard valuable information from honest clients, leading to a suboptimal global model.

Existing defenses struggle to address both these issues simultaneously, leading to poor performance in realistic non-IID FL scenarios.

Methods

The paper proposes GAS (GrAdient Splitting), a novel approach designed to enhance the Byzantine robustness of existing AGRs in non-IID settings. GAS operates in three key steps:

  1. Splitting: High-dimensional gradients are split into several lower-dimensional sub-vectors. This step is crucial for mitigating the "curse of dimensionality." By working with smaller sub-vectors, it becomes harder for Byzantine clients to craft malicious gradients that can consistently fool the aggregation.
  2. Identification: A robust AGR (like Multi-Krum or Bulyan) is applied to each group of sub-vectors. This allows for the identification of potentially Byzantine gradients based on their behavior within these lower-dimensional spaces. Crucially, GAS uses the output of these sub-vector aggregations to compute "identification scores" for each client. These scores act as a measure of how likely a client's sub-vector is to be from a Byzantine source.
  3. Aggregation: To address gradient heterogeneity, GAS selects a fixed number of clients with the lowest identification scores (indicating they are likely honest) and aggregates their gradients. This selective aggregation ensures that only the most trustworthy gradients contribute to the final model update, mitigating the negative impact of heterogeneous honest gradients.

A key advantage of GAS is its compatibility: it can be combined with most existing (f, λ)-resilient AGRs, enhancing their performance in non-IID settings without requiring them to be fundamentally redesigned.

Datasets

The experiments were conducted on four real-world datasets:

  • CIFAR-10
  • CIFAR-100
  • ImageNet-12 (a subset of ImageNet)
  • FEMNIST

For non-IID data generation, a Dirichlet distribution was used, with a concentration parameter β.

Key Insights and Ideas

  • Dual Threat of Non-IID: The paper clearly articulates that non-IID data poses a double challenge: the curse of dimensionality (making it easy for Byzantines to inject noise) and gradient heterogeneity (making it hard to distinguish honest from malicious gradients).
  • Splitting as a Decoupling Mechanism: By splitting gradients, GAS effectively decouples the problem of identifying Byzantine gradients from the problem of aggregating heterogeneous honest gradients. This allows for specialized handling of each challenge.
  • Identification Scores as a Bridge: The identification scores generated in step 2 are a clever way to leverage the robustness of AGRs on sub-vectors to inform the final aggregation, effectively filtering out potentially malicious clients.
  • Compatibility is Key: GAS doesn't replace existing robust AGRs but enhances them. This makes it a practical solution that can be readily integrated into existing FL systems.

Key Results

  • Significant Performance Gains: GAS consistently outperformed its baseline robust AGRs across various datasets and attacks in non-IID settings. For example, GAS improved the accuracy of Median by 15.93% under the Min-Sum attack on CIFAR-10.
  • Mitigation of Gradient Deviation: Figure 2 demonstrates that GAS significantly reduces the deviation between the aggregated gradient and the average of honest gradients, a key indicator of its ability to handle Byzantine attacks effectively.
  • Robustness Across Settings: GAS showed strong performance even when the number of Byzantine clients was unknown to the server, and it maintained its effectiveness across different levels of data heterogeneity.
  • Theoretical Guarantees: The paper provides a convergence analysis for GAS, offering theoretical backing for its effectiveness.

Limitations and Future Work

  • Splitting Strategy: The paper uses a simple, random splitting of gradients into sub-vectors. The authors suggest that exploring more sophisticated splitting mechanisms, such as splitting by layers, could be a promising future research direction.
  • Adaptive Client Selection: GAS could potentially be combined with adaptive client selection strategies to further enhance Byzantine robustness.
  • Unknown Byzantine Count: While GAS shows resilience when the number of Byzantine clients is unknown, its performance degrades slightly compared to when the count is known. Further research could explore more robust methods for estimating or handling this unknown count.

Summary updated

Abstract

Federated learning has exhibited vulnerabilities to Byzantine attacks, where the Byzantine attackers can send arbitrary gradients to a central server to destroy the convergence and performance of the global model. A wealth of robust AGgregation Rules (AGRs) have been proposed to defend against Byzantine attacks. However, Byzantine clients can still circumvent robust AGRs when data is non-Identically and Independently Distributed (non-IID). In this paper, we first reveal the root causes of performance degradation of current robust AGRs in non-IID settings: the curse of dimensionality and gradient heterogeneity. In order to address this issue, we propose GAS, a \shorten approach that can successfully adapt existing robust AGRs to non-IID settings. We also provide a detailed convergence analysis when the existing robust AGRs are combined with GAS. Experiments on various real-world datasets verify the efficacy of our proposed GAS. The implementation code is provided in https://github.com/YuchenLiu-a/byzantine-gas.
BibTeX
@inproceedings{liu2023byzantine,
  author = {Yuchen Liu and Chen Chen and Lingjuan Lyu and Fangzhao Wu and Sai Wu and Gang Chen},
  title = {{Byzantine-Robust Learning on Heterogeneous Data via Gradient Splitting}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=3DI6Kmw81p},
}
Figure