Timezone: »
Talk
The Price of Differential Privacy For Online Learning
Naman Agarwal · Karan Singh
We design differentially private algorithms for the problem of online linear optimization in the full information and bandit settings with optimal O(T^0.5) 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^0.5+1/ε). For bandit linear optimization, and as a special case, for non-stochastic multi-armed bandits, the proposed algorithm achieves a regret of O(T^0.5/ε), while the previously best known regret bound was O(T^{2/3}/ε).
Author Information
Naman Agarwal (Princeton University)
Karan Singh (Princeton University)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Poster: The Price of Differential Privacy For Online Learning »
Wed. Aug 9th 08:30 AM -- 12:00 PM Room Gallery #68
More from the Same Authors
-
2019 Poster: Efficient Full-Matrix Adaptive Regularization »
Naman Agarwal · Brian Bullins · Xinyi Chen · Elad Hazan · Karan Singh · Cyril Zhang · Yi Zhang -
2019 Poster: Online Control with Adversarial Disturbances »
Naman Agarwal · Brian Bullins · Elad Hazan · Sham Kakade · Karan Singh -
2019 Oral: Efficient Full-Matrix Adaptive Regularization »
Naman Agarwal · Brian Bullins · Xinyi Chen · Elad Hazan · Karan Singh · Cyril Zhang · Yi Zhang -
2019 Oral: Online Control with Adversarial Disturbances »
Naman Agarwal · Brian Bullins · Elad Hazan · Sham Kakade · Karan Singh -
2019 Poster: Provably Efficient Maximum Entropy Exploration »
Elad Hazan · Sham Kakade · Karan Singh · Abby Van Soest -
2019 Oral: Provably Efficient Maximum Entropy Exploration »
Elad Hazan · Sham Kakade · Karan Singh · Abby Van Soest -
2017 Poster: Efficient Regret Minimization in Non-Convex Games »
Elad Hazan · Karan Singh · Cyril Zhang -
2017 Talk: Efficient Regret Minimization in Non-Convex Games »
Elad Hazan · Karan Singh · Cyril Zhang