TL;DR
This paper introduces a novel "Vickrey mechanism" for privacy-preserving text generation that balances privacy guarantees with utility. By incorporating the second nearest neighbor into the selection process, it significantly improves the privacy-utility tradeoff compared to existing methods, offering up to 50% utility improvement for the same privacy level.
What Problem Does This Paper Address?
In natural language processing (NLP), generating text while preserving user privacy is a significant challenge. Many privacy-preserving techniques, particularly those based on differential privacy (DP), add noise to input data. However, when this noise is small, it can be easy for an adversary to reconstruct the original sensitive text, posing an empirical privacy risk. Existing methods often struggle to balance the need for strong privacy with the requirement for high utility in downstream tasks. This paper aims to bridge this gap by proposing a new mechanism that offers a better privacy-utility tradeoff and a framework for comparing different privacy-preserving text generation methods.
Methods
The core contribution is the Vickrey mechanism, inspired by the Vickrey auction (second-price auction). Traditional metric-DP text generation mechanisms typically add noise to an input word's embedding and then select the nearest neighbor to this noised embedding as the output. The Vickrey mechanism generalizes this by considering both the first and second nearest neighbors to the noised embedding. A tuning parameter, t, controls the probability of selecting the second nearest neighbor. A higher t means a greater chance of picking the second nearest neighbor, thus increasing privacy by making reconstruction harder.
The paper also proposes a framework for empirical privacy-utility tradeoff analysis. This involves defining an "expected inference error" for an adversary trying to reconstruct the original word and an "expected utility loss" for the downstream NLP task. They then frame the problem as a constrained optimization: maximize empirical privacy while keeping utility loss below a certain threshold. This framework allows for a more nuanced comparison of different DP mechanisms, especially when they use different distance metrics.
Datasets
The authors evaluated their approach on three datasets:
- Product Reviews dataset: A word-level dataset with positive and negative sentiment words.
- IMDb Movie Reviews dataset: A sentence-level dataset for binary sentiment classification, with a specific subset of words targeted for redaction.
- Twitter dataset: A dataset of tweets labeled for disaster events, used for classification.
They used both 300-dimensional GLOVE and FASTTEXT embeddings for these datasets.
Key Insights and Ideas
- The "empirical privacy risk" of small noise: Even with DP guarantees, small amounts of noise can be insufficient to prevent reconstruction of sensitive text, especially for common words.
- Vickrey auction as inspiration: The idea of using the second-highest "bid" (or in this case, the second nearest neighbor) provides a natural way to introduce more uncertainty and thus better privacy.
- Metric-DP vs. Empirical Privacy: The paper highlights that standard metric-DP parameters (like epsilon, ε) are not directly comparable across different distance metrics. An empirical privacy measure is needed to provide a common ground for comparison.
- Tuning parameter t is crucial: The parameter t in the Vickrey mechanism allows for fine-grained control over the privacy-utility tradeoff, enabling users to select a setting that best fits their needs.
- Generalization to k nearest neighbors: While the paper focuses on the second nearest neighbor, they show that the concept can be extended to k nearest neighbors, with diminishing returns beyond the second or third neighbor.
Key Results
- The proposed Vickrey mechanisms consistently outperform existing mechanisms (Laplace and Mahalanobis) in terms of the empirical privacy-utility tradeoff.
- On the tested datasets, they achieved up to 50% improvement in utility for the same empirical privacy guarantee.
- The empirical privacy measure (adversary's inference error) generally increases with the tuning parameter t, indicating better privacy.
- The utility loss generally increases with t, especially at higher privacy budgets (lower noise), as the mechanism is more likely to change the original word.
- The results show that the Vickrey mechanism with t = 0.75 often strikes a good balance, offering substantial privacy gains without excessively sacrificing utility.
Limitations and Future Work
- Optimization complexity for k > 2: While the paper generalizes to k nearest neighbors, selecting the optimal tuning parameters for k > 2 becomes more challenging due to an unbounded optimization space. The authors defer the details of this optimization to future work.
- Contextual information: The paper suggests exploring the inclusion of contextual information into the probability calibration between neighbors. This could further refine the privacy-utility tradeoff.
- Monotonicity assumption: In Algorithm 2 (parameter selection), they assume utility loss increases monotonically with epsilon (ε). Relaxing this assumption is noted as future work.
Summary updated