Learning from End User Data with Shuffled Differential Privacy over Kernel Densities

Tal Wagner

Introduction

This paper introduces a novel protocol for estimating kernel density functions from distributed user data using Shuffled Differential Privacy (DP). By reducing complex density estimation to simple binary summations, the authors achieve an accuracy that nearly matches "Central DP" (which requires a fully trusted server) without actually needing a trusted central party. This breakthrough allows for high-accuracy private machine learning—such as classification and semantic "class decoding"—directly from anonymized end-user snapshots.

The Privacy Tug-of-War

In the world of Differential Privacy, there is a classic tug-of-war between trust and accuracy:

  1. Central DP is the "gold standard" for accuracy, but it requires users to send their raw data to a central curator. If that curator is compromised or dishonest, privacy is lost.
  2. Local DP (widely used by tech companies) solves the trust issue by having users add noise to their data before sharing it. However, this noise aggregates quickly, often making the resulting models significantly less accurate.

The Shuffled DP model offers a promising middle ground. Users add a small amount of noise locally, and a "shuffler" (an intermediate, limited-functionality entity) anonymizes the messages so the final analyzer cannot trace which user sent what. While previous work on Shuffled DP focused on simple sums or iterative training (like Federated Learning), this paper tackles Kernel Density Estimation (KDE). KDE is a powerful tool for understanding data distributions, but performing it privately in a "one-shot" collection setting—where users send a single update and go offline—is technically challenging.

Methodology: Shuffled DP for KDE

The authors propose a protocol that transforms the complex task of KDE into a series of simple binary summations, or bitsums.

  • Locality-Sensitive Quantization (LSQ): This is the core technical engine. LSQ maps high-dimensional data points into sparse, binary vectors. The "magic" of LSQ is that the inner product of these binary vectors approximates the kernel similarity (like a Gaussian or Laplacian kernel) between the original points.
  • Shuffled DP KDE Protocol: Each user takes their private data point, applies LSQ to turn it into bits, and sends those bits through a Shuffled DP bitsum protocol. The analyzer then sums these bits to reconstruct a private version of the density function.
  • Highest Density Class (HDC) Classifier: To build a classifier, the learner estimates a private density function for each class (e.g., "Dog" vs. "Cat"). A new test point is assigned to the class where its estimated density is highest.
  • Private Class Decoding: In a fascinating qualitative application, the learner uses the private density function to find the "top words" in a public vocabulary that best represent a class. This effectively "reads" the semantic meaning of the private data without ever exposing a raw record.

Datasets and Experimental Setup

The researchers evaluated their approach on four diverse datasets, utilizing pretrained models to turn raw data into the feature vectors used by the KDE protocol:

  • Text: DBPedia-14 (Wikipedia summaries), AG News (news articles), and SST2 (movie review sentiments), using SentenceBERT embeddings.
  • Images: CIFAR-10 (object categories), using SimCLR embeddings.

Key Insights and Results

The most significant finding is the accuracy parity: Shuffled DP can achieve accuracy essentially matching Central DP for KDE. This suggests we can eliminate the need for a trusted central party while maintaining high accuracy. The act of shuffling "amplifies" privacy; because the analyzer doesn't know which bit came from which user, the local noise added by users can be much smaller than in the Local DP model.

Accuracy across datasets and protocols
  • Classification Accuracy: As seen in the results, on DBPedia-14, the Shuffled DP approach using the "3NB" (Correlated Noise) bitsum protocol achieved nearly 80% accuracy with a privacy budget ($\epsilon$) of 2. This is remarkably close to the non-private baseline and significantly outperforms Local DP.
  • Kernel Resilience: The experiments demonstrate that the Gaussian kernel is highly resilient to the noise introduced by the shuffled model. It consistently outperformed simpler inner-product (IP) kernels in low-privacy-budget (high-noise) regimes.
  • Communication Efficiency: The authors tested different bitsum protocols. The RR (Randomized Response) protocol is the most communication-efficient (1 bit per dimension), while the 3NB protocol provides the best accuracy at a slightly higher communication cost.
  • Semantic "Ghost" Recovery: The "Private Class Decoding" results are striking. Even though the model is trained on noisy, shuffled bits, it successfully identifies that the "Film" class is about "biopics, movies, and screenplays." The semantic signal survives the privacy-preserving process.

Limitations and Future Work

  • The "Chicken-and-Egg" User Count: Shuffled DP protocols usually need to know the number of participating users ($n$) in advance to calibrate the noise levels. In a real-world "opt-in" scenario, this isn't always known. The authors suggest a preliminary Local DP round to estimate $n$, though this adds complexity.
  • Communication Scaling: While the bit-width is low, the number of messages scales with the dimensionality of the embeddings. For very high-dimensional data, this could become a bottleneck.
  • Static Snapshots: The paper focuses on "one-shot" collection. Extending this to continuous monitoring—where users' data changes over time—remains an open and important challenge for practical deployments.

Summary updated

Abstract

We study a setting of collecting and learning from private data distributed across end users. In the shuffled model of differential privacy, the end users partially protect their data locally before sharing it, and their data is also anonymized during its collection to enhance privacy. This model has recently become a prominent alternative to central DP, which requires full trust in a central data curator, and local DP, where fully local data protection takes a steep toll on downstream accuracy. Our main technical result is a shuffled DP protocol for privately estimating the kernel density function of a distributed dataset, with accuracy essentially matching central DP. We use it to privately learn a classifier from the end user data, by learning a private density function per class. Moreover, we show that the density function itself can recover the semantic content of its class, despite having been learned in the absence of any unprotected data. Our experiments show the favorable downstream performance of our approach, and highlight key downstream considerations and trade-offs in a practical ML deployment of shuffled DP.
BibTeX
@inproceedings{wagner2025learning,
  author = {Tal Wagner},
  title = {{Learning from End User Data with Shuffled Differential Privacy over Kernel Densities}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=QjSOgxJ0hp},
}
Figure