Differentially Private Top-k Selection via Stability on Unknown Domain

Ricardo Silva Carvalho, Ke Wang, Lovedeep Gondara, Chunyan Miao
Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), PMLR 124:1109-1118, 2020.

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.

Cite this Paper

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.} }
Endnote
%0 Conference Paper %T Differentially Private Top-k Selection via Stability on Unknown Domain %A Ricardo Silva Carvalho %A Ke Wang %A Lovedeep Gondara %A Chunyan Miao %B Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI) %C Proceedings of Machine Learning Research %D 2020 %E Jonas Peters %E David Sontag %F pmlr-v124-silva-carvalho20a %I PMLR %P 1109--1118 %U https://proceedings.mlr.press/v124/silva-carvalho20a.html %V 124 %X 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.
APA
Silva Carvalho, R., Wang, K., Gondara, L. & Miao, C.. (2020). Differentially Private Top-k Selection via Stability on Unknown Domain. Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), in Proceedings of Machine Learning Research 124:1109-1118 Available from https://proceedings.mlr.press/v124/silva-carvalho20a.html.

Related Material