Dynamic Global Sensitivity for Differentially Private Contextual Bandits

Abstract

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.

arXiv commentRecSys 2022

References in corpus (9)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Online Clustering of Bandits
• AdaCliP: Adaptive Clipping for Private SGD
• Differentially Private Contextual Linear Bandits
• The Price of Differential Privacy For Online Learning
• Differentially-Private Federated Linear Bandits
• Multi-Armed Bandits with Local Differential Privacy
• Locally Differentially Private (Contextual) Bandits Learning
• Generalized Linear Bandits with Local Differential Privacy