Distributed Online Learning With Adversarial Participants In An Adversarial Environment
Distributed Online Learning With Adversarial Participants In An Adversarial Environment
复制标题
DOI：
10.1109/icassp49357.2023.10095178
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Xingrong Dong;Zhaoxian Wu;Qing Ling;Zhi Tian
中科院分区：
文献类型：
--
作者：
Xingrong Dong;Zhaoxian Wu;Qing Ling;Zhi Tian
本文研究了拜占庭攻击下的分布式在线学习。在线学习算法的性能的特点是（对抗性）遗憾，次线性界是首选。但是我们证明了，即使有一类最先进的鲁棒聚集规则，在对抗环境中，并且有拜占庭参与者，分布式在线梯度下降也只能实现线性对抗遗憾界，这是紧的。这是拜占庭攻击的必然结果，即使我们可以控制线性对抗性后悔的常数到一个合理的水平。有趣的是，当环境不是完全对抗时，诚实参与者的损失是独立同分布的。（独立同分布），我们表明，次线性随机遗憾，与上述对抗性遗憾，是可能的。我们开发了一个拜占庭强大的分布式在线梯度下降算法的势头，以达到这样的次线性随机遗憾界。
This paper studies distributed online learning under Byzantine attacks. The performance of an online learning algorithm is characterized by (adversarial) regret, and a sublinear bound is preferred. But we prove that, even with a class of state-of-the-art robust aggregation rules, in an adversarial environment and with Byzantine participants, distributed online gradient descent can only achieve a linear adversarial regret bound, which is tight. This is the inevitable consequence of Byzantine attacks, even though we can control the constant of the linear adversarial regret to a reasonable level. Interestingly, when the environment is not fully adversarial so that the losses of the honest participants are i.i.d. (independent and identically distributed), we show that sublinear stochastic regret, in contrast to the aforementioned adversarial regret, is possible. We develop a Byzantine-robust distributed online gradient descent algorithm with momentum to attain such a sublinear stochastic regret bound.