Private Prediction via Shrinkage

Abstract

We study differentially private prediction introduced by Dwork and Feldman (COLT 2018): an algorithm receives one labeled sample set $S$ and then answers a stream of unlabeled queries while the output transcript remains $(\epsilon ,\delta )$-differentially private with respect to $S$. Standard composition yields a $\sqrt{T}$ dependence for $T$ queries. We show that this dependence can be reduced to polylogarithmic in $T$ in streaming settings. For an oblivious online adversary and any concept class $\mathcal{C}$, we give a private predictor that answers $T$ queries with $|S|=\tilde{O}(VC(\mathcal{C}{)}^{3.5}{\log }^{3.5}T)$ labeled examples. For an adaptive online adversary and halfspaces over ${\mathbb{R}}^d$, we obtain $|S|=\tilde{O}\left(d^{5.5}\log T\right)$.