The Price of Differential Privacy For Online Learning

Abstract

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

To appear in the Proceedings of the 34th International Conference on Machine Learning (ICML), Sydney, Australia, 2017

References in corpus (2)

• Adaptive Online Prediction by Following the Perturbed Leader
• Towards minimax policies for online linear optimization with bandit feedback

Cited by in corpus (11)

• Practical and Private (Deep) Learning without Sampling or Shuffling
• Differentially Private Empirical Risk Minimization Revisited: Faster and More General
• Locally Differentially Private (Contextual) Bandits Learning
• Privacy-preserving Q-Learning with Functional Noise in Continuous State Spaces
• An Equivalence Between Private Classification and Online Prediction
• Dynamic Global Sensitivity for Differentially Private Contextual Bandits
• On the Equivalence between Online and Private Learnability beyond Binary Classification
• Privacy-Constrained Policies via Mutual Information Regularized Policy Gradients
• On The Differential Privacy of Thompson Sampling With Gaussian Prior
• Differentially Private Online Submodular Optimization
• Learning Optimal Reserve Price against Non-myopic Bidders