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 ∈ S 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 t 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. Another widely-used approach to ERM problems is objective perturbation (Chaudhuri & Monteleoni, 2008; Chaudhuri et al., 2011; Iyengar et al., 2019; Kifer et al., 2012) , which involves perturbing the objective function so that optimizing the perturbed objective ensures that the output is private. One very generic way of achieving objective perturbation is through input perturbation which consists in adding noise to the input dataset to obtain a private perturbed input. This permits the use of any non-DP algorithms on the perturbed input and hence simplifies practical implementation. One benefit over perturbing the objective is that the properties (e.g., convexity) of the objective are unchanged and so the stateof-the-art non-DP optimizers can be used. Experimentation with various non-DP algorithms becomes possible, and privacy guarantees are immediate. A crucial research direction is thus to investigate input perturbation methods that preserve the intrinsic properties of the data that are beneficial for the downstream task. * Equal contribution 1 Google Research 2 BIDSA, Bocconi. Correspondence to: Tommaso d'Orsi