The Price of Differential Privacy for Online Learning

By Naman Agarwal, Karan Singh. 2017

109 citations recorded by the source corpus.

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)$.

Subfields: Artificial Intelligence, Computer Science Applications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Abhradeep Thakurta
2. Peter Kairouz
3. Om Thakkar
4. Shuang Song
5. Zheng Xu
6. Di Wang
7. Jinhui Xu
8. B. McMahan

In Computer Science Applications

1. Di Wang
2. Jinhui Xu
3. Om Thakkar
4. Shuang Song
5. Abhradeep Thakurta
6. Uthaipon Tao Tantipongpipat
7. Peter Kairouz
8. Rachel Cummings

In Management Science and Operations Research

1. Shuang Song
2. Di Wang
3. Zheng Xu
4. Om Thakkar
5. B. McMahan
6. Abhradeep Thakurta
7. Peter Kairouz
8. Rachel Cummings

Citations in the corpus

• Practical and Private (Deep) Learning without Sampling or Shuffling (2021, background): “Differentially private empirical risk minimization (ERM) and private online learning are well-studied areas in the privacy literature [1, 2, 3, 6, 7, 14, 29, 35, 37, 38, 43, 51, 57, 58, 65, 67, 68, 74] 7 .”
• Differential Privacy for Growing Databases (2018, background): “There is a vast literature on online learning, including several works on differentially private online learning [JKT12, ST13, AS17].”
• Online Learning via the Differential Privacy Lens (2017, unknown): “The classical definition of DP [4] says a randomized algorithm A is ( , δ)-DP if D ∞(A(`1:t),A(`1:t) ≤ whenever `1:t and `1:t differ by at most one item.”
• Differentially Private Empirical Risk Minimization Revisited: Faster and More General (2018, background): “[17][30] and [2] investigated regret bound in online settings.”