Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914815420661760 |
|---|---|
| author | Ghazi, Badih Kamath, Pritish Kumar, Ravi Manurangsi, Pasin Sealfon, Adam |
| author_facet | Ghazi, Badih Kamath, Pritish Kumar, Ravi Manurangsi, Pasin Sealfon, Adam |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18534 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization Ghazi, Badih Kamath, Pritish Kumar, Ravi Manurangsi, Pasin Sealfon, Adam Data Structures and Algorithms Cryptography and Security 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). |
| title | Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization |
| topic | Data Structures and Algorithms Cryptography and Security |
| url | https://arxiv.org/abs/2405.18534 |