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-ˉk elements for any given ˉk≥k, thus, enforcing the principle of minimal privilege. Unlike previous methods, our privacy parameter ε 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