Perturb-and-Project: Differentially Private Similarities and Marginals
<|reference_start|>Perturb-and-Project: Differentially Private Similarities and Marginals: 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.<|reference_end|>
@article{cohen-addad2024perturb-and-project:,
    title={Perturb-and-Project: Differentially Private Similarities and Marginals},
    author={Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Vahab
  Mirrokni, Peilin Zhong},
    journal={arXiv preprint arXiv:2406.04868},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.04868},
    primaryClass={cs.LG cs.CR cs.DS}
}