Timezone: »

 
Poster
Oneshot Differentially Private Top-k Selection
Gang Qiao · Weijie Su · Li Zhang

Thu Jul 22 09:00 PM -- 11:00 PM (PDT) @
in Poster Session 6 »
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~\cite{dwork2014algorithmic} 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 composition theorems so without the linear dependence on $k$ which is inherent to various composition theorems. Finally, we present a novel application of efficient top-$k$ selection in the classical problem of ranking from pairwise comparisons.
Keywords: Privacy, Anonymity, and Security · Social Aspects of Machine Learning

Author Information

Gang Qiao (University of Michigan, Ann Arbor)
Weijie Su (University of Pennsylvania)
Li Zhang (Google)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors