# Fast Private Kernel Density Estimation via Locality Sensitive Quantization

arXiv: https://arxiv.org/abs/2307.01877 · HTML: https://mlsanity.com/paper/2307.01877/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 51 references that are in the map.
- First posted on arXiv 4 Jul 2023.

## Builds on (most cited first, 14 of 14)

- [Hashing-Based-Estimators for Kernel Density in High Dimensions](https://mlsanity.com/paper/1808.10530/) (2018)
- [Near-Optimal Coresets of Kernel Density Estimates](https://mlsanity.com/paper/1802.01751/) (2018)
- [Discrepancy, Coresets, and Sketches in Machine Learning](https://mlsanity.com/paper/1906.04845/) (2019)
- [Lossless Compression of Efficient Private Local Randomizers](https://mlsanity.com/paper/2102.12099/) (2021)
- [Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering](https://mlsanity.com/paper/1501.02056/) (2015)
- [Algorithms and Hardness for Linear Algebra on Geometric Graphs](https://mlsanity.com/paper/2011.02466/) (2020)
- [Sub-linear RACE Sketches for Approximate Kernel Density Estimation on Streaming Data](https://mlsanity.com/paper/1912.02283/) (2019)
- [The Bernstein Mechanism: Function Release under Differential Privacy](https://mlsanity.com/paper/1507.04499/) (2015)
- [On Adaptive Distance Estimation](https://mlsanity.com/paper/2010.11252/) (2020)
- [Faster Kernel Matrix Algebra via Density Estimation](https://mlsanity.com/paper/2102.08341/) (2021)
- [Privacy-Preserving Synthetic Location Data in the Real World](https://mlsanity.com/paper/2108.02089/) (2021)
- [Private Query Release via the Johnson-Lindenstrauss Transform](https://mlsanity.com/paper/2208.07410/) (2022)
- [Improved Utility Analysis of Private CountSketch](https://mlsanity.com/paper/2205.08397/) (2022)
- [Differentially Private Sparse Vectors with Low Error, Optimal Space, and Fast Access](https://mlsanity.com/paper/2106.10068/) (2021)

## Built on by (most cited first, 9 of 9)

- [Efficiently Computing Similarities to Private Datasets](https://mlsanity.com/paper/2403.08917/) (2024)
- [Differentially Private Kernel Density Estimation](https://mlsanity.com/paper/2409.01688/) (2024)
- [Learning from End User Data with Shuffled Differential Privacy over Kernel Densities](https://mlsanity.com/paper/2502.14087/) (2025)
- [Private Text Generation by Seeding Large Language Model Prompts](https://mlsanity.com/paper/2502.13193/) (2025)
- [New Bounds for Kernel Sums via Fast Spherical Embeddings](https://mlsanity.com/paper/2605.01263/) (2026)
- [Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation](https://mlsanity.com/paper/2610.05174/) (2026)
- [Compactly supported radial basis functions as probability density functions](https://mlsanity.com/paper/2607.26759/) (2026)
- [GLASS: Graph-Language Alignment with Spherical Scoring for Transferable Graph-Level Anomaly Detection](https://mlsanity.com/paper/2609.05253/) (2026)
- [Random Fourier Features in Near-Linear Time](https://mlsanity.com/paper/2610.14751/) (2026)

## Abstract (arXiv)

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.