Research map / Federated learning and privacy / Differential privacy
Learning from End User Data with Shuffled Differential Privacy over Kernel Densities
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.
Proposes a shuffled-DP protocol for privately estimating kernel density functions from distributed end-user data (via a reduction to bitsum protocols), and uses it to build a privately learned density-based classifier and class-decoding method.
Problem
Private data collection and learning from a one-shot pool of uncommitted end users under shuffled differential privacy, where prior shuffled-DP ML work focused on iterative distributed training with known parties.
Approach
Reduce shuffled-DP kernel density estimation to multiple bitsum protocols using locality-sensitive quantization (random Fourier features for Gaussian kernel, sign-based projection for inner product); classify by highest private class density (generalizing kNN/nearest class center) and decode class semantics from the learned density function.
Key results
- Under shuffled DP with 3NB bitsum, the HDC classifier's private KDE error decays nearly as fast as central DP's Gaussian mechanism.
- The Gaussian kernel is more resilient to privacy noise than the inner product kernel under shuffled DP, often giving better accuracy despite lower non-private accuracy.
- With RR each user sends exactly d one-bit messages; 3NB's expected message count is about (1+o(1))d, though in practice a few times larger.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the IP kernel instead of the Gaussian kernel without privacy | HDC classifier · All four datasets | classification accuracy | Helped |
| Use central DP instead of no privacy | HDC classifier · All four datasets | classification accuracy | No clear effect |
| Use the Gaussian kernel instead of the IP kernel under shuffled DP | HDC classifier · All four datasets; advantage is more pronounced at lower ε and with RR or Pure | classification accuracy | Mixed |
| Use 3NB instead of RR or Pure as the bitsum protocol | Shuffled DP Gaussian KDE · 1K random queries from each dataset's query set | KDE error | Helped |
| Use the Gaussian kernel instead of IP under shuffled DP | HDC classifier · Lower privacy budgets and bitsum protocols less optimized for accuracy (RR and Pure) | classification accuracy | Helped |
| Use 3NB instead of RR for communication | Shuffled DP learning protocol · Both Gaussian and IP kernels | messages per user: exactly d messages; (1+o(1))d | Hurt |
| Use Pure instead of RR or 3NB for communication | Shuffled DP learning protocol · Both Gaussian and IP kernels | messages per user: O(d^2\log(n)/\varepsilon_0) | Hurt |
| Learn shuffled DP KDE class representations without unprotected training examples | Shuffled DP class decoding · DBPedia-14, AG news, SST2 | semantic alignment of decoded terms | Helped |
Surprising findings
- Gaussian kernel often beats the inner product kernel under shuffled DP even though the inner product kernel is more accurate without privacy.
- Pure-DP bitsum protocol needs orders of magnitude more messages per user (O(d^2 log n / eps)) than RR or 3NB.
Limitations
- Protocols require knowing the number of participating users n in advance, which conflicts with open data collection.
- Class decoding is qualitative only; no quantitative measure of decoding quality.
- Shuffled DP accuracy under tight privacy/communication budgets is less robust for the inner product kernel.
Experimental setup
Datasets: DBPedia-14 AG news SST2 CIFAR-10 GloVe 6B
Benchmarks: DBPedia-14 AG news SST2 CIFAR-10
Metrics: classification accuracy KDE RMSE (supRMSE estimate error) communication cost (messages per user) qualitative class decoding
Baselines: central DP Gaussian mechanism HDC non-private HDC local DP randomized response nearest class center classifier
Builds on: locality-sensitive quantization random Fourier features 3NB shuffled bitsum protocol randomized response advanced composition
Closest papers by meaning
- A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility (AAAI 2024 · similarity 0.88)
- Oracle-Efficient Differentially Private Learning with Public Data (NeurIPS 2024 · similarity 0.88)
- Efficiently Computing Similarities to Private Datasets (ICLR 2024 · similarity 0.88)
- Certification for Differentially Private Prediction in Gradient-Based Training (ICML 2025 · similarity 0.87)
- Differential Privacy in Scalable General Kernel Learning via $K$-means Nystr{\"o}m Random Features (NeurIPS 2024 · similarity 0.87)
- Differentially Private Prototypes for Imbalanced Transfer Learning (AAAI 2025 · 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.