Federated Multi-Armed Bandits Under Byzantine Attacks

• URL: http://arxiv.org/abs/2205.04134v2
• Date: Sat, 15 Jun 2024 20:53:02 GMT
• Title: Federated Multi-Armed Bandits Under Byzantine Attacks
• Authors: Artun Saday, İlker Demirel, Yiğit Yıldırım, Cem Tekin,
• Abstract summary: Federated multi-armed bandits (FMAB) is an emerging framework where learners play an MAB game and communicate their aggregated feedback to a server to learn a globally optimal arm. We study the FMAB problem in the presence of Byzantine clients who can send false model updates threatening the learning process. We propose a median-of-means (MoM)-based online algorithm, Fed-MoM-UCB, to cope with Byzantine clients.
• Score: 8.974667651758095
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-armed bandits (MAB) is a sequential decision-making model in which the learner controls the trade-off between exploration and exploitation to maximize its cumulative reward. Federated multi-armed bandits (FMAB) is an emerging framework where a cohort of learners with heterogeneous local models play an MAB game and communicate their aggregated feedback to a server to learn a globally optimal arm. Two key hurdles in FMAB are communication-efficient learning and resilience to adversarial attacks. To address these issues, we study the FMAB problem in the presence of Byzantine clients who can send false model updates threatening the learning process. We analyze the sample complexity and the regret of $\beta$-optimal arm identification. We borrow tools from robust statistics and propose a median-of-means (MoM)-based online algorithm, Fed-MoM-UCB, to cope with Byzantine clients. In particular, we show that if the Byzantine clients constitute less than half of the cohort, the cumulative regret with respect to $\beta$-optimal arms is bounded over time with high probability, showcasing both communication efficiency and Byzantine resilience. We analyze the interplay between the algorithm parameters, a discernibility margin, regret, communication cost, and the arms' suboptimality gaps. We demonstrate Fed-MoM-UCB's effectiveness against the baselines in the presence of Byzantine attacks via experiments.

Related papers

• FedCAP: Robust Federated Learning via Customized Aggregation and Personalization [13.17735010891312]
  Federated learning (FL) has been applied to various privacy-preserving scenarios. We propose FedCAP, a robust FL framework against both data heterogeneity and Byzantine attacks. We show that FedCAP performs well in several non-IID settings and shows strong robustness under a series of poisoning attacks.
  arXiv  Detail & Related papers  (2024-10-16T23:01:22Z)
• Byzantine-Resilient Decentralized Multi-Armed Bandits [25.499420566469098]
  We develop an algorithm that fuses an information mixing step among agents with a truncation of inconsistent and extreme values. This framework can be used to model attackers in computer networks, instigators of offensive content into recommender systems, or manipulators of financial markets.
  arXiv  Detail & Related papers  (2023-10-11T09:09:50Z)
• Distributed Consensus Algorithm for Decision-Making in Multi-agent Multi-armed Bandit [7.708904950194129]
  We study a structured multi-agent multi-armed bandit (MAMAB) problem in a dynamic environment. A graph reflects the information-sharing structure among agents, and the arms' reward distributions are piecewise-stationary with several unknown change points. The goal is to develop a decision-making policy for the agents that minimizes the regret, which is the expected total loss of not playing the optimal arm at each time step.
  arXiv  Detail & Related papers  (2023-06-09T16:10:26Z)
• Combating Exacerbated Heterogeneity for Robust Models in Federated Learning [91.88122934924435]
  Combination of adversarial training and federated learning can lead to the undesired robustness deterioration. We propose a novel framework called Slack Federated Adversarial Training (SFAT) We verify the rationality and effectiveness of SFAT on various benchmarked and real-world datasets.
  arXiv  Detail & Related papers  (2023-03-01T06:16:15Z)
• Beyond ADMM: A Unified Client-variance-reduced Adaptive Federated Learning Framework [82.36466358313025]
  We propose a primal-dual FL algorithm, termed FedVRA, that allows one to adaptively control the variance-reduction level and biasness of the global model. Experiments based on (semi-supervised) image classification tasks demonstrate superiority of FedVRA over the existing schemes.
  arXiv  Detail & Related papers  (2022-12-03T03:27:51Z)
• Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
  We consider a distributed reinforcement learning setting where multiple agents explore the environment and communicate their experiences through a central server. $alpha$-fraction of agents are adversarial and can report arbitrary fake information. We seek to identify a near-optimal policy for the underlying Markov decision process in the presence of these adversarial agents.
  arXiv  Detail & Related papers  (2022-06-01T00:44:53Z)
• Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits [91.8283876874947]
  We design and analyze the BoBW-lil'UCB$(gamma)$ algorithm. We show that (i) no algorithm can simultaneously perform optimally for both the RM and BAI objectives. We also show that BoBW-lil'UCB$(gamma)$ outperforms a competitor in terms of the time complexity and the regret.
  arXiv  Detail & Related papers  (2021-10-16T17:52:32Z)
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification [19.777265059976337]
  Fed-SEL is a simple communication-efficient algorithm that builds on successive elimination techniques and involves local sampling steps at the clients. We show that for certain heterogeneous problem instances, Fed-SEL outputs the best-arm after just one round of communication. As our final contribution, we develop variants of Fed-SEL, both for federated and peer-to-peer settings, that are robust to the presence of Byzantine clients.
  arXiv  Detail & Related papers  (2021-09-13T04:22:21Z)
• Low-Latency Federated Learning over Wireless Channels with Differential Privacy [142.5983499872664]
  In federated learning (FL), model training is distributed over clients and local models are aggregated by a central server. In this paper, we aim to minimize FL training delay over wireless channels, constrained by overall training performance as well as each client's differential privacy (DP) requirement.
  arXiv  Detail & Related papers  (2021-06-20T13:51:18Z)
• Softmax with Regularization: Better Value Estimation in Multi-Agent Reinforcement Learning [72.28520951105207]
  Overestimation in $Q$-learning is an important problem that has been extensively studied in single-agent reinforcement learning. We propose a novel regularization-based update scheme that penalizes large joint action-values deviating from a baseline. We show that our method provides a consistent performance improvement on a set of challenging StarCraft II micromanagement tasks.
  arXiv  Detail & Related papers  (2021-03-22T14:18:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.