# On Differentially Private Online Predictions

arXiv: https://arxiv.org/abs/2302.14099 · HTML: https://mlsanity.com/paper/2302.14099/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 23 references that are in the map.
- First posted on arXiv 27 Feb 2023.

## Builds on (most cited first, 8 of 8)

- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [The Price of Differential Privacy For Online Learning](https://mlsanity.com/paper/1701.07953/) (2017)
- [The Price of Differential Privacy under Continual Observation](https://mlsanity.com/paper/2112.00828/) (2021)
- [Make Up Your Mind: The Price of Online Queries in Differential Privacy](https://mlsanity.com/paper/1604.04618/) (2016)
- [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022)
- [Littlestone Classes are Privately Online Learnable](https://mlsanity.com/paper/2106.13513/) (2021)
- [The Sparse Vector Technique, Revisited](https://mlsanity.com/paper/2010.00917/) (2020)
- [Robust Mediators in Large Games](https://mlsanity.com/paper/1512.02698/) (2015)

## Built on by (most cited first, 3 of 3)

- [Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noise](https://mlsanity.com/paper/2407.20068/) (2024)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)
- [Online Distribution Learning with Local Private Constraints](https://mlsanity.com/paper/2402.00315/) (2024)

## Abstract (arXiv)

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