Poster
Perturb-and-Project: Differentially Private Similarities and Marginals
Vincent Cohen-Addad · Tommaso d'Orsi · Alessandro Epasto · Vahab Mirrokni · Peilin Zhong
Hall C 4-9
[
Abstract
]
Tue 23 Jul 2:30 a.m. PDT
— 4 a.m. PDT
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.
Live content is unavailable. Log in and register to view live content