# Perturb-and-Project: Differentially Private Similarities and Marginals

arXiv: https://arxiv.org/abs/2406.04868 · HTML: https://mlsanity.com/paper/2406.04868/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 83 references that are in the map.
- First posted on arXiv 7 Jun 2024.

## Builds on (most cited first, 30 of 31)

- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent](https://mlsanity.com/paper/2102.05855/) (2021)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [Tensor principal component analysis via sum-of-squares proofs](https://mlsanity.com/paper/1507.03269/) (2015)
- [Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation](https://mlsanity.com/paper/2211.00724/) (2022)
- [Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry](https://mlsanity.com/paper/1411.5417/) (2014)
- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Sparse PCA: Algorithms, Adversarial Perturbations and Certificates](https://mlsanity.com/paper/2011.06585/) (2020)
- [Robust recovery for stochastic block models](https://mlsanity.com/paper/2111.08568/) (2021)
- [Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations](https://mlsanity.com/paper/1308.1385/) (2013)
- [Private Multiplicative Weights Beyond Linear Queries](https://mlsanity.com/paper/1407.1571/) (2014)
- [Differentially Private Covariance Revisited](https://mlsanity.com/paper/2205.14324/) (2022)
- [Consistent regression when oblivious outliers overwhelm](https://mlsanity.com/paper/2009.14774/) (2020)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [Marginal Release Under Local Differential Privacy](https://mlsanity.com/paper/1711.02952/) (2017)
- [Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers](https://mlsanity.com/paper/2111.02966/) (2021)
- [Private Query Release via the Johnson-Lindenstrauss Transform](https://mlsanity.com/paper/2208.07410/) (2022)
- [The Complexity of Sparse Tensor PCA](https://mlsanity.com/paper/2106.06308/) (2021)
- [Higher degree sum-of-squares relaxations robust against oblivious outliers](https://mlsanity.com/paper/2211.07327/) (2022)
- [Locality Sensitive Hashing with Extended Differential Privacy](https://mlsanity.com/paper/2010.09393/) (2020)
- [Improved Differentially Private Euclidean Distance Approximation](https://mlsanity.com/paper/2203.11561/) (2022)
- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [Faster Private Release of Marginals on Small Databases](https://mlsanity.com/paper/1304.3754/) (2013)
- [Differentially Private Sketches for Jaccard Similarity Estimation](https://mlsanity.com/paper/2008.08134/) (2020)

## Built on by (most cited first, 1 of 1)

- [On Purely Private Covariance Estimation](https://mlsanity.com/paper/2510.26717/) (2025)

## Abstract (arXiv)

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≤ n5/6/log n,. Finally, we provide a theoretical perspective on why textitfast 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.