[2309.00557] Concentrated Differential Privateness for Bandits


Obtain a PDF of the paper titled Concentrated Differential Privateness for Bandits, by Achraf Azize and 1 different authors

Obtain PDF

Summary:Bandits function the theoretical basis of sequential studying and an algorithmic basis of recent recommender methods. Nevertheless, recommender methods typically depend on user-sensitive knowledge, making privateness a essential concern. This paper contributes to the understanding of Differential Privateness (DP) in bandits with a trusted centralised decision-maker, and particularly the implications of making certain zero Concentrated Differential Privateness (zCDP). First, we formalise and examine completely different variations of DP to bandits, relying on the thought of enter and the interplay protocol. Then, we suggest three personal algorithms, particularly AdaC-UCB, AdaC-GOPE and AdaC-OFUL, for 3 bandit settings, particularly finite-armed bandits, linear bandits, and linear contextual bandits. The three algorithms share a generic algorithmic blueprint, i.e. the Gaussian mechanism and adaptive episodes, to make sure privacy-utility trade-off. We analyse and higher sure the remorse of those three algorithms. Our evaluation reveals that in all of those settings, the costs of imposing zCDP are (asymptotically) negligible compared with the regrets incurred oblivious to privateness. Subsequent, we complement our remorse higher bounds with the primary minimax decrease bounds on the remorse of bandits with zCDP. To show the decrease bounds, we elaborate a brand new proof method primarily based on couplings and optimum transport. We conclude by experimentally validating our theoretical outcomes for the three completely different settings of bandits.

Submission historical past

From: Achraf Azize [view email]
Fri, 1 Sep 2023 16:08:00 UTC (278 KB)
Thu, 15 Feb 2024 17:44:24 UTC (661 KB)

Supply hyperlink


Please enter your comment!
Please enter your name here