Byzantine-Resilient Decentralized Stochastic Optimization With Robust Aggregation Rules

Zhaoxian Wu, Tianyi Chen, Qing Ling

This paper, recently published by researchers from Sun Yat-Sen University and Rensselaer Polytechnic Institute, tackles a critical security bottleneck in decentralized machine learning: how to keep a peer-to-peer network training accurately when some of its members are actively trying to sabotage the process.

TL;DR

The authors identify why standard "robust" aggregation rules used in server-client setups fail in decentralized (peer-to-peer) networks, leading to a lack of consensus or biased models. They propose Iterative Outlier Scissor (IOS), a novel filtering algorithm that allows honest nodes to reach a precise consensus and converge to the optimal model even under heavy Byzantine attacks.

What Problem Does This Paper Address?

In decentralized stochastic optimization, there is no central server. Instead, "workers" (devices or nodes) update their local models and share them with immediate neighbors. This is great for privacy and scalability, but it is highly vulnerable to Byzantine attacks—where a subset of nodes sends malicious, arbitrary, or "poisoned" data to disrupt the training.

While we have robust rules for central-server systems (like the coordinate-wise median or Krum), the authors show that simply "plugging them in" to a decentralized network causes two major failures:

  1. Disagreement: Nodes may never reach a consensus, even if no attack is happening, because the robust rules prevent them from "averaging out" their differences.
  2. Bias (Non-doubly stochasticity): In a peer-to-peer network, if the "influence" nodes have on each other isn't perfectly balanced (mathematically represented as a doubly stochastic mixing matrix), the network ends up optimizing a distorted version of the objective function rather than the true average.

Methods

The authors first establish theoretical guidelines for what a decentralized robust rule should look like, defining two key properties: Robust Contractive Aggregation (RCA) and Robust Doubly Stochastic Aggregation (RDSA).

To meet these criteria, they introduce Iterative Outlier Scissor (IOS). The algorithm works as follows:

  • Iterative Filtering: At each communication step, an honest node looks at the models sent by its neighbors.
  • The "Scissor": It calculates a weighted average and then "scissors" out (discards) the neighbor's model that is furthest from that average.
  • Repetition: This process repeats until the node has discarded a number of neighbors equal to the estimated number of Byzantine attackers.
  • Final Aggregation: The remaining "trusted" models are averaged to update the local model.

Crucially, IOS is designed to maintain the "doubly stochastic" property of the network, ensuring that the influence of every honest node remains balanced throughout the training.

Datasets

The researchers evaluated IOS using:

  • MNIST: The classic dataset of 60,000 handwritten digits.
  • Topologies: They tested on various network shapes, including a "Two-castle" graph (two clusters with thin links), an "Octopus" graph, and random Erdos-Renyi graphs.
  • Data Distribution: They tested both i.i.d. (every node has similar data) and non-i.i.d. (nodes have different classes of digits) scenarios, the latter being much harder to defend.

Key Insights and Ideas

  • The Consensus Trap: The "aha moment" is the realization that robust rules designed to ignore outliers in a central server actually prevent nodes from reaching consensus in a decentralized network. If a rule is too "stubborn," nodes in different parts of the graph will never agree on a model.
  • Virtual Mixing Matrices: The paper introduces the concept of a "virtual" mixing matrix to describe how robust rules effectively change the network's topology. If this virtual matrix isn't doubly stochastic, the algorithm is mathematically guaranteed to converge to the wrong answer.
  • IOS is "FABA-plus": IOS is inspired by the FABA algorithm (Fast Aggregation against Byzantine Attacks) but modifies it specifically to handle the unique connectivity constraints of decentralized graphs.

Key Results

  • Resilience to Attacks: IOS was tested against several brutal attacks, including "sign-flipping" (sending the negative of the true gradient) and "ALIE" (A Little Is Enough). In almost all cases, IOS maintained an accuracy of ~91.7% on MNIST, matching the performance of a network with no attackers.
  • Superiority over Existing Rules: In non-i.i.d. scenarios where standard rules like Krum or Coordinate-wise Median dropped to 10-30% accuracy, IOS remained stable.
  • High Tolerance: Experiments showed that IOS remains effective even when nearly 1/3 of a node's neighbors are malicious (e.g., 6 out of 20 neighbors).

Limitations and Future Work

  • Knowledge of $q_n$: The algorithm requires an estimate of the number of Byzantine neighbors ($q_n$). If this estimate is significantly wrong, performance could degrade.
  • Computational Overhead: Because IOS is iterative (discarding one neighbor at a time), it is more computationally expensive than a simple mean, though the authors note it is still faster than complex geometric median calculations.
  • Variance Reduction: The authors suggest that combining IOS with variance reduction techniques (like SVRG) could further reduce the "asymptotic learning error" caused by stochastic noise in the gradients.

Summary updated

Abstract

This article focuses on decentralized stochastic optimization in the presence of Byzantine attacks. During the optimization process, an unknown number of malfunctioning or malicious workers, termed as Byzantine workers, disobey the algorithmic protocol and send arbitrarily wrong messages to their neighbors. Even though various Byzantine-resilient algorithms have been developed for distributed stochastic optimization with a central server, we show that there are two major issues in the existing robust aggregation rules when being applied to the decentralized scenario: disagreement and non-doubly stochastic virtual mixing matrix. This article provides comprehensive analysis that discloses the negative effects of these two issues, and gives guidelines of designing favorable Byzantine-resilient decentralized stochastic optimization algorithms. Under these guidelines, we propose iterative outlier scissor (IOS), an iterative filtering-based robust aggregation rule with provable performance guarantees. Numerical experiments demonstrate the effectiveness of IOS. The code of simulation implementation is available at github.com/Zhaoxian-Wu/IOS .
BibTeX
@article{wu2023byzantine,
  author = {Zhaoxian Wu and Tianyi Chen and Qing Ling},
  title = {{Byzantine-Resilient Decentralized Stochastic Optimization With Robust Aggregation Rules}},
  journal = {IEEE Trans. Signal Process.},
  year = {2023},
  url = {https://openreview.net/forum?id=LbURtGEOw9},
}

Loading related content...

Figure