On Differentially Private Online Predictions
This work addresses privacy concerns in online prediction tasks, offering a less restrictive and more efficient approach for applications like real-time data processing, though it is incremental in refining existing privacy definitions.
The paper tackles the problem of ensuring privacy in online learning by introducing an interactive variant of joint differential privacy, showing that it allows transforming any non-private learning rule into a private one with only a polynomial overhead in mistake bounds, unlike more restrictive notions that require double exponential overhead.
In this work we introduce an interactive variant of joint differential privacy towards handling online processes in which existing privacy definitions seem too restrictive. We study basic properties of this definition and demonstrate that it satisfies (suitable variants) of group privacy, composition, and post processing. We then study the cost of interactive joint privacy in the basic setting of online classification. We show that any (possibly non-private) learning rule can be effectively transformed to a private learning rule with only a polynomial overhead in the mistake bound. This demonstrates a stark difference with more restrictive notions of privacy such as the one studied by Golowich and Livni (2021), where only a double exponential overhead on the mistake bound is known (via an information theoretic upper bound).