Dynamic Global Sensitivity for Differentially Private Contextual Bandits
Bandit algorithms have become a reference solution for interactive recommendation. However, as such algorithms directly interact with users for improved recommendations, serious privacy concerns have been raised regarding its practical use. In this work, we propose a differentially private linear contextual bandit algorithm, via a tree-based mechanism to add Laplace or Gaussian noise to model parameters. Our key insight is that as the model converges during online update, the global sensitivity of its parameters shrinks over time (thus named dynamic global sensitivity). Compared with existing solutions, our dynamic global sensitivity analysis allows us to inject less noise to obtain $(\epsilon, \delta)$-differential privacy with added regret caused by noise injection in $\tilde O(\log{T}\sqrt{T}/\epsilon)$. We provide a rigorous theoretical analysis over the amount of noise added via dynamic global sensitivity and the corresponding upper regret bound of our proposed algorithm. Experimental results on both synthetic and real-world datasets confirmed the algorithm's advantage against existing solutions.
Code (0)
등록된 구현이 없습니다.
Tasks
Interactive RecommendationMulti-Armed BanditsSensitivitySimilar Papers 제목 키워드 기반
Differentially Private Selection using Smooth Sensitivity
Differentially private selection mechanisms offer strong privacy guarantees for queries aiming to identify the top-scoring element r from a finite set R, based on a dataset-dependent utility function. While selection que…
SensitivityPain-Free Random Differential Privacy with Sensitivity Sampling
Popular approaches to differential privacy, such as the Laplace and exponential mechanisms, calibrate randomised smoothing through global sensitivity of the target non-private function. Bounding such sensitivity is often…
SensitivityDifferentially Private Naive Bayes Classifier using Smooth Sensitivity
With the increasing collection of users' data, protecting individual privacy has gained more interest. Differential Privacy is a strong concept of protecting individuals. Naive Bayes is one of the popular machine learnin…
SensitivityRenyi Differential Privacy of Propose-Test-Release and Applications to Private and Robust Machine Learning
Propose-Test-Release (PTR) is a differential privacy framework that works with local sensitivity of functions, instead of their global sensitivity. This framework is typically used for releasing robust statistics such as…
SensitivityRepresentation Transfer for Differentially Private Drug Sensitivity Prediction
Motivation: Human genomic datasets often contain sensitive information that limits use and sharing of the data. In particular, simple anonymisation strategies fail to provide sufficient level of protection for genomic da…
BIG-bench Machine LearningCancer type classificationDimensionality ReductionPrediction+2