mlsanityData to 7 Oct 2026

Byzantine-Robust Federated Linear Bandits

arXiv 2204.01155 ↗First posted 3 Apr 2022cs.LG cs.MA stat.MLcited by 7

Not on the map. Why?

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.

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

Builds on

22 of 53 references.

References · 22

  1. 2019Advances and Open Problems in Federated Learningcited by 3,021
  2. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  3. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 698
  4. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 558
  5. 2019FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantizationcited by 349
  6. 2019Robust Aggregation for Federated Learningcited by 314
  7. 2018RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasetscited by 148
  8. 2020Robust Federated Learning: The Case of Affine Distribution Shiftscited by 102
  9. 2018Generalized Byzantine-tolerant SGDcited by 94
  10. 2020Differentially-Private Federated Linear Banditscited by 83
  11. 2018Differentially Private Contextual Linear Banditscited by 82
  12. 2019Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attackscited by 79
10 more
  1. 2021Federated Multi-armed Bandits with Personalizationcited by 62
  2. 2021Federated Linear Contextual Banditscited by 61
  3. 2021Federated Multi-Armed Banditscited by 59
  4. 2021Fault-Tolerant Federated Reinforcement Learning with Theoretical Guaranteecited by 52
  5. 2013Loss minimization and parameter estimation with heavy tailscited by 50
  6. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
  7. 2022Communication Efficient Federated Learning for Generalized Linear Banditscited by 13
  8. 2017Regularization, sparse recovery, and median-of-means tournamentscited by 11
  9. 2022Federated Optimization of Smooth Loss Functionscited by 6
  10. 2018Securing Distributed Gradient Descent in High Dimensional Statistical Learningcited by 5

Built on by

Cited by year

Citing papers per year: 2022: 4; 2023: 3.

7 papers.

  1. 2022Federated Neural Banditscited by 17
  2. 2022Byzantine-Robust Online and Offline Distributed Reinforcement Learningcited by 13
  3. 2022Federated Offline Reinforcement Learningcited by 13
  4. 2023Byzantine-Robust Distributed Online Learning: Taming Adversarial Participants in An Adversarial Environmentcited by 8
  5. 2022Federated Multi-Armed Bandits Under Byzantine Attackscited by 6
  6. 2023Byzantine-Resilient Decentralized Multi-Armed Banditscited by 3
  7. 2023Harnessing the Power of Federated Learning in Federated Contextual Banditscited by 1