Differentially Private Online Learning

By Prateek Jain, Pravesh Kothari, Abhradeep Thakurta. 2011

70 citations recorded by the source corpus.

In this paper, we consider the problem of preserving privacy in the online learning setting. We study the problem in the online convex programming (OCP) framework---a popular online learning setting with several interesting theoretical and practical implications---while using differential privacy as the formal privacy measure. For this problem, we distill two critical attributes that a private OCP algorithm should have in order to provide reasonable privacy as well as utility guarantees: 1) linearly decreasing sensitivity, i.e., as new data points arrive their effect on the learning model decreases, 2) sub-linear regret bound---regret bound is a popular goodness/utility measure of an online learning algorithm. Given an OCP algorithm that satisfies these two conditions, we provide a general framework to convert the given algorithm into a privacy preserving OCP algorithm with good (sub-linear) regret. We then illustrate our approach by converting two popular online learning algorithms into their differentially private variants while guaranteeing sub-linear regret ($O(\sqrt{T})$). Next, we consider the special case of online linear regression problems, a practically important class of online learning problems, for which we generalize an approach by Dwork et al. to provide a differentially private algorithm with just $O(\log^{1.5} T)$ regret. Finally, we show that our online learning framework can be used to provide differentially private algorithms for offline learning as well. For the offline learning problem, our approach obtains better error bounds as well as can handle larger class of problems than the existing state-of-the-art methods Chaudhuri et al.

Subfields: Artificial Intelligence, Computer Science Applications

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

In Computer Science Applications

Citations in the corpus

Private Stochastic Convex Optimization with Optimal Rates (2019, positive): “The problem of ERM with differential privacy (DP-ERM) has been well-studied and asymptotically tight upper and lower bounds on excess loss 1 are known [CM08, CMS11, JKT12, KST12, ST13, SCS13, DJW13, Ull15, JT14, BST14, TTZ15, STU17, WLK + 17, WYX17, INS + 19].”
Stochastic gradient descent with differentially private updates (2013, unknown): “[14]; however, their algorithm is just as computationally intensive as batch regularized convex optimization methods.”
Differentially Private Distributed Online Learning (2018, unknown): “Due to the composition theorem in [11], [33], we know that the privacy level of the iterative algorithm will degrade after T -fold adaptive composition.”
When Relaxations Go Bad: "Differentially-Private" Machine Learning (2019, unknown): “For instance, the online version of ERM as considered by Jain et al. [33] requires (cid:15) as high as 10 to achieve acceptable utility.”
Differentially Private Distributed Online Learning (2015, unknown): “Kakade and Tewari [10] and Jain et al. [7] have both proposed that online learning algorithms with good regret bounds can be used to achieve fast convergence rates for ofﬂine learning algorithms.”
Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, methodology): “Previously, the best known risk bounds were Ω( √ pn/ ) for general convex functions and Ω( p √ nΔ 2 ) for Δ-strongly convex functions (achievable via several different techniques ([11, 29, 21, 14])).”
Differential Privacy and Machine Learning: a Survey and Review (2014, unknown): “[25] provides (ǫ, δ)-differentially private versions for two of them: the Implicit Gradient Descent (IGD) and the Generalized Infinitesimal Gradient Ascent (GIGA) given all the functions are L-Lipschitz continuous for some”