Exploiting Heterogeneity in Robust Federated Best-Arm Identification

Abstract

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.

References in corpus (29)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• On the Convergence of FedAvg on Non-IID Data
• Towards Federated Learning at Scale: System Design
• Distributed Learning in Multi-Armed Bandit with Multiple Players
• Improving Federated Learning Personalization via Model Agnostic Meta Learning
• Personalized Federated Learning: A Meta-Learning Approach
• Local SGD Converges Fast and Communicates Little
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• Generalized Byzantine-tolerant SGD
• On the Convergence of Local Descent Methods in Federated Learning
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Robust Federated Learning in a Heterogeneous Environment
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
• FedSplit: An algorithmic framework for fast federated optimization
• Exploiting Shared Representations for Personalized Federated Learning
• Decentralized Cooperative Stochastic Bandits
• First Analysis of Local GD on Heterogeneous Data
• Adversarial Attacks on Stochastic Bandits
• Is Local SGD Better than Minibatch SGD?
• Distributed Exploration in Multi-Armed Bandits
• Data Poisoning Attacks on Stochastic Bandits
• On the Outsized Importance of Learning Rates in Local Update Methods
• Distributed Inference with Sparse and Quantized Communication
• Adversarial Attacks on Linear Contextual Bandits
• Multi-Agent Multi-Armed Bandits with Limited Communication
• Local SGD With a Communication Overhead Depending Only on the Number of Workers
• Distributed Newton Can Communicate Less and Resist Byzantine Workers