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

Abstract

In this paper, we provide lower bounds for Differentially Private (DP) Online Learning algorithms. Our result shows that, for a broad class of $(\epsilon ,\delta )$-DP online algorithms, for number of rounds $T$ such that $\log T\le 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 $T$. To the best of our knowledge, our work is the first result towards settling lower bounds for DP-Online learning and partially addresses the open question in Sanyal and Ramponi (2022).

Accepted at the Conference on Learning Theory (COLT) 2024, Edmonton, Canada