Research map / Federated learning and privacy / Differential privacy
Efficiently Computing Similarities to Private Datasets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives DP data structures for releasing sums of similarity functions (kernel KDE and distance queries) over a private dataset, with improved privacy-utility and query-time trade-offs via low-dimensional structure, and applies them to DP classification on CIFAR-10.
Problem
Computing similarities (kernel sums or distance sums) between a query point and a large private dataset in a differentially private way, releasing a data structure that can answer arbitrarily many queries without extra privacy loss.
Approach
Exploit low-dimensional structure of the similarity function: decompose l1 distance sums into d one-dimensional sums answered by noisy binary trees; use oblivious JL-style dimensionality reduction with additive error for Gaussian/exponential kernels; approximate smooth kernels like 1/(1+h) by sums of exponentials to reuse existing KDE structures.
Key results
- Theoretical l1 distance query error (1+alpha, d^1.5/(eps sqrt(alpha))) versus prior (1, (n d^7/eps^2)^{1/3}), with query time d.
- For Gaussian, exponential, and Cauchy kernels, KDE query time improves to d + 1/alpha^4 from d/alpha^2 in prior DP-KDE work.
- Average-similarity DP classification on CIFAR-10 is over 3 orders of magnitude faster than DP-SGD baselines for comparable accuracy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed ℓ1 distance-query data structure instead of the prior algorithm | Private ℓ1 distance queries · ℓ1 distance queries | additive error dependence: \left(1, \left( \frac{nd^{7}}{{\epsilon}^2} \right)^{1/3}\right) -> \left(1+\alpha, \frac{d^{1.5}}{{\epsilon}\sqrt{\alph | Helped |
| Use the proposed ℓ2 distance-query data structure instead of the prior algorithm | Private ℓ2 distance queries · ℓ2 distance queries | additive error dependence: \left(1, \left(\frac{n^{15}d^{7}}{{\epsilon}^2}\right)^{1/17}\right) -> \left(1+\alpha, \frac{1}{{\epsilon}\alpha^{1.5}} | Helped |
| Apply the proposed dimensionality-reduction-based KDE algorithm instead of the prior KDE algorithm | Private exponential KDE · Exponential KDE | query time: \frac{d}{\alpha^2} -> d + \frac{1}{\alpha^4} | Helped |
| Apply the proposed dimensionality-reduction-based KDE algorithm instead of the prior KDE algorithm | Private Gaussian KDE · Gaussian KDE | query time: \frac{d}{\alpha^2} -> d + \frac{1}{\alpha^4} | Helped |
| Apply the proposed dimensionality-reduction-based KDE algorithm instead of the prior KDE algorithm | Private Cauchy KDE · Cauchy KDE | query time: \frac{d}{\alpha^2} -> d + \frac{1}{\alpha^4} | Helped |
| Use the proposed similarity-based classification instead of DP-SGD baselines | CIFAR-10 classification · CIFAR-10 | runtime: > 3 orders of magnitude | Helped |
| Use the proposed ℓ1 query algorithm instead of the prior state-of-the-art algorithm | Private distance-query experiments · ℓ1 distance queries | accuracy | Helped |
| Apply oblivious dimensionality reduction before a prior DP-KDE algorithm | Private KDE · KDE queries | construction time and query time | Helped |
Surprising findings
- Prior l1 distance-query method always returns the trivial estimate 0 in experiments due to large constants in its theorem.
Limitations
- Lower bound only covers additive error for pure DP; gap between d^1.5 upper bound and d lower bound for l1.
- KDE results assume n is at least roughly 1/(alpha eps^2).
- Multiplicative error for l1 distance queries; lower bound does not address multiplicative error.
Experimental setup
Datasets: CIFAR-10
Benchmarks: CIFAR-10
Metrics: additive error query time classification accuracy runtime
Baselines: Cai et al. (2021) l1/l2 distance structures Backurs et al. (2021) DP-KDE DP-SGD classifiers
Builds on: Laplace mechanism advanced composition Johnson-Lindenstrauss transform DP-KDE data structure of Backurs et al. (2021)
Closest papers by meaning
- Learning from End User Data with Shuffled Differential Privacy over Kernel Densities (ICLR 2025 · similarity 0.88)
- Instance-Specific Asymmetric Sensitivity in Differential Privacy (NeurIPS 2024 · similarity 0.88)
- Optimal Differentially Private Model Training with Public Data (ICML 2024 · similarity 0.87)
- Privacy Profiles for Private Selection (ICML 2024 · similarity 0.87)
- Differential Privacy in Scalable General Kernel Learning via $K$-means Nystr{\"o}m Random Features (NeurIPS 2024 · similarity 0.87)
- Oracle-Efficient Differentially Private Learning with Public Data (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.