Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning
Abstract
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. (2022) employs a direct sampling approach from the vast collection of $O(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 that achieves time and space complexity of $\tilde{O}(d + k^2)$.Experimental results show that our algorithm runs orders of magnitude faster than their approach, while achieving similar empirical accuracy.
Cite
Text
Wu and Zhang. "Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning." Neural Information Processing Systems, 2024. doi:10.52202/079017-2266Markdown
[Wu and Zhang. "Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning." Neural Information Processing Systems, 2024.](https://mlanthology.org/neurips/2024/wu2024neurips-faster/) doi:10.52202/079017-2266BibTeX
@inproceedings{wu2024neurips-faster,
title = {{Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning}},
author = {Wu, Hao and Zhang, Hanwen},
booktitle = {Neural Information Processing Systems},
year = {2024},
doi = {10.52202/079017-2266},
url = {https://mlanthology.org/neurips/2024/wu2024neurips-faster/}
}