mlsanityData to 13 Oct 2026

Exploiting Heterogeneity in Robust Federated Best-Arm Identification

arXiv 2109.05700 ↗First posted 13 Sep 2021cs.LG cs.SY eess.SYcited by 20

Not on the map. Why?

Abstract (arXiv)

We study a federated variant of the best-arm identification problem in stochastic multi-armed bandits: a set of clients, each of whom can sample only a subset of the arms, collaborate via a server to identify the best arm (i.e., the arm with the highest mean reward) with prescribed confidence. For this problem, we propose Fed-SEL, a simple communication-efficient algorithm that builds on successive elimination techniques and involves local sampling steps at the clients. To study the performance of Fed-SEL, we introduce a notion of arm-heterogeneity that captures the level of dissimilarity between distributions of arms corresponding to different clients. Interestingly, our analysis reveals the benefits of arm-heterogeneity in reducing both the sample- and communication-complexity of Fed-SEL. As a special case of our analysis, we show that for certain heterogeneous problem instances, Fed-SEL outputs the best-arm after just one round of communication. Our findings have the following key implication: unlike federated supervised learning where recent work has shown that statistical heterogeneity can lead to poor performance, one can provably reap the benefits of both local computation and heterogeneity for federated best-arm identification. 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, and hence suitable for deployment in harsh, adversarial environments.

Key facts. Cited by 20 papers in the map (data through 13 Oct 2026). Builds on 64 of its 98 references that are in the map. First posted on arXiv 13 Sep 2021.

Builds on

64 of 98 references.

References · 64

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,653
  2. 2019Advances and Open Problems in Federated Learningcited by 3,040
  3. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,538
  4. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,470
  5. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,227
  6. 2020Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimizationcited by 903
  7. 2019Towards Federated Learning at Scale: System Designcited by 830
  8. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 708
  9. 2018Local SGD Converges Fast and Communicates Littlecited by 601
  10. 2021Exploiting Shared Representations for Personalized Federated Learningcited by 539
  11. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 364
  12. 2019FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantizationcited by 356
38 more
  1. 2020Personalized Federated Learning: A Meta-Learning Approachcited by 311
  2. 2019Improving Federated Learning Personalization via Model Agnostic Meta Learningcited by 268
  3. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  4. 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 160
  5. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 152
  6. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  7. 2013lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Banditscited by 148
  8. 2018RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasetscited by 148
  9. 2020Lower Bounds and Optimal Algorithms for Personalized Federated Learningcited by 122
  10. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  11. 2020FedSplit: An algorithmic framework for fast federated optimizationcited by 108
  12. 2019Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronizationcited by 107
  13. 2018Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithmscited by 106
  14. 2020Robust Federated Learning: The Case of Affine Distribution Shiftscited by 102
  15. 2018Generalized Byzantine-tolerant SGDcited by 94
  16. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  17. 2019Robust Federated Learning in a Heterogeneous Environmentcited by 89
  18. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
  19. 2021Heterogeneity for the Win: One-Shot Federated Clusteringcited by 87
  20. 2020Differentially-Private Federated Linear Banditscited by 83
  21. 2018Byzantine Stochastic Gradient Descentcited by 81
  22. 2019First Analysis of Local GD on Heterogeneous Datacited by 81
  23. 2020From Local SGD to Local Fixed-Point Methods for Federated Learningcited by 74
  24. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  25. 2021Federated Multi-armed Bandits with Personalizationcited by 62
  26. 2018Adversarial Attacks on Stochastic Banditscited by 56
  27. 2020Straggler-Resilient Federated Learning: Leveraging the Interplay Between Statistical Accuracy and System Heterogeneitycited by 56
  28. 2020Federated Bandit: A Gossiping Approachcited by 55
  29. 2019Data Poisoning Attacks on Stochastic Banditscited by 53
  30. 2021Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learningcited by 52
  31. 2016Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithmscited by 48
  32. 2019Social Learning in Multi Agent Multi Armed Banditscited by 48
  33. 2013Distributed Exploration in Multi-Armed Banditscited by 46
  34. 2019Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Banditscited by 40
  35. 2020The Gossiping Insert-Eliminate Algorithm for Multi-Agent Banditscited by 38
  36. 2020Distributed Cooperative Decision Making in Multi-agent Multi-armed Banditscited by 38
  37. 2020On the Outsized Importance of Learning Rates in Local Update Methodscited by 36
  38. 2020Adversarial Attacks on Linear Contextual Banditscited by 34

50 most cited of 64 All 64 (JSON)

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2022: 8; 2023: 7; 2024: 2; 2025: 2; 2026: 1.

20 papers.

Sort:

  1. 2022Near-Optimal Collaborative Learning in Banditscited by 18
  2. 2022Almost Cost-Free Communication in Federated Best Arm Identificationcited by 11
  3. 2023Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewardscited by 11
  4. 2022Federated Best Arm Identification with Heterogeneous Clientscited by 8
  5. 2022Distributed Linear Bandits under Communication Constraintscited by 8
  6. 2022Federated Multi-Armed Bandits Under Byzantine Attackscited by 6
  7. 2022Parallel Best Arm Identification in Heterogeneous Environmentscited by 6
  8. 2023Pure Exploration in Asynchronous Federated Banditscited by 6
  9. 2022Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Boundscited by 5
  10. 2022Communication-Efficient Collaborative Best Arm Identificationcited by 5
  11. 2023Federated Learning for Heterogeneous Bandits with Unobserved Contextscited by 1
  12. 2023Regret Lower Bounds in Multi-agent Multi-armed Banditcited by 1
8 more
  1. 2024Decentralized Blockchain-based Robust Multi-agent Multi-armed Banditcited by 1
  2. 2023ICQ: A Quantization Scheme for Best-Arm Identification Over Bit-Constrained Channelscited by 0
  3. 2023Reward Teaching for Federated Multi-armed Banditscited by 0
  4. 2023Distributed Optimization via Kernelized Multi-armed Banditscited by 0
  5. 2024Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomnesscited by 0
  6. 2025Near Optimal Best Arm Identification for Clustered Banditscited by 0
  7. 2025Service Placement in Small Cell Networks Using Distributed Best Arm Identification in Linear Banditscited by 0
  8. 2026ICMAPE: In-Context Multiagent Pure Explorationcited by 0