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

Tal Wagner

Sure, here's a blog-style summary of the paper:

TL;DR

This paper introduces a novel method for learning from user data while preserving privacy using "shuffled differential privacy" (shuffled DP). It achieves near-central DP accuracy with a privacy model that's more practical for data collection, enabling the learning of complex models like classifiers and even recovering semantic class information without ever seeing raw, unprotected data.

What Problem Does This Paper Address?

Collecting and learning from user data is crucial for many applications, but it raises significant privacy concerns. Traditional methods like central differential privacy (DP) require trusting a single entity with all data, which is often impractical. Local DP, where users protect their data individually, offers strong privacy but often leads to a steep drop in accuracy. The "shuffled DP" model offers a middle ground: users partially protect their data locally, and a central "shuffler" anonymizes their contributions. This paper tackles the challenge of applying shuffled DP to "one-shot" data collection scenarios, where data is gathered from a pool of uncommitted users, and aims to learn machine learning models with high accuracy while maintaining this privacy guarantee. A key challenge is learning complex models like classifiers without ever observing unprotected data, which could leak sensitive information.

Methods

The core of this work is a shuffled DP protocol for Kernel Density Estimation (KDE). KDE is a fundamental technique for estimating the probability distribution of data. The authors build upon existing work on shuffled DP for basic operations like summation (bitsum) and adapt it for KDE. Their approach leverages a concept called "locality-sensitive quantization" (LSQ) to break down the KDE problem into smaller, manageable bitsum problems.

Key methodological contributions include:

  • Shuffled DP KDE Protocol: A novel protocol that privately estimates kernel density functions from distributed user data using shuffled DP. This protocol is shown to achieve accuracy comparable to central DP.
  • Reduction to Bitsum: The KDE problem is reduced to multiple instances of a shuffled DP bitsum protocol. This allows them to leverage existing, highly optimized bitsum protocols.
  • Private Classification: The learned private KDE functions are used to build a "Highest Density Class" (HDC) classifier. This classifier assigns a test point to the class whose learned density function is maximized at that point.
  • Private Class Decoding: A unique capability of their method is the ability to "decode" the semantic meaning of a learned class representation. This is achieved by identifying vocabulary terms that are highly ranked by the learned class density function, even though the model never saw unprotected text data.
  • Practical Considerations: The paper also addresses practical aspects like discretization for secure implementation and analyzes trade-offs between privacy, accuracy, and communication costs.

Datasets

The authors evaluate their method on three textual datasets and one image dataset:

  • DBPedia-14: Text documents from Wikipedia articles (560K training, 70K test).
  • AG News: Text documents from news articles (120K training, 7.6K test).
  • SST2: Sentences from movie reviews (67.3K training, 1.82K test).
  • CIFAR-10: Images from object categories (50K training, 10K test).

These datasets were embedded into vector representations using pre-trained models (SentenceBERT for text, SimCLR for images). The paper notes that the datasets were not part of the pre-training sets to avoid privacy leakage.

Key Insights and Ideas

  • Shuffled DP Bridges the Gap: Shuffled DP proves to be a powerful privacy model for data collection, offering accuracy close to central DP while avoiding the need for full trust in a single curator.
  • KDE as a Foundation for ML: The paper demonstrates that a private KDE mechanism can serve as a robust building block for more complex machine learning tasks like classification.
  • Learning Semantics Without Raw Data: The ability to "decode" class semantics from learned density functions, without ever seeing unprotected data, is a significant privacy-preserving achievement. This suggests that even with strong privacy, models can capture meaningful representations.
  • Kernel Choice Matters: The choice of kernel (e.g., Gaussian vs. Inner Product) significantly impacts performance, especially under tighter privacy constraints. The Gaussian kernel, while having lower baseline accuracy, proved more resilient to privacy-induced errors.
  • Bitsum Protocol Trade-offs: Different bitsum protocols (RR, 3NB, Pure) offer distinct trade-offs between communication efficiency, accuracy, and privacy guarantees, allowing for tailored deployments.

Key Results

  • Near Central DP Accuracy: The proposed shuffled DP classifier achieves accuracy very close to central DP and non-private baselines, especially at moderate privacy levels.
  • Effective Class Decoding: For textual datasets, the learned class representations successfully identified semantically relevant terms, demonstrating that the model captures meaningful class information. For example, for the "Company" class in DBPedia-14, the decoded terms included "seacorp," "gencorp," and "southcorp."
  • Scalability: The method is designed for a "one-shot" data collection scenario, making it suitable for scenarios where users contribute data once.
  • Communication Efficiency: While communication costs vary with the chosen bitsum protocol, the paper provides analysis and empirical results showing manageable overheads for practical use cases. The 3NB protocol, for instance, offers a good balance of accuracy and communication.

Limitations and Future Work

  • User Count Assumption: A limitation of shuffled DP protocols is the requirement to know the number of participating users in advance. The paper addresses this by proposing a preliminary communication round for users to opt-in and for counts to be established.
  • Iterative vs. One-Shot: The paper focuses on "one-shot" data collection, contrasting with prior work on shuffled DP that often focused on iterative training. Extending the method to continuous monitoring or more complex iterative learning scenarios is a natural next step.
  • Exploring More Challenging Settings: The authors suggest future work could explore more complex ML pipelines and settings that involve continuous monitoring of end-user data.

Summary updated

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