Private Set Union with Multiple Contributions
Authors: Travis Dick
Haim Kaplan
Alex Kulesza
Uri Stemmer
Ziteng Sun
Ananda Theertha Suresh
Venue: NeurIPS 2025 spotlight ()
Keywords: Differential Privacy
Set Union
Partition Selection
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We study the the limits of differentially private set union (or partition selection) when each user can contribute multiple items.

Abstract: In the private set union problem each user owns a bag of at most $k$ items (from some large universe of items), and we are interested in computing the union of the items in the bags of all of the users. This is trivial without privacy, but a differentially private algorithm must be careful about reporting items contained in only a small number of bags. We consider differentially private algorithms that always report a subset of the union, and define the utility of an algorithm to be the expected size of the subset that it reports. 

Because the achievable utility varies significantly with the dataset, we introduce the *utility ratio*, which normalizes utility by a dataset-specific upper bound and characterizes a mechanism by its lowest normalized utility across all datasets. We then develop algorithms with guaranteed utility ratios and complement them with bounds on the best possible utility ratio. Prior work has shown that a single algorithm can be simultaneously optimal for all datasets when $k=1$, but we show that instance-optimal algorithms do not exist when $k>1$, and characterize how performance degrades as $k$ grows. At the same time, we design a private algorithm that achieves the maximum possible utility, regardless of $k$, when the item histogram matches a prior prediction (for instance, from a previous data release) and degrades gracefully with the $L_\infty$ distance between the prediction and the actual histogram when the prediction is imperfect.

Private Set Union with Multiple Contributions
Travis Dick Google Research
Haim Kaplan Tel Aviv University and Google Research
Alex Kulesza Google Research
Uri Stemmer Tel Aviv University and Google Research
Ziteng Sun Google Research
Ananda Theertha Suresh
Google Research
Abstract
In the private set union problem each owns bag of at most k items (from some large universe of items), and we are interested in computing the union of the items in the bags of all of the users. This is trivial without privacy, but differentially private algorithm must be careful about reporting items contained in only a small number of bags. We consider differentially private algorithms that always report a subset of the union, and define the utility of an algorithm to the expected size the subset that it reports.
Because the achievable utility varies significantly with the dataset, we introduce the utility ratio, which normalizes utility by dataset-specifet upper bound and characterizes a mechanism by its lowest normalized utility across all datasets. We then develop algorithms with guaranteed utility ratios and complement them with bounds on the best possible utility ratio. Prior work has shown that single but we
algorithm can be simultaneously optimal for all datasets when k show that instance-opting algorithms do not exist when k > 1. and characterize how performance degrades
grows. At the same time, we design a private algorithm that achieves the maximum possible utility, regardless of k, when the item histogram matches a prior prediction (for instance, from a previous data release) and degrades gracefully with the lo distance between the prediction and the actual histogram when the prediction imperfect.
Introduction
Consider a dataset where each entry is set of items donated by different user. The set union problem is to output the union of all of the sets. This simple problem arises in many practical scenarios, and when the items have the potential to be sensitive we may want privacy guarantees to ensure that the result does not reveal personal data. For example, private set union can be used for discovering n-grams
corpus [Gopi al., 2020), releasing keys SQL. queries [Wilson et al. 2020). and in general for determining the domain of private aggregate statistics Amin et al.) 2022]
Since the number of conceivable items (e.g., all possible n-grams) can be very large, necessary for the algorithm to restrict its output to subset of the true union [Gopi et al. 2020 al. 2022
often
Destontaines et al. 2022 Motivated by this, Cohen al. (22TT) Destontaines proposed an optimal (E, 8) (., differentialll private algorithm when each user contributes exactly one
item. However, in many realistic settings users can contribute multiple items. This prompts a natural question: can we design an optimal ( diffferenntlll private algorithm when each user contributes up k items?
We begin with the definition of differential privacy.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

1.0
1.0
=
0.9
0.8
Utility Ratio
0.7
0.6
1/2
0.5
0.2
0.4
1/3
0.0
0.3
1/4
20
80
100
8
Figure I: The maximum probability #(c; e, of reporting an item with count when = 0.1 and 5 0.0001.
Figure 2: Optimal utility ratios over datasets with three users for å = 0.01 and various settings of and For intermediate values of the ratio can be nearly as low as 1/k.
Definition 1.1 (Differential privacy (Dwork al. 2006) A randomized algorithm M satisfies (e, diifferrrent privacy for any two neighboring datasets D, D' and for any subset of the output space S, it holds that
(D( E S e
E +
Two datasets D and D' are neighboring if and only if dham (D, D') | DD DD- DI =1 =1
We can now provide a formal definition of the differentially private union problem.
Definition 1.2 (Differentially private set union). Fix universe X of items and contribution bound Let be a dataset consisting of bags B, C. |B,| S for i [n]. A differentially private set union algorithm M has output subset of Ui. and its goal is output subset which is as large as possible. We denote by UNION& 8) the set of all (s, (E,8)-dife) -)-ffferrenllllllyy private set union algorithms.
We define the utility of algorithm M E UN, on dataset D to be the expected cardinality of its output set, (D) In the best-case scenario, the utility is equal to the cardinality of the full union, i.e., E (
Usg[n] B,J. However, the best-case utility is typically not achievable. For example, consider a dataset in which each item contained the bag a single user: any algorithm in UNION& (e, 6) cannot report more than 5 fraction of the items in expectation, since for each item there is neighboring dataset which does not exist and hence reported with probability zero. In general, the achievable fraction of the best-case utility is highly dependent on the item frequencies, making it difficult to compare algorithms across datascts when the goal is a naive maximization of ([IM(D)]
The work of Cohen et 2022]. Destontaines et al. 2022 suggests an appropriate adjustment. Let the number of times item appears in dataset D be denoted by c(z, D) (or simply c(æ) when the underlying dataset clear). They showed that the utility of any algorithm M UNIONg(E, satisfies
B[IM(D)] I(D,,,0) = Σ =(((())ee,))
DEN
where æ is sigmoid- -ike function given by
c -1
c(x) $ ce
e-1
T (c(x);e,0)= = (1 (c(c)-cr)c) (1
6.) x + (c(x) (c())
if c < c(x) < ch
otherwise
and cj and C₁ are constants given by
In ( e + 26 -1
In 1+ 1- (1 x(cc,s,0)) (1)
C = 1
ct +
(e 1)6

---

In the special case 0, we have T(c(z);0,)) min(c(2)6, 1). See Figure I for an illustration of π.
Cohen et al. 2021 Desfontaines et al. 2022 showed that the upper bound of (T, e, 6) is achiev- able, simul sameoual for all datasets, when k 1. We will later that this is not possible when k > 1 (except under certain extreme values of ε and ö). However, II(D, 6) is achievable, re- gardless of k, for any single dataset (see Theorem 1.3 below). This is not trivial since algorithms in (E 6) can only return items appearing in their input dataset, which rules out constant algorithms that ignore their input and return fixed result. (Such algorithms are differentially private and, in other settings, can be used to trivially obtain optimality for any single dataset.)
The achievability of II(D,, E. 8) when A: motivates its We introduce the following target measure, which we use to establish bounds on the performance of algorithms in UNION (e,
normalizer for the utility (D)]]
Definition 1.3 (Utility ratio). The utility ratio of an algorithm M (N,
[M[[
us (M) == min
DED, eI,),
where Dr is the collection of all nonempty datasets where each user contributes at most items.
That un (a(M (M) is generally less than one when k is easily demonstrated numerically using linear program that finds the optimal mechanism for a finite collection datasets. Figure shows that the resulting behavior is complex, even considering only very small datasets, and the worst-case utility ratio appears to be close to 1/k. Our aim is to characterize this behavior theoretically.
1.1 Main results
Theorem 1.1 (Informal impossibility results). Let 6 = (1(k2²)), where the subscript denotes an Then for any algorithm M in UNIONN(E,,)) have
unstated dependence
ug ug(MM) = 0 ( (1(1(11 In
(Theorem 2.2
In addition, even if D is restricted to "easy" datasets where II(D, = ?((x'), we still have
(x(M) Ön K1/4
(Theorem 2.3
where Ô hides logarithmic terms.
Theorem [.] shows that instance-optimal algorithms are not generally possible when k > 1, with the bounds roughly matching the minimums in Figure However, we still construct algorithms with meaningful utility guarantees.
Theorem 1.2 (Informal achievability results). There exists an algorithm M in UNION& (e, d) such that for every dataset D,
B|M((D)I = IT(D)'','),
where e' ([(E)) and 8' = 52 ) (see Theorem 3.2 In addition, when 0 or ca (holding constant), there exists an M such that uy (M) = I (see Lemmas and 3.6
The results above raise an important question: can we ever do better than utility ratio of (11/k)? Theorem 1.3 shows that, if we can predict the histogram of items in the dataset in advance, then there exists private set union algorithm achieving the optimal utility regardless of k.
Theorem 1.3 (Informal achievability with predictions). For any nonempty histogram over X' and privacy parameters E and 8, there exists an algorithm M E UNION&(E, 6) such that
E [[[[] = I(D,e,6)
for any D matching the predicted histogram, regardless of the contribution bound k (Theorem 4.1
3

---

The private algorithm M satisfying Theorem 1.3 also performs well on datasets that are "similar" to the target dataset D. making an appropriate algorithm for settings where some public prediction regarding the union is available (see Section 4 for more details).
A note about k: In some settings we may not have any priori contribution bound k; in which case we need to choose one and enforce it. This introduces a natural tradeoff: larger k retain more data, but reduce the utility ratio (as indicated by our results). Similar contribution-
tradcoff's have been explored in prior work [Amin et al. 2019 [apsto et al., 20200 Amin el al. 2022 Although it is not our main focus here, in Appendix A we show one way that ie can be selected privately when no contribution bound is known in advance.
1.2 Related work
The differentially private set union problem was implicitly introduced by Korolova et al. [2009] in the early days of differential privacy. Subsequent work by Gopi et al. [020)] Carvalho al.
[2022] improved utility by processing users sequentially and choosing contributions in a clever way, minimizing waste on heavy items while maintaining low sensitivity. [Swanberg et al. [2023 Chen et al. [0244] proposed multi-round mechanisms with careful budget-splitting across the rounds; this allowed them to process users in parallel while retaining good utility. However, none of these works provide worst case utility guarantces, and they primarily compare different approaches empirically.
The optimal reporting probabilities when k = were introduced by Desfontaines et al. [2022] Cohen ct al, [202T]. (Knop and Steinke, 2023] studied the related problem of estimating the size of the union rather than the union itself. More distantly related work on privately finding the l most frequent
items in a database was published by |Bhaskar et al. [2010]. Durfee and Rogers) 2019 McKenna and
Sheldon 20200] Gillenwater et al. [0022]
2 Impossibility results
In this section we derive upper bounds on the utility ratio of any (E, 8) -iifferrenylll private set union mechanism when applied to datasets with contribution bound k. Our upper bounds all diminish with k showing that for datasets with large contribution bounds, no differentially private mechanisms can meaningfully compete with the optimal utility simultaneously for all datasets. All omitted proofs are given in Appendix B
Our first result shows that there exist regimes for and ô such that every set union mechanism has utility ratio ((1/k). In particular, as the contribution bound A grows, no mechanism is competitive with II( on every dataset D, despite the fact that Theorem establishes mechanism matching IIDD for any single D.
Theorem 2.1 (Warm-up). Lei k 2 2, s 2 0, 5 E and let M be any (e, ddiffferrrt private set union mechanism. Then there exists dataset D with contribution bound such that
E [|IM(D))]]
S h e k
M(D,e,,)
E M(D)) In particular, for = 22 llk)) and 8 I 2 we have I.D.a.))
Proof sketch. Let the item universe X contain items, and let D be the dataset with a single user that contributes every item, i.e., B3 = X. For each item x E X. construct a dataset D, by adding a second user to D that contributes only item x, i.e., B₂ {z). The privacy parameters and ê are chosen to ensure that (2) is much larger than T(1), so a mechanism M is only competitive on D, if it outputs item E with probability close to (2). However, since D, neighbors dataset containing only item x (after removing user 1), the total probability mass of outputting any set containing an item other than x must be at most 5. Thus, Pr(z E (D.)) & (D,) (=)) + 6. And, since (a)) 26. So, for M to compete
M is DP, we further have Pr(æ E M(D))) S E Pr(M(D) with I(D..,, we require that M outputs the singleton set (r} with non-trivial probability when run on the single-user dataset D. On the other hand, D neighbors the empty dataset, so the total probability mass it assigns to non-empty outputs is at most 6, implying that there exists an item y such that PD( = (v}) 8/k. Therefore, Pr(y e MD)))) S e 8/k + 28. By contrast, in the specified

---

parameter regime we have (2) = de + 6. When is sufficiently large that the ef 8 terms dominates, the mechanism M is only able to output y with probability approximately 7(2)/k.
Intuitively, the only way for to compete with (12))) )2) is for M to have an output distribution on the single-user dataset D that prioritizes 5, and it is not possible for single mechanism M to do this simultancously for all x E X.
weakness of Theorem 2.1 is that the utility ratio bound of 2/k holds only when 2 kt For large k. this is an extremely low privacy regime. The next result extends the argument of Theorem 2.1 and establishes a bound of O on the utility ratio of any mechanism that holds in almost any privacy regime. In particular, it holds for any & as long as ó decays like 1/k2.
Theorem 2.2. Let k 2 4, E 2 0, 8 x2. 657z
e''l and M be any (E. 6) diffeerenntlll private set e*4I
union mechanism. Then there exists a dataset D with contribution bound k such that
[[)
II(D,e,8) - k - (1+
12
1
log
Proof sketch. The proof follows a similar argument to the one for Theorem 2.1 but instead of adding single user to D, we add ((I(kk)) users, each contributing constant fraction of the previous user's items. The key advantage of this iterative construction is that the suboptimality incurred by the mechanism is determined by its inability to output items with sufficiently large probability across range of item counts from I to In(k). In particular, rather than requiring s to be (In(k)) to ensure that T (2) is much larger than x x(1), here we allow for constant and drive suboptimality from the ratio between x (In(k)) and (1).
The datasets that witness the utility ratio upper bound in Theorem 2.2 have the property that 1I(D, e, 8)/l Use[n) B, tends to zero as the contribution bound grows. In other words, even the optimal mechanisms for datasets D established by Theorem 1.3 are only able to return vanishing fraction of the items contained in D as the contribution bound & grows. Our final impossibility result shows that even class of datasets where II(D)= 2 Liggn]] l/2, the utility ratio achievable by any mechanism diminishes with k; albeit at a slower rate than for the previous results.
Theorem 2.3. Let 2 2, n > 2- Cb (so that π (n/2)) 1 & 2 1/n, and ō < 1/(40e= n /222)))))). Lei M be any (e, diifferreetl private set union mechanism. Then there exists dataset D with contribution bound l such that
EE M (D)II = =0((" log(nk) ((()loog(n)) 1/1 II(),,
k
Proof sketch. The key idea is reduction showing that a private set union mechanism M can be used to construct a mechanism for estimating matrix marginals whose performance is related to the utility ratio ug (M). Combined with an impossibility result for privately estimating matrix marginals based on robust fingerprinting codes (modified from the work of Steinke and Ullman 2015)), this yields bound on the utility ratio.
The marginal problem we reduce from is the following: given a binary matrix C E (0, 1 1aak the mechanism aims to output a vector in {0, 1 such that whenever a column of is entirely 0 or 1, the corresponding component of the output vector is also equal to 0 or 1 (respectively). On mixed columns of C, the mechanism can output either or 1. This an easier problem than computing the column marginals of C' (i.e., the fraction of is per column), since the mechanism is only required to identify "pure" columns. We are interested in mechanisms that are at most (3, 7 -inaccuureeee which requires that with probability least y their output correct all but at most 3k columns. (Steinke and Ullman (015)) upper bound B for differentially private mechanisms.
The reduction works as follows: view row of the matrix C' as the indicator vector for user u,'s bag of items from a universe of size k. Given a mechanism M for private set union, we obtain a set Ù approximating the union of the contributed items. We then output the vector nn E {0, 1 where m, = 1 if j E Ú and my- ~ Bernoulli(1/3) if j & Ú. Because M E UNION 6), every index j E Ó must be column of C' that contains at least one 1, so we never make mistakes on those columns. And for each pure column & Ú. we have 1/2 chance of correctly guessing whether the
5

---

column was all Os or all 1s. It follows that the expected number of mistakes made by the reduction mechanism most (k: u₁ (M) II(D))/2, where the union instance encoded by the rows of C. To finish the proof, we construct C to ensure that IT(D) 2 k/2, which ensures the expected fraction of marginal mistakes is bounded in terms of ug MM) Then we convert this high probability bound that contradicts the impossibility result for the marginal problem when uy (M) is too large.
3 Algorithms with utility guarantees
3.1 A simple budget splitting algorithm
straightforward approach when k > 1 is divide the budget by and apply the optimal A: = algo- rithm, including each item x E X' in the output independently with probability x (c(x, e/k 5/k). Clearly the utility of this mechanism is IT(D, e /k, 6/k). The following lemma argues that it is private. The proof is straightforward and included for completeness in Appendix C
Lemma 3.1. Let Mpnn(D: 6, k) be the mechanism that works as follows: for each item E X, include x in the oulput with probability r(c(æ, D);e/ e e/k, 8/k). Then Mapti is a (e, (di)--iifrrenntillly private union mechanism when users contribute most l items.
3.2 Bicriteria Approximation
The simple budget splitting algorithm achieves the II(D, E, 8) bound of Theorem 1.3 for every dataset D but with privacy parameters smaller by a factor of k than the target parameters. In the following theorem we compete with this bound for larger value of e, smaller than the "real" & by only factor of (6). This gain comes with multiplicative loss of 1/k over the &T,,,, bound.
Theorem 3.2. Let e, 8 < 1 be small enough constants. There exists an (e, 6D-DP algorithm whose expected number of identified items is
II
D2O (D.0
In(1/5) In(1/6)e= ))
2
k
We refer this result as "bicriteria" because our (e, 8D- algorithm incurs multiplicative loss of when compared not with the optimal reporting probabilities for parameters (s, but rather with those for the relaxed parameters
[m[1/6]
Im(1/5je
Our bicriteria algorithm, called Bicrit, is given below. We present an alternative construction of bicriteria algorithm in Appendix C.I
Algorithm Bicrit
Notation: Let & denote the contribution bound, let X' be domain of items, and let Ax, {B C X' |B| S k} denote the set of all possible bags of size at most ie from X.
Input:
Dataset D (Ax,))* containing n bags, privacy parameters 0.
1. Denote 4mm(2/8) and Blog(2/8je
2. For each x E X:
(a) Let b + Bernoulli (1)
(b) by = then report x with probability m(c()):,,5)
Note that Algorithm Bicrit does not need explicitly traverse all we can skip items to which no user contributes since r O.
The next lemma captures the privacy guarantee of Algorithm Bicrit. Lemma 3.3. Algorithm Bicrit is (E.6)-DP.
Proof. Fix two neighboring datasets D and D D U (B) for = (x1, .2,,.., .2) where < k. Let é Hz E B b, 1} be the random variable denoting the number of elements from B

---

that are sampled in Step 2a Let E' denote the event that 6= (2/66/), and its complement.
By the Chernoff bound we have Pr E S 6/2. Now, by composition (and by choice of é and in Step for any outcome event we have that
Pr(Bicrit(D") E F] = Pr[E] " +r PrE] Pr [Birri(DD)) E FI
s Pr(FF] (ro.. e F[F] + lnello-1)E8) + 8
s PPrEE] é Pr F + 8
S PreBiccccit()) =
The utility analysis of the bicriteria algorithm is straightforward:
Lemma 3.4. The expected number of identified items in Algorithm Bicrit tirttt is
E _ 0 (D.0 (m(1/8))
[I((1/8e=²) (1)((())))))
8
))
Proof. For any dataset D we have
E[]iicii(DD]]=
Σ T((());E,))
1
D, 8)
xEX
(I(D k
II
E
8
(1/4/((/)) 8lm(2/0)
3.3 Optimal Mechanisms in Extreme Privacy Regimes
Finally, we describe some mechanisms that behave optimally when the privacy parameter & is extremely large small.
Small regime. When e = the n function takes a particularly simple form: << 0, 8) min 1)- The following lemma gives mechanism M, that matches these output probabilities long as < 1/n, where n the number of users. Its proof straightforward and omitted.
Lemma 3.5. Let n be the number of users and assume that L/n. Let Mo(D;) 8) be mechanism that with probability nð picks user uniformly at random and outputs the set of items in B, and with probability nō outputs the empty set. Then Mg (0, 8) differentially private, and it outputs each item with probability c(z, D) 8 (c((2, 0, 8).
Large regime. We describe a mechanism that achieves the optimal utility II(D, s, 8) as co. The mechanism composes the budget splitting mechanism of Section 3.J with a simple mechanism Man that outputs the full union with probability 8 and otherwise outputs the empty set. Importantly, Mall outputs items that appear exactly once with the maximum possible probability o(; Lemma C.7 in Appendix C.2 shows that Man is a (0, -)-differentially private.
The intuition underlying the combination of Mau and Mapli is follows. For any dataset D. Mspli outputs each item with probability π (c((r, e/ 5/k) which is smaller than (c((r, D); 8). However, for all items that appear least twice, both probabilities converge to 1 in the limit as E + oc. The only catch is that Mspli outputs items appearing exactly once with probability 8/k instead (regardless of e). To fix this, we compose Mai and Mapli spending most of our budget on Man to get the maximum output probabilities for items that appear once, and relying on the fact that for any nonzero and count 2 2, we have lim x (c; 8, 5) 1. The final mechanism and its properties are summarized in the following lemma, which prove in Appendix C.2
7

---

Lemma 3.6. Let Munge (De,,,,,, k)) be the following mechanism: let 8' = 5- 33-mmn(6, 1/E) and output the union of Da 8') and (D: union mechanism. Furthermore, for any contribution bound k. dataset D with contributions bounded by and privacy parameter 6, we have that
8' k) Then Murge is an (E, 6) (.ed))))ffenntaall private set
I8 Miorge (D;E, 6,11 1. II(D;e,))
lim +00
4 Leveraging prediction
Finally, in this section, we study whether predicted information about the underlying dataset D, e.g.. based historical runs, improve the utility for private set union algorithms. In particular, consider the case where a predicted histogram for the item counts is available. Our goal is to perform well datasets whose histogram is close H.
The requirement in Definition 1.2 that the algorithm must output a subset of the input dataset excludes the trivially successful algorithm that always outputs the union {x (xx) > 0). However, somewhat surprisingly, we show that the predicted histogram set union algorithm MH that achieves the best possible expected utility II(D,,, E, 8). regardless of the
is correct, it is possible to design a private
contribution bound k. For any dataset D, let HD be its histogram where Va. H (2) = c(D, x). Note that the optimal utility bound IT(D, e, only depends HD. We abuse notation and define
I1( = Σ x (H()))=)))
TEA
and we have VD, (D,,,))) IT(HD,,
Moreover, for any d and histogram H, define
__, Σ T(H(z)
d: -
to be the IT bound when all item counts have been reduced by d. The result is stated below.
Theorem 4.1. Let be a predicted histogram. Then there exists an (e, --riivate set union mecha- nism M such that
[[]M = -11--==11mm (H (H,, where in particular we have M]]MH(()]I = =) HD H.
Proof. Given a predicted histogram H, we construct the mechanism Mr as follows. Compute (HD, H) max (HD(r) (=x) and sample p ~ U(0,1), Then Ma outputs the
(D = fa ((H()) - d; > p}.
The utility guarantee follows by noting that
[[[M(D))) = Pr(pp< < <HH()) - d:c, = =E ZEX
π (H(()) d; II = (H,,
ZEX
remains to prove that the algorithm private. Since T(c -d; e, 8) is monotonically increasing function of c. the output of the algorithm is determined by cp, defined the smallest such that (c--l; -d; e, 8) 2 p. see this, note that we can get Mrr by post-processing en and outputting the set { H (z) > CD}. Hence it is sufficient to prove that ep is private statistic of D.
Note that cp only depends on D through d Loo (HD H). and by the definition of ep, have
Pr(cp = m) = 7(m d) T(m - 1).
We denote the distribution of cD when = (H H) as Pa. For all neighboring datasets and D', by the reverse triangle inequality we have
(HD, H) lox H)I < loo loo (I,, HD) S.
Hence it is sufficient prove that Vd 2 0, Pa and Pa+i (e, iidintiiiiit.g... More precisely, we want to prove that for d 2 0, we have
Prm~p, (Pa(m) S e Pa+1 2 -
(2)
8

---

and
Pamm (Pa+ P&(m)) 2
(3)
By the definition of Pa. for all m 2 0, we have
Patm (m m²) Pa(m).
This implies
Pa (Pa(m) S e Pat1(m)) Pr (Po(m S e Pm dd)
and
Prm (Pi (m - d) S Po d)) Pr (Pi d) S e Po(m - d))
Hence is sufficient to prove Equation and Equation 3 for d 0.
By Destontaines et al. 2022 Lemma 1]. we have that there exist og and c₁ such that
0,
S 0
e ef e, (0 +
0 < c S ce:
t(c+1,E,0)
1-6 (TC,E,0) -8,, 1.
C₁ < S ch
if >
Moreover, the above implies T (1),,6) = 6, TCh, 0) E [11-6,1]
We start by proving Equation 2 We show that
Vm 2 2, Po(m) SE
(4)
Since, in addition, Prm-ro (m S 1) Po(1) xl,,,0) - =(0, 8) 6. Equation
2 holds.
To see Equation when 0 E m - S ce, we have
Po(m) = T(m, e, 0) x(m 1,
T(m,8,0) (E-((m 2, 8) +
I (e= - 1,,,5) + 6) - (e' - 2, 6) + +
(5)
e (=(mm 1,,, a 2, 8))
e Pm(),
where Equation 5 is due to the (c, 6)-DP guarantee of π.
If ch m > Ce, have
Po(m) (m,, 8, 8) π (m 1,
π (m, e, 8) - (1 - 6 T(m 2, -6))
< (1 - e (( (mm 1, - 8)) - (1-6 - --(mmmmm---- 2,e,8)-8))
(6)
I (T(m - 1,E,6) - (mm - 2,)
e P
where Equation 6 follows since, by the (s, 6)-DP guarantee of म, we have 1 - f(m 0) <
e5 (m 1, 8)) 6. For 2 > Ch. we have Po (o(m) T <m, (m,,,8) T(m 1,8,0)
Combining the three cases completes the proof of Equation
To prove Equation 33. similarly need to show that
Vm S C₁ +1,
Pi(m) < Po(m)
77)
and then since Pmm-- (m 2 Cą +2) = Pi (c, +2) = π (c,, +1, 0) π (Ch, e, <1 11
Equation (3) will follow. The proof of Equation 7 follows the proof of Equation (4) and is omitted here.
Acknowledgments and Disclosure of Funding
The authors thank Itai Dinur for helpful conversations about this work. Haim Kaplan and Uri
Stemmer are partially supported by the Israel Science Foundation (grants 11 1 and 1419/23) and the Blavatnik family foundation.

---

References
Kareem Amin, Alex Kulesza, Andres Munoz, and Sergei Vassilvtiskii. Bounding user contributions: bias-variance trade-off in differential privacy. In Proceedings of the 36th International Conference on Machine Learning (ICML). volume 97 of PMLR, pages 263-271, 2019. URL https://
proceedings .lr..mmll........ wtw.s..ree//////aa
html
Kareem Amin, Jennifer Gillenwater, Matthew Joseph, Alex Kulesza, and Sergei Vassilvitskii. Plume: Differential privacy scale. CoRR, abs/2201. 2022. URL
2201 11603
Raghav Bhaskar, Srivatsan Laxman, Adam Smith, and Abhradeep Thakurta. Discovering frequent patterns in sensitive data. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 503-512, 2010. /ttppsss:///oi. org/10
1145/1835804 1835869
Mark Bun, Thomas Steinke, and Jonathan Ullman. Make up your mind: The price of online queries in differential privacy. In Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms (SODA), pages 1306-1325, 2017.
Ricardo Silva Carvalho, Ke Wang, and Lovedeep Singh Gondara. Incorporating item frequency for differentially private set union. Proceedings of the AAAI Conference on Artificial Intelligence, 36 (9):9504-9511, 2022.
Justin Y Chen, Vincent Cohen-Addad Alessandro Epasto, and Morteza Zadimoghaddan. Scalable private set union beyond uniform weighting. 2024. Presented at TPDP 2024.
Edith Cohen and Xin Lyu. The target-charging technique for privacy analysis across interactive computations. In Advances Neural Information Processing Systems (NeurIPS), volume 36. pages 62139 62168, 2023. URL http:httts neurss cctpaper.cppppeppeeeeeee f_ (alles/paper/
Parii---app----e Conferenceeeeeeeeooooooooo-oe ppf
Edith Cohen, Ofir Geri, Tamas Sarlos, and Uri Stemmer. Differentially private weighted sampling. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (AISTAYS), volume 130 of PMIRR, pages 2404-24044 2412, 2021. URL
mmr
press/v130/cohen211 html
Damien Desfontaines, James Voss, Bryant Gipson, and Chinmoy Mandayam. Differentially private partition selection. Proc. Priv. Enhancing Technol., 2022(1):339-33) -52, 2022.
David Durfee and Ryan Rogers. Practical differentially private top-k selection with pay-what-you- get composition. In Proceedings of the 33rd International Conference on Neural Information Processing Systems (NeurIPS), pages 11, paper no. 317, 2019.
Cynthia Dwork, Krishnaram Kenthapudi, Frank McSherry, Iya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual international conference on the theory and applications of cryptographic techniques, pages 486-503. Springer, 2006.
Cynthia Dwork, Moni Naor, Omer Reingold, Guy Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the forty-first annual ACM symposium on Theory of computing (STOC), pages 381-390, 2009.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(344)2211-40 2014.
Alessandro Epasto, Mohammad Mahdian, Jieming Mao, Vahab Mirrokni, and Lijie Ren. Smoothly bounding user contributions in differential privacy. In Advances in Neural Information Processing Systems (NeurIPS). volume 33. pages 13999-14010, 2020. URL https:://prceeee newriiinnnnnnnniugge nwwrips................... ips. pdf
wwtpppppreeaiieeeeeeee files/ htc.//pper..llllssppre////////// pappr//00////1le/
Jennifer Gillenwater, Matthew Joseph, Andres Munoz, and Monica Ribero Diaz. A joint exponential mechanism for differentially private top-k. In Proceedings of the 39th International Conference
on Machine Learning (ICML), volume 162 of PMI.R, pages 7570-7582, 2022. URL https //proceedings.o
.mw.mmmmmmmm.....mmm.mm.....m..m mlr. wwwpppesssvveeee wwtess/vv22//pp/ http:///gggleeeaeeeaaaa... html
10

---

Sivakanth Gopi, Pankaj Gulhane, Janardhan Kulkarni, Judy Hanwen Shen, Milad Shokouhi, and Sergey Yekhanin. Differentially private set union. In International Conference on Machine Learning (ICML), pages 3627-3636. PMLR, 2020.
Haim Kaplan, Yishay Mansour, and Uri Stemmer. The sparse vector technique, revisited. In Conference on Learning Theory (COLT), volume 134 of PMLR, pages 2747-2776, 2021.
Alexander Knop and Thomas Steinke. Counting distinct elements under person-level differential privacy. In Proceedings of the 37th International Conference Neural Information Processing Systems (NeurIPS), pages 21, paper no. 1521, 2023.
Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas. Releasing search queries and clicks privately. In Proceedings of the 18th international conference on World Wide Web (WWW), pages 171-180, 2009.
Ryan McKenna and Daniel Sheldon. Permute Permute-and-ffip: a new mechanism for differentially private selection. In Proceedings of the 34th International Conference on Neural Information Processing Systems (NeurIPS), pages 11, paper no. 17, 2020.
Thomas Steinke and Jonathan R. Ullman. Interactive fingerprinting codes and the hardness of preventing false discovery. In Proceedings of The 28th Conference on Learning Theory (COLT), volume 40 of JMLR, pages 1588-1666 1628, 2015.
Marika Swanberg, Damien Desfontaines, and Samuel Haney. DP-SIPS: A simpler, scalable mechanism for differentially private partition selection. Proc. Priv. Enhancing Technol., 2023(4): 257-268, 2023.
Royce J. Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Commons--Marente and Bryant Gipson. Differentially private SQL with bounded user contribution. Proc. Priv. Enhancing Technol., 2020(2):300-25,, 2020.

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction provide accurate summaries of the major claims made in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The limitations of the results are captured in the formal theorem statements, and we emphasize the differences between various analyses and the settings they apply to in the text of the paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
12

---

Answer: [Yes]
Justification:
All nontrivial proofs provided in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
13

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttpe//gguddeeeeeeouuuuumbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
14

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The paper and its underlying research conform to the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The paper is not expected have any immediate societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
15

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
16

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
17

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
18

---

Appendices
A Cap Estimation
Suppose that each user contributes arbitrary number of items to the dataset. simple way to compute a differentially private set union in this case is to fix cap k enforce the cap by random selection (that is, if user contributes more than k items, retain k of them uniformly at random and discard the rest), and finally apply the simple budget splitting mechanism Maplit-
But how should we choose k? If k is too large, the budget will be overly subdivided; if lc is too small, then we will discard a large portion of the dataset. In either case we are likely to get poor utility. However, the ideal value of k depends on the dataset,
must consider the privacy implications of trying to find In this section we suggest a method to select that will not consume a substantial fraction of our privacy budget.
The idea simple. For each value of we compute the expected utility of M Maplit on the randomly capped dataset, and then run the exponential mechanism Dwork et al. (2014) (or some private noisy maximum algorithm) to pick the value of k that maximizes the expected utility. This will be successful if the sensitivity of the expected utility remains small even as l grows. On the one hand, as k increases, individual users can make more contributions to the capped dataset, which will tend to increase sensitivity. On the other hand, the per-item budget shrinks, reducing the effect of each contributed item. We will show that these effects cancel out such that the sensitivity can be bounded independently of k.
We first establish an upper bound on the increase in æ when the count of an item grows by one.
Lemma A.1. For e 2 0, T(C + 1; Tc 8) < ='=1 8
Proof. Recall the recursive definition of π from Desfontaines et al. 2022
6)) =0
(8)
F(c = min (1- -0)
We have
<c - - < min
+
-) x(c)
min {(e 1)F(CE + (c 1)T(T
- -
8)}
As function of π[c; E, 5), the left term in the minimum is increasing and the right term is decreasing. Therefore the minimum is bounded by the value of the two terms when they agree:
(e - 1)T(() 8) + = 1 (e - 1) (c)e,, - - 8),
(9)
which implics
c -1 (1- (1
1
π (c
(10)
Plugging this back into the left term, we obtain the bound
6-1 e (1 6) 6)+
=(c+1:E,0) 1: x(c:e,)) e= +
2 +8.
(11)
Let U(D,k) k) denote the expected utility of Maptit on dataset D after users are restricted to i items by uniform random selection. The following result shows that the sensitivity of UDD, k) can be bounded independently of k.
Lemma A.2. For for all neighboring datasets D' D) we have (U(D', -(D < -
d.
Proof. Let Dy denote the randomly capped version of D where the bound of k: items per user has been enforced using uniform random selection. We have
U U(Dk)) [1(GGee/,,8/k))
E.
Σ n((a,, Dx); ew);
(12)
D
19

---

Assume without loss of generality that D' contains user that D does not. Let S₁. denote the random set of items contributed by the new user in D. Because the bound is enforced independently for each user, we can couple D'2 and D2 using the pair (Dk, St). Then UD',, k) UD,, k) is equal to
E
Σ TEX
xell,, D.):s/k,8/k)
E DE
Σ
(a):
LEE
E De.Sk
Σ
(л(((x D&) I( Sx):e/k, 8/k) - <(((,, Da)ee..)
(13)
LEE
Because [Sp| I k, most of the terms in the sum are nonzero, and we can apply Lemma A.1 to conclude that
e - -1
8
S c ー-1 8.
()
(14)
2
If a small, then 1e)-1)/2+6 about e/2 22 and therefore the sensitivity of (D, k) is also small. In this case pick the cap k that approximately maximizes U UDD k). Concretely, let = (e" - 12//2 22/2++ denote our upper bound on the sensitivity. Then the exponential mechanism with privacy parameter e' obtains cap such that
the exponential mechanism (or approximate noisy maximum algorithm) to
U (D, max UaXU(D, 24 log
[CC
with probability 1 - where K. denotes the of possible caps we optimizing over. (The utility guarantees of approximate noisy maximum algorithms are similar.)
B Impossibility Results
This section contains complete proof's for the results stated in Section Appendix B.1 contains proofs of Theorem 2.1 and Theorem 2.2, while Appendix B.2 contains the proof of Theorem 2.3
B.1 Bounds from Tower Datasets
In this section prove Theorem 2.1 and Theorem 2.2 which strongest upper bounds on mechanism utility ratios, but only demonstrate difficulty on datasets that are very difficult (i.e., on these datasets, IT(D) is small compared to the size of the non-private union). The proofs organized slightly differently compared to the sketches provided in the main body. In particular, rather than explicitly constructing the datset D on which mechanism M has low utility, construct a distribution over datasets and show that the mechanism's 's average utility on that distribution is low. This will imply that there exists dataset in the support of the distribution for which the utility ratio of the mechanism is low, but the distributional approach simplifies a number of arguments when moving the more involved construction used in the proof of Theorem 2.2
Σx (SID)) since minimum is smaller than the
Recall that our goal is to bound max minpeD, average, we have the following lemma.
I[(D,.,))
Lemma B.I. For any distribution over datasets,
max min Es (A(SSD)) max E
Σs (MI() II(D,,,))
M
We will choose P to be uniform distribution over set of datasets with the same value of IT(D, 6). To define the class of datasets, we need few definitions.
Definition B.1 (Tower dataset). dataset D (Ba)
tower dataset of height h if there is
an ordering o [h] > [h] such that Bo(d) S Bo(411) for each i I h h-1 1. Furthermore, we call b(D) = (BBa))) B..g)l...,,IBBB.
the shape of the dataset D. We denote b, |Bogg We omit D and denote the shape by b (bi...., "u....,bb)) by) when appropriate.
20

---

Bi
B
B
B
B1
B
B2
B2
B2
B2
B2
B2
B3
B3
B3
B3
B3
B3
2 3
1 2 3
1 3
1 3
1 3
1 2 3
Figure 3: All possible tower datasets with three users with bj = 1, b2 = 2, and by = 3.
Notice that the datasets constructed in the proof sketch Theorem 2.1 were tower datasets of shape kI. In the rest of the section, unless otherwise stated all datasets tower datasets and the elements are (1. k}. In Figure 3 we illustrate all possible tower datasets for simple shape
When D is a tower dataset, the following result shows that IT(D) depends only on the shape of D:
Lemma B.2. For tower dataset D with shape and height h, if 1 + In (
J. then
(TD) = 5. Σ (here-
Proof. Note that there are elements that appear times and b2 bj elements that appear h times and so on. Furthermore, all the counts are smaller than the bound ce in Equation (1. Hence,
II(D) b1t(h) + Σ
-b/41- 6r)
6 b h -1
4-1
6 - -11
clh elh-r)s- -1
+ Σ (br41 - br)
e -
6 by (h-re
where the last equality follows by algebraic manipulation.
We now provide a complete proof for Theorem 2.1
Compared the proof sketch in the main body of the paper, we adopt proof technique that relies on the same key insights, but is slightly more aligned with the proof of Theorem 2.2 to help introduce the key ideas.
Theorem 2.1 (Warm-up). Let k > 2 0, 8 -'zZ and let M be any (e, -ddifferrrel privale union mechanism. Then there exists dataset 1) with contribution bound such that
[|IM(D) I(,
k
<
In particular, for llk)) and 6 < F we have IDD,)))
E M(D)I
I 2
Proof. We choose uniform prior over all datasets of shape (1, denoted by unif(1, k). Note that there are l such datasets. For notational simplicity, let D(i denote the dataset containing two users, one contributing the singleton element {i} and other contributing
& items. Every dataset D(i] has single item that appears twice and (k 1) items that appear once. Therefore, [I(D[()) = (2) + (A: (1). The bound on ensures that < o from (T), which implies that (2) 5 + 8. Together with the fact that π r(1) å (regardless of parameters), we have that
(D(i)) 8(e +),
(15)
for all < k. Now consider the dataset D containing single whose bag of items B(u) = (1, 2, .......... This dataset is neighbor to all the datasets of shape (1, k). hence for each such dataset D[i]
P(())DE < P((i) +
(16)
21

---

and for all non-empty sets S * {i},
Σ (7
P(SID()SS se
Σ P(S)D(() (7(1)
+ +0= = 6,
(17)
where Dit is a dataset with one user contributing only element {i}. Recall that unif k) is the uniform distribution over all datasets of shape (1, k) over elements (1,2,3, ..,,,..,kk
Now fix any mechanism M and for any item set C X and dataset D, let P(S) | D) denote the probability that M outputs S when run on D. Then we have
min EsP(s P(S (D |S| II(),,6)
Es P(S D) |S] II(D,E,))
E
Σ P(S D) |S]
8(e + +k)
Dwunif(1,A)
s
ΣΣ
Σ
P(S D(i)) 111
8(e² + +k)
s
1
Σ
P(i) D + E
P(S D 1Ss
8(E5 + k)
K
i=1
1
Σ
P(() D(D) Σ Pas(S D(1) k
8(e5 + +k)
i=1
8+(1)
SW
1
(P({i) D( 5
8(e + k)
k:
(8e" /k + 8k)
8(e +k)
e + 222
ke + 12
k
+ 6 k k
where (a) follows by Equation (5)) (6) follows by the definition of expectation, (c) uses the fact
that the size of each set is at most k. (d) follows by Equations (66) 17 (c) uses the fact that
Σ P((i)D(()) < 8 as D(0] has only one user.
Before moving the proof of Theorem 2.2 let reexamine the techniques used in this proof of Theorem 2.1
1. We imposed uniform prior over all datasets of shape (1, use Lemma B.1
2. We divided the sets into two groups and for each particular group, used differential privacy constraint w.r.t. a different neighboring dataset obtained by removing certain user from the dataset (e.g., Equations (16) (77)
(a) For nonempty sets S * {i). we used DP constraint w.rt. neighboring dataset D and used the fact that it assigns
probability to all these sets.
(b) For sets {i), we used DP constraint w.r.t. neighboring dataset D[0] and then summed over all such sets {i} and finally used the fact that D[0] has an empty neighboring dataset and hence the sum of probability it assigns all such sets is most 6.
Our main upper bound follows similar technique, but slightly more involved. We again impose a uniform prior on tower datasets of a certain shape with many users and we divide the sets into several groups and for each particular group, we differential privacy constraint w.r.t. different
22

---

neighboring dataset obtained by removing a certain user from the dataset. However, for the second step. we need recursively remove several users to get neighboring dataset that assigns zero probability to that set. To formalize this intuition, we need the following two definitions. The first definition is that of a partial dataset, which obtained by removing i users from the dataset as follows:
Definition B.2 (Partial dataset). Let r and i be non-negative integers such that + i S h. For tower dataset D {B1, .e...., Br3 height h let
.......,,,
D = [BI, B2, Br, Brtt41, B Br.i42....,
Note that height of D is h -
Notice that using this definition, we can start with and remove B,+1 to get Dj which is a neighbor of D, then we can continue and remove Br42 to get D2, which is at distance 2 from D and on. In our proof, we note that we remove users this particular order i.e., we start a particular user r and remove all users larger than
To get database for which we output S with zero probability we have to remove all users that contain S. To this end, we define the rank of a set as follows.
Definition B.3 (Rank of set). For tower dataset D of height and set S, let rank 8) denote the number of users such that set S contained in B; i.e.,
rank
ii $ S B.)l.
For example, if D {(1), (1, (1,,,3), (1, 4), 2,3, 4, 5)5 and [1,3}. then ran 2. For dataset height h, the rank ranges from 0 to ht
Note that because the user item sets are nested, we have that
rank D, maxfi E [M] 1 Bi},
since if S is a subset of user i's bag, it must also be subset of Bj for all j 2 6. In other words, rank( S) the index of the last user in /) that does not contain every item in S. We have defined rank of set w.r.t. dataset the number of users not containing the set, opposed to number of users containing the set for notational simplification, since ensures that the rank does not change if we remove users containing S in the particular order mentioned above.
To summarize, Definition B.2 allows us discuss neighboring datasets where we remove user bags B,+1, Br+ By++ and Definition B.3 allows us to discuss how many users do we need to remove get a dataset for which there is zero probability output S. We state the following set of properties for these partial datasets and rank, which will be useful in our proofs.
Lemma B.3 (Properties of the rank and partial datasets).
1. For any r $ h.
D = D.
(18)
2. D and D are neighboring datasets.
3. (annk(D, = r, then for any S h r
rank(D),
(19)
4. If rrrak(D,S)) = then |S| < by41.
5. If "rran((D,)) = then
P( =
Proof. (1) follows from the fact that we have not removed any users. (2) uses the fact that D and
D441 differ only in user r + 1. (3) follows from observing that if the rank of a set is then
removing users B for 2 does not change its rank. (4) uses the fact that C B and (5)
follows by the fact that D D does not contain any sets that contain S as the rank of S is
D
23

---

Suppose we have a uniform distribution over all datasets of a certain shape b = (b1 bg...., by). We draw a database from this distribution and then remove a user of particular size say by. Then we get
a database of shape 82- 11= = (b....., .,. by-1, bs+1,..., bn) with all datasets of these shape having the same probability to be the outcome. This is formalized by the following lemma.
Lemma B.4. Let (n) denote the uniform distribution over all datsets of shape b. If ~ unif then for any r: i
D ~ (6))
(20)
where ig _ (b1, b2, by, brti41, 0rti42, b...
Proof. To simplify boundary cases, we let Bg 0 and B X. We will argue that when sample D ~ (b) and obtain D' by removing a single user from D, say user Bj. then D' is a sample from [ where _ = (bi..... .......j--- bit1........ .b)) Then the claim about removing several users follows by induction: We get Dj by removing users from D, and each removal results in uniform distribution over tower datasets of the relevant shape.
We now rurn to proving the claim for removing a single user. Let D ~ unif(b) and D_j denote the dataset obtained by removing user j. Similarly, for concrete dataset d, let d-, denote the dataset obtained by removing user j and for shape b, Recall that b;-1 denote the shape vector after removing the jth component. Let p be the probability such that for every datset d of shape h, we have Pr(D = d) = p. Now fix any dataset d' of shape 8/-1 and consider Pr(D_, d'). By the Law of Total Probability, we have that
(b). ........ by-1, by+1..... bn)
Pr(D_, d')
Σ
Pr(D-; = d' 1D Ddd)Pr(D>
d of shape 5
Σ shape b
Ifd_, = =d}.
In other words, the probability that D_j d' is proportional the number of datasets of shape b such that removing user j from d produces d'. We will count the number of such datasets. A datset d has shape b and satisfies d_j d' if and only if d contains all the users of d' together with new user By such that |Byl = by (so that the shape of is b) and By-1 C Bj C B (so that d is tower dataset). The number of distinct choices for B, depends only on the shape b: B, must contain by distinct items selected from the by+1 items in Bj+1. And, it must include the by-1 items in By-1. So, the only freedom we have is to select by- b items from Bj+1 Bj-1 to include in B, in addition to Bj B- There are (*) 11/11 by-b3-1
))
ways to choose those items, giving
Pr(D-, = d') = (0)) 6, by-1
(btt1 bj-1 ) )
Since this is true for all d' of shape b-j. it follows that D-, is uniform over datasets of shape b-j- Li
Consider a set S that has rank r in dataset D. There is at least one item in S that appears at most h times in D, since otherwise the rank would be larger. This implies that the set S can only be output by any private set union mechanism M with probability at most т (rank(( D, S)), since otherwise we would output least one item with too high probability.
Consider a set S for which we have to remove probability to it. For items in this set, we expect the π bound to be of the order of 8e(h- l)s However, we show that single mechanism cannot assign a probability proportional to (h-r-1l for all such sets. To prove this, we use use the following contraction lemma.
items to get a dataset which assigns zero
Lemma B.S. Let (b) denote the uniform distribution over all datsets of shape b. If unif(b). then for any set S and rank r 2 0 and i 2 0 such that r + +i+ 2 < h,
bptit1
L Dr 5
brtit2 Trank ()
(21)
In other words, for any instantiation of the dataset Di say d'+11
brtitl leank(d",,.))
E[ [[Irank(D DS) = dGail I
(22)
bytit2
24

---

Proof. Fix a realization 1++1 for the dataset 1/+1 and rewrite the left hand side of (22 as
[[]rank(D) D d;+1] Pr(rann(D),
D = d.+1).
We will consider three cases based on the rank of S in di First, suppose that rank(d] < Then we know that 5 C B, (since only at most the smallest r 1 users in di do not contain S). But then from the tower dataset definition, we must have that B,+++1
B, S. which means we have added a new user to di+1 that also contains S. which does not change the rank of S and have rank DJ, , S) r. In particular, both sides of (22)
zero and the inequality holds. Next, suppose that rank(d +1, S) > r. Then we know that S is not contained in B,4++2, (since at most the r smallest users in 1 do not contain S). But again by the tower dataset definition, we have that Br+1+1 C Br+1+2. which implies that S y By+1+1 and so the rank of S in DÝ can only increase. so Da
In particular, both sides of (22) are zero and the inequality holds. It remains to handle the case when rank(d
=.. =r.
When rank(d"++;,S)
the right hand side of (22 equal b,-142" we need argue that this an upper bound on the probability that rank S) = conditioned on D d' 1- Observe iff S Br+i+1,
that in this case, rank DT) of this event given 1 and (S, 1++1) rr.
need to determine the conditional probability r. From Lemma B.4 together with the fact that D is uniform over tower datasets of shape b, we have that D; is uniform over datasets of shape 6/. After conditioning on D
1 1. the only randomness left is the draw of Uy+++1's 's bag. Say that an item bag R C X' is valid for user ur+i+1 if R b,+s+1 and By+s C R C Br+i+2 so that D is tower dataset of shape bj iff B,+i+1 is valid. Conditioned on D the item bag for user uy++-1 is drawn uniformly random from the set of valid bags. So, we can calculate the probability of the event C ur+++1 by counting the fraction of valid bags that contain
First, let's count the total number of valid bags. We need to choose a = byti+1 - b, items from the by+s42 by items in B,41+2 that are not already in B. obtain B,41+1 of the right size that does not violate the tower constraints. There (9) - (}=1)
ways to do that.
Next, we upper bound the number of valid choices that contain the set S. Let æ be any item in S that not present B,. Then every valid choice that contains S must also contain æ, so it sufficient to upper bound the number of valid bags that contain the single item The number of ways choose subset of Br+i42 that contains x is (a=1).
Taken together, we have shown that for any d' for which rank d(+1) we have
(8-1)
by+i+1 1 br S byts-2"
brti-1
Pr(S c Brtiti D :
B brtit2 br
where the final inequality follows from the fact that if x/y I 1 then x/y S (x + 2)/ (y + 2) for any non-negative v, y,
The next theorem gives an upper bound on the utility ratio for any mechanism M by its utility ratio on tower datasets. In the subsequent results, we optimize over b to get the best bounds for given e,e, 8.
Lemma B.6. For a given e, 6, let hmax A 1+
In
(er +110
Σ/z by (Eh, (gelo-))e) by D ble
Es (SDD))
max min M
min hShaaa
min bi
D
EI(),,,8)
Proof. By Lemma B.I for any distribution P.
Σs PM
Σs (M) II(D,,,))
max min M
< max ED M
D
IKD,e,8)
25

---

Let P be the uniform distribution over all tower datasets of shape b with height h S Amax over the elements {1, 2, .................. k). Since any dataset generated by this distribution has shape b, can compute their IT value by Lemma B.2 Hence, combining it with above equation, we get
Es Par (SD
max min M
max D-uuif(())
(23)
6 8 -r= byelh-r)e
In the rest the proof, we prove the following bound
clo ))
max E D
PM(SSD)SS
Σ br
by Σ
(24)
M
by
combining the above two equations and taking the minimum over all shapes b such that by. k and h(b) Σ hmnax yields the theorem. To prove Equation (24). we divide sets based on their rank as follows. For notational simplicity, we drop the subscript M.
E (b)
Σ P(SID)|S) 8
E Divuni(())
1 P
S F=u
E D~unif(h)
rank D.s.
0=0
5
h
Bg ~uni(i((
E. D )uii(()
1mnk(D)..9==PPS1)2))))
E Dg uunif())
b Bgggapiffff
Σ Prant(
where (a) follows by Lemma B.3 item (5) and (b) follows by Lemma B.3 item (4). We now going to bound (mt(()))( Es S)) for given value of r.
E Dgnunit(8)
rank D) P(S D2)
E Dijuuii(())
8 e P(S)DT)
8 + Σ ee umittt)
(
(a) + Σ
e DJ munitth)))
(P(S ( Di]
< 8 brt1
e
Σ 5
Epp wunit(() ((an
(25)
br42
where the first inequality follows by noting that DJ and DJ are neighboring datasets and applying differential privacy constraint to the event outputting a set of rank and the last inequality follows from Lemma B.5 (a) follows by law of total expectation and Lemmal B.4
26

---

B
B2
B3
B4
1
3
4
5 6 8
Figure Example the tower dataset in Theorem B.6 with = 8, h = 4, E = and a
Similarly, we can get Vi < r 2, we have
E (y
Σ Drank(
brtitl
S 8 +
E Epr vunif())
(26)
bytit2
S
Substituting Equation 266 for
,...,
2 into Equation 25) we get that
br+1 e +
br+1 25 +...
br41 elh (()-)
wunift))
I |
br+2
b,43
bn
Summing over all values of r yields
E (-
Σ P(SID)|S)
bp+1d
11
bp+1
oe
bp+1 22
by41 chh-r-1je
br+2
br+3
bn
h
b,.
1 +
by
e
+
by
22
+
by
(h-r))
br+1
bet2
bn
r=
by
6,
ba
Combining the above equation with Equation
23
yields Equation (24) and hence the theorem.
Next we move on to prove Theorem 2.2 We do this by finding a suitable value of that provides the desirable upper bound.
Let 1 + _ log k.. For r 2 1, let by = (Te((-1))e 1)067 (see Figure 4 for an example). Let a be such that by. k. Note that
= by [e(h-1)ar > (1h-1)ae k 1.
Hence, a I 1(h-1) log k < tower with b441/b = coe, Furthermore,
1 Note that the size of each set grows from b = to b; = k in the
2-
c 25 - )
(e + 1)6 )
e --1
2 log +
2
In
1+ In
2 1+
1+
log
h,
(c + 1)5
where the first inequality uses the fact that 5 2 0 and the second inequality uses the upper bound on in the assumption of the theorem.
Using Lemma
B.6 we get
Ed by (Iber be c(c D b-
Es PMS
max min
(27)
I1(D,,,8)
27

---

With b, = [e(r-1)ae
and I [x] I 2x for x 2 1, we get
by (o-r)e
Te Te(r-1)an 1Jae
(-r))
c ((0-1)ae
2e(r-1)ae 1)as ((0-1)e
c 1)ae
((t-r)(1-aje
(h ( 1)(1 10l a)c
ell-a)e -1
( 1))---))(--a))-
$ e(1-a)c -1
Recall that b, Exer be ( upper bounds the contribution of outputs of rank r- 1, = 1,..., h by
to the expected utility over D (b). We see that Ed_r by c decreases geometrically with But (((--)aee increases geometrically with r. So intuitively, since a is close 1/2, we get similar contribution from each rank. Plugging the above back into the ratio in Equation 27 we have
b,
min Es PM ()JS)
2
Pr=
h
ell all-ay a)e
bye(h-r)e
4
-= (1ree L)ee (1-r-1)(--a)
ell ell-a)= -1
E/= elr (orrlJaaeei cla--ra
4
((++1)(1- n e e r(---o
ell-a)e
ehe Σx erace-re
e(1-a)e Ih (2a-11) 4
e(l -1 earhs >hh (r(a-1)e
(6)
4e (1-)
(2(20-1)5 1)s
el2-aje ajt -
gake Σr=1
er(a-1)s 1)5
4he (2a-1) 1)e
c(a-1)e
1 cla-1js 1]6 (laheela-l)e ch(a)1)e)
4h
ea(h-1)e (1 - cl(a)-1))
(e) 12h
k
12
(
1: 1 log
where (a) follows from x S [a| I 2x since by = [elr- 1)0c (b) follows since a < 1/2 implies that
er(2a- 1)= < (22n-1)= 1)= for 2 1, and (c) follows since elh elb-1)ac 2
and 1aae ((1-1)= <
gas < V 2(k 1)/33.
B.2 Bounds from Fingerprinting Codes
In this section we prove Theorem 2.3
= Theorem 2.3. Let 2 2, n 2 Cj. (so that (n/2)) = 1), E 2 1/n, and 8 < 1/(40e" n2-2 2/1)) Let M be any (e, differrrentl private union mechanism. Then there exists dataset D with contribution bound k such that
E (
=0(("
nn² log(nk) (())
1/4
I(D,s,0)
k
28

---

Note that Theorem 2.3 requires that we have at least n = ( In (/) users to ensure that a 2: 6) = 1, and the contribution bound l must be relatively large compared to the number of users: lt Snn In n..
Remark B.7. Theorem 2.3 would hold even if we somewhat relax the definition of utility ratio. For example we can allow a small constant fraction (< 1/2) of the KII(D,E, 5) items that we report to be mistakes. Le. items that do not appear in the union. (Proving this will require a slight adaptation of Lemma [..). We do not pursue this in this paper and leave investigating possible relaxations of the definition of utility ratio for fature work.
The key idea in the proof of Theorem 2.3 is a reduction showing that a private set union mechanism A can be used construct mechanism for estimating the marginals of a matrix (see Definition [B.4) whose performance can be bounded in terms of the utility ratio ux(A), Combined with an impossibil- ity result for computing
mannnaaiass based on robust fingerprinting codes, due to Steinke and Ullman (015), we obtain our upper bound on the utility ratio.
Definition B.4. Let C E {0, 1 be a matrix and A {0, 10. + [0,1) be possibly randomized algorithm. We say that A is (3, -i-inaccurate for computing marginals of C if the following holds with probability at least qy: Except on at most 38 coordinates i [4] the ith column of C' is all ones or zeros then M (C), = 1 or M (C') = O, respectively. In other words, M must identify the columns of C that are all zeros or all ones, making a mistake on at most 3 fraction of the columns.
Roughly speaking, our reduction views the matrix C' E {0, 1 1 as the description of private set union instance where each column corresponds to an item and each row corresponds to a user. The 7th row of C' is indicator vector for the items in user i's bag. The mnon-private) union of the bags described above is exactly the set of columns for which outputting "1" is not mistake. Given that we only start from private set union mechanism that estimates the union imperfectly, the reduction outputs for all columns in the approximate union, and outputs 0 or I with equal probability for each of the remaining columns. The following lemma connects between the utility ratio of the private set union mechanism and the (3, (.l.7))-inm -iinaccuuracy of the resulting matrix marginal mechanism.
Lemma B.8. Let M E UNION,(S, 5) be an (e, 8) -privaaee set union mechanism with contribution bound E and utility ratio K- = ue( M.). Then for any n large enough such that π (n/22; E, 8) = 1 and E N, there exists an (E, ( differrentill private matrix marginal mechanism A {0, 1|axe > {0, 13 that uses M as a subroutine such that the following holds: For every matrix E {0, 1 such that at least half the columns of C have at least n/2 ones, the mechanism A is (3, >)iincccurate
for computing the marginals of C with B = 1 2 +
In( In(40/x)) (2 and 7 = 10
Proof. Fix any matrix C E 10, where at least half the columns have at least n/ ones. We can transform a realization of C into a private set union problem as follows: the item universe is X' = {}....,}} and the dataset is D has users, where user contributes bag B, (j E x Ciyy = 1} is determined by interpreting row i of C as an indicator vector.
The matrix marginal mechanism A works as follows: first, let Ū = M(D be the private union output by M when run on the dataset described by C. Then A outputs a vector y {0. 1] defined as follows: For each coordinate j E Ú, set y = 1. For the remaining coordinates j & Ú, choose yjj to be 0 or 1 with equal probability. Since A post-processes the output of M, it is (e, diffferreetlal private, so remains to bound the inaccuracy.
First, observe that the union U = U.=1 B; is exactly the set of columns that are not entirely zeros, which means that if A outputs 1 for any column' i E U", it is not mistake. Due to the subset requirement of private set union mechanisms, we are guaranteed that U c U and, since A outputs 1 for the columns in Ü, never errs on columns in Ü. On the other hand, for columns j g Ü, A flips a coin and will err with probability at most 1/2, so we need to argue that |Ú] is large compared to e. By assumption, with probability one, at least half of the columns of C' contain at least n/2 ones, and π (n/2: fn/2;,, 6) = 1. This implies that in the private set union instance D derived from C, at least f/2 of the items appear at least n/2 times, and therefore IT(D) = E [[((j, D)) 2 6/2.
Since K = (M(M) is the utility ratio of the private set union mechanism M, we are guaranteed that B]J01] 2 xlI(D) 2 nl/2. Note that since |0| < é with probability one, also have
29

---

B|J019 < 2.E.E E[J Next we use Siley-Zygmund inequality to lower bound the probaiblity that |0| 2 kl/4.
Lemma B.9 (Paley-Zygmund Inequality). If 2 a random variable with finite variance, then for 0 < 0 < 1, we have
(r 2 (E 2 (1 - 0)2 Eiz]
1
By Paley-Zygmund inequality, we have
Pr (1
For fixed U, the number of errors ne the algorithm makes is Binomial random variable with e |0] trials and success probability 1/2. We use Heoffding's ' inequality to prove the following concentration result on fle.
Lemma B.10 (Heoffding's Inequality). Let X..., Xn be independent random variables between 0 and 1. Consider the sum of these random variables, Sn = Di=1 Xt. we have
2t
Pr(S, - B[S, 2 t) S exp (-
By Heoffding's inequality, have
(E (8) log (40/k)
Pr
Te 2
S k/44..
2
2
Hence by union bound on the complements of the events |0|
2 kl/4 and ne S L-10
(40///))) we upper bound their intersection as follows
2
The
k + In(40/x)
)
Pr
2 K/8 k/40 k/10,
8
2
completing the proof.
The following hardness result for the problem of computing marginals follows from work on robust fingerprinting code (Steinke and Ullman 20155. We include its proof at the end of this section for completeness.
Lemma B.11. There is no (e,8) DD algorithm with e 0(1), 5 (4(e which is x) inaccurate for computing E-marginals on x & matrices with at least n ones in the majority of the columns for
1 -0 ((12 (log(n) + 2s + log(1/7))) 1/4
((=((og(())
B -
Equipped with this hardness result for privately computing marginals, we are ready to prove Theo- rem
Proof. Theorem 2.3 From Lemma B.8 follows that an (c, -prrivate algorithm for set union
with utility ratio gives us an (s, - algorithm for marginals which is (3, -inaccuuatee where
8 K
In (400m)
(2-1))
K
+
8
and 7 = x/10 on inputs matrices with n rows, such that the majority of the columns contain least n//2 ones, where is large enough such that x(n/2) 1.
30

---

If 8 2 m/(4 = m/000e"n) by the assumption that 8 < 1/(40e" we already have
K = 0 ((
n² (1 (ng((//k)) ) When ò < m7)444nn) follows from Lemma B. that
((
n2 (( 28 + log(1 (09)1) 1/4
In(40/k)
2 -
k + 8
t
2
2 8
Rearranging the terms and substituting 7 = k/10, we get
O ("² (mrioett//s))
1/4
OO( log (
(m)))//))))) =0
(0((()h((///))
1/4
((""bo(in)) 1/4 )
This implies that K =0
We conclude the proof by noting that the contribution
bound k < l in the construction.
Finally, we turn to the proof of Lemma B.11 which is variation on the bound provided by Steinke and Ullman 2013].
Proof. of Lemma B.11
We use the robust fingerprinting codes from Steinke and Ullman 2015 defined as follows (Definition 2.20 in Steinke and Ullman 2015)).
Definition B.5. A n-collusion resilient fingerprinting code of length E for m users robust fractions of errors, with failure probability Ç, and false accusation fraction is a pair of random variables C E {0, 1] mxx and Trace : {00 1 + 2)mm such that the following holds. For all adversaries Ad {0, 1xxx 10, and S [m] with |S|= = have
Pd.Trace,Adl (111 S S Di E [m]] Ad(Cs)' = = S 33)
A (Trace(Ad((s)) = 0)] 5
(28)
where Cg {0, (0,1)*x contains the rows of C indexed by S, and the superscript is used index the entries in vectors of length E, and
Pe.Trace (A(C))(A n [[m) ()] 2 n/m m)] S
(29)
Intuitively, Equation 28 says that if the adversary answers most columns correctly then Trace should accuse some users. More specifically, the first event in the intersection happens if the number of all ones columns j on which the adversary says (Ad(Css) = 0) or vice versa is smaller than BE. The second event happens if Trace does not accuse user. So require that with probability 1 - either the adversary makes more than 38 mistakes or Trace accuses some users. (Note the stronger condition i g [m] rather & [n]] in Equation (28). this means that Trace is committed to answer a larger set of responses of the ad adversary.) Equation (29) requires that Trace will not accuse more than 77 fraction of the innocent users (that not contained in S). Specifically, we require that with probability smaller than ( Trace (wrongly) accuses more than fraction of the users who are not in S.
Steinke and Ullman 2015 Steinke and Ullman 2015 ))
constructed codes as specified in the following theorem (Theorem 2.21 in
Theorem B.12. For every S S m, 0 < 3 < 1/2, and 0 S S 1, there is a recoillssion-resilienn fingerprinting code of length for m users robust 3-fraction of errors with some fixed failure probability
S
S min (n(m n) 2 Win(m-n))) + ((1/2-33))
false accusation fraction for
n2 log(nn))))) =
(1/2- 3)1
31

---

For lower bounds on DP algorithm we use such code with m n + 1 users, and accusation fraction ? = O(1/n), since we want failure probability Ç O(1/n). We call such a code a B-robust, fingerprinting code for n users with failure probability Ç (although the code is in fact for n + 1 users, n of them colliding).
For our puprpose, we need to modify the code of Theorem B.12 as follows.
Theorem B.13. There exists a code with the same parameters as the code of Theorem B. 1.12 such that the support of its matrices consists only of matrices in which the majority of the columns contain majority of one and failure probability al most twice larger.
Proof. We define a code C' and Trace' satisfying the requirements as follows. We generate C and Trace from the distribution of the code of Theorem [2 Then if C' instantiates to a matrix in which less than half the columns contains more than half I's we instantiate C' to the complement of C' and instantiate Trace' to flip its input before applying Trace. Otherwise we instantiate C" and Traae' to be equal to C' and Trace respectively.
We claim that this with failure probability at most 2Ç where Ç is the failure probability of original code C, Trace. We prove this by contradiction. Suppose there is Ad' that breaks C², Trace'. That is it either satisfies Condition 28 or Condition (29) with probability larger than 2Ç.
code C' and Trace' satisfies Conditions (28 and 29 of Definition B.5
We construct an adversary Ad for C, Trace as follows. The adversary Ad gets set S of n row of C' and then flips a coin and with probability 1/2 simply applies Ad' to these n rows and returns the same vector that Ad returns. Otherwise, it applies Ad' to the complements of the rows that it got and returns the complement of what Ad' returned. Let S' be the set of rows to which we apply Ad' ( S' = S with probability 1/2 and otherwise S' S).
It follows from the definition of C², Trace', that with probability 1/2 Ad applies Ad' to set S' of n row from the codebook C' (the same distribution). Conditioned on this event, by our assumption, Trace' would satisfy either Condition (28) or Condition (29) with probability at least 2Ç. When C", Trace' satisfy Condition (28) with respect to Ad', then C.Trace satisfy Condition (28) with respect
to Ad. Similar claim holds for Condition (29).
This implies that Ad fails with probability larger than in its attack C, Trace, which is contradiction.
The existence of fingerprinting codes rules out DP algorithms which accurately compute marginals, described in the theorem below.
Theorem B.14. If a B-robust, fingerprinting code of length for users with failure probability exists, then for any & and 8 such that
c 7-5
n1
there is no (E, 81-privete, (3, (3,.7)-innne -inacccueeeee algorithm for computing the marginals of E-attributes of n-users. Furthermore, such DP algorithm does not exists even we require that it is 3-inaccurate only on n. x matrices in which the majority of the columns contain more than n/2 ones.
Proof. Let M be (s, pprivate 3 i-inaccurate algorithm for computing l mmarginass of n users. Define Ad(Cs) == M(Cs) be an adversary for the fingerprinting codes in Theorem B. that computes the marginals of the codewords of the users in S (this is an n X & matrix) and responds with the result.
Consider the set of users S In + 1] \ {1). Since Ad(Cs) is correct on (1 3) marginals with probability 7, and the complement of the event in Equation (28) holds with probability 1 - Ç. it follows that
Pc,rrace,Ad [[Trace[Ad(S]] + 27-
follows that there exists some E [n + 1] (1) such that
7-6 n
Pe,TTaco,Aa(CC [(i (rr))((d((ss))]
32

---

Opening this up using the total probability formula, we get that
Σ
Ad E (Trace(Ad(Bs))) Pc cl 2
7
(30)
(O.1)
Now consider the set of users S' Im + 1J {(*). By Equation 29 we get that
Pe,rrace, [1 E Trace(Ad((ss)) =
and again by the total probability formula we can write this as follows
Pirace, TTrace(Ad(Bs)) P (E(0,))
Σ
(31)
Note that (1) Trace Trace (M() is (E, 8D (Trace postprocess the output of the adver-
sary, Ad, which private), and (2) |SAS = 2, so for every B the summations in Equations (30)
and 3.. the databases Bs and Bg differ by two users. It follows that for every such pair Bs, Bs
Preaee, [(i" E eTTace(Ad(Bss))
é (c TTacce(Ad ))]] + +) +
(32)
We use Equation (3 and 31 to upper bound the left hand side of Equation 33 by e (c + 8) +
we get that
el - 5) + 5 7-5
n
If e and 8 do not satisfy this condition then we get contradiction so M cannot exist and the lemma follows.
Taking ( -n 17 2( 2 and n + Theorem B.13 we have that there exist robust
fingerprinting codes with code length
n² log(1/n)
n22 (log(n) + 25 + 1og(1/>1))
f= 0
=
(1/2 3y1
(1/2 B)1
When < n/), we have e (6 (e < 2-5, and Lemma B.1 then follows from Theorem
B.14
C Algorithms with utility guarantees missing proofs
We prove Lemma 3.1
Lemma 3.1. Let Myn k, be the mechanism that works as follows: for each item x E X, include x in the oulput with probability n[c(x, e);e/,, 8/k). Then Masti is (e, -ddifferrent private set union mechanism when users contribute at most items.
f0sss/////// 8/k) = O, items that do not appear in the input dataset are output with probability O. It remains to check that Maphi is (e, differrential private.
Proof. Since e0
The key idea is to think of Mspti as the composition of | simpler mechanisms, one for each item E X. In particular, for each item E X. let M, 'D - {0. }} be the mechanism that outputs 1 with probability (c((x, D),e/k e/k, 8/k) and 0 otherwise. Then Msplit post-processes the output of the mechanisms Mr by including the items whose mechanisms output when sufficient to prove that the composition of the mechanisms (Mæ)zex is (s, -diffccrentially private.
D. Therefore, it is
Fix any pair of neighboring datasets D and D'. Since each user contributes at most i items, we know that for all but most of the items æ. the mechanism M, has exactly the same output distribution on D and D', since c(z, D) c(x, D'). Intuitively, it follows that when we apply composition theorem to the collection (Mz that we only need to "pay" for of the mechanisms (instead of all ())). This is formalized in Lemma C. Finally, prior work establishes that, due to the definition of each mechanism M, (e/k: - private. It follows that Mspii is (e, 8) diffferrrttt private, required.
33

---

The following easy lemma is needed in the proof of Lemma 3.1
Lemma C.1. Let M1 : DD + "/,...,,M Mn 'D + Vn be a collection of (E. -i-iifferentially private mechanisms with each V; being finite. Say that MI...., Ma are k-aligned if for every pair of neighboring datasets D and D' we have that Mc(D) has the same distribution as Mc(D") except for at most indices i E [n]. Then the composite mechanism M = (ke, kDP
(D.)) is
Proof. Fix pair of datasets D and D' and suppose without loss of generality that the mechanisms are numbered so that (D) has the same distribution as (D')') for all > k (i.e., all of the mechanisms with different distributions are in the first k). Let B 341 x ... V& and A Ya+1 X ... x I', and let AI and 1g denote the projections from V X .... x to and B, respectively.
For any output set O C 31 x x... x Vn of the composite mechanism and any value E A let O== denote the set {(b, a) 1 B and (b, a) E O}, which the "slice" of O where the components in A are equal to a. Then we have
Pr(M(DD E e0) Σ
Pr(M(D) 0 (L a) Pr(II((((D)) = aa)
aEA
Σ
) (MTM)) = a)
aEA
Σ ( Pr(T))(((D))) =
aeA
Pr(TT((((D') E (0 ) Pr(T((((()) =m)) + 1-
c
aEA
(D) E 0) + k5,
where the inequality follows from the fact that II (DM)) is the composition of i (c, mechannsmss and, by assumption, (D)) has the same distribution as II (D')...
C.1 An alternative bicriteria algorithm
In this section, we present an alternative construction of a bicriteria algorithm. This algorithm achieves weaker guarantees compared to the one presented in Section 3.2 but it leverages different ideas, some of which might be useful in other applications. Before describing this alternative algorithm, we introduce tools from prior work that are needed for the construction.
Sparse vector with individual charging, Recall the celebrated sparse vector technique introduced by Dwork al. [2009]: Given a dataset 1) and threshold t. the goal is to privately identify the first query q. out of a sequence of queries whose value on the dataset D is "significant" i.e., qi (D) Z t. Following Dwork
al. [2009], this technique was extended by Bun al. (2017) to allow for identifying the first query that whose value is "close" to the threshold t. More specifically, they introduced an algorithm called BetweenThresholdd. with the following properties: In each round
i = 1,,,3,.... when getting the next query g. algorithm Between Thresholds guarantees that:
1) If (D) < t then the algorithm returns and continues to the next round.
2) Else if qi (D) >> then the algorithm returns H and continues to the next round.
3) Else (i.e., (D) t) then the algorithm returns T and halts.
The surprising aspect here as was first shown by Dwork et al. [2009] is that the privacy parameters of BetweenThreehhllde do not scale with the number of queries. That is, the algorithm maintains (c, D)DP no matter how many queries it received before halting. What if we need to identify more than query, say the first i queries whose value on D is roughly t? The textbook approach for this would to re-execute algorithm BetweenThresholldd after every T answer, paying in composition.
Kaplan et al. 2021 showed that this can be significantly relaxed. They introduced variant of the sparse vector technique called individual charging. Instead of halting after the first answer, the algorithm deletes from D all elements that "contributed" to this answer (at most ss t elements) and
34

---

continues. More specifically, the algorithm of Kaplan et al. [2021] processes the next query as BetweenThresholds with item (3) replaced by:
3) Else (i.e., (D( z t) then the algorithm returns T, deletes from D all users such that (:()) = 1, | For the sake of this informal presentation, us interpret (((D) R L as qi( D) E t + A for some error parameter A.
and continues to the next round
algorithm, answers of type and H are obtained "for free". But now a T answer does not halt the algorithm altogether; instead we only "pay" for it by deleting some of the items from the data (at most Ra 1), and continue. For example, if there are k queries with value x t that involve different elements in D, then the algorithm of Kaplan et al. [2021] identifies all of these queries at the price of one execution of SetteenThresseee oooreshhlds (instead of k executions), thus avoiding the cost of composition. The algorithm of Kaplan et al. [2021] was later optimized by Cohen and Lyu 2023]; J we will use their optimized version.
In other words, like with the standard NetweenThreshol
Overview of our bicriteria approximation. At high level, the algorithm works as follows. Let t= 2A, where A as defined in 3 above. With this choice of t, the algorithm only returns on queries whose value is between A and 3AA. Now, given a dataset D containing items from universe X' we do the following: For every x E X, issue the counting query is to the algorithm of Cohen and Lyu (023) (this query simply counts the number of occurrences of x in D). We then report all items a for which we got an answer of H or T. We show that this algorithm obtains the aforementioned approximation bound. This includes overcoming three main obstacles:
The algorithms of Kaplan et al. [2021]. Cohen and Lyu 2023 do not operate with the optimal reporting probabilities x. That is, for an item r with count c(z), the probability that the algorithm returns or H on the query 9r is strictly smaller than 7 (c(x)); e, 8), since it operates using Laplace noise and thresholding. To overcome this, we bound the optimal reporting probabilities in terms of the Laplace reporting probabilities.
2. In the analysis we need to argue about the effect of elements that the algorithm deletes from D during runtime. We do this via a charging argument, showing that if elements are deleted throughout the execution, then the algorithm must have reported at least R x elements.
3. The algorithm of Cohen and Lyu 2023 can return H or T even if c(x) 0 (with very small probability). Therefore, we refrain from applying this algorithm to items with count zero. Furthermore, to compete with II( E', 8') we have to deterministically report items such that (c((r), 6') 1. Thus we refrain from applying the algorithm to these items as well. These exclusions require some care in our privacy analysis.
We now formally introduce the algorithm of Kaplann et
2021
Cohen and Lyu 2023
Algorithm 2 BetseenThreehoolds with Charging Kaplan et al.) 2021 Cohen and Lyu 2023]
Input: Dataset D, "hit" budget > O, privacy parameter > 0, thresholds tę < fr.
1. For every user j E D set C2 =
2. For round i = 1, 2,..... do:
(a) Receive counting query fa
(b) fo + f((D) - Lap(
(c) If f < 4 then return L. If f I, then return H. Otherwise:
For each j e D such that fB, do:
-C, Cj + 1.
CI then remove B, from D.
. Reetum T.
Theorem C.2 CChen and Lyu 2023)) ). Let s < 1 and let te < t, be such that t, - -t 2 3. Algo-
rithm is (65T, e +/t)) In particular, for 7 = 4 In())) we get that Algorithm is (24s In 1 6)- DP.
Here we think of as counting query, meaning that it is predicate detined over the data domain X, and for dataset S E X" define g(S) Exes 9(z).
35

---

We are now ready to formally present our bicriteria approximation algorithm.
Algorithm 3 Bicriteria
Notation: Let & denote the contribution bound, let A' be domain of items, and let Ax,a {B $ X' |B] & k} denote the set of all possible bags of size at most & from X.
Input: Dataset D
A k privacy parameter 0.
1. Instantiate BetweenThreeholdd (Algorithm 2 D with parameters 4ln(z),
privacy parameter é 2 and thresholds In and tt
2. For each æ E X do:
(a) c(2 D) then do not report a and proceed to the next iteration.
(b) Else if c(x, D) 2 t + ln())) then report x: and proceed to the next iteration.
(c) Otherwise:
Feed the counting query c(x, D) to Algorithm BetweenThresholoo ds and obtain an answer a.
If a L then do not report and proceed to the next iteration.
If a E (T, H} then report x and proceed the next iteration.
Algorithm does not really need to explicitly traverse all I E X' as we can skip items to which no user contributes.
Similarly to Algorithm Bicrit (presented Section 3.2
The next lemma captures the privacy guarantees of Algorithm This mostly follows from the privacy guarantees of BetweenThresholee however, in order to handle the fact that in Steps 2a and 2 of Algorithm 3 we make a deterministic decision (without issuing any query to algorithm allow later relate the reporting probabilities of our algorithm with the optimal reporting probabilities.
as captured by Theorem C.2 The proof does require some care,
This is necessary in order
Lemma C.3. Algorithm Bieriteria is ( (ke" ())-D.
Proof. Fix two neighboring datasets D and D D U (B) for B f2 [z) where z < k. Our goal is to show that
Bicriteria(D") Bicriteria(D')
For the sake of the analysis, consider modified variant of Algorithm Bicriteria, denoted as Bicriteriape. D and defined as follows. Algorithm Bicriteriap,,r n is identical to Bicriteria, except that in iterations on items I such that E B, Algorithm Bicriteriago p does not perform Steps 22 and 2bb Note that Algorithm Bicriteriage D "knows" the two datasets Do DJ, and it being applied to one of them, Also note that we only modify iterations corresponding to items E B.
We first argue that
Bicriteriape.. (D") (c,5) Bicriteriapp.
This follows the outcome of Bicriteriape, (D') can be viewed a post-processing of the outcome of BetxeenThresholdd(("" DO DD_ but not Dd, and after interacting with Betxeen/hrresholds/ (D*) it generates outcome Algorithm A attempts to
To see this, we design algorithm A that knows
that is distributed exactly as the outcome of Between/Threesholds perform as much of the computation of Bicriteriap , (D*) by itself, and only interacts with BetweenThreshol.. poossolls([))) dD(") when necessary. Specifically, Algorithm A mimics the loop of Step 2 and behaves differently on iterations where x E B and where x & B: If E then queries BetweenThreshol ds D*) and proceeds according to Step 2c (recall that in such iterations we do not perform Steps and 2b If & B then A can perfectly simulate this iteration without accessing the data holder RetweenThrreshl lds( D*). In both cases A maintains the counts Cj. and excludes rows j from the computation once they have reached their cap of This shows that Bicriteriapy D (D*) can be written post-processing of BetweenThrrehoods((())
36

---

Next, note that the outcome distributions of Bicriteria(D") and Bicriteriaps, (D*)
are within statistical distance kōe To see this, note that throughout the execution of Bicriteriape, p (D%) there are at most Σ iterations of Step in which BarchBiriiapppppp (D")
issues a query to Algorithm Between/Treehhold even though Bicriteria(D)) would not have queried (because makes deterministic decision in Steps 2a oa 2b) which Bicriteriape.r (D") skips over). Recall that whenever BetweenThresho Laplace distribution. Define the good event stating that during all of these (at most 2) queries to BetweenThresholle the Laplace noises that are sampled are bounded in absolute value by (n()) By the properties the Laplace distribution and by a union bound, this event occurs with probability at least - kōe When this event happens, in all these (at most 2) iterations, the answer reported by Bicriteriap,, p (D)) is identical to the (deterministic) answer reported by (icriteria(D"). Furthermore, none of these queries to BetweenThreshoode results in T, and thus do not change the internal state of BetweenThresholds. This shows that Bicriteria(D") and Bicrit Sicriteriapo, Di (D)) are within statistical distance kdef.
queried, it samples one RV from the
Overall,
Bicriteria(D") (oo,kee)) Bicriteriago ,D' (D))
((e,6) Bicriteriap p (D*)
((o,beet) (
showing that Bicriteria (e, 6(1 + ke )--D
We now proceed with the utility analysis of Algorithm 3 As we mentioned, the first step here is to relate the optimal reporting probabilities with the reporting probabilities that arise from our algorithm, which we refer as the Laplace reporting probabilities, defined as follows.
Definition C.1. The reporting probability of the Laplace mechanism with parameters e, 5 are
in =
Taap (n;
Pr I Lap(t) 1,
In 23 1]
fisne n In 2 (n()))))] +1
else
Remark C.4. The parameters in Definition C.1 were chosen such that for 1 we have (1;E, 8) and for n' = In(
+ we have TLap(n' (n';e,
ô. The choice
for n' could be slightly improved by tuning to 8) rather than (1 5), which we did not do for simplicity.
Lemma C.5. Let < 1/2 and 8 < 10 For every it holds that
26 2 T(nEE,)). E
Lap n;
-
Proof. We prove the lemma for the following definition mLaps which for our choice of e, wise smaller (for every n) compared to Definition C.1
0. Pr in Lap(?) 1 In())]
if = 0
Laap E, 6)
if S n < In 65
else
37

---

The proof proceeds by case analysis based on the value of n. We begin with the case that -
Lap - In( ) In this case we have that
swwttch
20
Lap 28,
6 exep(( 22 dx
- 21 Iuf
exp(2en
In(
28
exp(22n)
E 8 et -1
2 (n;
Let now consider in the range this range we have
Lap switch wwitchh/+ where switch
1 +
In(
(e*+1)8 |.
In
28
1
T Lap
n;; 2E.
=
+
E exxx(22xx)ds
2
-n+ 20
In( +
=
exp( 2en + In(
2
28
exp( -2n)..
48
opt Recall that "switch is the first crossover point of and that for smaller than this we have that e (n;e, = 5 -- Thus, we need show that for n E (awiitchr opt switch) holds that
exp( (-en 2 8 -1
48
Simplifying the above inequality, it suffices to show that
f(n) A 2en
en
1
+
E
5 0.
46
Note that the function 2x3 x is increasing on (-00, 0), decreasing on (0, 36 ), and increasing again
Lap on (2 00). So the maximum of f(n) for [n swwtchh? n "wiitchl must be taken at the endpoints. We calculate:
f(n Lap = (
e
c +
1)
= 1 (
22
E
< 0,
25
28
48
2 28
26
where the last inequality holds whenever
5. Similarly,
(n S 26
e + 28 3
e²
ee + 28 -
- + 6
(e +16
(e + 1)6
46
(+)
It can be verified that the expression denoted by (+) is at most which case
- whenever S and d < 100 in
( opt
<
22
c + 28 -17
+ 45
E
6
(ee + 1)5
28
6
+
6
(er + 1)6
48
C2E
E
1
+
8
6(eF
+ 1122 8
4
8 8
2e
100 +
< 0.
6(e- 1)22
38

---

We now proceed to study values for in the range E (n Rend] where Hend As before, the reporting probability of Laplace this range (and actually for every n 2 n1 "wwitch)) is
Lapp
Lap A In( 2482 )
20
TLap
n1; 28,
exp( exxp(-2en) 22n).
46
As for π in that range, first observe that the second crossover point of the optimal reporting probabili- ties, denoted n opt is larger than Lap Indeed, when = S 1/2. Rend
c
28
1
1
c
-1
(1 of o e+1)) -1
n Bend
In
In
1
E
(ee
+ 1)6
E
1
In
In
g2
IV
66
982
IV
In
n end
Lap
2482
Thus, for every n E
[n
switch+
opt
n
Lap
we have
(n;
(1
ns
1+
5
+
en
e
e
opt
E, 8)
e
-
ne
m opt
1
8
+ e
en
opt
e + 8
e
e +
8
e +0 0
e-m swithh
1+
e
-1
c 1
e
8
8
1 6
e
e +1
8
E 28
1- 8
+ 1
+
(c + 1)5
6
e +1
8
e + 28
1
11
e
(e + 1)6
4
8
6
11 e
en
-
1
38
4'
So suffices to verify that
E -2m)
exp(
2 1
++
5
e
En
E
48
38
4
which holds whenever
5
exp( -2m))
2n
E
35
4'
ie., whenever,
1
en
E
en
48
3
Note that 1 - en
> 1 in our current range. Thus, it suffices to verify that
6
8
245
E
which holds for every n S
Rend = In 2482
Lap
All in all, for all n < n Red we have that
Lap
28 n;; 2e
Lap
-
2
T(n;e,))
8
39

---

Lap Finally, for n > Rend we have that
28 8
Lap n:: n:2e, 2 mT)E,,)).
We now ready analyze the utility of our bicriteria algorithm. Lemma C.6. The expected number or identified items Algorithm Bicriteriais Ed
Ω2 ( (n)n)))) -II (1,2 (D, (n(1/s) ( k
(m((1/)))
Proof. Let us consider a variant of Algorithm Bicriteria, called BicriteriaNoDel, which is identical to Bicriteria except that in Step [ we initialize Algorithm BetweenThresholld. with parameter 7 oo. This means that rows are never deleted from D during the execution of BetweenThrosholds in BicriteriaNoDel.
The resulting algorithm BicriteriaNoDel is not DP (with satisfactory privacy parameters), but its utility is high, in the sense that it achieves the Laplace reporting probabilities. Specifically, for every dataset D we have
B|[BicriterriaMooall11 2 ITap (D
TLap (dlo):
(m((188) ( .).
Σ ZED
In(1/5)
We begin by showing that the utility of Bicriteria is comparable that of BicriteriaNoDel. To this end, let R denote the internal randomness of Bicriteria (or BicriteriaNaDell, which we represent as a vector consisting of | samples from the Laplace distribution. We write Bicriteria, or Bi Bicriten wwrieeriaaooeee teriaNoDel, to denote these algorithms after fixing r. We next argue that for every and D it holds that
Bicriteria, (D)] (D)I 2
|Bicriterrialooel,.())
where A = 4, + (n( (n is the maximal possible value for c(ar, D) with which might issue a query to denote the set of all points that are reported by Bi bicriteriaNoDe,,()) During the execution of Bicriteria,, (eriia,())) some of the items in A might not get reported. Specifically, an item a e A might get reported if previous iterations of the algorithm deleted rows from D that involve a. Otherwise, a would be reported just as in the execution of Bicri teri aNo
during an iteration of Step 2 To see this, let A C X
Definition C.2. We say that an item a E A is compromised previous iterations of (icréteria, (before the iteration on a) deleted rows that involve the item
Let R C A denote the set of compromised items. Note that all items EA\ R (which are not compromised) are reported by (Drriteria,,)). We now show at least 7 [ of the items in are reported by Bicriteria, (D).
To this end, recall that every row in the dataset contains most items. Thus, in order to have [R] [R] compromised items we must delete at least A rows from the dataset. In order for this to happen, the
sum of the counters maintained by algorithm BetweenThresholde we delete a row only once its counter reaches r). In order for this to be the happen, we must observe least |||r AA iterations in which algorithm BetzeenThreeholld returns T. (This is because the counters are only increased during iterations with a answer, and at most A counters are increased). Finally recall that in iterations with T answer we report the corresponding item. Thus, if there [R] compromised items, then Algorithm Bicriteria,, D) reports at least R
must be least |R]T I (because
items.
AA
Now, if [
A| then the number of items reported by Bicriteria, (D) is at least 2
|
1
FA
2
and otherwise this number is at least 2 have that
[A] (as all non compromised items get reported). So any case
|A]T
Bicriteria, (D))
|BicriteriaNoDel,((D)
2Ak
2Ak
40

---

Overall,
E[Bicriteria(D]]
[[BBicriterialbbee[00
2
2 2
T
D2Ω
E
.6)
In(1/8)
2 T
ed
IT
D2Ω
2
In(1/8)
In(1/5)
Eō
20
D2Ω
h
In
In
(n(1/8)
In (n(1/8)
where the second-to- loond-to-last inequality follows from Lemma
C.5
C.2 Extreme privacy regimes omitted proofs
We start with the following straightforward lemma about Man-
Mat(D;0 Lemma C.7. Let Mati D;; 8) be the mechanism that returns the union of items D with probability 6 and the empty otherwise. Then Mall is (0, (0, diffferentilll private set union mechanism.
Proof. It is clear that the output of Man (D) is always a subset the union of D, so it remains to check that Man (0, 5) diffferrentialyy private. Fix any pair of neighboring datasets D and D' (in fact, the proof works for any pair of datasets, even if they are not neighbors) and let U and U be their unions, respectively. Then for any output set O, have that
Pr(Mai (D) E 0) 110 OJ(1 19(1-00 6) + IU E 0088
110 0J(1 -1(110) 6) IQU 006 EO) IUU" O))6
S Pr(Mai( E (0) 5
as required.
We now restate and prove Lemma 3.6
Lemma 3.6. Let Murge Dze, 5, k) be the following mechanism: let 8' = 5 1in(m, 1/e) and output the union of Mar(D; 8') and M Mypti (D;e, union mechanism. Furthermore, for any contribution bound k. dataset D with contributions bounded by k, and privacy parameter 8, we have that
8', k). Then Miage is an (s, -)dfferrrenllllll private set
Mirge (MMMgggeD;; eD; k,k, II(D;e,8)
lim +0000
1.
Proof. From basic composition together with the privacy guarantees from Lemma C.7 and Lemma 3.1 it follows that Marge is (s, -D. Next, since Mall and Maplie both output subsets of their input dataset, the union of their outputs is also subset of the input. remains prove the utility guarantee.
Let D1 = fx E X c(x, D) 1} be the set of items that appear in exactly once, and D fx E X c(x, D) 1} be the set of items that appear in D two more times. Then have that
I(D;s,0) = Σ m(((z, D);
ZEX
Σ (1;e,,0 8) + Σ (2;
2
zED.
zED
5 Dil + min(1, e5 6, e 25)) D>1l,
where the inequality follows from the fact that π is non-decreasing and the last equality follows from
the fact that 77 (1; d) = 8 and the recursive definition of (2; 8). (i.e. we have that (T) < m
and (1 (2))ee 4 (1 ((1)) Taking the limit as g - oc we have that lim (D);,,8)
8- Dil + DDsll
41

---

Since we are interested in the utility of Marge only when E - oo if suffices to determine the expected
output size of Muzze when > 1/6. In this case, have that 8' = 1/E and é 8' 1/E, which gives:
Marge (;E,,,K)]]=
[pl1-Eprr(a E Marge TEX
Pr(x
For any item x E D1, we have that
Pr(x E Mange
Pr(xe E M = 5 11/6.
Next, for any item D>1, we have that
Pr(x E Marg (Die, 6, k)) 2 Pr(æ E Mapii (D;e, 1/e)) 2 m(2;e/k,1/e)
min((1 e /e + e/ 2/8))
Putting it together, we have that
Migee ( D; e, k)]] 2 (6 1/e) [Di + min(1, // 1/8,e c/k 2/e)) |D>1]=
Taking the limit as + oo gives that limg- Munge (D; k)]l 8 |Di| + |D>1]-
Since both limits exist and are equal, follows that
EigMa ED; 6, R)]] 1, II(D;E,6)
lim 51000
required.
42


Reviews:
[{"review_id": "RWQPE0vGTj", "reviewer": "Reviewer_wdtm", "summary": "This paper studies the problem of differentially private set union: given a collection of sets $ D = (B\\_i)\\_{i=1}^n $, each contributed by an individual, output a set $ Y $ approximating $ \\\\bigcup\\_{i=1}^n B\\_I $ in an $ ( \\\\varepsilon, \\\\delta ) $-differentially-private way.\n$ Y $ must be a subset of $ \\\\bigcup\\_{i=1}^n B\\_I $, and the goal is to make it as large as possible subject to that constraint.\n\nA key parameter is $ k $, an upper bound on the cardinality of each $ B\\_i $.\n\nThe paper presents new mechanisms for this problem, and also proves impossibility results.\n\nPrevious work showed there is a function $ \\\\Pi(D,\\\\varepsilon,\\\\delta) $ which upper bounds the performance of any $ (\\\\varepsilon,\\\\delta) $-DP mechanism on a particular dataset $D$, and that when $k=1$ there is a mechanism that achieves this for all datasets $D$.\n\nThis paper shows that in contrast, when $k>1$, no mechanism can achieve the $ \\\\Pi(D,\\\\varepsilon,\\\\delta) $ bound for all datasets, even in the \"easy\" case when $ \\\\Pi(D,\\\\varepsilon,\\\\delta) $ is on the order of the size of the answer.\n\nOn the other hand, the paper describes new mechanisms for the $k>1$ regime.\nOne of them achieves a provable performance guarantee for all datasets (which necessarily is worse than $ \\\\Pi(D,\\\\varepsilon,\\\\delta) $).\nThe other mechanism is parameterized by an estimate $D$ of the true output, and achieves the limit $ \\\\Pi(D,\\\\varepsilon,\\\\delta) $ if the estimate is exactly correct, with performance decreasing as the quality of the estimate decreases (while always satisfying the privacy requirement, even if the estimate is completely wrong).\nIt is worth noting that the trivial strategy of always outputting $D$ is not allowed, since the mechanism's output must always be a subset of the true answer.", "questions": "- I'm not sure Definition 1.1 has the right citation. I have not checked carefully, but my understanding is Dwork et al's \"Calibrating noise to sensitivity in ...\" only introduced $\\\\epsilon$-DP. I have seen the $(\\\\epsilon,\\\\delta\\)$ version in Definition 1.1 attributed to Dwork, Kenthapadi, McSherry, Mironov, Naor's \"Our Data, Ourselves: Privacy via Distributed Noise Generation\" in Eurocrypt 2006. Probably that one should be cited. (I skimmed that paper, it looks like they call it \"$\\\\delta$-approximate $\\\\varepsilon$-indistinguishability\", and they seem to be presenting it as an original definition.)\n\n- The definition of $\\\\Pi(D,\\\\varepsilon,\\\\delta)$ on lines 56–60 doesn't say what happens when $\\\\varepsilon=0$. At least, the constants $c\\_\\\\ell,c\\_h$ have $1/\\\\varepsilon$ in them. The $\\\\varepsilon=0$ case comes up on line 87, and in the statements of Theorems 2.1 and 2.2, and on line 267.\n\n- Line 83 describes \"the bounds rougly mirroring the behavior in Figure 2\", but for large $\\\\varepsilon$, Figure 2 seems to contradict the bound in question, since the utility ratio starts to increase again and eventually reaches 1 as $ \\\\varepsilon $ increases. I guess it is not really a contradiction because Theorem 1.1's minimum value for $\\\\delta$ depends on $\\\\varepsilon$, and so maybe it is not satisfied on the right side of Figure 2. Still, it makes that text on line 83 look untrue. (Or did I misunderstand something here?)\n\n- The second bound in Theorem 1.1 (lines 80-81) has an unspecified dependence on $n$. This is indicated by the subscript $n$ in the $\\\\tilde{O}\\_n$ notation, but it may be unusual or unintuitive enough that it's worth commenting on in the prose: how exactly should one think of this bound? What does it mean? At least, I found it a bit tricky to wrap my head around, since usually $n$ is the increasing variable in asymptotic bounds.\n\n- Line 236: Not strictly necessary, but it would be nice to hear more about what $B\\_i$ is. Is there a precise mathematical definition of $B\\_i$ in terms of the query $q\\_i$ and dataset $D$? Or maybe an example would be appropriate, just to give some intuition?\n\n- Small things:\n\n\t- Line 38: \"Two datasets $D$ and $D'$ as neighboring...\" seems to be be missing something, e.g. \"We consider two datasets $D$ and $D'$ as neighbouring...\".\n\n\t- Line 135: \"after removing user $i$\": unless I missed it, $i$ isn't defined here. I guess you mean user 1?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "# Strengh: Clear writing\n\nThe paper was a pleasure to read. The background and the new results were easy to understand.\n\n# Strength: New mechanisms for private set union\n\nThe paper describes two new mechanisms for private set union with $k>1$: a general-purpose one (Theorem 1.2) and one that takes advantage of a prediction of what the set union is likely to include (Theorem 1.3) to get a surprising accuracy guarantee.\n\n# Strength: Impossibility results and mathematical analyses\n\nThe paper includes impossibility results that their new mechanisms can be compared to, as well as rigorous mathematical analyses of the new mechanisms.\n(The reduction from matrix marginals in the proof of Theorem 2.3 was nice and pleasingly simple.)\n\nAlso, there as an interesting use of linear programming to show the best utility ratios acheivable for certain ranges of parameters. (Lines 73-76 and Figure 2.)\n\n# Minor weakness: no empirical evaluation\n\nThe paper stands on its own as it is, but it would have been nice to see the method tried out, even on synthetic data.\nIt's always nice to see an example when understanding the performance of something.", "was_revised": true, "final_justification": "I only had relatively minor questions and the authors have addressed them. I'm maintaining my original positive rating.", "rebuttal": "Thank you for taking the time to review our work. We address your specific points below.\n\n**> I'm not sure Definition 1.1 has the right citation**\n\nAgreed. This was indeed a mistake and we will update the citation.\n\n**> The definition of $\\Pi(D, \\epsilon, \\delta)$ on lines 56-60 doesn't say what happens when epsilon=0**\n\nIn the case when $\\epsilon = 0$, we have $\\pi(c, \\epsilon, \\delta) = \\min(c \\delta, 1)$. We will clarify this in the paper.\n\n**> Line 83 describes \"the bounds roughly mirroring the behavior in Figure 2\", but for large k, Figure 2 seems to contradict the bound in question, since the utility ratio starts to increase again and eventually reaches 1 as k increases. I guess it is not really a contradiction because Theorem 1.1's minimum value for k depends on epsilon, and so maybe it is not satisfied on the right side of Figure 2. Still, it makes that text on line 83 look untrue. (Or did I misunderstand something here?)**\n\nYour understanding is correct, our impossibility results establish combinations of the privacy parameters $\\epsilon$ and $\\delta$ under which high utility ratios are impossible. But, for fixed $\\delta$, taking $\\epsilon$ to zero or infinity allows for a utility ratio of 1 (see Lemmas 3.3 and 3.4), which matches the behavior in the plots.  We intended for the text on line 83 to point out that the curves for each value of k have minimum values near 1/k, the worst-case ratio from the first part of Theorem 1.1. We agree that it is currently confusing and we will revise the text.\n\n**> The second bound in Theorem 1.1 (lines 80-81) has an unspecified dependence on n. This is indicated by the subscript n in the $\\tilde O_n$ notation, but it may be unusual or unintuitive enough that it's worth commenting on in the prose: how exactly should one think of this bound? What does it mean? At least, I found it a bit tricky to wrap my head around, since usually n is the increasing variable in asymptotic bounds**\n\nThe main focus of our paper is to study how the user contribution limit k impacts the utility ratio, so we emphasize the dependence on k in Theorem 1.1. The full bound is presented in Theorem 2.3, which includes the dependence on n. The bound holds when k is large compared to n and hence we include n as a subscript. We will clarify the notation used in Theorem 1.1 in the revision. \n\n**> Line 236: Not strictly necessary, but it would be nice to hear more about what $B_i$ is. Is there a precise mathematical definition of $B_i$ in terms of the query $q_i$ and dataset $D$? Or maybe an example would be appropriate, just to give some intuition?**\n\nThe current text on line 236 uses clashing notation with the rest of the paper which we will address. In the work of Kaplan et al., the query $q_i$ counts the number of users u that match a predicate q and the set of users to remove (denoted by $B_i$ in the current version) contains all users u for which q(u) = 1.\n\n**> Line 38: \"Two datasets D and D' as neighboring...\" seems to be be missing something, e.g. \"We consider two datasets D and D' as neighbouring...\"**\n\nRight. We will fix this typo.\n\n**> Line 135: \"after removing user i\": unless I missed it, i isn't defined here. I guess you mean user 1?**\n\nRight. We will fix this typo."}, {"review_id": "3oJtN3Z7eY", "reviewer": "Reviewer_Y51E", "summary": "This paper investigates the private set union problem when each user may contribute multiple items. The authors introduce a new performance metric called the “utility ratio,” which normalizes expected output size by a dataset-specific upper bound and measures worst-case performance across all datasets. They prove that instance-optimal algorithms exist for the single-contribution case but fail when users can submit multiple items, characterizing how performance degrades as the maximum contribution count grows. For settings with a prior histogram prediction, they design a mechanism that achieves the optimal utility ratio when the prediction is exact and degrades gracefully with prediction error. Both theoretical analyses and empirical evaluations across various settings demonstrate that their algorithms achieve optimal or near-optimal utility ratios.", "questions": "For high-k scenarios where per-user contribution counts are large, are there feasible algorithmic improvements or relaxation schemes to mitigate the performance degradation?\n\nWhat are the computational and communication costs of the mechanisms, and how do they compare empirically to existing methods?\n\nHow sensitive is the proposed robust mechanism to different error distributions in the prior histogram prediction?\n\nHow does the utility ratio perform across different privacy-utility trade-off points as privacy parameters ($\\epsilon$, $\\delta$) vary?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths: \n\nThe paper makes significant theoretical contributions, proving tight lower and upper bounds on the utility ratio and constructing matching algorithms. It also extends to scenarios with prior histogram information, offering robust mechanisms with provable guarantees. The work deepens our understanding of differentially private set union with multiple contributions, revealing fundamental limitations and guiding algorithm design. The introduction of the utility ratio provides a unified framework for comparing mechanisms across datasets.\n\nWeaknesses: \n\nWhile the authors characterize how the worst-case utility ratio deteriorates as per-user contribution bounds grow, they do not propose or evaluate any algorithmic techniques to mitigate this degradation. In extreme multi-item settings, the utility may drop sharply without clear avenues for improvement.\n\nThere is little discussion of the runtime complexity or messaging costs of the proposed algorithms. In privacy-constrained settings, these overheads can dominate, especially when each user contributes multiple items, but the paper omits any comparative performance profiling against existing baselines.\n\nThe robust mechanism fundamentally assumes access to a reasonably accurate prior histogram of the data distribution. However, the paper does not comprehensively explore how sensitive the overall utility is to different types of prediction errors or misspecified priors.\n\nThe work fixes privacy parameters ($\\epsilon$, $\\delta$) and does not systematically study the privacy–utility frontier. As a result, readers lack guidance on how the utility ratio behaves under tighter privacy budgets or in regimes where sensitivity amplification techniques might apply.", "was_revised": true, "final_justification": "The rebuttal has well addressed all of my initial concerns. I think this paper is technically solid, and other reviewers also recognize it as well-structured with significant theoretical contributions to differential privacy. Therefore, I recommend acceptance.", "rebuttal": "Thank you for taking the time to review our work. We address your specific points below.\n\n**> While the authors characterize how the worst-case utility ratio deteriorates as per-user contribution bounds grow, they do not propose or evaluate any algorithmic techniques to mitigate this degradation.**\n\nOur results show that in the worst case, every mechanism is subject to low utility ratios for some privacy regimes and datasets, so mitigations do not exist. However, one interesting direction that we partially address is to explore non-worst-case conditions under which mechanisms can achieve high utility ratios. Our mechanism that makes use of predictions (Section 4) is one example: in cases where a reasonably accurate prediction of the histogram is available, it is possible to do much better than our impossibility results.\n\n**> There is little discussion of the runtime complexity or messaging costs of the proposed algorithms. In privacy-constrained settings, these overheads can dominate, especially when each user contributes multiple items, but the paper omits any comparative performance profiling against existing baselines**\n\nLet $N = \\sum_i |B_i|$ denote the sum of bag sizes in an input dataset. The mechanisms discussed in Lemma 3.1, Lemma 3.4, and Theorem 4.1 all run in linear time in $N$ because they essentially build a histogram of the items that appear in the dataset and then do linear time operations on the histogram. The mechanism from Lemma 3.3 is also linear in $N$, since whenever it does not output an empty set, it just outputs the items of a randomly chosen user. Finally, the bi-criteria mechanism from Theorem 3.2 can also be implemented to run in linear time in $N$ with a bit of bookkeeping. Note that the linear dependence on N is unavoidable for any algorithm that goes over every data point. We will clarify this.\n\n**> The robust mechanism fundamentally assumes access to a reasonably accurate prior histogram of the data distribution. However, the paper does not comprehensively explore how sensitive the overall utility is to different types of prediction errors or misspecified priors**\n\nTheorem 4.1 shows that the expected output size of the mechanism that uses predictions degrades with the $\\ell_\\infty$ distance between the true and predicted dataset histograms. If the distance is $d$, then the mechanism performs as well as the Pi bound on a dataset where every item count is decreased by $d$. Studying robustness with respect to other discrepancy measures is an interesting future direction to explore. We will clarify this in the paper.\n\n**> The work fixes privacy parameters (epsilon, delta) and does not systematically study the privacy-utility frontier. As a result, readers lack guidance on how the utility ratio behaves under tighter privacy budgets or in regimes where sensitivity amplification techniques might apply**\n\nWe did not emphasize the privacy-utility frontier, but our results do characterize some interesting regions of the privacy parameter space where utility ratios are bounded in different ways. For example, Lemmas 3.3 and 3.4 show that for fixed $\\delta$, utility ratios of 1 are achievable in the limit as $\\epsilon$ tends to zero or infinity. On the other hand, for a range of intermediate $\\epsilon$ values, our results establish that utility ratios cannot be better than roughly $1/k$. Understanding implications for amplification, composition, etc. would be a nice direction for future research."}, {"review_id": "8VZoQ2Vb4G", "reviewer": "Reviewer_wkMV", "summary": "This paper studies the private set union problem in the context of differential privacy, where each user contributes a bag of up to $k$ items from a large universe. The goal is to compute a subset of the union of all user-contributed items while preserving $(\\varepsilon, \\delta)$-differential privacy. The challenge arises because reporting infrequent items can violate privacy guarantees. Unlike previous work, which focused on the case where $k = 1$, this paper generalizes the setting to $k > 1$ and provides the first theoretical utility bounds in this more general case.\n\nThe main reason the previous paper do not have a good theoretical analysis on the private set union is because that it is not trivial to formalize the utility. As mentioned by the authors, a simple example shows any $(\\varepsilon,\\delta)$-differentially private algorithm cannot output a subset with expected cardinality larger than $|\\bigcup_{i} S_i| \\cdot \\delta$, so it does not make much sense to directly analyzing the size of the output. In this paper, the authors introduce the utility ratio, which normalizes the expected utility by a dataset-specific upper bound. This allows comparison of algorithms in terms of their worst-case normalized performance. Given this measurement, the authors give several impossibility results and matching algorithms.", "questions": "In this paper, for the union set case where $k = 1$, you refer to the sampling-based algorithm from the Cohen et al. paper. I believe there is another algorithm based on thresholding the histogram:\n\n(i) Add Laplace noise with parameter $1/\\varepsilon$ to the frequency of elements in $|\\bigcup_{i} S_i|$;\n\n(ii) Output all elements whose noisy frequency exceeds a threshold $T$, where $T$ is approximately $\\log(1/\\delta)/\\epsilon$.\n\nIt should be easy to show that this algorithm is $(\\epsilon,\\delta)$-differentially private (see the proof of Lemma 5 in the paper “Releasing Search Queries and Clicks Privately,” WWW 2009 for details). Clearly, these two algorithms are not equivalent. However, I did some preliminary calculations by myself, and I believe the thresholding approach achieves asymptotically similar error bounds to the i.i.d. sampling algorithm in Cohen et al.\n\nMy motivation for comparing these two algorithms is that the thresholding method appears more intuitive. In particular, it provides a natural explanation for why $\\pi$ is a three-piece function:\n\n(i) the frequency almost surely falls below the threshold (corresponding to the case $c(x) \\leq c_{\\ell}$);\n\n(ii) the frequency almost surely exceeds the threshold (corresponding to the case $c(x) > c_{h}$); and\n\n(iii) the intermediate case.\n\nSo if they are indeed equivalent (in terms of the utility), then perhaps using the thresholding algorithms as the benchmark would be better? What do you think?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper considers an important problem in differential privacy and presents several clearly stated theoretical results. In fact, to the best of my knowledge, it is the first paper to provide any form of theoretical utility bounds for private set union with $k > 1$. (The work by Gopi et al. analyzes only the privacy guarantees, while the Cohen et al. paper implicitly handles only the special case where $k = 1$.) Here, $k$ denotes the maximum cardinality of the input subsets. Moreover, the paper is well-written and easy to follow. The proof sketches included in the main text are especially helpful in conveying the core techniques and proof ideas.\n\nIn my view, the most intuitive way to define “utility” in the context of private set union is to aim to preserve all items $x$ with reasonably large frequency $c(x)$. The function $\\pi(c(x))$ offers a strong intuition for how frequency impacts utility, making it natural to define a utility ratio for the general case of $k > 1$. This, in turn, provides a meaningful and intuitive characterization of utility for the private set union problem. It is also quite surprising that the authors are able to show tightness of their algorithm, especially given that it is significantly simpler than the algorithmic framework in Gopi et al., which involves more complex histogram updating strategies.\n\nIn conclusion, I believe this paper would be a good fit for NeurIPS.", "was_revised": true, "final_justification": "The authors properly respond my questions.", "rebuttal": "Thank you for taking the time to review our work. We address your specific points below.\n\n**> For the union set case where k=1, you refer to the sampling-based algorithm from the Cohen et al. paper. I believe there is another algorithm based on thresholding the histogram... I believe the thresholding approach achieves asymptotically similar error bounds... perhaps using the thresholding algorithms as the benchmark would be better?** \n\nWe agree that the thresholding approach is very intuitive, and that it achieves asymptotically similar error bounds. But since the strictly optimal (not just asymptotic) reporting probabilities are known in the k=1 case, and since we can actually achieve it under some assumptions (see Theorem 1.3) then we believe that working with the optimal reporting probabilities is a stronger baseline."}, {"review_id": "gZrB9oGjtO", "reviewer": "Reviewer_mdhA", "summary": "Assume each user owns a subset of at most $k$ items that belong to a large universe $\\mathcal{X}$, the Differentially Private Set Union (I prefer calling it Differentially Private Partition Selection, see comments) problem is to compute the union of the items from all users while satisfying a reasonable definition of differential privacy (DP). Previous works show that one can construct an optimal $(\\epsilon, \\delta)$-DP algorithm when each user has exactly one item. However, designing an optimal $(\\epsilon, \\delta)$-DP algorithm when each user contributes up to $k$ items is an open problem. \n\nThis paper presents several key findings for this open problem. First, Instance-optimal algorithms are not generally possible when $k > 1$. Second, it is possible to have an appropriate algorithm for settings where some public prediction regarding the union is available. Finally, the paper presents several concrete algorithms under various public predictions, accompanied by detailed proofs of privacy and utility. \n\nIn summary, this paper provides important results for the Differentially Private Partition Selection problems, helping researchers better understand its privacy boundaries.", "questions": "I cannot find a topic for NIPS 2025 that meets the topic of this paper. Could the authors formally state that the topic of this paper is considered for NIPS 2025?", "limitations": "Aside from the problem of meeting the topics of NIPS 2025, I identify that the definition of Private Set Union provided by the authors is not the one defined in the cryptography topic. Specifically, in cryptography, PSU considers several (typically two) parties each having a set, and the output of PSU is the union of sets without leveraging the intersections of these sets. The detailed definitions and constructions for two parties and multiple parties can be found in [1][2], respectively. I suggest changing the term used in this paper or having a separate description to clarify the differences between the two definitions. \n\nI have to say that the reason I bid on this paper is that I am quite familiar with the cryptographic PSU, but not the one defined in this paper. I tried my best to read the paper based on my DP knowledge, and I believe this paper is well-written. I am looking forward to seeing feedback from other reviewers. \n\n[1] Kolesnikov, V., Rosulek, M., Trieu, N., & Wang, X. Scalable private set union from symmetric-key techniques. ASIACRYPT 2019, pp. 636-666. Cham: Springer International Publishing.\n[2] Liu, Xiang, and Ying Gao. Scalable multi-party private set union from multi-query secret-shared private membership test. ASIACRYPT 2023, pp. 237-271. Singapore: Springer Nature Singapore, 2023.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\n1. Important (impossible and possible) results for the Differentially Private Partition Selection problem. \n2. Concrete algorithms under possible settings. \n3. Detailed privacy and utility proofs.\n\n# Weaknesses\n\n1. I am wondering if the topic of this paper meets one of the topics of NIPS 2025.\n2. Private Set Union has been a well-defined **cryptography** topic. I suggest changing the term \"Private Set Union\" to another one, e.g., Differentially Private Partition Selection. \n3. No implementations and experiments are given in this paper. I believe this is a minor problem since this paper focuses mainly on theoretical results.", "was_revised": true, "final_justification": "Thanks again for the authors feedback. I believe changing the name from Private Set Union to Differentially Private Set Union can reflect the specific privacy constraint that this paper targets. I suggest having a separate paragraph descrbing the definition of Private Set Union from the crypto field and explicitly state the difference.", "rebuttal": "Thank you for taking the time to review our work. We address your specific points below.\n\n**> I cannot find a topic for NIPS 2025 that meets the topic of this paper. Could the authors formally state that the topic of this paper is considered for NIPS 2025?**\n\nThe relevant topic from the NeurIPS call for papers is \"privacy\" (under \"Social and economic aspects of machine learning\"). Differential privacy is a longstanding interest of the ML community and has consistently appeared at previous conferences. (For example, the same problem has been studied in Gopi et al. (2020), which was presented at ICML 2020.)\n\n**> Private Set Union has been a well-defined cryptography topic... I suggest changing the term used in this paper or having a separate description to clarify the differences between the two definitions**\n\nWe agree and are open to changing the name. One option is to change the name to \"Differentially private set union\" to reflect the specific privacy constraint we are working with. This is also consistent with prior work such as Gopi et al. (2020), and Carvalho et al. (2022)."}]

Author rebuttal:

Meta-review: This paper considers the problem of computing a differentially private set union when each user holds at most k items. Past work provided optimal mechanisms for k=1. This work provides theoretical results for k > 1. No mechanism is optimal or can achieve high utility for every dataset. The authors therefore consider the utility ratio, a dataset-normalized utility measure, and prove impossibility results and construct algorithms with strong theoretical guarantees for utility ratio.

Reviewers were unanimously in favor of this paper. They found the problem and the results to be important, with the first substantive results for the k > 1 case and strong impossibility and possibility results, clear writing, and insightful mathematical analysis and proofs. Few or no substantive weaknesses were raised. One reviewer suggested to avoid or qualify the name “private set union” since this has a different meaning in cryptography, which is a useful suggestion. Congratulations on a well received paper.
Decision: Accept (spotlight)