On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective
<|reference_start|>On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective: 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 number of rounds $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 $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).<|reference_end|>
@article{dmitriev2024on,
    title={On the Growth of Mistakes in Differentially Private Online Learning: A
  Lower Bound Perspective},
    author={Daniil Dmitriev, Krist'of Szab'o, Amartya Sanyal},
    journal={arXiv preprint arXiv:2402.16778},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.16778},
    primaryClass={cs.LG cs.CR}
}