Byzantine-Resilient Decentralized Stochastic Optimization with Robust Aggregation Rules

This work focuses on decentralized stochastic optimization in the presence of Byzantine attacks. During the optimization process, an unknown number of malfunctioning or malicious nodes, which we term as Byzantine workers, disobey the algorithmic protocol and send wrong messages to their neighbors. Even though various Byzantine-resilient algorithms have been developed for distributed stochastic optimization, we show that there are still two major challenges during the designation of robust aggregation rules suitable for decentralized stochastic optimization: disagreement and non-doubly stochastic mixing matrix. This paper provides a comprehensive analysis disclosing the negative effects of these two issues, and gives guidelines of designing favorable Byzantine-resilient decentralized stochastic optimization algorithms. Following the guidelines, we propose an iterative filtering-based robust aggregation rule termed iterative outlier scissor (IOS), which has provable Byzantine-resilience. Numerical experiments demonstrate the effectiveness of IOS.