2024/05/28 by Badih Ghazi, Ghazi, Badih, Pritish Kamath +7 · 1 citation
Computer Science · Decision Sciences · #Auction Theory and Applications #Cryptography and Data Security #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2405.18534
openalex publication_date 2024/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work, we give a new technique for analyzing individualized privacy accounting via the following simple observation: if an algorithm is one-sided add-DP, then its subsampled variant satisfies two-sided DP. From this, we obtain several improved algorithms for private combinatorial optimization problems, including decomposable submodular maximization and set cover. Our error guarantees are asymptotically tight and our algorithm satisfies pure-DP while previously known algorithms (Gupta et al., 2010; Chaturvedi et al., 2021) are approximate-DP. We also show an application of our technique beyond combinatorial optimization by giving a pure-DP algorithm for the shifting heavy hitter problem in a stream; previously, only an approximateDP algorithm was known (Kaplan et al., 2021; Cohen & Lyu, 2023).