The Price of Differential Privacy For Online Learning

2017/01/27 by Naman Agarwal, Karan Singh, Agarwal, Naman +1 · 3 citations
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Privacy-Preserving Technologies in Data #Mobile Crowdsensing and Crowdsourcing

paper · pdf · doi:10.48550/arxiv.1701.07953

Abstract

We design differentially private algorithms for the problem of online linear optimization in the full information and bandit settings with optimal O(√(T)) regret bounds. In the full-information setting, our results demonstrate that ε-differential privacy may be ensured for free -- in particular, the regret bounds scale as O(√(T))+O(\frac1ε). For bandit linear optimization, and as a special case, for non-stochastic multi-armed bandits, the proposed algorithm achieves a regret of O(\frac1ε√(T)), while the previously known best regret bound was O(\frac1εT^(2)/(3)).

Citations

• The Nonstochastic Multiarmed Bandit Problem

Cited by

• Prediction with Expert Advice under Local Differential Privacy
• Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings
• Private Learning of Littlestone Classes, Revisited

Related

• Online Learning via the Differential Privacy Lens
• Differentially Private Online Learning
• Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment
• Private Online Learning via Lazy Algorithms
• Local Differential Privacy for Bayesian Optimization