On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909355441389568 |
|---|---|
| author | Dmitriev, Daniil Szabó, Kristóf Sanyal, Amartya |
| author_facet | Dmitriev, Daniil Szabó, Kristóf Sanyal, Amartya |
| contents | In this paper, we provide lower bounds for Differentially Private (DP) Online Learning algorithms. Our result shows that, for a broad class of $(\varepsilon,δ)$-DP online algorithms, for number of rounds $T$ such that $\log T\leq O(1 / δ)$, the expected number of mistakes incurred by the algorithm grows as $Ω(\log \frac{T}δ)$. 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_16778 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective Dmitriev, Daniil Szabó, Kristóf Sanyal, Amartya Machine Learning Cryptography and Security In this paper, we provide lower bounds for Differentially Private (DP) Online Learning algorithms. Our result shows that, for a broad class of $(\varepsilon,δ)$-DP online algorithms, for number of rounds $T$ such that $\log T\leq O(1 / δ)$, the expected number of mistakes incurred by the algorithm grows as $Ω(\log \frac{T}δ)$. 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). |
| title | On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective |
| topic | Machine Learning Cryptography and Security |
| url | https://arxiv.org/abs/2402.16778 |