Byzantine-Robust Decentralized Learning via Remove-then-Clip Aggregation

Caiyi Yang, Javad GhaderiAAAI 2024 · OpenReview

TL;DR

This paper introduces a novel decentralized learning algorithm called Remove-then-Clip (RTC) aggregation, designed to be robust against Byzantine attacks and data heterogeneity. RTC effectively filters out malicious updates from Byzantine workers while preserving valuable information from benign ones, leading to improved convergence and accuracy in challenging distributed learning scenarios.

What Problem Does This Paper Address?

Modern machine learning models are increasingly trained on distributed data across numerous devices. While this offers benefits like privacy and scalability, it introduces vulnerabilities. "Byzantine workers" can intentionally send corrupted or malicious updates, disrupting the learning process. Compounding this issue is "data heterogeneity," where each worker has a unique distribution of data, making it difficult to distinguish between genuine data variations and malicious attacks. Existing robust decentralized learning methods often struggle with this non-IID data setting, leading to slow convergence or reduced accuracy. This paper tackles the challenge of building a decentralized learning system that is resilient to both Byzantine attacks and non-IID data distributions.

Methods

The core contribution is a new robust aggregation mechanism called Remove-then-Clip (RTC). This method is integrated into a standard decentralized stochastic gradient descent (DSGD) framework. Here's how it works at each benign worker:

  1. Filtering Phase (Remove): The worker iteratively identifies and removes the neighbors whose model updates are most distant from its own. This removal process continues until the cumulative "weight" of the removed neighbors (based on the network's communication weights) reaches a predefined threshold, dmax. This step aims to discard potentially malicious updates that are outliers.
  2. Clipping Phase (Clip): For the remaining "benign" neighbors, their updates are then "clipped." This involves projecting each neighbor's update onto a sphere centered at the worker's current model. The radius of this sphere is carefully chosen based on the remaining neighbors' updates. This step further mitigates the impact of any remaining malicious influences and ensures updates stay within a reasonable range.
  3. Aggregation: The filtered and clipped updates are then aggregated using a weighted average, incorporating the worker's own update.

The paper also incorporates a momentum term into the DSGD algorithm, which helps accelerate convergence and provides an additional layer of defense against certain types of attacks. Theoretical analysis is provided to prove that this DSGD-RTC method converges to a neighborhood of a stationary point for non-convex objectives, even under Byzantine and non-IID conditions.

Datasets

The paper uses the MNIST dataset for evaluation. For data distribution:

  • IID (Independent and Identically Distributed): The training dataset is partitioned equally among all workers.
  • Non-IID (Non-Independent and Identically Distributed): The dataset is sorted by labels and then sequentially divided into equal parts for all workers. This creates a more challenging scenario where workers have distinct data characteristics.

Key Insights and Ideas

  • The "Remove-then-Clip" Strategy: The novel combination of aggressively filtering out the most distant neighbors before applying a more general clipping mechanism is key. This two-stage approach is more effective than methods that only filter or only clip, as it leverages more information from benign neighbors.
  • Handling Data Heterogeneity is Crucial: The paper emphasizes that real-world decentralized learning often involves non-IID data. Many existing Byzantine-robust methods fail in this setting, highlighting the importance of developing algorithms that can handle both issues simultaneously.
  • Adaptive dmax: The paper suggests an adaptive strategy for estimating dmax if an accurate value isn't known beforehand, making the method more practical.
  • Theoretical Guarantees: Proving convergence for non-convex objectives under Byzantine and non-IID conditions is a significant theoretical contribution, providing confidence in the algorithm's robustness.

Key Results

The empirical evaluations demonstrate the superiority of the proposed DSGD-RTC method:

  • Convex Setting (5 Byzantine workers): RTC consistently outperforms existing robust aggregators (RFA, UBAR, SCCLIP) under three different attack models (IPM, ALIE, DISSENSUS). It achieves accuracy improvements of 3%-35% over SCCLIP and RFA in various scenarios. UBAR, in particular, showed poor performance.
  • Non-Convex Setting (5 Byzantine workers): Similar to the convex setting, RTC leads in accuracy, showing improvements of 5%-13% over SCCLIP and RFA.
  • Non-Convex Setting (10 Byzantine workers): With a higher number of Byzantine workers, the performance gap widens. RTC shows significant improvements, with gains of 22%-35% over SCCLIP and RFA under IPM and DISSENSUS attacks, respectively. This highlights the algorithm's scalability and resilience to more aggressive attacks.

Limitations and Future Work

  • dmax Estimation: While an adaptive strategy for dmax is proposed, accurately estimating this parameter in practice can still be challenging.
  • Theoretical Bounds: The paper notes that the theoretical bound for RTC is less stringent than that of SCCLIP due to the use of a more feasible clipping threshold. Future work could explore ways to relax the dependence of convergence guarantees on data heterogeneity.
  • Further Analysis: The authors suggest that more careful analysis or alternative approaches could be explored to further improve convergence guarantees, especially concerning heterogeneity.

Summary updated

Abstract

We consider decentralized learning over a network of workers with heterogeneous datasets, in the presence of Byzantine workers. Byzantine workers may transmit arbitrary or malicious values to neighboring workers, leading to degradation in overall performance. The heterogeneous nature of the training data across various workers complicates the identification and mitigation of Byzantine workers. To address this complex problem, we introduce a resilient decentralized learning approach that combines the gradient descent algorithm with a novel robust aggregator. Specifically, we propose a remove-then-clip aggregator, whereby each benign worker meticulously filters the neighbors' values and subsequently projects the remaining values to a sphere centered at its local value, with an appropriately selected radius. We prove that our proposed method converges to a neighborhood of a stationary point for non-convex objectives under standard assumptions. Furthermore, empirical evaluations are provided to demonstrate the superior performance of our method in comparison to existing algorithms, under various Byzantine attack models.
BibTeX
@inproceedings{yang2024byzantine,
  author = {Caiyi Yang and Javad Ghaderi},
  title = {{Byzantine-Robust Decentralized Learning via Remove-then-Clip Aggregation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=9NyWx6PzxX},
}
Figure