Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2406.02140 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916273778065408 |
|---|---|
| author | Liu, Jingcheng Upadhyay, Jalaj Zou, Zongrui |
| author_facet | Liu, Jingcheng Upadhyay, Jalaj Zou, Zongrui |
| contents | In this paper, we introduce the $\ell_p^p$-error metric (for $p \geq 2$) when answering linear queries under the constraint of differential privacy. We characterize such an error under $(ε,δ)$-differential privacy. Before this paper, tight characterization in the hardness of privately answering linear queries was known under $\ell_2^2$-error metric (Edmonds et al., STOC 2020) and $\ell_p^2$-error metric for unbiased mechanisms (Nikolov and Tang, ITCS 2024). As a direct consequence of our results, we give tight bounds on answering prefix sum and parity queries under differential privacy for all constant $p$ in terms of the $\ell_p^p$ error, generalizing the bounds in Henzinger et al. (SODA 2023) for $p=2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_02140 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimality of Matrix Mechanism on $\ell_p^p$-metric Liu, Jingcheng Upadhyay, Jalaj Zou, Zongrui Cryptography and Security Machine Learning In this paper, we introduce the $\ell_p^p$-error metric (for $p \geq 2$) when answering linear queries under the constraint of differential privacy. We characterize such an error under $(ε,δ)$-differential privacy. Before this paper, tight characterization in the hardness of privately answering linear queries was known under $\ell_2^2$-error metric (Edmonds et al., STOC 2020) and $\ell_p^2$-error metric for unbiased mechanisms (Nikolov and Tang, ITCS 2024). As a direct consequence of our results, we give tight bounds on answering prefix sum and parity queries under differential privacy for all constant $p$ in terms of the $\ell_p^p$ error, generalizing the bounds in Henzinger et al. (SODA 2023) for $p=2$. |
| title | Optimality of Matrix Mechanism on $\ell_p^p$-metric |
| topic | Cryptography and Security Machine Learning |
| url | https://arxiv.org/abs/2406.02140 |