Perturb-and-Project: Differentially Private Similarities and Marginals

Vincent Cohen-Addad, Tommaso D’Orsi, Alessandro Epasto, Vahab Mirrokni, Peilin Zhong
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:9161-9179, 2024.

Abstract

We revisit the objective 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 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-cohen-addad24a, title = {Perturb-and-Project: Differentially Private Similarities and Marginals}, author = {Cohen-Addad, Vincent and D'Orsi, Tommaso and Epasto, Alessandro and Mirrokni, Vahab and Zhong, Peilin}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {9161--9179}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/cohen-addad24a/cohen-addad24a.pdf}, url = {https://proceedings.mlr.press/v235/cohen-addad24a.html}, abstract = {We revisit the objective 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 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.} }
Endnote
%0 Conference Paper %T Perturb-and-Project: Differentially Private Similarities and Marginals %A Vincent Cohen-Addad %A Tommaso D’Orsi %A Alessandro Epasto %A Vahab Mirrokni %A Peilin Zhong %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-cohen-addad24a %I PMLR %P 9161--9179 %U https://proceedings.mlr.press/v235/cohen-addad24a.html %V 235 %X We revisit the objective 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 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.
APA
Cohen-Addad, V., D’Orsi, T., Epasto, A., Mirrokni, V. & Zhong, P.. (2024). Perturb-and-Project: Differentially Private Similarities and Marginals. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:9161-9179 Available from https://proceedings.mlr.press/v235/cohen-addad24a.html.

Related Material