2024/06/07 by Vincent Cohen-Addad, Tommaso d'Orsi, Cohen-Addad, Vincent +7 · 1 citation
Decision Sciences · Engineering · #Advanced Research in Systems and Signal Processing #Construction Project Management and Performance #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #G.3 #Machine Learning (cs.LG) #Manufacturing Process and Optimization
paper · pdf · doi:10.48550/arxiv.2406.04868
openalex publication_date 2024/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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.