On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective

arXiv:2402.16778v1 Announce Type: cross
Abstract: In this paper, we provide lower bounds for Differentially Private (DP) Online Learning algorithms. Our result shows that, for a broad class of $(\varepsilon,\delta)$-DP online algorithms, for $T$ such that $\log T\leq O(1 / \delta)$, the expected number of mistakes incurred by the algorithm grows as $\Omega(\log \frac{T}{\delta})$. This matches the upper bound obtained by Golowich and Livni (2021) and is in contrast to non-private online learning where the number of mistakes is independent of …

algorithms arxiv class cs.cr cs.lg delta growth log mistakes online learning perspective private result