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