Federated Online Clustering of Bandits
- URL: http://arxiv.org/abs/2208.14865v1
- Date: Wed, 31 Aug 2022 13:46:02 GMT
- Title: Federated Online Clustering of Bandits
- Authors: Xutong Liu, Haoru Zhao, Tong Yu, Shuai Li, John C.S. Lui
- Abstract summary: Contextual multi-armed bandit (MAB) is an important sequential decision-making problem in recommendation systems.
We study the federated online clustering of bandit (FCLUB) problem, which aims to minimize the total regret while satisfying privacy and communication considerations.
- Score: 35.21933787486559
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Contextual multi-armed bandit (MAB) is an important sequential
decision-making problem in recommendation systems. A line of works, called the
clustering of bandits (CLUB), utilize the collaborative effect over users and
dramatically improve the recommendation quality. Owing to the increasing
application scale and public concerns about privacy, there is a growing demand
to keep user data decentralized and push bandit learning to the local server
side. Existing CLUB algorithms, however, are designed under the centralized
setting where data are available at a central server. We focus on studying the
federated online clustering of bandit (FCLUB) problem, which aims to minimize
the total regret while satisfying privacy and communication considerations. We
design a new phase-based scheme for cluster detection and a novel asynchronous
communication protocol for cooperative bandit learning for this problem. To
protect users' privacy, previous differential privacy (DP) definitions are not
very suitable, and we propose a new DP notion that acts on the user cluster
level. We provide rigorous proofs to show that our algorithm simultaneously
achieves (clustered) DP, sublinear communication complexity and sublinear
regret. Finally, experimental evaluations show our superior performance
compared with benchmark algorithms.
Related papers
- Meta Clustering of Neural Bandits [45.77505279698894]
We study a new problem, Clustering of Neural Bandits, by extending previous work to the arbitrary reward function.
We propose a novel algorithm called M-CNB, which utilizes a meta-learner to represent and rapidly adapt to dynamic clusters.
In extensive experiments conducted in both recommendation and online classification scenarios, M-CNB outperforms SOTA baselines.
arXiv Detail & Related papers (2024-08-10T16:09:51Z) - Privacy Preserving Semi-Decentralized Mean Estimation over Intermittently-Connected Networks [59.43433767253956]
We consider the problem of privately estimating the mean of vectors distributed across different nodes of an unreliable wireless network.
In a semi-decentralized setup, nodes can collaborate with their neighbors to compute a local consensus, which they relay to a central server.
We study the tradeoff between collaborative relaying and privacy leakage due to the data sharing among nodes.
arXiv Detail & Related papers (2024-06-06T06:12:15Z) - On Differentially Private Federated Linear Contextual Bandits [9.51828574518325]
We consider cross-silo federated linear contextual bandit (LCB) problem under differential privacy.
We identify three issues in the state-of-the-art: (i) failure of claimed privacy protection and (ii) incorrect regret bound due to noise miscalculation.
We show that our algorithm can achieve nearly optimal'' regret without a trusted server.
arXiv Detail & Related papers (2023-02-27T16:47:49Z) - Semi-decentralized Federated Ego Graph Learning for Recommendation [58.21409625065663]
We propose a semi-decentralized federated ego graph learning framework for on-device recommendations, named SemiDFEGL.
The proposed framework is model-agnostic, meaning that it could be seamlessly integrated with existing graph neural network-based recommendation methods and privacy protection techniques.
arXiv Detail & Related papers (2023-02-10T03:57:45Z) - On Differential Privacy for Federated Learning in Wireless Systems with
Multiple Base Stations [90.53293906751747]
We consider a federated learning model in a wireless system with multiple base stations and inter-cell interference.
We show the convergence behavior of the learning process by deriving an upper bound on its optimality gap.
Our proposed scheduler improves the average accuracy of the predictions compared with a random scheduler.
arXiv Detail & Related papers (2022-08-25T03:37:11Z) - Decentralized Stochastic Optimization with Inherent Privacy Protection [103.62463469366557]
Decentralized optimization is the basic building block of modern collaborative machine learning, distributed estimation and control, and large-scale sensing.
Since involved data, privacy protection has become an increasingly pressing need in the implementation of decentralized optimization algorithms.
arXiv Detail & Related papers (2022-05-08T14:38:23Z) - Near-Optimal Correlation Clustering with Privacy [37.94795032297396]
Correlation clustering is a central problem in unsupervised learning.
In this paper, we introduce a simple and computationally efficient algorithm for the correlation clustering problem with provable privacy guarantees.
arXiv Detail & Related papers (2022-03-02T22:30:19Z) - Local Clustering in Contextual Multi-Armed Bandits [44.11480686973274]
We study identifying user clusters in contextual multi-armed bandits (MAB)
We propose a bandit algorithm, LOCB, embedded with local clustering procedure.
We evaluate the proposed algorithm from various aspects, which outperforms state-of-the-art baselines.
arXiv Detail & Related papers (2021-02-26T21:59:29Z) - Differentially Private k-Means Clustering with Guaranteed Convergence [5.335316436366718]
Iterative clustering algorithms help us to learn the insights behind the data.
It may allow adversaries to infer the privacy of individuals with some background knowledge.
To protect individual privacy against such an inference attack, preserving differential privacy (DP) for the iterative clustering algorithms has been extensively studied.
arXiv Detail & Related papers (2020-02-03T22:53:47Z)
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.