On The Differential Privacy of Thompson Sampling With Gaussian Prior

2018/06/24 by Aristide C. Y. Tossou, Tossou, Aristide C. Y., Christos Dimitrakakis +1
Computer Science · #Artificial Intelligence (cs.AI) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Machine Learning (cs.LG) #cs.AI #cs.CR #cs.LG

paper · pdf · doi:10.48550/arxiv.1806.09192

Accepted in Privacy in Machine Learning and Artificial Intelligence Workshop 2018

arxiv created 2018/06/24 · arxiv updated 2018/06/26

Abstract

We show that Thompson Sampling with Gaussian Prior as detailed by Algorithm 2 in (Agrawal & Goyal, 2013) is already differentially private. Theorem 1 show that it enjoys a very competitive privacy loss of only O(ln² T) after T rounds. Finally, Theorem 2 show that one can control the privacy loss to any desirable ε level by appropriately increasing the variance of the samples from the Gaussian posterior. And this increases the regret only by a term of O(\fracln² Tε). This compares favorably to the previous result for Thompson Sampling in the literature ((Mishra & Thakurta, 2015)) which adds a term of O((K ln³ T)/(ε²)) to the regret in order to achieve the same privacy level. Furthermore, our result use the basic Thompson Sampling with few modifications whereas the result of (Mishra & Thakurta, 2015) required sophisticated constructions.

Related

• Thompson Sampling Itself is Differentially Private
• Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret
• Differential Privacy and Survey Sampling
• Privacy Guarantees in Posterior Sampling under Contamination
• Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising