Missing Mass for Differentially Private Domain Discovery

Travis Dick, Matthew Joseph, Vinod Raman · 2026

Read Missing Mass for Differentially Private Domain Discovery by Travis Dick, Matthew Joseph, Vinod Raman (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-14016.txt.

Introduction

Dick, Joseph, and Raman study differentially private domain discovery, where users hold item sets from a shared but unknown pool. The goal is to name a useful subset without leaking private data. For set union, they show a simple weighted Gaussian baseline has near-optimal missing mass on Zipf-like data. It also carries a distribution-free bound for the worst item. Plugged into known-domain methods for top-k and hitting set tasks, it yields new guarantees, and tests beat older baselines.

Catalog record

CREATORTravis Dick, Matthew Joseph, Vinod Raman
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77758
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.14016

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Missing Mass for Differentially Private Domain Discovery Travis Dick, Matthew Joseph, Vinod Raman 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 ℓ 1 \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 k and k 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. 1 Introduction Modern data analysis often requires working in data domains like queries, reviews, and purchase histories that are a priori unknown or impractically large (e.g., the set of all strings up to a fixed length). For these datasets, domain discovery is a critical first step for efficient downstream applications. Differential privacy ( Dwork et al. 2006 ) (DP) enables privacy-preserving analysis of sensitive data, but it complicates domain discovery. In the basic problem of set union, for example, each user has a set of items, and the goal is simply to output as many of these items as possible. This is a necessary step before further analysis, so set union (also known as key selection or partition selection) is a core component of several industrial ( Wilson et al. 2020 ; Rogers et al. 2021 ; Amin et al. 2023 ) and open source ( OpenDP 2025 ) DP frameworks. For similar reasons, there are by now many DP set union algorithms in the literature. However, there are almost no provable utility guarantees (see Section 1.1 ). This makes it difficult to understand how well existing algorithms work, or how much they can be improved. Our Contributions. We prove utility guarantees for several problems in DP domain discovery. First, by reframing DP set union in terms of mass instead of cardinality (i.e., the fraction of all items recovered, rather than the number of unique items), we prove utility guarantees for the simple and scalable Weighted Gaussian Mechanism ( Gopi et al. 2020 ) (WGM). We first show that the WGM has near-optimal \ell_{1} missing mass on Zipfian data (Theorem 3.3 ). We then prove a similar but distribution-free \ell_{\infty} missing mass guarantee (Theorem 3.6 ). Next, we build on these results by considering unknown domain variants of top- k and k -hitting set and obtain further utility guarantees for simple algorithms that run WGM to compute a baseline domain and then run a standard known-domain algorithm afterward. Relying on Theorem 3.6 enables us to prove utility guarantees for both top- k (Theorem 4.3 ) and k -hitting set (Theorem 4.5 ). Finally, we evaluate our algorithms against the existing state of the art on six real-world datasets from varied domains (Section 5 ). These experiments demonstrate that, in addition to their theoretical guarantees, our WGM-based methods obtain strong empirical utility. 1.1 Related Work DP Set Union. Early work by Korolova et al. 2009 introduced the core idea of collecting a bounded number of items per user, constructing a histogram of item counts, and releasing items whose noisy counts exceed a carefully chosen threshold. Desfontaines et al. 2022 developed an optimal algorithm for the restricted setting where each user contributes a single item. Gopi et al. 2020 adapted noisy thresholding in the Weighted Gaussian Mechanism (WGM) by scaling contributions to unit \ell_{2} norm. Swanberg et al. 2023 investigated a repeated version of WGM, and Chen et al. 2025 further built on these ideas by incorporating adaptive weighting to determine user contributions, and proved that the resulting algorithm dominates the WGM (albeit by a small margin, empirically). A separate line of work has studied sequential algorithms that attempt to choose user contributions adaptively, obtaining better empirical utility at the cost of scalability ( Gopi et al. 2020 ; Carvalho et al. 2022 ) . We note that, as the utility results of Desfontaines et al. 2022 and Chen et al. 2025 are stated relative to other algorithms, our work is, to the best of our knowledge, the first to prove absolute utility guarantees for DP set union. DP Top- k . While several algorithms have been proposed for retrieving a dataset’s k most frequent items given a known domain ( Bhaskar et al. 2010 ; McKenna & Sheldon 2020 ; Qiao et al. 2021 ; Gillenwater et al. 2022 ) , to the best of our knowledge only Durfee & Rogers 2019 provide an algorithm for the unknown domain setting (see discussion in Section 5.2 ). They also provide a utility guarantee in terms of what Gillenwater et al. 2022 call k -relative error, which bounds the gap between the smallest-count output item and the k^{th} highest-count item. In contrast, we prove a utility result for the more stringent notion of missing mass (see discussion in Section 4.1 ). DP k -Hitting Set. In k -hitting set, the objective is to output a set of k items that maximizes the number of users whose subset intersects with it. This problem can also be viewed as an instance of cardinality-constrained submodular maximization. Previous works on private submodular maximization by Mitrovic et al. 2017 and Chaturvedi et al. 2021 establish approximation guarantees in the known-domain setting. However, they are not directly applicable when the domain is unknown. 2 Preliminaries 2.1 Notation Let \mathcal{X} denote a countable universe of items. A dataset W of size n is a collection of subsets \{W_{i}\}_{i\in[n]} where W_{i}\subset\mathcal{X} and |W_{i}|<\infty. We will use N=\sum_{i}|W_{i}| to denote the total number of items across all users in the dataset and M:=|\bigcup_{i}W_{i}| to denote the number of unique items across W . For an element x\in\bigcup_{i}W_{i} , we let N(x):=\sum_{i}\mathbf{1}\{x\in W_{i}\} denote its frequency. For a number r\in[M] , we use N_{(r)} to denote the r ’th largest frequency after sorting \{N(x)\}_{x\in\bigcup_{i}W_{i}} in decreasing order. We will use \mathcal{N}(0,\sigma^{2}) to denote a mean-zero Gaussian distribution with standard deviation \sigma. Finally, we use the notation \tilde{O}_{k}\left(\cdot\right) to suppress poly-logarithmic factors in k and likewise for \tilde{\Omega}_{k} and \tilde{\Theta}_{k}. 2.2 Differential Privacy We say that a pair of datasets W,W^{\prime} are neighboring if W^{\prime} is the result of adding or removing a single user from W . In this work, we consider randomized algorithms \mathcal{A}:(2^{\mathcal{X}})^{\star}\rightarrow 2^{\mathcal{X}} which map a dataset W to a random subset S\subseteq\mathcal{X} . We say that \mathcal{A} is ({\epsilon},\delta) -differentially private if its distribution over outputs for two neighboring datasets are “close.” Definition 2.1 ( Dwork et al. 2006 ) . A randomized algorithm \mathcal{A} is ({\epsilon},\delta) -differentially private if for all pairs of neighboring datasets W,W^{\prime} , and all events Y\subseteq 2^{\mathcal{X}} , \mathbb{P}_{S\sim\mathcal{A}(W)}\left[S\in Y\right]\leq e^{{\epsilon}}\mathbb{P}_{S^{\prime}\sim\mathcal{A}(W^{\prime})}\left[S^{\prime}\in Y\right]+\delta. We only consider approximate differential privacy ( \delta>0 ) since we will often require that \mathcal{A}(W)\subseteq\bigcup_{i}W_{i} , which precludes pure differential privacy ( \delta=0 ). 2.3 Private Domain Discovery and Missing Mass In private domain discovery, we are given a dataset W of n

Read the complete text