Poster
Oneshot Differentially Private Top-k Selection
Gang Qiao · Weijie Su · Li Zhang
Keywords: [ Privacy, Anonymity, and Security ] [ Social Aspects of Machine Learning ]
Abstract:
Being able to efficiently and accurately select the top- 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- elements. We show that the oneshot Laplace mechanism with a noise level of is approximately differentially private. Compared to the previous peeling approach of running Report Noisy Max times, the oneshot Laplace mechanism only adds noises and computes the top elements once, hence much more efficient for large . In addition, our proof of privacy relies on a novel coupling technique that bypasses the composition theorems so without the linear dependence on which is inherent to various composition theorems. Finally, we present a novel application of efficient top- selection in the classical problem of ranking from pairwise comparisons.
Chat is not available.