This paper 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 paper 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.
翻译:本文关注在存在拜占庭攻击的情况下从事去中心化随机优化。在优化过程中,存在未知数量的故障或恶意工人,被称为拜占庭工人,他们不遵守算法协议并向其邻居发送任意不正确的消息。尽管已经开发了各种拜占庭鲁棒算法用于带有中央服务器的分布式随机优化,但本文表明,在应用于去中心化场景时,现有的鲁棒聚合规则存在两个主要问题:不一致性和非双随机虚拟混合矩阵。本文提供了全面的分析,揭示了这两个问题的负面影响,并提供了设计有利于拜占庭鲁棒的去中心化随机优化算法的指导方针。在这些指导方针下,我们提出了迭代离群值剪刀(IOS),这是一种迭代过滤型鲁棒聚合规则,具有可证明的性能保证。数值实验证明了IOS的有效性。仿真实现的代码可在github.com/Zhaoxian-Wu/IOS上获取。