Abstract
This paper introduces GW (Greedy updates Without sampling), a novel approach to the Differentially Private Set Union (DPSU) problem. By incorporating local item frequencies and leveraging public datasets for knowledge transfer, the GW mechanism eliminates the need for wasteful random sampling, significantly lowering the noise threshold and increasing the number of items successfully released by up to 25%.
The DPSU Problem and the Sampling Bottleneck
The Differentially Private Set Union (DPSU) problem involves releasing the largest possible set of unique items (such as a vocabulary) from a collection of users' data without revealing the participation of any specific individual. Standard DP mechanisms typically follow a two-phase process: first, building a histogram where users "vote" for items they possess within a capped weight budget; second, adding noise to the histogram and outputting items that exceed a threshold $\rho$.
A major challenge in this framework is the sampling step. To bound sensitivity, traditional methods often require users to sample a limited number of items to vote for. This sampling is often "blind," potentially wasting a user's limited weight budget on common items that would have passed the threshold anyway. Furthermore, optimizing the sampling limit itself often requires additional privacy budget expenditure.
The GW Mechanism: Greedy Updates Without Sampling
The authors propose two main innovations to overcome these limitations:
- Eliminating Sampling via Greedy Updates: Instead of random sampling, the GW mechanism considers all of a user's items. It employs a Greedy Update (GU) strategy, using the user's local item frequency (how often an item appears in their specific documents) to decide how to spend their weight budget. Because the update order is determined by internal user data, it remains differentially private while being far more efficient.
- Knowledge Transfer (GW-KT): When a public, non-sensitive dataset is available, the mechanism can use global frequencies from that data to guide the greedy selection. This "hints" at which items are likely to be common, allowing the mechanism to reach the threshold for those items more rapidly.
Key Results and Performance
Mathematical proofs and empirical tests demonstrate that the GW mechanism consistently operates with a lower noise threshold $\rho$ than previous state-of-the-art "Policy" mechanisms, particularly at lower privacy budgets ($\epsilon$).
Evaluations on sensitive natural language datasets—including Reddit comments, Twitter customer service conversations, and financial news—show significant utility boosts. The basic GW mechanism outperformed previous state-of-the-art methods by approximately 10% on the Twitter and Finance datasets. When public data was incorporated for Knowledge Transfer (GW-KT), utility gains jumped by 12% to 25%.
Conclusion
The GW mechanism demonstrates that local frequency is a powerful, privacy-neutral tool for optimization. By replacing uniform sampling with greedy updates, the approach maximizes the utility of the privacy budget. Furthermore, the success of cross-domain knowledge transfer suggests that common linguistic patterns are consistent enough to boost DP utility even when public and private data domains differ significantly.
Summary updated