(Nearly) Optimal Algorithms for Private Online Learning in Full-information and Bandit Settings
We give differentially private algorithms for a large class of online learning algorithms, in both the full information and bandit settings. Our algorithms aim to minimize a convex loss function which is a sum of smaller convex loss terms, one for each data point. To design our algorithms, we modify the popular mirror descent approach, or rather a variant called follow the approximate leader. The technique leads to the first nonprivate algorithms for private online learning in the bandit setting. In the full information setting, our algorithms improve over the regret bounds of previous work (due to Dwork, Naor, Pitassi and Rothblum (2010) and Jain, Kothari and Thakurta (2012)). In many cases, our algorithms (in both settings) match the dependence on the input length, T , of the optimal nonprivate regret bounds up to logarithmic factors in T . Our algorithms require logarithmic space and update time.
This work provides new algorithms for differentially 
      private online learning in basically all settings where results are known 
      in the non-private case. The results very closely parallel (with some 
      additional small factors and dependences) the best non-private bounds. 
      There has been significant recent interest in differentially private 
      learning, and this paper gives a much more comprehensive and compelling 
      suite of results than previous work. The approach is actually 
      quite simple at its heart---do follow the approximate leader using a 
      private (noisy) history that you maintain using standard algorithms for 
      maintaining a differentially private counter. The natural suitability of 
      follow the leader algorithms for privacy has been observed before, but the 
      treatment here and the actual bounds obtained are very nice. I'd 
      prefer that you describe this work as giving a class of private learning 
      algorithms, or a technique for constructing such algorithms, rather than a 
      "general technique for making online algorithms differentially private" 
      (since it's not the case that you can take an arbitrary online algorithm 
      and make it private using this technique---right?). The practice 
      of citing references without listing authors made this paper hard to 
      read---I was constantly flipping to the bibliography, since in many cases 
      knowing the reference was important to understanding the ideas (e.g. in 
      cases where the text did not make sufficiently clear whether the 
      referenced work was in the private or non-private case). In Table 
      1, it's probably worth reminding the reader that the delta in the first 
      column comes from (eps, delta)-DP. Why aren't there citations for 
      the non-private results in Table 2? And also, the caption says it's the 
      full-information setting, but the results are clearly for the bandit 
      setting. And it seems your results for the adaptive case should have a 
      T^3/4, not T^2/3, no? Do you think the explicit dependences you 
      see on the dimensionality are necessary when preserving privacy? Do you 
      think there's a provable (small) gap between what is achievable in the 
      dependence on T between private and non-private algorithms (accounting for 
      your different poly-log factors)? The second to last paragraph on 
      p.6 has strange redundancy.