Differentially Private Domain Discovery
Abstract
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.
Cite
Text
Raman et al. "Differentially Private Domain Discovery." International Conference on Learning Representations, 2026.Markdown
[Raman et al. "Differentially Private Domain Discovery." International Conference on Learning Representations, 2026.](https://mlanthology.org/iclr/2026/raman2026iclr-differentially/)BibTeX
@inproceedings{raman2026iclr-differentially,
title = {{Differentially Private Domain Discovery}},
author = {Raman, Vinod and Dick, Travis and Joseph, Matthew},
booktitle = {International Conference on Learning Representations},
year = {2026},
url = {https://mlanthology.org/iclr/2026/raman2026iclr-differentially/}
}