Skip to yearly menu bar Skip to main content


Spotlight 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 #2301

Abstract: We revisit the objective perturbations framework for differential privacy where noise is added to the input AS and the result is then projected back to the space of admissible datasets 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 tn5/6/logn. 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.

Chat is not available.