Fast Private Kernel Density Estimation via Locality Sensitive Quantization

Tal Wagner, Yonatan Naamad, Nina Mishra
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:35339-35367, 2023.

Abstract

We study efficient mechanisms for differentially private kernel density estimation (DP-KDE). Prior work for the Gaussian kernel described algorithms that run in time exponential in the number of dimensions d. This paper breaks the exponential barrier, and shows how the KDE can privately be approximated in time linear in d, making it feasible for high-dimensional data. We also present improved bounds for low-dimensional data. Our results are obtained through a general framework, which we term Locality Sensitive Quantization (LSQ), for constructing private KDE mechanisms where existing KDE approximation techniques can be applied. It lets us leverage several efficient non-private KDE methods—like Random Fourier Features, the Fast Gauss Transform, and Locality Sensitive Hashing—and “privatize” them in a black-box manner. Our experiments demonstrate that our resulting DP-KDE mechanisms are fast and accurate on large datasets in both high and low dimensions.

Cite this Paper


BibTeX
@InProceedings{pmlr-v202-wagner23a, title = {Fast Private Kernel Density Estimation via Locality Sensitive Quantization}, author = {Wagner, Tal and Naamad, Yonatan and Mishra, Nina}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {35339--35367}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/wagner23a/wagner23a.pdf}, url = {https://proceedings.mlr.press/v202/wagner23a.html}, abstract = {We study efficient mechanisms for differentially private kernel density estimation (DP-KDE). Prior work for the Gaussian kernel described algorithms that run in time exponential in the number of dimensions $d$. This paper breaks the exponential barrier, and shows how the KDE can privately be approximated in time linear in $d$, making it feasible for high-dimensional data. We also present improved bounds for low-dimensional data. Our results are obtained through a general framework, which we term Locality Sensitive Quantization (LSQ), for constructing private KDE mechanisms where existing KDE approximation techniques can be applied. It lets us leverage several efficient non-private KDE methods—like Random Fourier Features, the Fast Gauss Transform, and Locality Sensitive Hashing—and “privatize” them in a black-box manner. Our experiments demonstrate that our resulting DP-KDE mechanisms are fast and accurate on large datasets in both high and low dimensions.} }
Endnote
%0 Conference Paper %T Fast Private Kernel Density Estimation via Locality Sensitive Quantization %A Tal Wagner %A Yonatan Naamad %A Nina Mishra %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-wagner23a %I PMLR %P 35339--35367 %U https://proceedings.mlr.press/v202/wagner23a.html %V 202 %X We study efficient mechanisms for differentially private kernel density estimation (DP-KDE). Prior work for the Gaussian kernel described algorithms that run in time exponential in the number of dimensions $d$. This paper breaks the exponential barrier, and shows how the KDE can privately be approximated in time linear in $d$, making it feasible for high-dimensional data. We also present improved bounds for low-dimensional data. Our results are obtained through a general framework, which we term Locality Sensitive Quantization (LSQ), for constructing private KDE mechanisms where existing KDE approximation techniques can be applied. It lets us leverage several efficient non-private KDE methods—like Random Fourier Features, the Fast Gauss Transform, and Locality Sensitive Hashing—and “privatize” them in a black-box manner. Our experiments demonstrate that our resulting DP-KDE mechanisms are fast and accurate on large datasets in both high and low dimensions.
APA
Wagner, T., Naamad, Y. & Mishra, N.. (2023). Fast Private Kernel Density Estimation via Locality Sensitive Quantization. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:35339-35367 Available from https://proceedings.mlr.press/v202/wagner23a.html.

Related Material