Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915716183097344 |
|---|---|
| author | WU, Hao Zhang, Hanwen |
| author_facet | WU, Hao Zhang, Hanwen |
| contents | We study the differentially private top-$k$ selection problem, aiming to identify a sequence of $k$ items with approximately the highest scores from $d$ items. Recent work by Gillenwater et al. (ICML '22) employs a direct sampling approach from the vast collection of $d^{\,Θ(k)}$ possible length-$k$ sequences, showing superior empirical accuracy compared to previous pure or approximate differentially private methods. Their algorithm has a time and space complexity of $\tilde{O}(dk)$.
In this paper, we present an improved algorithm with time and space complexity $O(d + k^2 / ε\cdot \ln d)$, where $ε$ denotes the privacy parameter. Experimental results show that our algorithm runs orders of magnitude faster than their approach, while achieving similar empirical accuracy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_09552 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning WU, Hao Zhang, Hanwen Cryptography and Security We study the differentially private top-$k$ selection problem, aiming to identify a sequence of $k$ items with approximately the highest scores from $d$ items. Recent work by Gillenwater et al. (ICML '22) employs a direct sampling approach from the vast collection of $d^{\,Θ(k)}$ possible length-$k$ sequences, showing superior empirical accuracy compared to previous pure or approximate differentially private methods. Their algorithm has a time and space complexity of $\tilde{O}(dk)$. In this paper, we present an improved algorithm with time and space complexity $O(d + k^2 / ε\cdot \ln d)$, where $ε$ denotes the privacy parameter. Experimental results show that our algorithm runs orders of magnitude faster than their approach, while achieving similar empirical accuracy. |
| title | Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2411.09552 |