Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.14016 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915863055040512 |
|---|---|
| author | Dick, Travis Joseph, Matthew Raman, Vinod |
| author_facet | Dick, Travis Joseph, Matthew Raman, Vinod |
| contents | We study several problems in differentially private domain discovery, where each user holds a subset of items from a shared but unknown domain, and the goal is to output an informative subset of items. For set union, we show that the simple baseline Weighted Gaussian Mechanism (WGM) has a near-optimal $\ell_1$ missing mass guarantee on Zipfian data as well as a distribution-free $\ell_\infty$ missing mass guarantee. We then apply the WGM as a domain-discovery precursor for existing known-domain algorithms for private top-$k$ and $k$-hitting set and obtain new utility guarantees for their unknown domain variants. Finally, experiments demonstrate that all of our WGM-based methods are competitive with or outperform existing baselines for all three problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_14016 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Missing Mass for Differentially Private Domain Discovery Dick, Travis Joseph, Matthew Raman, Vinod Cryptography and Security We study several problems in differentially private domain discovery, where each user holds a subset of items from a shared but unknown domain, and the goal is to output an informative subset of items. For set union, we show that the simple baseline Weighted Gaussian Mechanism (WGM) has a near-optimal $\ell_1$ missing mass guarantee on Zipfian data as well as a distribution-free $\ell_\infty$ missing mass guarantee. We then apply the WGM as a domain-discovery precursor for existing known-domain algorithms for private top-$k$ and $k$-hitting set and obtain new utility guarantees for their unknown domain variants. Finally, experiments demonstrate that all of our WGM-based methods are competitive with or outperform existing baselines for all three problems. |
| title | Missing Mass for Differentially Private Domain Discovery |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2603.14016 |