# Byzantine-Robust Distributed Online Learning: Taming Adversarial Participants in An Adversarial Environment

arXiv: https://arxiv.org/abs/2307.07980 · HTML: https://mlsanity.com/paper/2307.07980/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 57 references that are in the map.
- First posted on arXiv 16 Jul 2023.

## Builds on (most cited first, 24 of 24)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Robust Aggregation for Federated Learning](https://mlsanity.com/paper/1912.13445/) (2019)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Generalized Byzantine-tolerant SGD](https://mlsanity.com/paper/1802.10116/) (2018)
- [Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks](https://mlsanity.com/paper/1912.12716/) (2019)
- [Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums](https://mlsanity.com/paper/2205.12173/) (2022)
- [Byzantine-robust Federated Learning through Collaborative Malicious Gradient Filtering](https://mlsanity.com/paper/2109.05872/) (2021)
- [Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1903.04277/) (2019)
- [Byzantine-Resilient Decentralized Stochastic Optimization with Robust Aggregation Rules](https://mlsanity.com/paper/2206.04568/) (2022)
- [Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2302.04552/) (2023)
- [Online Distributed Optimization on Dynamic Networks](https://mlsanity.com/paper/1412.7215/) (2014)
- [Phocas: dimensional Byzantine-resilient stochastic gradient descent](https://mlsanity.com/paper/1805.09682/) (2018)
- [Distributed Momentum for Byzantine-resilient Learning](https://mlsanity.com/paper/2003.00010/) (2020)
- [Secure Distributed Optimization Under Gradient Attacks](https://mlsanity.com/paper/2210.15821/) (2022)
- [Byzantine-Robust Federated Linear Bandits](https://mlsanity.com/paper/2204.01155/) (2022)
- [Byzantine Resilient Non-Convex SVRG with Distributed Batch Gradient Computations](https://mlsanity.com/paper/1912.04531/) (2019)
- [Federated Multi-Armed Bandits Under Byzantine Attacks](https://mlsanity.com/paper/2205.04134/) (2022)
- [Centralized and distributed online learning for sparse time-varying optimization](https://mlsanity.com/paper/2001.11939/) (2020)
- [Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds](https://mlsanity.com/paper/2206.02834/) (2022)
- [Robust Online and Distributed Mean Estimation Under Adversarial Data Corruption](https://mlsanity.com/paper/2209.09624/) (2022)
- [Distributed Constrained Online Learning](https://mlsanity.com/paper/1903.06310/) (2019)
- [Online Learning with Adversaries: A Differential-Inclusion Analysis](https://mlsanity.com/paper/2304.01525/) (2023)
- [Distributed Online Optimization with Byzantine Adversarial Agents](https://mlsanity.com/paper/2109.12340/) (2021)

## Built on by (most cited first, 8 of 8)

- [Generalization Error Matters in Decentralized Learning Under Byzantine Attacks](https://mlsanity.com/paper/2407.08632/) (2024)
- [A survey on secure decentralized optimization and learning](https://mlsanity.com/paper/2408.08628/) (2024)
- [FedCanon: Non-Convex Composite Federated Learning with Efficient Proximal Operation on Heterogeneous Data](https://mlsanity.com/paper/2504.11903/) (2025)
- [Decentralized Blockchain-based Robust Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2402.04417/) (2024)
- [Adversarially Robust Multitask Adaptive Control](https://mlsanity.com/paper/2511.05444/) (2025)
- [Coded Robust Aggregation for Distributed Learning under Byzantine Attacks](https://mlsanity.com/paper/2506.01989/) (2025)
- [Byzantine-Robust and Communication-Efficient Distributed Training: Compressive and Cyclic Gradient Coding](https://mlsanity.com/paper/2603.28780/) (2026)
- [Enhanced Byzantine-Robust Federated Learning Via Truncated-Quadratic Loss for Heterogeneous Data](https://mlsanity.com/paper/2607.10970/) (2026)

## Abstract (arXiv)

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.