Oneshot Differentially Private Top-k Selection
This work addresses a key component in private data analysis, offering a more efficient solution for tasks like ranking from pairwise comparisons, though it is incremental in improving upon existing mechanisms.
The paper tackles the problem of efficiently and accurately selecting the top-k elements with differential privacy, introducing the oneshot Laplace mechanism that achieves approximate differential privacy with a noise level of O~(√k/ε) and is more efficient than prior methods for large k.
Being able to efficiently and accurately select the top-$k$ elements with differential privacy is an integral component of various private data analysis tasks. In this paper, we present the oneshot Laplace mechanism, which generalizes the well-known Report Noisy Max mechanism to reporting noisy top-$k$ elements. We show that the oneshot Laplace mechanism with a noise level of $\widetilde{O}(\sqrt{k}/\eps)$ is approximately differentially private. Compared to the previous peeling approach of running Report Noisy Max $k$ times, the oneshot Laplace mechanism only adds noises and computes the top $k$ elements once, hence much more efficient for large $k$. In addition, our proof of privacy relies on a novel coupling technique that bypasses the use of composition theorems. Finally, we present a novel application of efficient top-$k$ selection in the classical problem of ranking from pairwise comparisons.