Missing Mass for Differentially Private Domain Discovery

Computer Science > Cryptography and Security [Submitted on 14 Mar 2026] Missing Mass for Differentially Private Domain Discovery Travis Dick, Matthew Joseph, Vinod Raman 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. Comments: ICLR 2026 Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2603.14016 [cs.CR]   (or arXiv:2603.14016v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2603.14016 Focus to learn more Submission history From: Vinod Raman [view email] [v1] Sat, 14 Mar 2026 16:42:46 UTC (3,319 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-03 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)