# Differentially Private Kernel Density Estimation

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 110 of its 149 references that are in the map.
- First posted on arXiv 3 Sep 2024.

## Builds on (most cited first, 30 of 110)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Hierarchical Text-Conditional Image Generation with CLIP Latents](https://mlsanity.com/paper/2204.06125/) (2022)
- [Scalable Diffusion Models with Transformers](https://mlsanity.com/paper/2212.09748/) (2022)
- [Scaling Rectified Flow Transformers for High-Resolution Image Synthesis](https://mlsanity.com/paper/2403.03206/) (2024)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [On the Opportunities and Risks of Foundation Models](https://mlsanity.com/paper/2108.07258/) (2021)
- [The Power of Scale for Parameter-Efficient Prompt Tuning](https://mlsanity.com/paper/2104.08691/) (2021)
- [GLIDE: Towards Photorealistic Image Generation and Editing with Text-Guided Diffusion Models](https://mlsanity.com/paper/2112.10741/) (2021)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Large Language Models Encode Clinical Knowledge](https://mlsanity.com/paper/2212.13138/) (2022)
- [LlamaFactory: Unified Efficient Fine-Tuning of 100+ Language Models](https://mlsanity.com/paper/2403.13372/) (2024)
- [Ethical and social risks of harm from Language Models](https://mlsanity.com/paper/2112.04359/) (2021)
- [BloombergGPT: A Large Language Model for Finance](https://mlsanity.com/paper/2303.17564/) (2023)
- [Membership Inference Attacks From First Principles](https://mlsanity.com/paper/2112.03570/) (2021)
- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [AutoDAN: Generating Stealthy Jailbreak Prompts on Aligned Large Language Models](https://mlsanity.com/paper/2310.04451/) (2023)
- [Quantifying Memorization Across Neural Language Models](https://mlsanity.com/paper/2202.07646/) (2022)
- [SiT: Exploring Flow and Diffusion-based Generative Models with Scalable Interpolant Transformers](https://mlsanity.com/paper/2401.08740/) (2024)
- [Extracting Training Data from Diffusion Models](https://mlsanity.com/paper/2301.13188/) (2023)
- [P-Tuning v2: Prompt Tuning Can Be Comparable to Fine-tuning Universally Across Scales and Tasks](https://mlsanity.com/paper/2110.07602/) (2021)
- [GPTFUZZER: Red Teaming Large Language Models with Auto-Generated Jailbreak Prompts](https://mlsanity.com/paper/2309.10253/) (2023)
- [Jailbreaking ChatGPT via Prompt Engineering: An Empirical Study](https://mlsanity.com/paper/2305.13860/) (2023)
- ["Do Anything Now": Characterizing and Evaluating In-The-Wild Jailbreak Prompts on Large Language Models](https://mlsanity.com/paper/2308.03825/) (2023)
- [Sora: A Review on Background, Technology, Limitations, and Opportunities of Large Vision Models](https://mlsanity.com/paper/2402.17177/) (2024)

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

- [On Differentially Private String Distances](https://mlsanity.com/paper/2411.05750/) (2024)
- [SLDP: Semi-Local Differential Privacy for Density-Adaptive Analytics](https://mlsanity.com/paper/2602.18910/) (2026)
- [Differentially Private Nonparametric Modal Learning with Applications to Regression and Clustering](https://mlsanity.com/paper/2607.29675/) (2026)

## Abstract (arXiv)

We introduce a refined differentially private (DP) data structure for kernel density estimation (KDE), offering not only improved privacy-utility tradeoff but also better efficiency over prior results. Specifically, we study the mathematical problem: given a similarity function f (or DP KDE) and a private dataset X subset ℝd, our goal is to preprocess X so that for any query y∈ℝd, we approximate sumx ∈ X f(x, y) in a differentially private fashion. The best previous algorithm for f(x,y) =| x - y |1 is the node-contaminated balanced binary tree by [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024]. Their algorithm requires O(nd) space and time for preprocessing with n=|X|. For any query point, the query time is d log n, with an error guarantee of (1+α)-approximation and ε-1 α-0.5 d1.5 R log1.5 n. In this paper, we improve the best previous result [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024] in three aspects: - We reduce query time by a factor of α-1 log n. - We improve the approximation ratio from α to 1. - We reduce the error dependence by a factor of α-0.5. From a technical perspective, our method of constructing the search tree differs from previous work [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024]. In prior work, for each query, the answer is split into α-1 log n numbers, each derived from the summation of log n values in interval tree countings. In contrast, we construct the tree differently, splitting the answer into log n numbers, where each is a smart combination of two distance values, two counting values, and y itself. We believe our tree structure may be of independent interest.