Differentially Private Top-k Selection via Stability on Unknown Domain
Ricardo Silva Carvalho, Ke Wang, Lovedeep Gondara, Chunyan Miao
Abstract
We propose a new method that satisfies approximate differential privacy for top-$k$ selection with unordered output in the unknown data domain setting, not relying on the full knowledge of the domain universe. Our algorithm only requires looking at the top-$\bar{k}$ elements for any given $\bar{k} \geq k$, thus, enforcing the principle of minimal privilege. Unlike previous methods, our privacy parameter $\varepsilon$ does not scale with $k$, giving improved applicability for scenarios of very large $k$. Moreover, our novel construction, which combines the sparse vector technique and stability efficiently, can be applied as a general framework to any type of query, thus being of independent interest. We extensively compare our algorithm to previous work of top-$k$ selection on the unknown domain, and show, both analytically and on experiments, settings where we outperform the current state-of-the-art.
BibTeX
@InProceedings{pmlr-v124-silva-carvalho20a,
title = {Differentially Private Top-k Selection via Stability on Unknown Domain},
author = {Silva Carvalho, Ricardo and Wang, Ke and Gondara, Lovedeep and Miao, Chunyan},
booktitle = {Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)},
pages = {1109--1118},
year = {2020},
editor = {Peters, Jonas and Sontag, David},
volume = {124},
series = {Proceedings of Machine Learning Research},
month = {03--06 Aug},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v124/silva-carvalho20a/silva-carvalho20a.pdf},
url = {https://proceedings.mlr.press/v124/silva-carvalho20a.html},
abstract = {We propose a new method that satisfies approximate differential privacy for top-$k$ selection with unordered output in the unknown data domain setting, not relying on the full knowledge of the domain universe. Our algorithm only requires looking at the top-$\bar{k}$ elements for any given $\bar{k} \geq k$, thus, enforcing the principle of minimal privilege. Unlike previous methods, our privacy parameter $\varepsilon$ does not scale with $k$, giving improved applicability for scenarios of very large $k$. Moreover, our novel construction, which combines the sparse vector technique and stability efficiently, can be applied as a general framework to any type of query, thus being of independent interest. We extensively compare our algorithm to previous work of top-$k$ selection on the unknown domain, and show, both analytically and on experiments, settings where we outperform the current state-of-the-art.}
}