Being able to efficiently and accurately select the top-k elements without privacy leakage is an integral component of various  data analysis tasks and has gained significant attention . In this paper, we introduce theoneshot mechanism , a fast, low-distortion, and differentially private primitive for the top-k problem. Compared with existing approaches in the literature, our algorithm adds Laplace noise to the counts and releases the top-k noisy counts and their estimates in a oneshot fashion, thereby substantially reducing the computational cost while maintaining satisfying utility. Our /}\eps proof of privacy for this mechanism relies on a novel coupling technique that is of independent theoretical interest . Finally, we apply the oneshot mechanism to multiple hypothesis testing and ranking from pairwise comparisons and thus obtain their differentially private counterparts .
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 (\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 .
R
without privacy leakage
with differential privacy
A
private
D
and has gained significant attention
D
introduce the
D
oneshot mechanism
R
, a fast, low-distortion, and differentially private primitive for the
present the oneshot Laplace mechanism, which generalizes the well-known Report Noisy Max mechanism to reporting noisy
R
problem. Compared with existing approaches in the literature, our algorithm adds Laplace noise to the counts and releases the top-k noisy counts and their estimates in a oneshot fashion, thereby substantially reducing the computational cost while maintaining satisfying utility. Our
elements. We show that the oneshot Laplace mechanism with a noise level of
A
(\sqrt{k
A
) 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
D
for this mechanism
R
is of independent theoretical interest
bypasses the use of composition theorems
R
apply the oneshot mechanism to multiple hypothesis testing and
present a novel application of efficient top-k selection in the classical problem of
D
and thus obtain their differentially private counterparts