Perturb-and-Project: Differentially Private Similarities and Marginals
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916350247567360 |
|---|---|
| author | Cohen-Addad, Vincent d'Orsi, Tommaso Epasto, Alessandro Mirrokni, Vahab Zhong, Peilin |
| author_facet | Cohen-Addad, Vincent d'Orsi, Tommaso Epasto, Alessandro Mirrokni, Vahab Zhong, Peilin |
| contents | We revisit the input perturbations framework for differential privacy where noise is added to the input $A\in \mathcal{S}$ and the result is then projected back to the space of admissible datasets $\mathcal{S}$. Through this framework, we first design novel efficient algorithms to privately release pair-wise cosine similarities. Second, we derive a novel algorithm to compute $k$-way marginal queries over $n$ features. Prior work could achieve comparable guarantees only for $k$ even. Furthermore, we extend our results to $t$-sparse datasets, where our efficient algorithms yields novel, stronger guarantees whenever $t\le n^{5/6}/\log n\,.$ Finally, we provide a theoretical perspective on why \textit{fast} input perturbation algorithms works well in practice. The key technical ingredients behind our results are tight sum-of-squares certificates upper bounding the Gaussian complexity of sets of solutions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_04868 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Perturb-and-Project: Differentially Private Similarities and Marginals Cohen-Addad, Vincent d'Orsi, Tommaso Epasto, Alessandro Mirrokni, Vahab Zhong, Peilin Machine Learning Cryptography and Security Data Structures and Algorithms F.2; G.3 We revisit the input perturbations framework for differential privacy where noise is added to the input $A\in \mathcal{S}$ and the result is then projected back to the space of admissible datasets $\mathcal{S}$. Through this framework, we first design novel efficient algorithms to privately release pair-wise cosine similarities. Second, we derive a novel algorithm to compute $k$-way marginal queries over $n$ features. Prior work could achieve comparable guarantees only for $k$ even. Furthermore, we extend our results to $t$-sparse datasets, where our efficient algorithms yields novel, stronger guarantees whenever $t\le n^{5/6}/\log n\,.$ Finally, we provide a theoretical perspective on why \textit{fast} input perturbation algorithms works well in practice. The key technical ingredients behind our results are tight sum-of-squares certificates upper bounding the Gaussian complexity of sets of solutions. |
| title | Perturb-and-Project: Differentially Private Similarities and Marginals |
| topic | Machine Learning Cryptography and Security Data Structures and Algorithms F.2; G.3 |
| url | https://arxiv.org/abs/2406.04868 |