Differentially Private Online Learning
Prateek Jain, Pravesh Kothari and Abhradeep Thakurta JMLR W&CP 23: 24.1 - 24.34, 2012
In this paper, we consider the problem of preserving privacy in the context of online learning.
Online learning involves learning from data in real-time, due to which the learned model as well
as its predictions are continuously changing. This makes preserving privacy of each data point
significantly more challenging as its effect on the learned model can be easily tracked by observing
changes in the subsequent predictions. Furthermore, with more and more online systems (e.g.
search engines like Bing, Google etc.) trying to learn their customers' behavior by leveraging their
access to sensitive customer data (through cookies etc.), the problem of privacy preserving online
learning has become critical.
We study the problem in the framework of online convex programming (OCP) -- a popular online learning setting with several theoretical and practical implications -- while using differential privacy as the formal measure of privacy. For this problem, we provide a generic framework that can be used to convert any given OCP algorithm into a private OCP algorithm with provable privacy as well as regret guarantees (utility), provided that the given OCP algorithm satisfies the following two criteria: 1) linearly decreasing sensitivity, i.e., the effect of the new data points on the learned model decreases linearly, 2) sub-linear regret. We then illustrate our approach by converting two popular OCP algorithms into corresponding differentially private algorithms while guaranteeing Õ(√T) regret for strongly convex functions. Next, we consider the practically important class of online linear regression problems, for which we generalize the approach by Dwork et al. (2010a) to provide a differentially private algorithm with just poly-log regret. Finally, we show that our online learning framework can be used to provide differentially private algorithms for the offline learning problem as well. For the offline learning problem, our approach guarantees better error bounds and is more practical than the existing state-of-the-art methods (Chaudhuri et al., 2011; Rubinstein et al., 2009).