TL;DR
Federated learning (FL) is vulnerable to Byzantine attacks, especially when client data is non-IID (label skewness). This paper introduces BOBA, a novel aggregation method that effectively handles label skewness, providing robust and unbiased model training even under Byzantine attacks. BOBA achieves this through a two-stage approach that first fits an "honest subspace" and then filters out malicious gradients, outperforming existing methods in challenging non-IID scenarios.
What Problem Does This Paper Address?
Federated learning (FL) allows multiple clients to collaboratively train a global model without sharing their private data. However, FL systems are susceptible to Byzantine attacks, where malicious clients can send arbitrary gradients to disrupt training. While existing robust aggregation rules (AGRs) defend against these attacks, they primarily assume that client data is independent and identically distributed (IID). In reality, FL data is often non-IID, with "label skewness" being a common and challenging scenario where each client only has access to a limited set of classes.
This non-IID setting poses two main problems for existing AGRs:
- Selection Bias: AGRs that rely on clustering gradients can unfairly favor clients with data from majority classes, leading to biased models that perform poorly on underrepresented classes.
- Increased Vulnerability: The inherent variation in gradients from honest clients in a non-IID setting makes it harder to distinguish malicious gradients, amplifying their impact and making AGRs more vulnerable to attacks.
This paper addresses these limitations by proposing BOBA, a novel AGR designed to be robust to Byzantine attacks specifically in the presence of label skewness.
Methods
BOBA employs a two-stage approach:
- Stage 1: Fitting the Honest Subspace: This stage aims to identify a low-dimensional affine subspace that captures the distribution of honest client gradients, even in the presence of Byzantine gradients. It uses a "trimmed reconstruction loss" objective, which is more robust than standard methods like Truncated Singular Value Decomposition (TrSVD). This objective iteratively fits an affine subspace by minimizing the reconstruction error on a subset of gradients that are closest to the subspace, effectively ignoring those that deviate significantly. This stage projects all gradients onto this fitted subspace, weakening Byzantine gradients by removing components orthogonal to the honest subspace.
- Stage 2: Finding the Honest Simplex: This stage leverages a small amount of server data to estimate the label distribution for each client. It leverages the insight that expected honest gradients form a (c-1)-simplex, where 'c' is the number of classes. By estimating each client's label distribution and filtering out those with strongly negative entries (indicating they fall outside the expected simplex), BOBA can effectively discard potential Byzantine gradients.
The paper also provides theoretical analysis, proving BOBA's convergence and demonstrating its unbiasedness and optimal order robustness.
Datasets
The paper uses the following datasets for training and evaluation:
- MNIST
- CIFAR-10
- AG-News
Key Insights and Ideas
- Label Skewness is a Major Challenge: The paper highlights that label skewness, a realistic non-IID scenario, significantly degrades the performance of existing Byzantine-robust FL methods due to selection bias and increased vulnerability.
- Honest Gradients Form a Simplex: A key theoretical insight is that in a label-skewed setting, the expected gradients of honest clients lie on a (c-1)-simplex. BOBA leverages this geometric property to identify and filter malicious gradients.
- Two-Stage Approach is Crucial: BOBA's success stems from its two-stage design: first, robustly identifying the "honest subspace" and then precisely filtering clients based on their estimated label distributions. This combination effectively handles both the geometric distribution of honest gradients and the identification of malicious deviations.
- Server Data is Key for Robustness: The paper demonstrates that even a small amount of clean server data is crucial for achieving both unbiasedness and robustness, especially in challenging non-IID settings.
Key Results
- Superior Unbiasedness and Robustness: BOBA significantly outperforms baseline AGRs in terms of unbiasedness (measured by Maximum Recall Drop - MRD) and worst-case accuracy under various Byzantine attacks in label-skewed settings. For instance, on CIFAR-10, BOBA improved worst-case accuracy by 18.3% compared to baselines.
- Efficiency: BOBA is computationally efficient, with a complexity comparable to standard FL aggregation methods, and is faster than half of the baseline AGRs tested.
- Robustness to Server Data Quality: BOBA shows remarkable consistency in performance even when server data is corrupted with noise (feature skewness) or exhibits label skewness.
- Minimal Server Data Requirement: BOBA achieves strong performance with a surprisingly small amount of server data (as few as 5 samples per class on CIFAR-10).
- Generalizability: BOBA can be effectively integrated with different FL frameworks like FedAvg and FedProx, maintaining its unbiasedness and robustness.
Limitations and Future Work
- Hyperparameter Sensitivity: While BOBA is generally robust, its performance can be affected by extreme hyperparameter choices (e.g., very large 'f' or very small 'pmin'). The authors recommend moderate values for these parameters.
- Extension to Mixture Distributions: The paper notes that BOBA primarily focuses on label skewness but can be extended to more general mixture distributions.
- More Complex Non-IID Settings: While BOBA shows promise in handling combined label and feature skewness, further research could explore even more complex non-IID scenarios.
Summary updated