Timezone: »

Locally Differentially Private (Contextual) Bandits Learning
Kai Zheng · Tianle Cai · Weiran Huang · Zhenguo Li · Liwei Wang

Tue Dec 08 09:00 PM -- 11:00 PM (PST) @ Poster Session 2 #645
We study locally differentially private (LDP) bandits learning in this paper. First, we propose simple black-box reduction frameworks that can solve a large family of context-free bandits learning problems with LDP guarantee. Based on our frameworks, we can improve previous best results for private bandits learning with one-point feedback, such as private Bandits Convex Optimization etc, and obtain the first results for Bandits Convex Optimization (BCO) with multi-point feedback under LDP. LDP guarantee and black-box nature make our frameworks more attractive in real applications compared with previous specifically designed and relatively weaker differentially private (DP) algorithms. Further, we also extend our algorithm to Generalized Linear Bandits with regret bound $\tilde{\mc{O}}(T^{3/4}/\varepsilon)$ under $(\varepsilon, \delta)$-LDP and it is conjectured to be optimal. Note given existing $\Omega(T)$ lower bound for DP contextual linear bandits (Shariff & Sheffet, NeurIPS 2018), our result shows a fundamental difference between LDP and DP for contextual bandits.

Author Information

Kai Zheng (Kuaishou)
Tianle Cai (Princeton University)
Weiran Huang (Noah's Ark Lab)
Zhenguo Li (Noah's Ark Lab, Huawei Tech Investment Co Ltd)
Liwei Wang (Peking University)

More from the Same Authors