Differentially Private Domain Discovery
Authors: Vinod Raman
Travis Dick
Matthew Joseph
Venue: ICLR 2026 Oral (2026)
Keywords: Differential Privacy
Partition Selection
Top-k Selection
Primary area: alignment, fairness, safety, privacy, and societal considerations

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.

analysis of sensitive Published as a conference paper at ICLR 2026
MISSING MASS FOR DIFFERENTIALLY PRIVATE DOMAIN DISCOVERY
Travis Dick Google Research
Matthew Joseph Google Research
Vinod Raman
Department Statistics
University of Michigan, Ann Arbor
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 output an informative subset of items. For set union, show that the simple baseline Weighted Gaussian Mechanism (WGM) has a near-optimal l missing mass guarantee on Zipfian data as well a distribution- guarantee. We then apply the WGM as a domain -iinovny precursor for existing known-domain algorithms for private top-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.
Loo missing
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 a critical first step for efficient downstream applica- tions. Differential privacy (Dwork et (006) (DP) enables data, but it complicates domain discovery.
In the basic problem of set union, for example, each user has set of items, and the goal is simply output as many of these items as possible. This necessary step before further analysis, so set union (also known as key selection partition selection) is core component of several indus- trial (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 liter- ature. However, there are almost no provable utility guarantees (see Section I.T). This makes 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.c., 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 al. 2020) (WGM). We first show that the WGM has near-optimal & missing mass on Zipfian data (Theorem) 3.3
We then prove a similar but
distribution-free f.c missing mass guarantee (Theorem 3.6
Next, we build on these results by considering unknown domain variants of top-k and k-hittinn set and obtain further utility guarantees for simple algorithms that run WGM compute baseline do- main and then run standard known-domain algorithm afterward. Relying on Theorem (36 enables us 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 their theoretical guarantees, our WGM-based methods obtain strong empirical utility.
"Work done while interning Google Research.

---

Published as a conference paper at ICLR 2026
1.1 RELATED WORK
DP Set Union. Early work Korolova et al. (2009) introduced the core idea of collecting a bounded number of items per user, constructing histogram of item counts, and releasing items whose noisy counts exceed carefully chosen threshold. Destontaines et al. (2022) developed an optimal algo- rithm 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 l norm. (Swanberg et al. 2003)) investigated a repeated version of WGM, and Chen et al. (2025)
further built on these ideas by incorporating adaptive weighting 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 choose user contributions
adaptively. obtaining better empirical utility at the cost of scalability Goop et al. al. 2022).
2020
Carvalho
We note that, as the utility results of Desfontaines et al. (022)) 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 dataset's it most frequent
items given a known domain (Bhaskar et al. 2010: McKenna & Sheldon, 2020 Qiao et al.) [02T]
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
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 tt highest-count item. In contrast, we prove utility result for the more stringent notion of missing mass (see discussion in Section 4.1).
DP /s- H-Hitting Set. In k-hitting set, the objective is to output set of & items that maximizes the number of users whose subset intersects with it. This problem can also be viewed as an instance of cardinality-constaaine mization by Mitrovic et (2017) and Chaturveddi et al. (202T) establish approximation guarantees in the known-domain setting. However, they are not directly applicable when the domain is unknown.
submodular maximization. Previous works private submodular maxi-
2
PRELIMINARIES
2.1 NOTATION
Let X denote countable universe of items. A dataset W of size is collection of subsets [Wahigjm] where W; C and [W|] < co. We will use = [W,] to denote the total num- ber of items across all users in the dataset and M == U, W denote the number of unique items across W. For an element E U, W,, we let N(x) = Σ, 1(x E W.} denote its frequency. For a number E [M], we use ((r) to denote the r'th largest frequency after sorting (N(x))xeU, in decreasing order. We will use (10 o²) to denote a mean-zero Gaussian distribution with stan- dard deviation a. Finally, we use the notation O₂ (-) to suppress poly-logarithmic factors in k and likewise for Ω4 and θ
2.2 DIFFERENTIAL PRIVACY
We say that pair of datasets W, W' are neighboring if W' is the result of adding or removing a single user from W. In this work, we consider randomized algorithms A (2*)* 2 which map a dataset W to a random subset X. We say that A is (c, deifffrrrnne private if its distribution over outputs for two neighboring datasets are "close."
Definition 2.1 (Dwork al. (2006)). A randomized algorithm A (e, diifferrennll private for all pairs of neighboring datasets W, W", and all events C 2
P PS-A(W) [S E Y] I e'P S +
We only consider approximate differential privacy (8 > 0) since we will often require that A(W) S
U, Wi which precludes pure differential privacy (6 0).
2

---

Published as a conference paper at ICLR 2026
2.3 PRIVATE DOMAIN DISCOVERY AND MISSING MASS
In private domain discovery, we are given a dataset W of n users, each of which holds subset of items W; X such that [W:] < 6o and X' is unknown. Given W, is goal is to extract an informative subset S S U, W that captures the "domain" of W while preserving differential privacy. In this paper, we often measure quality terms of the missing mass of S.
Definition 2.2. Given dataset W and output set S, the missing mass of S with respect to W is
((r)
MM(W,S)
Σ
N
ZEU, WAS
Smaller values of MM,W, S) indicate the that S better captures the high-frequency items in U, W,.
A useful perspective to the MM is that it is the & norm of the vector (N(z)/N)xet WAS. This view yields a generalization of the MM objective by taking the p' norm of the vector of missing frequencies. That is, for p 2 0, define
( N(x) (
MM, (W,,WW
(I)
zEU; WAS
where 11 R- + IR denotes the Ep norm. The usual missing mass objective corresponds to setting p = 1. However, it is also meaningful to set p * 1. For example, when = oo, the objective corresponds to minimizing the maximum missing mass. When p 0, we recover the cardinality-basee objective studied by existing work (see Related Work).
3 PRIVATE SET UNION
In general, we consider algorithms that satisfy the following "soundness" property: an item only appears in the output if it also appears in the input dataset.
Assumption 1. every algorithm A: (2*)* + 2 and dataset W, we require A(W) C C W.W.
| is standard across works in the unknown domain setting. However, even with this assumption, is difficult to obtain a meaningful trade-off between privacy and missing mass without assumptions on W.
Assumption
To see why, fix some n E N. and consider the singleton dataset W where each user has a single, unique item, such that W, {x,} and x; # I, for i * j. Fix j [n] and consider the neighboring dataset W' obtained by removing W, from W. Since we require that A(W") C U, W we have that P [zy E A(W)) = 0. Since A is (c, -diffeerrtel private, we know that IP (ay A(W))
8. Since j E [n| was picked arbitrarily, we know that this true for all j E [n] and hence, ES~A(W) [MM(A,)) S)] 2
As is usually picked to be o (2), cantly minimize MM for these datasets.
not possible to signifi-
Fortunately, in practice, these sorts of pathological datasets are rare. Instead, datasets often exhibit what is known Zipf's 's Power law (Zipf) 1949; Gabaix 1999. Adamic & Huberman 2002 Piantadosi 2014). This means that the frequency of items in a dataset exhibit a polynomial decay. Hence, natural way of measuring the complexity of W is by how "Zipfian" is.
Definition 3.1 (CC, s) Zipfiann. Let C 2 and s 2 0. A dataset W is (C, s) s)-ziffiaan if Noe) < for all r [M], where N(r) is the 'th largest frequency and N is the total number of items in W."
N
In light of the hardness above, we first restrict our attention to datasets that are SZipfann for s When S 1, the hard dataset previously outlined becomes a valid Zipfian dataset. We note that this restriction only impacts how we define the utility guarantee of the algorithm, and not its privacy guarantee; differential privacy is still measured with respect to the worst-case pair of neighboring datasets.
As s increases, the empirical mass gets concentrated more and more at the highest frequency item. Accordingly, any upper bound on missing mass should ideally decay increases. Another im- portant property of (C, s) -Zipfian datasets W is that they restrict the size of any individual set W,. Lemma 3.1. whose proof is in Appendix C.I makes this precise.
3

---

Published as a conference paper at ICLR 2026
Lemma 3.1. Let W be any -Zifsnn dataset. Then, max; [W] & (CN)
The rest of this section uses these two properties of Zipfianddatasets to obtain high-probability upper bounds on the missing mass. Our main focus will be on simple mechanism used in practice known as the Weighted Gaussian Mechanism (WGM) (Gopi et al. 2020
3.1 THE WEIGHTED GAUSSIAN MECHANISM
The WGM is parameterized by noise-level 0, threshold T > 1, and user contribution bound Au 2 1. Given a dataset W, the WGM operates in three stages. In the first stage, the WGM constructs a random dataset by subsampling without replacement from each user's itemset to ensure that each user has at most Ag items. In the second, stage the WGM constructs a weighted histogram over the items in the random dataset. In the third stage. the WGM computes noisy weighted histogram by adding mean-zero Gaussian noise with standard deviation to each weighted count. Finally, the WGM returns those items whose noisy weighted counts are above the threshold T'. Pseudocode appears in Algorithm
Algorithm Weighted Gaussian Mechanism
Input: Dataset W, noise level a, threshold T. and user contribution bound Åo. Construct random dataset W such that for every E [n]. W; S W; is random sample (without replacement) of size min [W[] from W,.
Compute weighted histogram H U, W; - such that, for each æ E U, W.
H(x) = Σ ==1
1fx E W,).
WW.1
For each æ E U, W. sample 2₂ ~ N(0, and compute noisy H'(x)) = H(x) + Zn. Keep items with large noisy weighted counts 5 { E U, H² T
Output:
The following theorem from Gopi et al. 2020
verifies the approximate DP guarantee for the WGM.
Theorem 3.2 (Theorem 5.1 GGop et al. 2020 For every Do 2 1, 0 E (0, ifo 0 are chosen such that
20
- 20
c
20
Ea
and
T Z
max IS
Vt
then the WGM run with (a, T) and input Do is (c, 8) 8)differrnt private.
In Appendix C.2.1 we prove that the smallest choice of o and T to satisfy the constraints
in Theorem 3.2 gives that θ ( (oog(()))) and T @ max fo log ( 11))
6 (max a 1}). This result will be useful for deriving asymptotic utility guarantees involving
the WGM.
3.2 UPPER BOUNDS ON MISSING MASS
Our main result in this section is Theorem 3.3 which provides a the missing mass for the WGM in terms of the Ziplian parameters of the input dataset.
upper bound on
Theorem 3.3. For every 8 >> 1, C 2 and (C, (),,)-Zipp -Ziifin dataset W, if the WGM is run with noise parameter > O, threshold T > 1, and user contribution bound Do 2 1, then with probability at least 1 3 over S WGM(W, Ao), we have that
C²
max; W
SM =09,CN
(T (T+
s-1
NVT
where q- min (max, Wol.Ao).
4

---

Published as a conference paper at ICLR 2026
Note that in Theorem 3.3 the missing mass decays as the total number of items N grows. Moreover, as decreases or s increases, the upper bound on missing mass decreases when N is sufficiently and T. This matches intuition, decreasing C' and increasing results in datasets that exhibit faster decays in item frequencies so relatively more of the mass is contained in high-mass items.
large compared
The proof of Theorem 3.3 relies on three helper lemmas. Lemma provides an upper bound on the missing mass due the subsampling stage. Lemma C.3 guarantees that high-frequency item in the original dataset will remain high-frequency in the subsampled dataset. Finally, Lemma C.4 provides high--robabiilty upper bound on the frequency of items that are missed by the WGM during the thresholding step. We provide the full proof in Appendix C.2.2
Theorem 3.3 bounds the overall missing mass of the WGM mechanism. As corollary, note that
if Do 2 max; [Wa] then the missing mass contributed by the subsampling step vanishes. By Theorem 3.2 and Lemma C.I] for every user contribution bound An 1, we need to pick
1og(1/5) and T = - (max (o, 1}) to achieve (c, d)-differenti privacy. Substi- tuting these values into Theorem 3.3 gives the following corollary.
θ
Corollary 3.4. In the setting of Thhorrm 3.3 if we choose the minimum and ' to ensure (c, D)-D, then with probability at least 1 - 3, we have that
( C² (max; [W 27
MM(W, S) O3,sAoo.C.N
s CV
where q² min (Do, max; [Wi]]-
Corollary 3.4 shows that the error due to subsampling can dominate the missing mass. Accordingly, should aim set Ao close possible max; [W]] In fact, if one has apriori public knowl- edge of max; [, then one should set Ao = max, [ By Lemma 3.1 for any (C, -)Zipfinn dataset W, max; [W] < (CN) and hence the loss due to setting Ao will only be logarithmic in N. However, Corollary 3.4 omits logarithmic factors in Ag. one should avoid An >> max; [W.]-
Theorem 3.5 whose proof is in Appendix D.I. shows that the dependence of and N in our upper bound from Corollary 3.4 can be tight.
Theorem 3.5. Let A be any (c, diffferrentill private algorithm satisfying Assumption ! For dataset W* such that
every s 1, 2 1, there exists a
C²/s
(e-1)/s
e² - (a-1)/s)
Es-A(W-)) MM(W* [S)] =
In 1
c.V
25
The proof of Theorem 3.5 exploitss Assumption Tby showing that any private algorithm that satisfies
Assumption | cannot output low-frequency items with high-probaabiliyy. We end this section by noting that our proof technique in Theorem also give us bounds on the foo missing mass (see
Equation T). Note that unlike Theorem 3.3 Theorem 3.6 whose proof is in Appendix C.2.3 does not require the dataset to be Zipfian.
Theorem 3.6. Let W be any dataset. For every e > 0, 5 E (0, and user contribution bound
Ao 2 1, picking e (t (+Vlog(L/o) and T = T (max(o, 1}) gives that the WGM is
(e, 8) diffferrenty private and with probability at least - 3 over WGM(W, Ao), we have
inax [W,]
(M, S &S...8.8
NN
where q" min(Ao max; [Wa]].
Upper bounds on the too norm missing mass will be useful for deriving guarantees for the top-k selection (Section 4.1 and k-hitting set (Section 4.2) problems.
4 APPLYING THE WEIGHTED GAUSSIAN MECHANISM
This section applies WGM to construct unknown domain algorithms for top-k and k-hitting set. For both problems, spend half of the overall privacy budgetrunning WGM obtain domain D, and
5

---

Published as a conference paper at ICLR 2026
then spend the other half of the privacy budget running a known-domain private algorithm, using domain D, for the problem in question. By basic composition, the overall mechanism satisfies the desired privacy budget. Pseudocode for this approach is given in Algorithm 2
Algorithm 2 Meta Algorithm
Input: Dataset W, noise-level and threshold (a, T), output size k; user contribution bound Ag 2 1, known-domain mechanism B
Let D < WGM(W, Δо) be the output WGM with noise-level and threshold (a, T') and input Ao Let S < B(W, k) be the output of B on input W and domain D
Output:
In the next two subsections, we introduce the top-k selection and k-hitting set problems, summarize existing known-domain algorithms. and provide the specification all algorithmic parameters. An important difference between the results in this section and that of Section is that by using MM bounds, we no longer require our dataset to Zipfian in order to get meaningful guarantees.
4.1 PRIVATE ToP-k SELECTION
In the DP top-k selection problem, are given some k N and goal is output, in decreasing order, the & largest frequency items in dataset W. Various loss objective have been considered for this problem, but we focus on missing mass.
Definition 4.1. For dataset W, N, q S k and ordered sequence of domain elements (I1,...,Toh Fgh. we denote the top-k missing mass by
Σ (O) Ei N(a.)
(W, MM((W,S
MM
N
We let the sequence S have length S l because we will allow our mechanisms to output less than items, which will be crucial for obtaining differential privacy when the domain X' unknown. Note that MM(W, S) MM, if one takes & IU: Wil. As before, our objective to design approximate DP mechanism B which outputs a sequence S C U, W of size at most k that minimizes MM (W,S) with high probability.
To adapt Algorithm to top-k, we need to specify a known-domain private top-k algorithm. We use the peeling exponential mechanism (see Algorithm for its simplicity, efficiency, and tight privacy composition. Its privacy and utility guarantees appear in Lemmas 4.1 and 4.2 respectively.
Algorithm Peeling Exponential Mechanism
Input: Dataset W, domain D, noise-level A, output size & [ Let (x) = Σ 1(2 e W;} for D.
Let (x) = (xx) + Zz for D where Zn Gumbel(A).
Output: Ordered sequence (R1) such that ((x)) Nio for all [k]].
Lemma 4.1 (Corollary 4.1 Durfee Rogers, 2019)). For every e O, (0, 1) and 1, if X Ös
then Algorithm 3 is (c, d)dfffrrrett private.
Lemma 4.2. For every dataset W, domain D. X 2 and k S |D]. if Algorithmm 3 is run with noise-level X, then with probability 1 - 3 over its output S, we have that
1
Σ
N(x)
Σ N(x) RES
0
log
D
N
N
B
(W.D)
where T&(W D) D is the true set of top-k most frequent items in D.
We provide the exact to achieve (c, diffferenta privacy for Lemma 4.1 in Lemma B.1 The proof of Lemma 4.2 is standard, relies Gumbel concentration inequalities, and appears Appendix

---

Published as a conference paper at ICLR 2026
C.3 Similar upper bounds for other performance metrics have also been derived (Bafna & Ullman
2017). ). With Lemmas 4.2 and [.1 in hand, using the same choice (a. T) as in Theorem 3.2 for
WGM yields our main result. The proof of Theorem 4.3 can be found in Appendix
Theorem 4.3. Fix c > 0, 8 (0, and user contribution bound Do 2 1. For every dataset W and k 2 1, if one picks a = e log (1/)) T= 5/. (ma.6//mmx/mmmm (maxfo, 11) from Theorem 3.2 and
from Lemma 4.1 then Algorithm run with Algorithm is (e, (e.d)-differentially private and with probability
= 66/2 M
13, its outpu satisfies
k
max; W
VB (ooo((M) M) )
MM - Ō3,AAoo
N
CVq-
where q" == min Do, max, [Wi]].
We end this section by proving that a linear dependence on & on the top-k missing mass is unavoid- able for algorithms satisfying Assumption when S 1.
Corollary 4.4. Let < 1 and 5 E 1), Let A be any (e, ddiffferrent private algorithm satisfying Assumption ! Then, for every ls 2 1, there exists dataset W such that
k
Bs-A(W.R) (W,)) 2 Ωs
EN
The proof of Corollary 4.4 is in Appendix and was used to prove the lower bound for set union (Theorem 3.5)
and is largely consequence of Lemma D.I. which
4.2 PRIVATE A A-HITTING SET
In the k-hitting problem, our goal is to output set S of items of size at most which inter- sects as many user subsets possible, which is useful for data summarization and feature selection (Mitrovic et al. 2017). More precisely, our objective to design an approximate DP mechanism which maximizes the number of hits Hits Hits(W, W, S) Σ 1 n W; # 0). Since this problem is also NP-hard without privacy concerns (Karp, 1972). we will measure performance relative to the optimal solution, i.e., show that with high probability,
algorithm output S satisfies
Hits(W, S) 2 7 Opt(W, k) err(e, 6, k)
where Opt(W, k) == arg maxxcca, Hits(W, S) is the optimal value, err(e, 6, k) is an additive error term that depends problem specific parameters, and (0, is the approximation factor.
Like our algorithm for top-k selection, our mechanism for the k-hitting problem will follow the general structure of Algorithm 2 We will take the known-domain algorithm B to be the privatized version of the greedy algorithm for submodular maximization, as in Algorithm from Mitrovic et al. (201)) This mechanism repeatedly runs the exponential mechanism (equivalently the Gumbel mechanism) to pick an item that hits a large number of users. After each iteration, we remove all users who contain the item output in the previous round and continue until we either have output items, run out of items, or run out of users, and return the overall set of items. We call this algorithm the User Peeling Mechanism and its pseudo-code is given in Algorithm in Appendix C.4
By combining this with the same WGM choice of (a, T') as in Theorem 3.2 for the first step of Algorithm 2 we get the main result of this section.
Theorem 4.5. Fix > 0 and 8 e (0, 1). For every dataset W, A 2 1, and user contribution bound Ag. if one picks a = θ log(L/o)). T S 8/2 (maxfor 13) from Theorem 3.2 and A = 0s/2 (1 (2V)) from Lemma 4.1 then Algorithm run with Algorithm is (e, 6) diifferrent private and with probability
B. its output satisfies
Hits(W,S) (1-2) )) Opt Ög.8,20
(K max, [Wa] (
33/2 log (MK))
evq"
where q-' min (A,, max; [Wi]] and M = 10, Ws/.

---

Published as a conference paper at ICLR 2026
Theorem 4.5
proved in Appendix C.4. gives that if & is not very large (i.e.,
In(MR) In(M) max; /Wa),
then with high probability, the additive sub-optimality gap is on the order of
k3/2 max; [Wil- log(M)
020.6,8.8
<vq"
When |
>> M, this provides improvement over Theorem in Mitrovic et al. 2017 whose guarantee is in terms log((X() and not log(M).
As in the lower bound proof for top-k selection, again rely on the work behind Theorem 3.5 to show that one must lose from the optimal value by restricting the algorithm to output a subset of U, W.
(0. 1) and A be any (e, diffferrrett private algorithm satisfying Corollary 4.6. Let < 1, 8
Assumption 7
Then, for every k 2 1, there exists a dataset W such that
1
E ASWA(WA))
(W,S)) (W, SS) 2 Opt(W, k) 52g
5 EXPERIMENTS
We empirically evaluate methods six real-life datasets spanning diverse settings. Informally, Reddit (Gopi et al.) (020), Amazon Games (Ni et al. 2019). and Movie Reviews (Harper & Konstan 2015) are "large". while Steam Games (Steam) 2025). Amazon Magazine (Ni et al., 2019), and Amazon Pantry (Ni et al. 2019) are "small" (see Appendix B for details). All experiments use a total privacy budget of 10 DDPP additional experiments using (0.1, 10- appear in Appendix F but are not significantly qualitatively different. Dataset processing and experiment code can be found
the Supplement.
5.1 SET UNION
Datasets. We evaluate the WGM and baselines all six datasets, relegating experiments the small datasets to the Appendix F.I..] for space.
Baselines.
The baselines are the Policy Gaussian mechanism from Gopi et al. (2020) and the Policy Greedy mechanism from Carvalho et al. (2022), as these have obtained the strongest (though least scalable) performance in past work. As suggested in those papers, set the policy hyperparameter 3 throughout.
Results. Figure D plots the average MM across trials, for all three mechanisms a function of to bound An E {1, 50, 100, 150, 200, 300}. Across datasets, we find that the WGM obtains MM within 5% of that of the policy mechanisms, in spite of their significantly more intensive computation. This contrasts with previous empirical results for cardinality, where sequential methods often output s 2X more items (see, e.g., Table in (Swanberg et (2023)). Plots for the small datasets (Appendix F.I.1 show a similar trend.
Morld Eavicro
0.00
0.70
013
0.15
(a) Reddit
(b) Amazon Games
(c) Movie Reviews
Figure 1: Set Union MM as a function of Ag. Note that lower is better.
8

---

Published as a conference paper at ICLR 2026
5.2 ToP-k
Datasets. All methods achieve near 0 top-k missing mass across all values of number of selected items E (5, 10, 20, 50, 100, 200) on the three large datasets, as most mass concentrated a small number of heavy items. We therefore focus on the three small datasets.
Baselines. We compare our WGM-then -ooek mechanism to the umited-domain top-k mechanism Durfee & Rogers 2019). Unlike our algorithm, the limited-domain mechanism has hyperpa- rameter k. As such, for each k E {5, 10, 20, 50, 100, 200), we take as baselines the limited-domain algorithm with & E {k, 5k; 10k, )o). When k oc, set Au algorithm. Otherwise, when mended in Section 3 Durfee & Rogers 2019).
for the monited-domaii DC, we set Ag = 100 for the limited-domati algorithm, as recom-
Results. Figure compares our method against the limited-domain method across different choices for k. Note that each line for the limited-domain method uses different k. We find that across all datasets, our method consistently obtains smaller top-k MM than all limited-domain baselines, and its advantage grows with k. Plots in Appendix F.2 demonstrate similar trends for a more stringent l loss.
332
3.20
A102
3.0
25
180
125
100
325
200
25
325
350
175
280
35
90
175
20
(a) Steam Games
(b) Amazon Magazine
(c) Amazon Pantry
Figure 2: Top-k MM function of k using Ao 100.
5.3 K-HITTING SET
Datasets. We use the same datasets as in the top-k experiments, for the same reason: a small number of items covers nearly all users in the large datasets.
Baselines. To the best of our knowledge, there are no existing private algorithm for the k-hitting set problem for unknown domains. Hence, we consider the following baselines: the non-private greedy algorithm and the private non-domain algorithm from Mitrovic et al. (2017) after taking U, W; to be a public known-domain. Note that the latter baseline is not a valid private algorithm in the unknown domain setting since, in reality, U, W; is private.
Results. Figure 3 plots the average number of users hit, along with its standard error across trials, as function of l {5, 10, 20, 50, 100, 200). fixing Ag 100. We find that our method performs comparably with both baseline methods, neither of which is fully private. particular, for the Steam Games and Amazon Magazine datasets, our method outperforms the known-domain private greedy algorithm that assumes public knowledge of U. W.. This because our method's application of WGM for domain discovery produces domain that is smaller than U, W; while still containing high-quality items. This makes an easier problem for the peeling mechanism in the second step.
FUTURE DIRECTIONS
We conclude with some possible future research directions. First, our upper and lower bounds for top-k and k-hitting set do not match, closing these gaps is natural problem. Second, all of our methods enforce by bounds by uniform subsampling without replacement from each user's 's item set. Recent work by Chen et al. (2025) employs more involved and dependennn subsampling strategies to obtain higher cardinality answers. Extending similar techniques to missing mass may be useful.

---

Published as a conference paper at ICLR 2026
-2.0
10:03
.043
70943
4.802
14003
10383
153
175
125
17%
180
(a) Steam Games
(h) Amazon Magazine
(c) Amazon Pantry
Figure Number of missed users as a function of k, using As = 100.
REFERENCES
Lada A Adamic and Bernardo A Huberman. Zipf's law and the Internet Glottometrics, 2002.
Kareem Amin, Jennifer Gillenwater,
Matthew Joseph, Alex Kulesza, and Sergei Vassilvitskii. Plume: differential privacy at scale. In Privacy Engineering Practice and Respect (PEPR), 2023.
Mitali Bafna and Jonathan Ullman. The price of selection differential privacy. In Conference on Learning Theory, pp. 151-168. PMLR, 2017.
Raghay Bhaskar, Srivatsan Laxman, Adam Smith, and Abhradeep Thakurta. Discovering frequent
patterns in sensitive data In Knowledge Discovery and Data Mining (KDD), 2010.
Ricardo Silva Carvalho, Ke Wang, and Lovedeep Singh Gondara. Incorporating item frequency for differentially private set union In Conference on Artificial Intelligence (AAAI), 2022.
Anamay Chaturvedi, Huy Le Nguyen, and Lydia Zakynthinou. Differentially private decomposable submodulaa maximization In Conference on Artificial Intelligence (AAAI), 2021.
Justin Y Chen, Vincent Cohen-Addad, Alessandro Epasto, and Morteza Zadimoghaddam. Scalable Private Partition Selection via Adaptive Weighting In International Conference on Machine Learning (ICML), 2025.
Damien Desfontaines, James Voss, Bryant Gipson, and Chinmoy Mandayam, Differentially private partition selection) Privacy Enhancing Technologies Symposium (PETS), 2022.
David Durfee and Ryan M Rogers. Practical differentially private top-k selection with pay-what- you-get composition Neural Information Processing Systems (NeurlPS), 2019.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis
In Theory of Cryptography Conference (TCC), 2006.
Xavier Gabaix. Zipf law for cities: an explanation The Quarterly Journal of Economics, 1999.
Jennifer Gillenwater, Matthew Joseph, Andres Munoz, and Monica Ribero Diaz. A Joint Expo- nential Mechanism For Differentially Private Top-k In International Conference Machine Learning (ICML), 2022.
Sivakanth Gopi, Pankaj Gulhane, Janardhan Kulkarni, Judy Hanwen Shen, Milad Shokouhi, and Sergey Yekhanin. Diiferentially private set union| In International Conference on Machine Learn- ing (ICML), 2020.
Maxwell Harper and Joseph A. Konstan. The Movielens Datasets: History and Context 2015.
RM Karp. Reducibility among combinatorial problems Complexity of Computer Computations,
1972.
Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas. Releasing search queries and clicks privately In International Conference on World Wide Web, 2009.
10

---

Published as a conference paper at ICLR 2026
Ryan McKenna and Daniel R Sheldon. Bermute-and-fie A new mechanism for differentially pr- vate selection Neural Information Processing Systems (NeurIPS), 2020.
Marko Mitrovic, Mark Bun, Andreas Krause, and Amin Karbasi. Differentially private submod-
ular maximization: Data summarization in disguise In International Conference Machine Learning (ICML), 2017.
Jianmo Ni, Jiacheng Li, and Julian McAuley, Justitying recommendations using distantly-lbeeled re-
views and fine-gr mne-grained aspects. Empirical Methods in Natural Language Processing (EMNLP),
2019.
OpenDP.
Privatizing histograms.
https://doca opwndp.org/en//ttteeoee /ttpgg//////abblle
gett
het.mppllesssstttrammsaa html 2025.
Steven T Piantadosi. Zipf's word frequency law in natural language: critical review and future directions Psychonomic bulletin & review, 2014.
Gang Qiao, Weijie Su, and Li Zhang. Oneshot differentially private top-k selection. In International Conference on Machine Learning, pp. 8672-8681. PMLR, 2021.
Ryan Rogers, Subbu Subramaniam, Sean Peng, David Durfee, Seunghyun Lee. Santosh Kumar Kancha. Shraddha Sahay, and Parvez Ahammad. Linkedln's Audience Engagements API: A
Privacy Preserving Data Analytics System at Scale Jourmal of Privacy and Confidentiality 2021.
Steam. Steam games dataset.
https://wwe /wwpo/////wwk.gggl.......
steam iieaamvvideo games/data 2025. Accessed: 2025-09-22.
Marika Swanberg, Damien Desfontaines, and Samuel Haney. DP-SIPS: A simpler, more scalable
mechanism for differentially private partition selection 2023.
Roman Vershynin, High-dimensional probability: An introduction with applications in data science
Cambridge University Press, 2018.
Royce J Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons- Marengo, and Bryant Gipson. Differentally Private SQL with Bounded User Contribution 2020.
George Kingsley Zipf. Human behavior and the principle of least effort: An introduction human ecology Aldison-Wesley Press, 1949.
A USEFUL CONCENTRATION INEQUALITIES
In this section, we review some basic concentration inequalities that we use in the main text. The first is the following Gaussian concentration equality.
Lemma A.1 (Gaussian concentration (Vershynin| 2018)). Let Xi...., Xn be an iid sequence of mean-zero Gaussian random variables with variance o². Then, for every 8 E (0, 1), with probability least 5, we have that
2n
max X,I < v 2
The second is for the concentration of a sequence of Gumbel random variables. While this result is likely folklore, we provide a proof for completeness.
Lemma A.2. Let XI...., X, be an iid sequence of Gumbel random variables with parameter X. Then, for every 1), with probability at least - 8, we have that
2n
max X, S A
11

---

Published as a conference paper at ICLR 2026
Proof. Consider single X,, and recall that the CDF of Gumbel distribution with parameter À is (x) exp(- - exp( (ap(-x/A)) x/)). Then
P P
T = P > + < -T]
exp( exp + exp(-exp(T/A)
I expl -T/) + exp( cxpp(()))
where the inequality uses e v œ. Substituting in > llo((2n/)) yields
P| > t - 2n
+ exp((2n/0)
since for 2 1 and 5 E (0,1), 2n In result.
Union bounding over the samples completes the
B PRIVACY ANALYSIS OF PEELING EXPONENTIAL MECHANISM
Lemma B.1 (Lemma 4.2 in Gillenwater et al.
(2022)). For every > 8, (0, 1) and k 1, if
where
8 llog (t) + 8e
8 log (1)
60 max
k
then Algorithm
3is is (c.ffddifferentiaall private.
C MISSING PROOFS
C.I PROOF OF LEMMA 3.1
Proof. Let W be a (C, s)-Zipfian dataset. Let r* max; [W.]. Then, it must be the case that
CN N(r)) Since W is (C, -ZZiffia, also know that N(r)) S [raya. Hence, have that
(r*)* CN implying that r* s (C.)
C.2 PROOFS FOR THE WGM
C.2.1 PROOF OF a AND T
(Vlog(t)
Lemma C.1. For every e 5 E (0. and Ao 2 1, there exists
and
= Ōs,A, (max(a, 1}) which satisfy the conditions in Theorem 3.2
Proof. Starting with a, it suffices find the smallest such that
+
60
20
2
By monotonicity of o- --1()), we have that
1
5
1
8
4-1
20
2
20
Hence, it suffices find the smallest that satisfies
2co² + 2
120.
Using the quadratic formula we can deduce that we need to take
Φ --1
8
log
(#)
0 2
Ω
12

---

Published as a conference paper at ICLR 2026
where the last inequality follows from the fact that (p) = / /2 (TT))
for >
1.2 Now for
T, have
(1-2) 1
(
((1-2))
oΦ
+
o
Isrsao
v8
Hence, it suffices to upper bound
1
8
20
o
By Bernoulli's inequality and monotonicity of t (.), we have that
(11-2)
8 30
Φ -
S 1-1
1
2Do
Since 5 < 1 and Ao 2 1, we have that
1
8
24u
2 log
2D
5
Hence, it suffices to take
24u
Au
T= T= 1=1+01 2 2og
=
max
0 log
1
8
This completes the proof.
C.2.2 PROOF OF THEOREM 3.3
Before prove Theorem 3.3 present three helper lemmas, Lemma C.2 and C.4 which correspond to three different "good" events. Lemma C.2 provides an upper bound on the miss- ing mass due to the subsampling stage. Lemma C.3 guarantees that high-frequency item in the original dataset will remain high-frequency in the subsampled dataset. Lemma C.4 provides a high-probability upper bound the frequency of items that are missed by the WGM during the thresholding step. The proof of Theorem 3.3 will then follow by combining Lemmas C.2
C.3 and
Lemma C.2. Let W be a sY-ifann dataset for C 2 and 1. Fix contribution bound
Ao 2 1. Let W be the random dataset such that W; C W; is a random sample without replacement size min(Do, W.}. Then, for every 3 (0,1). 1). with probability B, we have that
C2/s
(CN))
MM(W,U,W <
log
P'N
Do where p* min (1, max; [w:
Proof.
Let min 1,, (
and p² min; Pt. Fix an item U, W.
Then
TP
x
W;
II - p:) S exp
Σ Ps
K.EW.
where N(x) E, 1 1f E W.). Fix 3 (0, 1) and consider the threshold
1 log
(CN)
Q = p
1
13

---

Published as a conference paper at ICLR 2026
Note that Q" by definition of p². Since W is (C, (C,,s--ipfian for any it must be the case that items whose frequencies are above Q. By the union bound, we get that
[M] with N(r) Q,
CCN Q
1/a
by r I CN Hence, there at most CN 1/e
"heavy"
Nir)
CN
1/8
Fr E Uw: \ W, and N(a) Q -
C P
Q
so with probability at least B, have that N(x) Q
U, W, aor E W.W.
Under this event, we have that
MM(W,U..)) S N
Σ N(x)
S N
Σ N
(
r2ro
{
{(O)
(NN)
1/s 3 Using the fact that
where ro = max get that
N(r) - CNr and s > 1 (by assumption),
1
Σ
NO)
SC
Σ r SC
x=
C
(ro 1) 10=
N
ro-1
+200
Since ro 2 completes the proof.
CN
1/s
we get MM(W,U,W)
< Ck/a
Using Q =
1 log
(CN)
n²
Lemma C.3. In the same setting as Lemma C.2 for every B E (0, 1), we have that with probability
1- B, for every x E U, W.
((x) T2 N(x) Z Nzx),
where p² = min (1,
An maxi W.T
log (ON))M) and N(x) = (..ee. W.).
T2: = p
Proof. Fix some x U,W, W, such that N(x) 2 T2. Then, N(x) the sum of independent Bernoulli
random variables with success probability least p". Thus, we have that [(() 2 p² (xx) and multiplicative Chernoff's s inequality gives
1 (p-N(aa) S exp <xxp( (-for s exp (-
PP [(x) <
Now, since W is (C, s), --Ziifiaa, have that N(x) < CN for all U, W., there can be at
1/s
most
CN T2
elements U,W, W. with N(x) 2 r2- A union bound yields
1 NO) (CN))T 3r UW.: T2, N(x)
3
CN 1/a
P
SB,
72
which completes the proof.
Lemma C.4. For every dataset W, if the WGM is run with noise parameter a > O, threshold
T > 1, and user contribution bound Do 2 1, then for every (0, 1), with probability at least
1-3 S NGM(W,Ao)) we have that (x) < To. Vx M, where To T log 22
and M W, W.
Proof. By Line in Algorithm we have that for all x E M, its noisy weighted count is H'(x) < T. Hence, by standard Gaussian concentration bounds (see Appendix A). with probability at least
1 - B over just the sampling of Gaussian noise in Line 3, we have H ((x) < To for all M.
14

---

Published as a conference paper at ICLR 2026
We now ready to prove Theorem 3.3
Proof. (of Theorem 3.3 Let the random dataset obtained by sampling set W; elements of size min Ao, [W, without replacement from each W,, and let S be the overall output of the WGM.
Let (x) Ei=1 1( Wi be the frequency of item in the subsampled dataset and note that (z) (() for all E U, W,, where H is the weighted histogram of item frequencies from W. Let M U, W be the random variable denoting the set of items U W but not where
in the algorithm's output S. Finally, define T1 p
2v and T2 := log 3(CN)*
To = T' // 2 log 2N
Let E1. Eg. and Ey be the events of Lemma probability for each event to be Then, by the union bound, E1 EE n E3 occurs with probability 3. 1- B. It suffices to show that Eg n Fg n F3 implies the stated upper bound on MM(W S). We decompose MM(W,S) S) into two parts, mass missed by subsampling and mass missed by noisy thresholding:
and C.4 respectively, setting the failure
MM(W,S) MM(W,U..) N
Σ N(x). DEM
(2)
Under E,, we have that
T-1
C2/$ log
3(CN)
MM(W,,.)) 5 P
B
hence for the remainder of the proof, we will focus on bounding + ExEM N(x). First, claim that under Eg and Es, we have that ((x) I max(T1, T2) =: for all E M. This is because, by event E.., we have that for every x E M, N(x)) T. Thus, there exists an M such that (x)) 2 T2, then by event E2, it must be the case that (N)) < N(x) S o To. which implies that (1x) Ti.
Now, define ro == max (CN) .11. If 2 then CN < r. Since N(x) S for every E M,
every such item has rank greater than Tg- Hence,
N
1 N
E
1 N
E
No
Σ r2re
tt <
JEM
8270
ro-1
8
Substituting in the definition of To and continuing yields
01/s
max
2 p
log
3(CN))/0
Σ N(x) N(r) <
p
N
N
BEM
Now, are ready complete the proof. Using the decomposition of MM(W,S) in Equation along with En n Eg n E3 implies that
11/$
3(CN)I/
C
max 2 8 log
3/NN///
3
MM(W,S) < 8-1
log
N
B
s-1
P'N
1//
3(CN)
9 9max V Vo log
8
p*N
B
1//$
6N
3(CN)
max
V
T (
22og
2log
log
p* N
B
The proof is complete after noting that Va
max; W.
p
15

---

Published as a conference paper at ICLR 2026
C.2.3 PROOF THEOREM 3.6
As in the proof of Theorem 3.3 we start with the following lemma which bounds the maximum missing mass due to the subsampling step.
Lemma C.S. Let W be any dataset. Fix user contribution bound Do 1. Let W be the random dataset such that W; S W, random sample withou replacement of size min ( (Do, W.). Then, for every B E (0, 1), with probability 1 B, we have that
N log
3
MM (W,U,)
PdN
where p" min (1, max, A (wl)
Proof. Let W be any dataset, Ao 2 1 and 8 E (0, 1). We will follow the same proof strategy as
Ao and p² min; pt- Fix an item E U, W. in the proof of Lemma C.2 Let min (1, (1,1w.) Then,
(- P. (
P
W;
II (1 - p:) S exp
where ((x) - E; 1/x E W.). Fix
(0, 1) and consider the threshold
1
N
Q
log
1.
p
Since EzeU, w, N()) N, we have that that there are at most Hence, by the union bound, we get that
N items such that N(x) Q.
P Br Uw, W. and N(x) Q - SB.
N
Hence, with probability at least
3, we have that if xr & U, We then N(x) S Q, giving that
log 3
MM (W, <
PºN
which completes the proof.
Now, we use Lemma C.5 complete the proof of Theorem 3.6
Since the proof follows almost
identically, we only provide sketch here.
Proof. (sketch of Theorem 3.6)
As in the proof of Theorem 3.3
define q min(max; Wal, Ao}
and To T' + oov 2 log
GN 3
Keep
==
2 but take
8
3N
To
log
p
B
Let Eg be defined identically in terms of Tg. That is, Eg is the event that H()) Tp for all M,
where To T T+o log and M U, W. \ Likewise, define E3 terms of 72 analogous to that in the proof of Theorem 3.3 That is, Eg is the event that for all x e U, W,, either N(x) m follows identitically
or ((x) _ (xr). The fact that Eg occurs with probability at least
from the proof of Theorem 3.3 As for event Es, note that we have
P
3x E Uw: N(x) 2 T2, N(x) < D
P' e
<
3'
16

---

Published as a conference paper at ICLR 2026
which follows similarly by using multiplicative Chemoff's, the union bound, and the fact that there can be at most N. items with frequency at least 72. Hence, E3 occurs with probability least 1 - &
72
Then, by the union bound we have that with probability 1 20 both Eg and E3 occur. When this happens, we have that (xx) S max(n) 12) for x E M because either N(x) S T2, or otherwise pp" (x) & N(x)= & T implying that ((x) I 71- Consequently, under Eg and Eg, we have that
((x)
max m1, T2)
max WAS
N
N
By Lemma C.5
the event
3N log 3
(M, p* N
occurs with probability
8 3.
Hence, under E1 n Eg n Es, we have that
(xr)
MM (W, S max MM.
max Dc WAS
N
}
8 N
3N
6NV
max log
Vq
T T 2 log
vv
3
3
Vin(1/5) and T (
which occurs with probability 1 B. Finally, plugging in θ completes the claim.
C.3 PROOF OF THEOREM
Since the privacy guarantee follows by basic composition, we only focus on proving the utility guarantee in Theorem 4.3 First, we provide the proof of Lemma 4.2
Proof. (of Lemma 4.2 Let T =T(WW D) S and O S TW D). Then, |/| |0| < and
Σ
N(x) Σ N(x [Nxx)
N(x)
N(x).
(W.D(
ZES
xEI
SEO
Since = = JO]. there exists one-to-one mapping in O. Thus, we can write
O that pairs each item in I with item
M
= N()))
N(x))
((N)) (T()))))
DET
SEO
zel
By definition of and O, we have that for every and y E O, O,) (z). Hence, we have that N(x) - Nyy < Zy Ze and
(NN()) - & (Zn(s) - bz).
ØE!
zEI
Define R = Exer (7 (Z) 2.). Our goal is to get high-probability upper bound on R via concentration. By Gumbel concentration (Lemma A.2), with probability 1 B, we have that max,eD 7zll < A 1og(2
())))))))))) /3). Hence, under this event, we get that
R S 2k l)g(2)
Altogether, with probability 1 - B, we have
Σ
N(x) Σ N(x) R 2k (og(()D)/3)
(W,)
#ES
Dividing by N completes the proof.
17

---

Published as a conference paper at ICLR 2026
Combining Lemmas 4.2 and 4.1 then gives the following corollary.
Corollary C.6. For every dataset W, domain D, k & [ 0, and E (0, 1), if Algorithm 3 run with θs from Lemma 4.1 then Algorithm 3 is (e, -difffrrrnell private and with probability least
B over its output S, have that
1//22 log D
E N(x) - EN(x)
I Ös,B
N
eN
DE (ETT(WD)
ZES
With Corollary C.6 in hand, we are now ready to prove Theorem of (a, 2') as Theorem 3.2
4.3 after picking the same choice
(in(1/0) and T
Proof. (of Theorem 4.3) Recall that by Theorem 3.6 if we set a
θ
A (max(ar, 13), then the WGM is (e/2, - private and with probability at least B/2 over D WGM(W, Ao), we have that
max [Wa] eN V
MM (W, D) S Ö 5/2.//23//2
Let (W) be the true set of top-k elements and (W. D) be the set of top-k elements within the (random) domain D. Then, under this event, Equation gives that
max; [W;]
Σ
N(x)
E N(a) (W..(
S (W, S 0O0,6/299/2
eN VT
DET((W)
By Corollary C.6 we know that running Algorithm on input W, domain D and = Öx7²
gives (e/2, 8 differentialyy privacy and that with probability at least 1-3/2, its output satisfies
1 N
Σ
N(x)
Σ ((x)
I 06/2.8/2
h//2 log [D]
(5)
eN
FES
Adding Inequalities and 5 together and taking 1 - B, the output S of Algorithm satisfies
[D]
- IU, W/
=: gives that with probability
max, W Evg-
Vlllg((M)
MM (w, s 0
which completes the proof.
C.4 PROOF OF THEOREM 4.5
Before we prove Theorem 4.5 we first present the pseudo-code (Algorithm for the user peeling mechanism described in Section along with its privacy and utility guarantees.
The following lemma gives the utility and privacy guarantee of Algorithm Lemma C.7. For every dataset W. domain D. and k I [D). if Algorithm parameter X > 0, then with probability - over its output S, we have that
is run with noise
Hit (1-1 Opt(W, 2k:
211
where OW, D,k) arg D.g. Hits(W,S). If one picks X = θ /K
from Lemma
4.1 then Algorithm 4 is (c, differentially private and with probability 1 - 3 over its outpul S, we have
(W,s 2 (1 (1- Opt(W, D. Ōs.0
3/32 log (lDik)
18

---

Published as a conference paper at ICLR 2026
Algorithm 4 User Peeling Mechanism
Input: Dataset W, domain D. number of clements
k, noise-level À
Initialize W <- W, D1 + D, and output set Sp <- 9
1, j j= l...... do
Compute histogram (()x) E, (x e W for all x Dy-
Compute noisy histogram (x) = H² Zμ for all x E Dj where Z2 ~ (Am
Let xy arg max (x)
Update Sj + 13-1 (zy). Dj+1 + Dj (a3), and W + {W, E W : 2y $ W.}.
end Output: Sk
Since Algorithm 4 also uses the peeling exponential mechanism, the privacy guarantee in Lemma C.7] exactly from Lemma and so we omit the proof here. As for the utility guarantee, the proof similar the proof of Theorem in Mitrovic et al. (2017). For the sake of completeness, we provide self-contained analysis below.
Proof. Note that there exists at most | random variables Z Let E be the event that !Zl S a for all x E D and E [k]. where a Aln (2Ikk) Then, by Gumbel concentration (Lemma A.2 have that P(E) event F. happens.
B. For the rest of this proof, will operate under the assumption that
Define the function 2D + N f(S) = E= 1W, n + 0) Hit S). Then, f is a monotonic, non-negative submodular function. For x E D and S S D let A(x, 5) = S(S U (x)) ((S) 2 O. Let 5* arg maxxcDDisss ((S) be the optimal subset of D and denote Opt f(S).. First, claim that for every S C D,
Opt Opt-/(S)
max rES'S
S)x 2
(6)
k
This is because
s S S(SSUSS
S(() + Σ Axx
#ES
$ f(S) + max AIr, S). zES*\S
where the first two inequalities follows from monotonicity and submodularity respectively. Now, let "iy...., Fgg be the (random) items selected by the algorithm, and S₁- {, with So 0.
At round j E [k:]. define the current domain D2 = D D S Let
z arg max (1x,5-11).
Then, by Equation 6 we have A A S 2 Opt - 1(8 This implies that
Sgr)) Opt ((5
(A S - Si-1))
k Opt f(S
(HP( Hi(x)))
k
where the last equality stems from the fact that for every 2 E Dj, A(a, S Hz(()).
Recall that +²((x) (x) =- (1) + 23 for all D. We can upper bound H H1(x)) HH;)))
H = (x)) - (Ix)) + (Z) - Lzz < Zz - L,zz
where last inequality is because At (xx;) (ary) s 0 by the choice of æı E arg max A (x))
and the fact that 23 E St \Sy-1 Dj. Therefore,
Opt -((S-11) (Zz, -Zzz)
A S,-1) 2
(7)
k
19

---

Published as a conference paper at ICLR 2026
Let G, = Opt (f))). Using f(S)) f(S)-1) (rz S)-1), rearrange Equation to get
(1-1) G (1 1 1 + (Z4z -Zzz)
On the event E, we have that 24 Z 1 | + |2/= - 2a, hence
G3 (1 1) G-- 1 2a.
Recursing for 1,,... k and using the fact that Go Opt and (1 - ) S e_ gives
1 Gx Opt +2ak.
Substituting in the definition of G3 and a X In( 2 gives
f(S)) 2 (1 (1-
2) Opt 24 log
2
B
The guarantee in Lemma C.7 is with respect to the optimal set of i elements within the domain D. Since D S U, W we have that
Opt(W, D) S (P,
The following simple lemma shows that when the domain D contains high-frequency items from W. Opt(W, k) is not too far away from Op)(W.k).
Lemma C.8. Fix dataset W, 2 O, and let D = fx E U, W. N(x) 2 r}. Then, Opt(W, D, 2 Opt(W,k) kr.
Proof. Recall that f(S) == Hits(W, 5) is a monotone, non-negative submodular function. Let Si S X be the subset of X' that achieves f(Si) Opt(W, k) and S2 be the subset of D that achieves f(S2) = Opt(W, D, k). By submodularity and the definition of X \ D we have that
f(S1) < f(f.f(SnDDD f(S, nx D) s f(S2) + kT,
which completes the proof.
Lemma C.8 allows us to use the MM upper bound obtained by the WGM in Theorem 3.6 to up-
grade the guarantee provided by Lemma C.7 to be in terms of Opt(W, k) instead of Opt W. D, k). By using the same choice of (a, 7') as in Theorem 3.2 we get the main result of this section. As be- fore, since the privacy guarantee follows by basic composition, we only focus on proving the utility guarantee.
Proof. (of Theorem 4.5) Recall that by Theorem 3.6 that if we set a Vin(1/0)
and
Ô 5/2 (max(o 1) }}), then the WGM is (c/2,8/2 diff)rrrrretntallly private and with probability at least
1 - B/2 over D ~ WGM(W, Ao), we have that
max; [W cNvq"
MM (W, D) S Ô Ô 5/2.9/2//2
By Lemma under this event we have that
max; WWl ev/-
Opt 2 Op,(W, Ô O2..8/2,812
Now, by Lemma C.7 we know that running Algorithm 4 on input W, domain D and À 08/2
gives 2/2ff//2)diiffeeentiall privacy and that with probability least - B/2,, its
output satisfies
Hits(W,S) (1- - Opt(W, D2k) - 05/2.9/2
3/2 log (ID|B)
(-
20

---

Published as a conference paper at ICLR 2026
Hence, by the union bound, with probability least 1 B, both events occur and we have that
Hit 2 (1 1 Opt(W, D) - ÖB,6,S ( (=ev
k max;
ev + 1./2
[Wi
log (MK)
where we use the fact that |D| M.
D LOWER BOUNDS
D.1 LOWER BOUNDS FOR MISSING MASS
In this section, we prove Theorem 3.5 The following lemma will be useful.
Lemma D.1. Let A be any (c, diffferrretlllll private algorithm satisfying Assumption 7 Then, for every dataset W and item E W,, if (xx) & - In
+ e' =zz)) then PS~A(W) (xc E S s 2-
Proof. Fix some dataset W. Let A be any randomized algorithm with privacy parameters S 1 and E (0, 1) satisfying Assumption This means that for any item x E U. W, such that Nw (2) = 1, have that
PS-A(W)) [a S] S 6,
where for dataset W, we define (w == E; 1/ E W.). Now, suppose U, W; is item such that Nw (x) = 2. We can always construct a neighboring dataset W" by removing a user such that Nw (x) Thus, have that
Ps~A(W) [x' E S] S E e'PSAAWW (x E S] +8 de + 80e" + +).
More generally, by unraveling the recurrence, we have that for any U, W. with Nw b.
h-1 ((e))
c
PS-A(W) (or E S) S
Since W was arbitrary, for any dataset and any x U, W. with Nw (x) = we have that
pess
PS-A(W) $ 57 2
e
Now, consider the exclusion probability p 1/2. Our goal is to compute the largest ba such that for any dataset W, any E U, W; with (w(x) S b* has PSSAA(W) [r $ S) 2 2. It suffices to solve
for in the inequality 5-"" e--1 2 1/2, which yields b < 1 In (1 + e'
28 =
Lemma D.I provides uniform upper bound on the the probability that any private mechanism can output a low frequency item. We now use Lemma D.I to complete the proof of Theorem 3.5
Proof. (of Theorem 3.5) Let b' _ In (1 =-11) in the proof of Lemma D.1 By Lemma D.1 for any dataset W and item x U, W2 such that N(x) S b*, we have Ps--A(W) [x &
2"
Consider dataset W of size n, taking sufficiently large, where Ni.) θ (-) for all ranks [M*], where M Uú W (note that such dataset is possible if, for example, one restricts each user to contribute exactly a single item). We can lower bound the missing mass of A on W as
ES~A(W') [MM(W* SS)
Σ
PS (o Nx))
N
zEU, ((x)
Σ
N(2).
2N
xEU, MM
21

---

Published as a conference paper at ICLR 2026
Our next goal will be find the smallest rank r" such that N(r)) S b It suffices to solve the
inequality CN S b" for r. Doing so gives that r 2
CON
r*. Hence, for this W we have 6-
that
ESNA(W-) [MM(W*, (S]] 2
1
E
N(x)
2N
seU, WT W7.N(2)Sh
M
1
N
2N
M
Ω
Since 8 > 1, we can take M (and hence n) to be large enough so that
M'
CN
CN
Ω
Σ
Ω
dr
N
ps
N
Thus,
1
CN
ES-A(W')) [MM(W* SS)] = 9
rs dr
N
(r-)2--
C1/#N(1 1///// (b*) (b*)6--1)/a
C2/$N
(6-1)//
1 ln
1 e-
-5-1)
-1
(x-1)/8)
Ω
28
C1/8
(e-1)/e
1 e-
- (0-1)/0)
Ω
In
8-1 1
c.V
26
which completes the proof.
D.2 LOWER BOUNDS FOR TOP-k SELECTION
Proof. (of Corollary 4.4p Define b* = In (1+ + 1 like in Lemma D.1 Recall from Lemma
D.1 that for any dataset W and any item x U, W, such that N(x) s b", we have that
PS (xr $ S] 2
Consider any dataset W such that IU. W k and N( b" for all E [k]]
Then Ei_, No)
kbb.. But, we also have that (S~A(WW)) EEEEs Nx)) < kb*
Hence,
2
ES~A(W-AA A) MM .s]
kb* Ωt
k
2
2N
cN
completing the proof.
D.3 LOWER BOUNDS FOR K-HITTING SET.
Proof. (of Corollary 4.6) Define b* = In (1 + c'-1 as in Lemma D.1 Recall from Lemma D.1
that for any dataset W and any item x É U, W, such that N(x) S b", we have that
PS-A(WA)) (x $ $ 2 2
22

---

Published as a conference paper at ICLR 2026
This is due to our restriction that A(W, k) S U, W, Consider any dataset W consisting of & unique items and n = kb" users such that each item hits a disjoint set of b" users. Since the frequency of each of the Ic items is at most b* A can output each item with probability at most 1/2. Hence, in expectation, A outputs most k/2 distinct items, hitting most 2 users, while the optimal set of items includes all & items and hits all users.
ké"
E EXPERIMENT DETAILS
In this section, we provide details about the datasets used in Section Tableeprooiin statistics for the 6 datasets we consider. Reddit (Gopi et al. 2020) is a text-data dataset of posts from r/askreddit. For this dataset, each user corresponds to set of documents, and following prior methodology. take a user's 's item set to be the set of tokens used across all documents. Movie Reviews (Harper & Konstan 2015) is dataset containing movie reviews from the MovieLens website. Here, group movie reviews by user-id, and take a user's itemset to be the set of movies they reviewed. Amazon Games, Pantry, and Magazine (Ni et al. 2019)
review datasets for video games, prime pantry, and magazine subscriptions respectively. Like for Movie Reviews, we group rows by user-id and take user's item set the set of items they reviewed. Finally, Steam Games (Steam) 2025) is dataset of 200k user interactions (purchases/play) on the Steam PC Gaming Hub. As before, we group the rows by user-id and take a user's itemset to the be the set of games they purchased/played.
Dataset
No. Users
No. Items
No. Entries
Reddit
245103
631855
18272211
Movie Reviews
162541
59047
25000095
Amazon Games
1540618
71982
2489395
Steam Games
12393
5155
128804
Amazon Magazine
72098
2428
88318
Amazon Pantry 247659
10814
447399
Table Number of users, items, and entries (user-item pairs) for each dataset
E. RANK vs. FREQUENCY PLOTS
3.3 requires that W be (C, s) j)-Zipfian for >>> 1. Figures 4 and 5 present log-log plots of frequency vs. rank for the large and small datasets respectively. In all cases, observe that the real-world datasets we consider are (C, -iiiffnn for s > and sufficiently large C. Note that our definition of Zipfian dataset only requires the frequency vs. rank plot be upper bounded by decaying polynomial.
In order get meaningful upper bounds MM, Theorem
Lnpdin
Zp Laptis
Bed-dtt (slopem-1.21)
Data
Baa--tt line [slopem-1.57)
Data
10
Best-ft ft lime (1opam-2.25
Log 2wr.oooooo
Lack
Log10/Punk)
Lag100Rank
(a) Reddit
(b) Amazon Games
(c) Movie Reviews
Figure 4: Log-log plot of frequency vs. rank for large datasets
23

---

Published as a conference paper at ICLR 2026
<pt's Log-log Hot Steam Laree datasot
Ziph's Log rit Amazon Pagadme
Zish's Lat LogeLsg Put Amazon Hartry
Data
Data
Duta
Boa-dtt Ins (slopem-1.46)
Besiift line (slepu-11.5 55)
Bes--lt Ins (slrpem-1113
LOG Lomooggnnn
6.0
0.5
1.0
1.5
2.0
25
3.0
355
0.
0.5
1.0
1.5
2.0
255
3.0
35
0.0
0.5
1.0
15
2.0
2.5
3.0
35
48
Lagl0tfunk)
(a) Steam Games
(b) Amazon Magazine
(c) Amazon Pantry
Figure 5: Log-log plot of frequency vs. rank for small datasets
E.2
USER ITEM SET SIZE DISTRIBUTIONS
Figures 7 the Empirical CDF (ECDF) of user item set sizes for the large and small datasets respectively.
User bern Heddlt dctaset
Item Stree Arranon Carres delawe:
Conviattv Probattitt
0.
0.4
3.0
User Set
Sbe
San
(a) Reddit
(b) Amazon Games
(c) Movie Reviews
Figure 6: ECDFs of user item set sizes for large datasets.
ECDD of User Item Sal Stae for Sheam Games detenst
ECDF of foom Set Stees for demszon Pagazine debocet
ECEF User hem Set Stees Amaaton Pentry deracet
1.0
0.0)
5.8
0.6
0.6
0.4
0.4
200 520
100
150
Sue of User Itom Set
5:00 of Lsst Rom Set
User Itom
(a) Steam Games
(b) Amazon Magazine
(c) Amazon Pantry
Figure 7: ECDFs of user item sizes for small datasets.
F ADDITIONAL EXPERIMENTAL RESULTS
F.1
PRIVATE DOMAIN DISCOVERY
F.1.1 RESULTS FOR SMALL DATASETS
Figure plots the MM function of Ay for the small datasets. Again, find that the WGM achieves comparable performance to the policy mechanism while being significantly more compu- tationally efficient.
24

---

Published as a conference paper at ICLR 2026
1/5
X11
130
250
255
(a) Missing Mass
(b) Missing Mass
(c) Missing Mass
Figure 8: MM as a function Ag E {1,50, 100, 150, 200, 300} for the small datasets.
F.1.2
RESULTS FOR c = 0.10
Figures
and 10 plot the MM for the large and small datasets respectively when 0.1 and
8 10
3.0
X52
3.0
140
345
(a) Missing Mass
(b) Missing Mass
Missing Mass
Figure 9: MM as function of Ao E (0, 100, 150, 200, 300} for large datasets when 0.1 and
10
37.
X72
0.13
3.5
3.30
1.4
(a) Missing Mass
(b) Missing Mass
Missing Mass
Figure 10: MM as a function of Ag E {1, 50, 100, 150, 200, 300} for small datasets when e = 0.1 and 10-5
F.2 TOP-k SELECTION
The top-k E loss defined as
(W: minf (1
Σ
IN N(S)
N
(1)
where S is any ordered sequence of items. Unlike the top-k MM, the top-k & loss cares about the order of items output, and hence is more stringent measure of utility.
Figure 11 plots the top-k é MM for c = 1.0, 5 = 10 and Ao = 100. Similar to Figure 2 we observe that our method (purple) achieves significantly less Top-k e loss compared to all baselines.
25

---

Published as a conference paper at ICLR 2026
100
189
175
100
125
17%
(a) Steam Games
(h) Amazon Magazine
(c) Amazon Pantry
Figure 11: Top-k & loss vs. with 1.0, 8 = 10 5 and Ag 100.
Steam Games
Topio Np--Mbaangg MON
40000
.0200
0.4
0.0
(a) Top-k MM
(b) top-k &
40303
0.4
0.3
0.2
20200
0.1
125
200
1.50
125
175
(c) Top-k
(d) top-k
Fartrr
122000
102030
62000
0.30
42000
22000
50
300
150
175
200
50
75
100
150
135
200
(e) Top-k MM
(f) top-k
Figure 12: Top-k MM and Top-k é vs. is for l E (5, 10, 20, 50, 100, 2003, with = -0.1, 8 = 10-5
and Ag 100.
Figure 12 plots the top-k MM and top-k loss for the small datasets when 0.1 and 8 10 5 Like the case when é 1.0, our method (purple) continues to outperform the baselines across all values.
26

---

Published as a conference paper at ICLR 2026
F.3 k-HITTING SET
Figure
13 plots the Number of missed users for the small datasets when 0.1, ā - 10-5, and
An 100. We observe that our method (blue) performs comparably and sometimes outperforms the case where the domain Ug W is public.
1400
20943
(4000)
25
375
125
350
(a) Steam Games
(b) Amazon Magazine
(c) Amazon Pantry
Figure 13: Number of missed users vs. h for & E (5, 10, 20, 50, 100, 200} with c = 0.1, = 10-5 and Ao 100.
27


Reviews:
[{"review_id": "dmrcp2Z9hj", "reviewer": "Reviewer_XPcs", "summary": "This paper studies several problems in differentially private domain discovery, such as missing mass, top-k selection, and k-hitting set. The authors show that the weighted Gaussian mechanism is useful for these problems. The authors also prove utility lower bounds, showing the algorithm enjoys some level of optimality. The algorithm is tested on several real-world datasets.", "questions": "1. If a good bound on $\\max_|W_i|$ or the $s$ parameter of the Zipf distribution is not known a priori, is there a good way to privately find a good $\\Delta_0$ for the WGM mechanism?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed algorithms based on the weighted Gaussian mechanism are generally applicable to many problems for domain discovery, including finding a set of elements with small missing mass, top-k selection,and k-hitting set.\n2. The lower bound results demonstrate that the algorithms are optimal to some extent. For the missing mass problem, the algorithm achieves near-optimal error in terms of privacy parameter $\\epsilon$ and total number of items $N$. For top-k selection and k-hitting set, the lower bound is at least $k/\\epsilon$, while the upper bounds have an additional $k^{3/2}/\\epsilon$ term, \n3. Experiments are performed on many real-world datasets, and the performance is comparable or better than previous baseline algorithms.", "weaknesses": "1. It seems that the performance of the algorithm depends on the choice of user contribution $\\Delta_0$, which ideally has to be close to $\\max_|W_i|$. This requires prior knowledge of the maximum elements, or at least some estimate of the parameter of the Zipf distribution of the underlying dataset.\n2. There is a mismatch in the upper and lower bounds for top-k selection and k-hitting set.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nkMUuPkatB", "reviewer": "Reviewer_FKQB", "summary": "This paper studies several questions about user-level differentially private (DP) algorithms on an unknown domain. The dataset consists of users, each with a subset $W_i$ of items from an unknown (or enormous) universe $\\mathcal{X}$ and the goal is to output a set $S$ with large overlap with the union $\\bigcup_i W_i$ while maintaining DP with respect to adding/removing any given subset $W_i$. For instance, in the set union problem, the goal is to output $S$ which is a subset of the union with as large cardinality as possible. Unfortunately, for this problem, there are no known absolute utility bounds: prior works can compare algorithms but have no guarantees on the size of the output. This paper investigates a relaxed objective which is missing mass. Consider the empirical distribution over the universe given by the input dataset (the multiset union of all $W_i$) and call this vector $f$. The missing mass is defined as the $\\ell_1$ norm of $ f_{\\mathcal{X} \\setminus S}$, the fraction of elements not contained in $S$. The authors note that $\\ell_0$ norm is the normal private set union objective and the $\\ell_p$ missing mass for $p > 1$ may also be of interest.\n\nThe first main result is about set union with $\\ell_1$ missing mass. The authors show that the standard weighted Gaussian mechanism (WGM) from prior work achieves a missing mass guarantee if the item frequencies $f$ follow a power law (Zipfian distribution). With a Zipfian exponent $s$, a simplified version of the bound is $\\tilde{O}\\left(\\left(\\frac{\\max_i |W_i|}{\\epsilon N \\sqrt{\\Delta_0}}\\right)^{(s-1)/s}\\right)$ where $\\Delta_0$ is the standard \"contribution cap\": in a preprocessing step, each $W_i$ is subsampled to keep only $\\Delta_0$ elements.\nFurthermore, the authors show that the $\\left(\\frac{1}{\\epsilon N}\\right)^{(s-1)/s}$ dependence is necessary for any private algorithm.\nThe authors show a simpler result on the $\\ell_\\infty$ missing mass without any Zipfian assumptions. This amounts to showing that there is a frequency threshold, above which, any item will be returned by WGM.\n\nThe authors show how to use the $\\ell_\\infty$ analysis to get utility bounds for top-$k$ selection and $k$-hitting set on unknown (very large) domains by first applying set union and then running a known domain algorithm. They use the $\\ell_\\infty$ missing mass bound from set union to get missing mass type utility bounds for top-$k$ and approximation algorithm bounds for $k$-hitting set.", "questions": "- Consider the statement \"Note that in Theorem 3.3 the missing mass decays as the total number of items N grows. Moreover, as C decreases or s increases, the upper bound on missing mass decreases.\" Should the second sentence be conditional on $N$ being sufficiently large compared to $T$ and $\\sigma$ (which should be the case for reasonable privacy parameter settings).\n\n- An interesting direction would be to show that WGM is close to optimal on Zipfian data for all $\\ell_p$ missing mass for $p > 1$. Is there any chance of showing something like this? Similarly, plotting missing mass as $p$ increases would be interesting, especially if the plots were significantly different for different algorithms.\n\n- Are both changes of (1) considering missing mass and (2) Zipfian data necessary for giving an absolute utility guarantee? Is there a specific technical challenge to analyzing the cardinality of the set output by WGM on Zipfian data?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Achieving absolute utility bounds for private set union has been a challenge in the existing literature. By relaxing the objective to missing mass as opposed to just the cardinality of $S$ as well as introducing an assumption on the frequency distribution, the authors obtain absolute bounds on the utility of the standard WGM algorithm.\n\n- The upper and lower bounds on Zipfian data show that different algorithmic ideas cannot significantly improve upon the basic WGM algorithm in this setting (at least in terms of missing mass).\n\n- The authors show how these bounds can be translated to problems where set union can be used as a subroutine for the top-$k$ and $k$-hitting set problems.\n\n- One interesting facet of the theoretical analysis is that the preprocessing step, where sets $W_i$ are subsampled to have a maximum cardinality cap, is an important factor in the bounds. In prior studies of private set union, the details of step are not thoroughly investigated.", "weaknesses": "An asymptotic bound on the missing mass of a mechanism in a specific setting would be more useful if it had implications in practice either by predicting practical performance in parameter settings or by allowing different algorithms to be compared theoretically.\n\n- The experimental results could be significantly more in depth: this would highlight several aspects of the theoretical work. Some concrete suggestions:\n  - It would be instructive to compare the theoretical error bound against empirical performance on synthetic Zipfian data.\n  - It would be useful to plot the frequency distribution on the real datasets to see if they follow a power law.\n  - Reporting the size distribution of $|W_i|$ would be interesting to compare the setting of $\\Delta_0$ to those statistics. The theoretical result suggests that $\\Delta_0$ should be set to $\\max |W_i|$ though increasing $\\Delta_0$ worsens performance for the Amazon games dataset and the small datasets. Is this because $\\Delta_0$ has exceeded the size of any $W_i$ or for another reason?\n- The statement that the gap between WGM and the policy baselines is smaller in the missing mass case compared to the $\\ell_0$ cardinality case is misleading. While the gap is 5 percentage points (MM is measured as a percentage), WGM performs up to 50% worse than the baselines in some instances when measured as a ratio. This is the apples-to-apples comparison to make when commenting that \"for cardinality... sequential methods often output $\\approx 2X$ more items [than WGM].\"\n- Comparison to more baseline algorithms would also be interesting. In the theoretical results, it is very reasonable to only analyze WGM as it is a well-studied algorithm and other candidate algorithms may be very difficult to analyze. On the other hand, if an important empirical takeaway is that \"WGM obtains MM within 5% of that of the policy mechanisms, in spite of their significantly more intensive computation,\" it would be useful to compare to other methods of Swanberg et al. and Chen et al. which offer better cardinality results while still using a similar amount of computation to WGM.\n- Missing mass analysis of any other algorithm, for example the weighted Laplace mechanism to start, would be interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7eR6U1NvKM", "reviewer": "Reviewer_sdpD", "summary": "The paper studies the problem of discovering items from an unknown domain in a *differentially private* manner, under a user-level privacy guarantee.  \n\nThe main technical tool is the Weighted Gaussian Mechanism (WGM) (Gopi et al., 2020), which operates as follows:  \n1. It builds a histogram over items held by all clients, normalizing each user’s contribution so that its $\\ell_2$-norm is bounded by $1$.  \n2. It adds Gaussian noise to the non-zero entries of the histogram.  \n3. It applies a thresholding step to remove low-frequency items.  \n\nThe paper analyzes the performance of WGM under two error metrics—the $\\ell_1$ and $\\ell_\\infty$ norms of the *missing mass*—where the analysis for the $\\ell_1$ case assumes a Zipfian distribution over the domain.  \n\nFinally, the authors extend their approach to the top-$k$ discovery and $k$-hitting set problems, and provide empirical evaluations demonstrating the effectiveness of their method.", "questions": "1. It would be helpful to clarify whether the error metrics defined in **Definition 2.2** are newly proposed in this paper or have appeared in prior work. \n   If they are not novel, please include appropriate citations to previous literature.\n\n2. The asymptotic upper and lower bounds for differentially private top-$k$ selection are already well studied. For instance:  \n   * Bafna, Mitali, and Jonathan Ullman. *“The Price of Selection in Differential Privacy.”* In *Conference on Learning Theory*, pp. 151–168. PMLR, 2017.  \n   * Steinke, Thomas, and Jonathan Ullman. *“Tight Lower Bounds for Differentially Private Selection.”* In *FOCS 2017*, pp. 552–563. IEEE, 2017.  \n\n   It is known that the cumulative gap of $\\tilde{O}(k^{3/2})$ between the true and selected top-$k$ scores is tight. \n   Therefore, it may not be necessary to  \n   * re-prove **Lemma 4.2**, or  \n   * include **Corollary 4.4**, whose lower bound is not tight.  \n\n3. The citation for **Lemma 4.1** appears to be inaccurate.\n   The equivalence between adding Gumbel noise and iteratively applying the exponential mechanism (without replacement) was shown as early as Durfee & Rogers, NeurIPS 2019.\n   Moreover, their updated arXiv version (see footnote on p.11 of [arXiv:1905.4273](https://arxiv.org/pdf/1905.4273)) acknowledges that this technique was proposed even earlier.\n\n4. In **Theorem 3.2**, it would be clearer to express $T$ in $\\Theta$-notation rather than $\\tilde{\\Theta}$-notation, since  \n   (1) $\\sigma$ is already expressed in $\\Theta$-notation, and  \n   (2) it would make the asymptotic behavior of $T$ easier to interpret.\n\n5. The text in **Figures 1–3** is too small to read when printed. Please consider increasing the font size for readability.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The problem studied and the proposed error metrics are interesting.  \n\nIt is also good to see a systematic and thorough investigation of this topic, which helps clarify the behavior of differentially private item discovery mechanisms under various conditions.", "weaknesses": "1. Some key related works are missing and should be discussed.\n\n2. The motivation and interpretation of the experimental design are less clear:\n   * It is unclear whether the datasets used in the experiments are justified to follow the Zipfian distribution assumed in the analysis—particularly for parameters $s > 1$ (and not even $s = 1$).\n  \n   * It would be helpful to clarify whether the key theoretical results, such as **Theorem 3.3** and **Corollary 3.4**, are empirically validated in the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MNJzOO8TN3", "reviewer": "Reviewer_Ed3k", "summary": "This paper studies differentially private domain discovery, where each user holds a subset of items from an unknown shared domain, and the goal is to output an informative subset while preserving privacy. The authors revisit the Weighted Gaussian Mechanism (WGM) and show that, when utility is measured in terms of missing mass (the fraction of unrecovered probability mass rather than set cardinality), WGM achieves strong and in some cases near-optimal guarantees.\n\nKey contributions include:\n\n1. Reformulating the DP set union problem in terms of mass instead of cardinality, and proving that WGM achieves near-optimal ℓ1 missing mass on Zipfian data, and a distribution-free  ℓ∞ missing mass bound.\n2. Extending the analysis to unknown-domain variants of top-k and k-hitting set, showing new utility guarantees by using WGM as a preprocessing step.\n3. Conducting experiments on six real-world datasets, demonstrating that WGM-based methods outperform existing baselines in accuracy and scalability.", "questions": "1.  How does WGM perform on non-Zipfian or adversarial data?\n2.  How does the mechanism perform under correlated user data?\n3.  Does adding Gaussian noise per element remain efficient when domain size is very large?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.  **Originality**: Reformulating domain discovery in terms of missing mass provides a novel and tractable utility metric.\n2.  **Quality**: The analysis is rigorous, with clear theorems and well-motivated assumptions. The near-optimal ℓ1 and distribution-free ℓ∞ guarantees add strong theoretical credibility.\n3.  **Clarity**: Well-written, clear notation, and logically structured.\n4.  **Significance**: The results contribute a unified framework for private domain discovery, potentially influencing future research in private data analytics and unknown-domain learning.", "weaknesses": "1.  The Zipfian assumption may restrict generality; robustness under other distributions is not fully discussed.\n2.  Section 6 outlines directions but lacks concrete proposals (e.g., how adaptive subsampling might integrate into WGM).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)