Differential Privacy with Multiple Selections
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909262940209152 |
|---|---|
| author | Goel, Ashish Jiang, Zhihao Korolova, Aleksandra Munagala, Kamesh Sarmasarkar, Sahasrajit |
| author_facet | Goel, Ashish Jiang, Zhihao Korolova, Aleksandra Munagala, Kamesh Sarmasarkar, Sahasrajit |
| contents | We consider the setting where a user with sensitive features wishes to obtain a recommendation from a server in a differentially private fashion. We propose a ``multi-selection'' architecture where the server can send back multiple recommendations and the user chooses one from these that matches best with their private features. When the user feature is one-dimensional -- on an infinite line -- and the accuracy measure is defined w.r.t some increasing function $\mathfrak{h}(.)$ of the distance on the line, we precisely characterize the optimal mechanism that satisfies differential privacy. The specification of the optimal mechanism includes both the distribution of the noise that the user adds to its private value, and the algorithm used by the server to determine the set of results to send back as a response and further show that Laplace is an optimal noise distribution. We further show that this optimal mechanism results in an error that is inversely proportional to the number of results returned when the function $\mathfrak{h}(.)$ is the identity function. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_14641 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Differential Privacy with Multiple Selections Goel, Ashish Jiang, Zhihao Korolova, Aleksandra Munagala, Kamesh Sarmasarkar, Sahasrajit Data Structures and Algorithms Cryptography and Security We consider the setting where a user with sensitive features wishes to obtain a recommendation from a server in a differentially private fashion. We propose a ``multi-selection'' architecture where the server can send back multiple recommendations and the user chooses one from these that matches best with their private features. When the user feature is one-dimensional -- on an infinite line -- and the accuracy measure is defined w.r.t some increasing function $\mathfrak{h}(.)$ of the distance on the line, we precisely characterize the optimal mechanism that satisfies differential privacy. The specification of the optimal mechanism includes both the distribution of the noise that the user adds to its private value, and the algorithm used by the server to determine the set of results to send back as a response and further show that Laplace is an optimal noise distribution. We further show that this optimal mechanism results in an error that is inversely proportional to the number of results returned when the function $\mathfrak{h}(.)$ is the identity function. |
| title | Differential Privacy with Multiple Selections |
| topic | Data Structures and Algorithms Cryptography and Security |
| url | https://arxiv.org/abs/2407.14641 |