Byzantine-Robust Distributed Online Learning: Taming Adversarial Participants in An Adversarial Environment
This addresses the problem of securing distributed online learning against adversarial participants for applications in decentralized systems, though it is incremental as it builds on existing robust aggregation methods.
The paper tackles distributed online learning under Byzantine attacks, proving that even with robust aggregation rules, only linear adversarial regret is achievable, but sublinear stochastic regret is possible when losses are i.i.d., and they develop a Byzantine-robust algorithm to achieve this.
This paper studies distributed online learning under Byzantine attacks. The performance of an online learning algorithm is often characterized by (adversarial) regret, which evaluates the quality of one-step-ahead decision-making when an environment provides adversarial losses, 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 in the presence of 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 momentum algorithm to attain such a sublinear stochastic regret bound. Extensive numerical experiments corroborate our theoretical analysis.