mlsanityData to 7 Oct 2026

Perturb-and-Project: Differentially Private Similarities and Marginals

arXiv 2406.04868 ↗First posted 7 Jun 2024cs.LG cs.CR cs.DScited by 1

Not on the map. Why?

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.

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

Builds on

31 of 83 references.

References · 31

  1. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  2. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  3. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  4. 2021Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descentcited by 71
  5. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  6. 2020Reducibility and Statistical-Computational Gaps from Secret Leakagecited by 50
  7. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  8. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  9. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  10. 2015Tensor principal component analysis via sum-of-squares proofscited by 35
  11. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  12. 2014Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometrycited by 24
19 more
  1. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  2. 2020Sparse PCA: Algorithms, Adversarial Perturbations and Certificatescited by 18
  3. 2021Robust recovery for stochastic block modelscited by 18
  4. 2013Efficient Algorithms for Privately Releasing Marginals via Convex Relaxationscited by 17
  5. 2014Private Multiplicative Weights Beyond Linear Queriescited by 17
  6. 2022Differentially Private Covariance Revisitedcited by 15
  7. 2020Consistent regression when oblivious outliers overwhelmcited by 12
  8. 2022Minimax Rates for Robust Community Detectioncited by 12
  9. 2017Marginal Release Under Local Differential Privacycited by 9
  10. 2021Consistent Estimation for PCA and Sparse Regression with Oblivious Outlierscited by 9
  11. 2022Private Query Release via the Johnson-Lindenstrauss Transformcited by 8
  12. 2021The Complexity of Sparse Tensor PCAcited by 7
  13. 2022Higher degree sum-of-squares relaxations robust against oblivious outlierscited by 6
  14. 2020Locality Sensitive Hashing with Extended Differential Privacycited by 5
  15. 2022Improved Differentially Private Euclidean Distance Approximationcited by 5
  16. 2023Differentially-Private Hierarchical Clustering with Provable Approximation Guaranteescited by 5
  17. 2013Faster Private Release of Marginals on Small Databasescited by 4
  18. 2020Differentially Private Sketches for Jaccard Similarity Estimationcited by 3
  19. 2023Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex Gaussian Perturbationscited by 3

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025On Purely Private Covariance Estimationcited by 1