Poster
in
Workshop: Trustworthy and Socially Responsible Machine Learning
Distributed Differential Privacy in Multi-Armed Bandits
Sayak Ray Chowdhury · Xingyu Zhou
Abstract:
We consider the standard -armed bandit problem under a distributed trust model of differential privacy (DP), which enables to guarantee privacy without a trustworthy server. Under this trust model, previous work largely focus on achieving privacy using a shuffle protocol, where a batch of users data are randomly permuted before sending to a central server. This protocol achieves () or approximate-DP guarantee by sacrificing an additive factor in -step cumulative regret. In contrast, the optimal privacy cost to achieve a stronger () or pure-DP guarantee under the widely used central trust model is only , where, however, a trusted server is required. In this work, we aim to obtain a pure-DP guarantee under distributed trust model while sacrificing no more regret than that under central trust model. We achieve this by designing a generic bandit algorithm based on successive arm elimination, where privacy is guaranteed by corrupting rewards with an equivalent discrete Laplace noise ensured by a secure computation protocol. We numerically simulate regret performance of our algorithm, which corroborate our theoretical findings.
Chat is not available.