This work 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 incurs adversarial losses, and a sublinear regret 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 Byzantine-robust distributed online momentum algorithms to attain such sublinear stochastic regret bounds for a class of robust aggregation rules. Numerical experiments corroborate our theoretical analysis.
Bio: Qing Ling received the B.E. degree in automation and the Ph.D. degree in control theory and control engineering from the University of Science and Technology of China, Hefei, China, in 2001 and 2006, respectively. He was a Postdoctoral Research Fellow with the Department of Electrical and Computer Engineering, Michigan Technological University, Houghton, MI, USA, from 2006 to 2009, and an Associate Professor with the Department of Automation, University of Science and Technology of China, from 2009 to 2017. He is currently a Professor with the School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou, China. His current research interest includes distributed and decentralized optimization and its application in machine learning. He received the 2017 IEEE Signal Processing Society Young Author Best Paper Award as a supervisor. He served as a TPC Chair of the 2023 IEEE SPAWC Workshop. He was an Associate Editor and a Senior Area Editor of IEEE SIGNAL PROCESSING LETTERS, and an Associate Editor of IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT. He is now an Associate Editor of IEEE TRANSACTIONS ON SIGNAL PROCESSING.