THE CONFERENCE
FOR AUTHORS
FOR PARTICIPANTS

Timezone: »

 
Talk
The Price of Differential Privacy For Online Learning
Naman Agarwal · Karan Singh

Tue Aug 08 08:30 PM -- 08:48 PM (PDT) @ C4.8
in Privacy and security 2 »

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}/ε).

[ PDF]  [ ss Summary/Notes]  [ Video] 

Author Information

Naman Agarwal (Princeton University)
Karan Singh (Princeton University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors