A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits
We study federated contextual linear bandits, where $M$ agents cooperate with each other to solve a global contextual linear bandit problem with the help of a central server. We consider the asynchronous setting, where all agents work independently and the communication between one agent and the server will not trigger other agents' communication. We propose a simple algorithm named \texttt{FedLinUCB} based on the principle of optimism. We prove that the regret of \texttt{FedLinUCB} is bounded by $\tilde{O}(d\sqrt{\sum_{m=1}^M T_m})$ and the communication complexity is $\tilde{O}(dM^2)$, where $d$ is the dimension of the contextual vector and $T_m$ is the total number of interactions with the environment by $m$-th agent. To the best of our knowledge, this is the first provably efficient algorithm that allows fully asynchronous communication for federated contextual linear bandits, while achieving the same regret guarantee as in the single-agent setting.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits
Linear contextual bandit is a popular online learning problem. It has been mostly studied in centralized learning settings. With the surging demand of large-scale decentralized model learning, e.g., federated learning, h…
Federated LearningFederated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users
We study the problem of federated contextual combinatorial cascading bandits, where $|\mathcal{U}|$ agents collaborate under the coordination of a central server to provide tailored recommendations to the $|\mathcal{U}|$…
Achieving Linear Speedup in Asynchronous Federated Learning with Heterogeneous Clients
Federated learning (FL) is an emerging distributed training paradigm that aims to learn a common global model without exchanging or transferring the data that are stored locally at different clients. The Federated Averag…
Federated LearningFirst Provably Optimal Asynchronous SGD for Homogeneous and Heterogeneous Data
Artificial intelligence has advanced rapidly through large neural networks trained on massive datasets using thousands of GPUs or TPUs. Such training can occupy entire data centers for weeks and requires enormous computa…
Stochastic OptimizationFederated LearningFair and efficient contribution valuation for vertical federated learning
Federated learning is a popular technology for training machine learning models on distributed data sources without sharing data. Vertical federated learning or feature-based federated learning applies to the cases that …
FairnessFederated LearningVertical Federated Learning