Abstract:
We revisit the objective perturbations framework for differential privacy where noise is added to the input and the result is then projected back to the space of admissible datasets . Through this framework, we first design novel efficient algorithms to privately release pair-wise cosine similarities. Second, we derive a novel algorithm to compute -way marginal queries over features. Prior work could achieve comparable guarantees only for even. Furthermore, we extend our results to -sparse datasets, where our efficient algorithms yields novel, stronger guarantees whenever 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.