Nearly-Optimal Private Selection via Gaussian Mechanism
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909895771553792 |
|---|---|
| author | Leeman, Ethan Manurangsi, Pasin |
| author_facet | Leeman, Ethan Manurangsi, Pasin |
| contents | Steinke (2025) recently asked the following intriguing open question: Can we solve the differentially private selection problem with nearly-optimal error by only (adaptively) invoking Gaussian mechanism on low-sensitivity queries? We resolve this question positively. In particular, for a candidate set $\mathcal{Y}$, we achieve error guarantee of $\tilde{O}(\log |\mathcal{Y}|)$, which is within a factor of $(\log \log |\mathcal{Y}|)^{O(1)}$ of the exponential mechanism (McSherry and Talwar, 2007). This improves on Steinke's mechanism which achieves an error of $O(\log^{3/2} |\mathcal{Y}|)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_06871 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Nearly-Optimal Private Selection via Gaussian Mechanism Leeman, Ethan Manurangsi, Pasin Cryptography and Security Data Structures and Algorithms Steinke (2025) recently asked the following intriguing open question: Can we solve the differentially private selection problem with nearly-optimal error by only (adaptively) invoking Gaussian mechanism on low-sensitivity queries? We resolve this question positively. In particular, for a candidate set $\mathcal{Y}$, we achieve error guarantee of $\tilde{O}(\log |\mathcal{Y}|)$, which is within a factor of $(\log \log |\mathcal{Y}|)^{O(1)}$ of the exponential mechanism (McSherry and Talwar, 2007). This improves on Steinke's mechanism which achieves an error of $O(\log^{3/2} |\mathcal{Y}|)$. |
| title | Nearly-Optimal Private Selection via Gaussian Mechanism |
| topic | Cryptography and Security Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.06871 |