# Efficiently Computing Similarities to Private Datasets

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 63 references that are in the map.
- First posted on arXiv 13 Mar 2024.

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

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [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)
- [Quantifying Memorization Across Neural Language Models](https://mlsanity.com/paper/2202.07646/) (2022)
- [Extracting Training Data from Diffusion Models](https://mlsanity.com/paper/2301.13188/) (2023)
- [Large Language Models Can Be Strong Differentially Private Learners](https://mlsanity.com/paper/2110.05679/) (2021)
- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Reconstructing Training Data from Trained Neural Networks](https://mlsanity.com/paper/2206.07758/) (2022)
- [Synthetic Text Generation with Differential Privacy: A Simple and Practical Recipe](https://mlsanity.com/paper/2210.14348/) (2022)
- [Truth Serum: Poisoning Machine Learning Models to Reveal Their Secrets](https://mlsanity.com/paper/2204.00032/) (2022)
- [Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning](https://mlsanity.com/paper/2102.12677/) (2021)
- [Differentially Private Synthetic Data via Foundation Model APIs 1: Images](https://mlsanity.com/paper/2305.15560/) (2023)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Near-Optimal Coresets of Kernel Density Estimates](https://mlsanity.com/paper/1802.01751/) (2018)
- [Kernel Density Estimation through Density Constrained Near Neighbor Search](https://mlsanity.com/paper/2011.06997/) (2020)
- [Selective Pre-training for Private Fine-tuning](https://mlsanity.com/paper/2305.13865/) (2023)
- [Privately Learning Subspaces](https://mlsanity.com/paper/2106.00001/) (2021)
- [The Bernstein Mechanism: Function Release under Differential Privacy](https://mlsanity.com/paper/1507.04499/) (2015)
- [Dimensionality Reduction for Wasserstein Barycenter](https://mlsanity.com/paper/2110.08991/) (2021)
- [Privately Customizing Prefinetuning to Better Match User Data in Federated Learning](https://mlsanity.com/paper/2302.09042/) (2023)
- [Fast Private Kernel Density Estimation via Locality Sensitive Quantization](https://mlsanity.com/paper/2307.01877/) (2023)
- [Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering](https://mlsanity.com/paper/2107.01804/) (2021)
- [The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction](https://mlsanity.com/paper/2205.00371/) (2022)

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

- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [Provable Differentially Private Computation of the Cross-Attention Mechanism](https://mlsanity.com/paper/2407.14717/) (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)
- [Even Faster Kernel Matrix Linear Algebra via Density Estimation](https://mlsanity.com/paper/2510.02540/) (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)
- [Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures](https://mlsanity.com/paper/2506.00165/) (2025)
- [Random Fourier Features in Near-Linear Time](https://mlsanity.com/paper/2610.14751/) (2026)

## Abstract (arXiv)

Many methods in differentially private model training rely on computing the similarity between a query point (such as public or synthetic data) and private data. We abstract out this common subroutine and study the following fundamental algorithmic problem: Given a similarity function f and a large high-dimensional private dataset X subset ℝd, output a differentially private (DP) data structure which approximates sumx ∈ X f(x,y) for any query y. We consider the cases where f is a kernel function, such as f(x,y) = e-|x-y|22/σ2 (also known as DP kernel density estimation), or a distance function such as f(x,y) = |x-y|2, among others. Our theoretical results improve upon prior work and give better privacy-utility trade-offs as well as faster query times for a wide range of kernels and distance functions. The unifying approach behind our results is leveraging `low-dimensional structures' present in the specific functions f that we study, using tools such as provable dimensionality reduction, approximation theory, and one-dimensional decomposition of the functions. Our algorithms empirically exhibit improved query times and accuracy over prior state of the art. We also present an application to DP classification. Our experiments demonstrate that the simple methodology of classifying based on average similarity is orders of magnitude faster than prior DP-SGD based approaches for comparable accuracy.