# Byzantine-Robust Federated Linear Bandits

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 53 references that are in the map.
- First posted on arXiv 3 Apr 2022.

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

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization](https://mlsanity.com/paper/1909.13014/) (2019)
- [Robust Aggregation for Federated Learning](https://mlsanity.com/paper/1912.13445/) (2019)
- [RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets](https://mlsanity.com/paper/1811.03761/) (2018)
- [Robust Federated Learning: The Case of Affine Distribution Shifts](https://mlsanity.com/paper/2006.08907/) (2020)
- [Generalized Byzantine-tolerant SGD](https://mlsanity.com/paper/1802.10116/) (2018)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks](https://mlsanity.com/paper/1912.12716/) (2019)
- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Federated Multi-Armed Bandits](https://mlsanity.com/paper/2101.12204/) (2021)
- [Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee](https://mlsanity.com/paper/2110.14074/) (2021)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits](https://mlsanity.com/paper/2106.02575/) (2021)
- [Communication Efficient Federated Learning for Generalized Linear Bandits](https://mlsanity.com/paper/2202.01087/) (2022)
- [Regularization, sparse recovery, and median-of-means tournaments](https://mlsanity.com/paper/1701.04112/) (2017)
- [Federated Optimization of Smooth Loss Functions](https://mlsanity.com/paper/2201.01954/) (2022)
- [Securing Distributed Gradient Descent in High Dimensional Statistical Learning](https://mlsanity.com/paper/1804.10140/) (2018)

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

- [Federated Neural Bandits](https://mlsanity.com/paper/2205.14309/) (2022)
- [Byzantine-Robust Online and Offline Distributed Reinforcement Learning](https://mlsanity.com/paper/2206.00165/) (2022)
- [Federated Offline Reinforcement Learning](https://mlsanity.com/paper/2206.05581/) (2022)
- [Byzantine-Robust Distributed Online Learning: Taming Adversarial Participants in An Adversarial Environment](https://mlsanity.com/paper/2307.07980/) (2023)
- [Federated Multi-Armed Bandits Under Byzantine Attacks](https://mlsanity.com/paper/2205.04134/) (2022)
- [Byzantine-Resilient Decentralized Multi-Armed Bandits](https://mlsanity.com/paper/2310.07320/) (2023)
- [Harnessing the Power of Federated Learning in Federated Contextual Bandits](https://mlsanity.com/paper/2312.16341/) (2023)
- [Learning from Unreliable Trajectories: Adversarially-Robust Federated Q-Learning](https://mlsanity.com/paper/2610.06918/) (2026)

## Abstract (arXiv)

In this paper, we study a linear bandit optimization problem in a federated setting where a large collection of distributed agents collaboratively learn a common linear bandit model. Standard federated learning algorithms applied to this setting are vulnerable to Byzantine attacks on even a small fraction of agents. We propose a novel algorithm with a robust aggregation oracle that utilizes the geometric median. We prove that our proposed algorithm is robust to Byzantine attacks on fewer than half of agents and achieves a sublinear tildeO(T3/4) regret with O(√T) steps of communication in T steps. Moreover, we make our algorithm differentially private via a tree-based mechanism. Finally, if the level of corruption is known to be small, we show that using the geometric median of mean oracle for robust aggregation further improves the regret bound.