Scalable Private Partition Selection via Adaptive Weighting
Authors: Justin Y. Chen
Vincent Cohen-Addad
Alessandro Epasto
Morteza Zadimoghaddam
Venue: ICML 2025 poster (2025)
Keywords: differential privacy
private partition selection
private set union
parallel algorithms
Primary area: social_aspects->privacy
TL;DR: We develop state-of-the-art parallel algorithms for differentially private partition selection.

Abstract: In the differentially private partition selection problem (a.k.a. set union, key discovery), users hold subsets of items from an unbounded universe. The goal is to output as many items as possible from the union of the users' sets while maintaining user-level differential privacy. Solutions to this problem are a core building block for many privacy-preserving ML applications including vocabulary extraction in a private corpus, computing statistics over categorical data and learning embeddings over user-provided items. We propose an algorithm for this problem, MaxAdaptiveDegree (MAD), which adaptively reroutes weight from items with weight far above the threshold needed for privacy to items with smaller weight, thereby increasing the probability that less frequent items are output.  Our algorithm can be efficiently implemented in massively parallel computation systems allowing scalability to very large datasets. We prove that our algorithm stochastically dominates the standard parallel algorithm for this problem. We also develop a two-round version of our algorithm, MAD2R, where results of the computation in the first round are used to bias the weighting in the second round to maximize the number of items output. In experiments, our algorithms provide the best results among parallel algorithms and scale to datasets with hundreds of billions of items, up to three orders of magnitude larger than those analyzed in prior works.

Scalable Private Partition Selection via Adaptive Weighting
Justin Y. Chen'
Vincent Cohen-Addad
Alessandro Epasto? Morteza Zadimoghaddam"
Abstract
Consider the example of a system releasing information the queries asked to a search engine over period of time (Korolova et al., 2009; Bavadekar et al., 2021). Such system can provide valuable insights to researchers and the public (for instance on health concerns Bavadekar et al. (2021)) but care is needed in ensuring that the queries output do not leak private and sensitive user information.
In the differentially private partition selection problem (a.k.a. private set union, private key discovery), users hold subsets of items from an unbounded universe. The goal is to output as many items as possible from the union of the users' sets while maintaining user-level differen- tial privacy. Solutions this problem are core building block for many applications including vocabulary extraction in a private corpus, computing statistics over cate- gorical data and learning embeddings over user- provided items. We propose an algorithm for this problem, MaxAdapt veDegree (MAD), which adaptively reroutes weight from items with weight far above the threshold needed for privacy to items with smaller weight, thereby increasing the proba- bility that less frequent items are output. Our algo- rithm can be efficiently implemented in massively parallel computation systems allowing scalability to very large datasets. We prove that our algo- rithm stochastically dominates the standard paral- lel algorithm for this problem. We also develop two-round version of our algorithm, MAD2R, where results of the computation in the first round are used to bias the weighting in the second round to maximize the number of items output. In ex- periments, our algorithms provide the best results among parallel algorithms and scale to datasets with hundreds of billions of items, up three orders of magnitude larger than those analyzed by prior sequential algorithms.
In this paper, focus the problem of private partition selection (Desfontaines et al., 2022; gopi et al., 2020) which models the challenge of extracting as much data as possible from such a dataset while respecting user privacy. More formally, the setting of the problem (which is also known as private set union or private key discovery) is that each user has a private subset of items (e.g., the queries issued by the user) from an unknown and unbounded universe of items (e.g., all strings). The goal is to output many of the items in the users' sets as possible (i.e., the queries issues by the users), while providing a strong notion of privacy-User level Differential Privacy (DP) (Dwork & Roth, 2014).
ML
Private partitionn selection models many challenges beyond the example above, including the problem of extracting the vocabulary (words, tokens or n-gram) present in a private corpus (Zhang al., 2022; Kim et al., 2021). This task is fundamental prerequisite for many privacy-preservin natural language processing algorithms (Wilson et al., 2019; Gopi et al., 2020), including for training language mod- els for sentence completion and response generation for emails (Kim al., 2021). Similarly, learning embedding models over categorical data often requires identify the categories present in private dataset (Ghazi et al., 2023; 2024). Partition selection underpins many other appli- cations including analyzing private streams (Cardoso & Rogers, 2022; Zhang et al., 2023), learning sparse his- tograms (Bonch et al., 2021), answering SQL queries (Des- fontaines et al., 2022) and sparsifying the gradients in the DP SGD method (Ghazi et al., 2023). Unsurprisingly given these applications, private partition selection algorithms (Korolova et al., 2009) are core building block of many standard differentially private libraries e.g., PyDP (PyDP, 2024), Google's DP Libraries (Google, 2024; Amin et al., 2022), and OpenMined DP Library (OpenMined. 2024).
1. Introduction
The availability of large amounts of user data has been one of the driving factors for the widespread adoption and rapid development of modern machine learning and data analytics.
Massaacussetts Institute of Technology, Cambridge, MA, USA "Google Research, New York, NY, USA Google Rescarch, Zurich, Switzcrland, Correspondence to: Justin Chen <juste@ mit.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Real-world datasets for these applications can be mas- sive, potentially containing hundreds of billions of data

---

Scalable Private Partition Selection via Adaptive Weighting
points, thus requiring algorithms for partition selection that can be efficiently run in large-scale data process- ing infrastrructures-e.. MapReduce (Dean & Ghemawat, 2004), Hadoop (Apache Software Foundation), Spark (Za- haria et al., 2016). In our work, we design a highly par- allelizable algorithm for this problem which requires con- stant parallel rounds in the Massively Parallel Computing model (Karloff et al., 2010) and does not assume fit the input in memory. This contrasts to prior algorithms such as (Gopi et al., 2020; Carvalho et al., 2022) which all require (with the key exception of the uniform weighting method described below) to process all the data sequentially on a single machine and assume storing the input in-memory thus precluding efficient parallelization.
Unfortunately, however, uniform weighting is lossy in that it may overallocate weight far above the threshold to high frequency items, missing opportunity to boost the weight of items closer to the decision boundary. This has inspired the design of greedy weighting schemes such as (Gopi et al., 2020; Carvalho et al., 2022) where each user's allocations depend on data of previously analyzed users. All of these algorithms are inherently sequential and require memory proportional to the items present in the data.
To our knowledge, the uniform weighting (Korolova et al., 2009) is essentially the only known solution to the private partition selection problem which is amenable to implemen- tation in a massively parallel computation framework. The sole exception is the scalable, iterative partition selection (DP-SIPS) scheme of (Swanberg et al., 2023) which has as core computation repeated invocations of the uniform weighting algorithm.
1.1. Weight and Threshold Approach
Before introducing our algorithm, we review the popular weighting- approach to partition selection which is used in many algorithms (Korolova al., 2009; Gopi et al., 2020; Carvalho et al., 2022; Swanberg al., 2023). This approach is of interest in the context of large-scald data some of its variants can be parallelized efficiently (Korolova et al., 2009; Swanberg et al., 2023).
1.2. Our Contributions
In this work, we design the first, adaptive, non- uniform weighting algorithm that is amenable to mas- sively parellel implementations. Our algorithm, called MaxAdapt i iveDegree size of the input and can be implemented in a constant num- ber of rounds in a parallel framework. From a technical point of view, the algorithm is based on a careful rerouting of overallocated weight to less frequent items, that together with delicate sensitivity analysis shows no privacy loss compared to uniform weighting. This means that that-given given the same privacy parameters-bott algorithms utilize exactly the same amount of noise and the same threshold (but our algorithm can better allocate the weight). As a result, we are able to prove that our algorithm stochastically dominates the basic, uniform weighting strategy.
requires linear work in the
Notice that differential privacy imposes to not output any item which is owned by only a single user. However, it is possible for a private algorithm to output items which appear in many different sets. This intuition is at the basis of the weighting- based algorithms.
Algorithms in this framework start by subsampling each user's set to bound the maximum number of items per user. Then, these algorithms proceed by increasing, for each user, the weight associated the items present in the user data. Fi- nally, the algorithm adds Gaussian (or Laplace) noise to the total accumulated weight of each item, and outputting all items with noised weight above certain threshold (Ko- rolova et al., 2009; Gopi et al., 2020; Carvalho et al., 2022: Swanberg et al., 2023). The amount of noise and value of the threshold depends on the privacy parameters and cru- cially on the sensitivity of the weighting function to the addition or removal of any individual user's set. Loosely speaking, the contribution of each user the item weights must be bounded in order to achieve differential privacy. Algorithms within this framework differ in the choice of how to assign item weights, but in all designs the key goal is that of limiting the sensitivity of the weighting function.
We extend our result to multiple rounds in (MAD2R), splitting our privacy budget across the rounds, running MAD in each round, and outputting the union of items found in both rounds. Similar to DP-SIPS, in the second round, we remove from the input any items found in the first round (this is private by post-processing). By careful generalization of the privacy analysis of the weight and threshold approach, we show that it is possible to also use the noisy weights from the prior round. We leverage this in two ways. First, we additionally remove items which have very small weights from the first round-these have little chance of being output in the second round. Second, we bias the weighting produced by MAD in the second round to further limit overallocation to items which received large weights in the first round. The combination of these ideas yields significant empirical improvements over both the basic algorithm and DP-SIPS.
basic strategy is uniform weighting (Korolova et al., 2009) where each user contributes equal weight each of the items in their set. It is easy bound the sensitivity of this basic weighting and thus to prove differential privacy. Because of its simplicity, the basic uniform weighting al- gorithm is extremely parallelizable requiring only basic counting operations over the items in the data.
2

---

Scalable Private Partition Selection via Adaptive Weighting
In MAD, users with a too small large of a cardinality (we equivalently refer to this as the user's degree) are labeled non-adaptive: these users will add uniform weight to their items (or biased weight in the case of MAD2R). The rest of the users participate in adaptive reweighting with the pri- vacy analysis making use of the upper bound on their degree. Initially each of these users sends a small amount of weight uniformly among their items (the total amount of weight sent per user is bounded by 1 rather than the square root of their degree, which is the case for the basic weighting algorithm). Then, items with weight significantly above the threshold are truncated to only have weight slightly above the threshold (we do not want to truncate all the way to the threshold as the added noise can decrease weights). The weight removed via truncation is returned to each user pro- portional their initial contributions. Then, users reroute carefully chosen fraction of this "excess" weight back to their items. Finally, users add additional uniform weight to their items to make up for the small amount of weight that was initially sent.
the basic algorithm and let U be the set of items oulput when using MAD as the weighting algorithm. Then, for items i E u and free parameter B 2 0,
. IfPr(i E U) < ((3), then Pr(i E U*) e
-Othewisee Pr(i E U*) 2 (3).
where & is the standard Gaussian cdf.
Compared to the basic algorithm, MAD has a higher proba- bility of outputting any item that does not reach the adaptive threshold in its initial stage as it reroutes excess weight to these items. The theorem shows that MAD stochastically dominates the basic algorithm on these items. For the re- maining items, they already have overwhelming probabil- ity of being output as their final weight before adding noise is at least several standard deviations above the threshold (this is quantitatively controlled by the parameter (). In Appendix C, we also describe a simple, concrete family of instances where MAD significantly improves upon the baselines.
Bounding the sensitivity of MAD requires careful analysis and is significantly more involved than for basic weight- ing. Several design choices made in our algorithm, such as using an initial uniform weighting inversely proportional to cardinality rather than square root of cardinality, using a minimum and maximum adaptive degree, and choosing the fraction of how much excess weight to reroute are all required for the following theorem to hold. Furthermore, we generalize the analysis of the weight and threshold paradigm to allow us use noisy weights from first round in biasing weights in the second round of MAD2R. This biasing fur- ther complicates the sensitivity analysis of MAD which we address by putting limits on the minimum and maximum bias.
Finally, we conduct experiments several publicly- available datasets with up to 800 billions of (user, item) pairs (up to three orders of magnitude larger than prior datasets used in sequential algorithms). Our algorithm outperforms scalable baselines and is competitive with the sequential baselines.
1.3. Related Work
Our algorithms are in the area of privacy preserving algo- rithms with differential privacy guarantee which the de facto standard of privacy (we refer to (Dwork & Roth, 2014) for an introduction to this area). As covered the appli- cation and prior work on private partition selection in the introduction, we now provide more details on the work most related to our paper.
Theorem 1.1 (Privacy, Informal version of Theorem B.1 and Corollary B.2). Using MAD as the weighting algorithm achieves (e, DD with the exact same noise and threshold parameters as the basic algorithm. Running MAD in two rounds with biases via MAD2R is (e, ()-P..
The differentially private partition selection problem was first studied in (Korolova al.. 2009). They utilized the now-standard approach of subsampling to limit the number of items in each user's set, constructing weights over items, and thresholding noised weights to produce the output. They proposed a version of the basic weighting algorithm which uses the Laplace mechanism rather than the Gaussian mech- anism. This algorithm was also used in (Wilson et al., 2020) within the context of a private SQL system. The problem received renewed study in (Gopi et al., 2020) where the au- thors propose generic class of greedy, sequential weighting algorithms which empirically outperform basic weighting (with either the Laplace or Gaussian mechanism). (Carvalho et al., 2022) gave an alternative greedy, sequential weighting algorithm which leverages item frequencies in cases where each user has a multiset of items. (Desfontaines et al., 2022)
Within MAD, items have their weight truncated if it exceeds an "adaptive threshold" after adding the initial weights. is set to be B standard deviations of the noise above the true threshold that will be used to determine the output where B 2 O is a free parameter of the algorithm. By design, before adding noise, every item which receives at least weight 7 in the basic algorithm will also receive weight at least 7 by MAD. Furthermore, the weights on all other items will only be increased under MAD compared to the basic algorithm. Taking the final step of adding noise, we show the following theorem.
Theorem 1.2 (Stochastic Dominance, Informal version of Theorem C) Let U be the set of items output when using
3

---

Scalable Private Partition Selection via Adaptive Weighting
analyzed in depth the optimal strategy when each user has only a single item (all sets have cardinality one). This is the only work that does not utilize the weight and thresh- old approach, but it is tailored only for this special case. The work most related to ours is DP-SIPS (Swanberg et al., 2023) which proposes the first algorithm other than basic weighting which is amenable to implementation in a paral- lel environment. DP-SIPS splits the privacy budget over a small number of rounds, runs the basic algorithm as black box each round, and iteratively removes the items found in previous rounds for future computations. This simple idea leads to large empirical improvements, giving a scalable algorithm that has competitive performance with sequential algorithms.
Algorithm Meta-algorithh for private partition selection.
Weight 6, Ao, ALG, h) Input: User sets S = {(u, Sw) HeEI)) privacy parame- ters (s, 6), degree cap Ao. weighting algorithm ALG, upper
bound on the novel foc sensitivity, function h N + R
Output: Subset of the union of user sets U C u
Ua Su, noisy weight vector Wext
I: Select corresponding the Gaussian Mechanism (Proposi- tion 2.4) for (s. (s.6/2)-DP with A2 = 1.
2: Set p t- maxic[Aol h(t) + Fa ((1 () 3)
3: for all v [x] do
4: if |f|S 2 Au then
5: Randomly subsample S. to Au items. degrees.
b Cap user
6: end if
7: end for
2. Preliminaries
8: w +- ALG(S)
D Weights on items 2
9: miii t wi( + +
D Add noise
Definition 2.1 (Differentially-Priiee Partition Selection). In the differentially- prreeittalll--rivtteeee partition selection (a.k.a. private set union or key selection) problem, there are n users with each user u having a set S., of items from an unknown and possibly infinite universe E of items: the input is of the form S {u, uem)) The goal is output a set of items U of maximum cardinality, such that U is subset of the union of the users' sets Ut = Uuein] Sw. while maintaining leerl differentially privacy.
10: U - (iEll m(i) 2 p]
t Apply threshold.
i(i
ifieu ifiEE
11: (1) N(0,0
The E E \ 4 part is only for privacy analysis (we only
ever query this vector on i E E2). 12: return U, Wext
3. Weight and Threshold Meta-Algorithm
As standard in prior work (Korolova et al., 2009; Gopi et al., 2020; Carvalho et al., 2022; Swanberg et al., 2023) we consider the central differential privacy model, where the input data is available to curator that runs the algorithm and wants to ensure differential privacy for the output of the algorithm. We now formally define these notions.
In this section, we formalize the weighting- -asse meta- algorithm used in prior solutions to the differentially private partition selection problem (Korolova et al., 2009; Gopi et al., 2020; Carvalho et al., 2022; Swanberg et al., 2023). Our algorithm MAD also falls within this high-level approach with a novel weighting algorithm that is both adaptive and scalable to massive data. We alter the presentation of the algorithm from prior work in subtle, but important, way by having the algorithm release a noisy weight vector Text in addition to the normal set of items U. This allows us to develop a two-round version of our algorithm MAD2R which queries noisy weights from the first round to give improved performance in the second round, leading to signficant em- pirical benefit.
Definition 2.2 (Neighboring Datasets). We say that two input datasets S and S' are neighboring if one can be ob- tained by removing a single user's set from the other, i.e., S' = S } for some new user c.
Definition 2.3 (Differential Privacy (Dwork & Roth, 2014)).
A randomized algorithm M is (e, d)-differentially private, or (e. 6 if for any two neighboring datasets S and S'
and for any possible subset of outputs O C (U:UU U E},
The weight and threshold meta-algorithm is given in Al- gorithm 1. Input is a set of user sets S = {(u, S.)) hue(m)- privacy parameters E and 6, a maximum degree cap Ag. and a weighting algorithm ALG (which can itself take some op- tional input parameters), and a function N + which describes the sensitivity of ALG.
Pr(M(S) E sé .Pr(((())) E 0) 8
Let Φ : R + R. be the standard Gaussian cumulative density function.
Proposition 2.4 (Gaussian Mechanism (Balle & Wang, 2018)). Let f : 'D + Rdd be a function with &2 sensitiv- ity 22. For any e > O and d E (0,1], the mechanism M(x) = fxx + Z with Z ~ NN0, 021) is (s, if
First, each user's set is randomly subsampled so that the size of each resulting set is at most Ao (the necessity of this step will be further explicated). Then, the ALG takes in the hardinality-capper sets and produces a set of weights over all items in the union. Independent Gaussian noise with standard deviation a is added each coordinate of the
22
E3
A2
20
e क
5 5.
20
A
2x
A
4

---

Scalable Private Partition Selection via Adaptive Weighting
weights, and items with weight above certain threshold p output. By construction, this algorithm will only ever output items which belong to the true union, U S U, with the size of the output depending on the number of items with noised weight above the threshold.
which are unique to the new user, and is defined the small- est value A (t) such that for all possible inputs (Su)a=1 and new user sets S.,
(t) 2 max w (1).
TET
For the sake of analysis (and not the implementation of the algorithm), we diverge from prior work to return vector Wezt of noisy weights over the entire universe E. This vector is implicitly used in the proof of privacy for releasing the set of items& U, but it is never materialized as | is unbounded. Within our algorithms, we will ensure that we only ever query entries of this vector which belong to U1 so we only ever have to materialize those entries. Note, however, that it would not be private to release @ as the output of a final algorithm the domain of that vector exactly the true union of the users' sets.
Then, the calculation of p to obtain (c, 8)DP is obtained based on the novel foe sensitivity, 6, a, and Do. This is formalized in the following theorem whose proof is given in Appendix B.
Theorem 3.3. Let (E, Ao, ALG, h be inputs Algo- rithm I. If ALG has bounded Eg and novel loo sensitivities
A 21 and (1) S h()),
then releasing U, Wext satisfies (e, ()-P)
The privacy of this algorithm depends on certain "sensitivity" properties of ALG as well as our choice of a and Consider any pair of neighboring inputs S and S' = S U {(v, S.)}. let U and ut be the corresponding unions, and let w and w/ be the item weights assigned by ALG on the two inputs, respectively,
4. Maximum Adaptive Degree Weighting
Our main result is an adaptive weighting algorithm MaxAdaptiveDegre (MAD) which is amenable to par- allel implementations and has the exact same lg and novel fo sensitivities as Basic. Therefore, within the weight and threshold meta-algorithm, both algorithms utilize the same noise and threshold p to maintain privacy. Our algo- rithm improves upon Basic by reallocating weight from items far above the threshold to other items.
Definition 3.1. The fg sensitivity of weighting algorithm is defined as the smallest value 22 such that,
2
Σ (wi(i)- w(t))² + Σ w'))3. iEM
SEL'VU
We present the full algorithm in Algorithm 2. For sim- plicity, we will first describe the "unbiased" version of our algorithm where b, bmins bmaz are set to ones and UserWei WhtttisSghtss b, Dyinn dmaa) is a vector of weights over all items with 1/v/s.. for every i E S, and zeros in other coordinates. The algorithm takes two additional parameters: a maximum adaptive degree dmaz E og] and an adaptive threshold T = p + Bo for free parame- ter B 2 O. Users with set cardinalities greater than dmaa are set aside and contribute basic uniform weights to their items at the end of the algorithm. The rest of the users participate in adaptive reweighting. We start from a uniform weighting where each user sends 1/1swl weight each of their items. Items have their weights truncated to and any excess weight is sent back to the users proportional to the amount they contributed. Users then reroute a carefully chosen fraction (depending on dmaa) of this excess weight across their items. Finally, each user adds 1/v1s.| 1/|s.. to the weight of each of their items.
Given bounded &g sensitivity, choosing the scale of noise o appropriately for the Gaussian mechanism in Proposition 2.4 ensures that outputting the noised weights on items in U satisfies (e, -DP.. So if we knew U, then the output of the algorithm after thresholding would be private via post- processing.
However, knowledge of the union 24 is exactly the problem we want to solve. The challenge is that there may be items in lt which do not appear in U. Let T 22 \ L be these "novel" items with f = T) As long as the probability that output by the algorithm is most 2
any of these items (e, 6)DD will be maintained. Consider a single item i E T which has zero probability of being output by weight and threshold algorithm run on S but is given some weight w/ (i) when ALG is run on S'. The item will be output only if after adding the Gaussian noise with standard deviation a, the noised weight exceeds p. The probability that any item in T is output follows from union bound. In order union bound only over finitely many events, we rely on the fact that t < Ao: this is why the cardinalities must be capped. This motivates the second important sensitivity measure of ALG.
Each of these stages requires linear work in the size of the input, i.e. the sum of the sizes of the users sets. Furthermore, each stage is straightforward to implement within parallel framework. As there are a constant number of stages, the algorithm can be implemented with total linear work and constant number of rounds.
Definition 3.2. The novel fo sensitivity of a weighting al- gorithm is parameterized by the number t = [T] of items
5

---

Scalable Private Partition Selection via Adaptive Weighting
Algorithm 2 MAD(S, T, dmazy b, Driines bmas)
Input: User sets 8 {(u, ((,)))))) (.))) adaptive threshold 2 0, maximum adaptive degree dmew > 1, biases b: u -> R. minimum bias Unain E [0.5, 1], maximum bias bmaz E [1, oc]
Output: w U - RR weighting of the items
1: Initialize weight vectors w. Winit, Werune: Wveroute with zeros.
2: Set reroute discount factor = bman 2/dmux
3: Tadapt = =fu [n]:
(0min)) )a S Suul S dmaz)
Only users with certain degrees act adaptively,
4: for all E Tadapt do
5: Wisnte += 1/1Sul V Su
P Initial & sensitivity bounded weights.
6: end for
7: r(t) t min {0,
(anie(()-r for Eu (1)
Fraction of weight that exceeds the threshold.
8:
9: (i)unc()) + --minfut Wemee minffimme (1), foriEu
>> Truncate weights above threshold.
10: for all u Iadapt do
11: eu + (1/15ul) Siss r())
Excess weight returns each user proportional to their contribution. D- Reroute excess to items, discounted by a/ s//man-
12: Wveronte (1) += dmma/dmaa for i E Su
13: end for
14: w- + Wtrune + Wreroute
Total & bounded adaptive weights. D See Algorithm 4,
15: W. + -UserWeightsSu, b, bman )max) Vu E [n]
16: for all u E Ludapt do
17: w(i) += w/ (1) 1/ Sul f & E Su
Add lg bounded weight and subtract initial weights.
18: end for
19: for all u E [m]] Tadapt do
20: w(i) += wg (i) for i E S.
D Add & bounded weight for non-adaptive items.
21: end for
22: return
4.1. MAD2R: Biased Weights in Multiple Rounds
outputs U1 U well query access to Wezt- We will only ever query items in U, so we maintain #i which is West restricted to l without ever materializing Wezt. Importantly though, we never release wi as a final output.
This unbiased version of MAD directly improves on the basic algorithm. We further optimize our algorithm by refining an idea from the prior work of DP-SIPS (Swanberg et al., 2023). In that work, the privacy budget is split across multi- ple rounds with Basic used in each round. In each round, items found in previous rounds are removed from the users' sets, so that early rounds, easy-to-outphl (loosely speak- ing, high frequency) items are output, with more weight being allocated to harder-to-outpur items in future rounds. The privacy of this approach follows from post-processing: we can freely use the differentially private output U from early rounds to remove items in later rounds.
In the second round, we make three preprocessing steps before running MAD. Let 01 be the standard deviation of the noise in the first round and p2 be the threshold in the second round. For parameters Cub, Cub 2 0, Let wws
क Cl and W.b कn + Cus on be lower and upper confidence bounds on the true item weights wi in the first round, respectively.
(a) (DP-SIPS) We remove items from users' sets which belong to U1.
We propose MaxAdapt i (MAD2R) which as a starting point runs MAD in two rounds, splitting the privacy budget in DP-SIPS. As MAD stochastically dominates Basic, c, this provides drop-in improvement. Our key insight comes from the modified meta-algorithm we present in Section 3 which also outputs the vector of noisy weights Wezt- As long as the ALG maintains bounded sensitivity, we are free to query the noisy weights from prior rounds when constructing weights in future rounds.
Rooundds
(b) (Ours) We remove items i from users' sets which have weight significantly below the threshold where (i)(i) < P2. If (i) is very small, we have little chance of outputting the item in the second round and would rather not waste weight on those items. This is particularly relevant for long-tailed distributions we often see in practice where there are many elements which appear in only one or a few users' sets.
We leverage this by running in two rounds with the full pseudocode given in Algorithm 5. In the first round, we run the unbiased version of MAD described above to produce
(c) (Ours) For items with uns 2 P2, we assign these items biases b(i) = pa/ Via UserWei ght (Algo- rithm 4), we (loosely) try to have each user contribute a b(i) fraction of their normal l/vis.i weight while
6

---

Scalable Private Partition Selection via Adaptive Weighting
increasing the weights on unbiased items. As the lower bound these item weights is very large, we do not need to spend much of our &2 budget on these items. For technical reasons, in order to preserve the over- all sensitivity of MAD, we must enforce minimum and maximum bias parameters min E [0.5, 1] and bma E [1, x). The weights returned by Userwe i ghts are in the interval [bmen/ / Vis.T, /mon/ /is.]] and have an lz norm of 1.
We now compare the empirical performance of MAD and MAD2R against two parallel (Basic, DP-SIPS) and two sequential algorithms (PolicyGaussian and GreedyUpdate for the partition selection. We observe that our algorithms output most items (at parity of privacy parameter) among the parallel algorithms for every dataset and across various parameter regimes. Moreover, parallelization allows us to analyze datasets with up to 800 billion entries, orders of magnitude larger than sequential algorithms. In the rest of the section, we describe the datasets, algorithms,, and com- putational setting, before presenting our empirical results.
4.2. Privacy
We state the key lemmas that MAD, when used in the Wei BeiihhtnnThheshhee
5.1. Datasets
meta-algorithm, is (e, D)... The privacy of MAD2R then follows from basic composi- tion, importantly using our generalized analysis in Section 3 which allows us to compute biased weights from the noisy weights of the first round. The key technical challenge is to bound the ly and novel for sensitivities of MAD. Given space constraints, we defer the proofs to Appendix B.
We consider 9 datasets with statistics detailed in Table I. First, we consider small-scale datasets that are suitable for fast processing by sequential algorithms in a single-core architecture. These includes, for the sake of replicabil- ity, datasets used in prior works (Gopi et al., 2020; Car- valho et al., 2022: Swanberg et al., 2023). These datasets have up to 3 million distinct items and 300 million entries. Higgs (Leskovec & Krevl, 2014) is dataset of Tweets dur- ing the discovery of the Higgs. IMDb (Maas et al., 201 1) is dataset of movie reviews, Reddit (Gopi et al., 2020) is a dataset of posts to r t/askreddit. Finance (Aenlle) is dataset of financial headlines, Wiki (Wijkhuizen) is a dataset of Wikipedia abstracts, Twitter (Axelbrooke, 2017) is a dataset of customer support tweets, and Amazon (McAuley & Leskovec, 2013; 3; Zhang et al., 2015) is dataset of product reviews. For each of these text-based datasets we replicate prior methodology (Gopi et al., 2020; Carvalho et al., 2022) where items represent the tokens used in a document and each document corresponds to a user (in some datasets, ac- tual users are tracked across documents, in which case, we use combine the users' documents into one document).
Lemma 4.1 (Novel Loo sensitivity). Algorithm 2 has novel so sensitivity bounded by A (t) I $ma=.
Lemma 4,2 (lg sensitivity). Algorithm has Ez-sensitivity upper bounded by 1.
4.3. Utility
In Theorem 1.2, we show that for any input, MAD'S per- formance stochastically dominates Rasice c: the probability that an item is output by Basic is upper bounded by the probability it is output by MAD. We defer formal statement of Theorem 1.2 and its proof to Appendix C.
This result captures the worst-case behavior of MAD; it is always at least as good as Basic. MAD can actually do much better it increases the weight on items below the threshold r. In Appendix C, we also show instance where MAD significantly improves upon Basic and DP-SIPS.
We also consider two very- publicly-available datasets Clueweb (Boldi et al., 2011) and Common Crawl'. The latter has approximately 2 billion distinct items and 800 billion entries. This is 3 orders of magnitude larger than the largest dataset used in prior work. Clueweb (Boldi et al., 201 1) is a dataset of web pages and their hyper-links, items corresponds to the hyperlinks on a web page and each page corresponds to user. Common Crawl is very-large text dataset of crawled web pages often used in LLM research.
5. Experiments
Dataset
Users
Items
Entries
Higes
2.8 x 10
5.9 10*
4.6 x 10
IMDb
5.0 10
2,0 10
7.6 10
Reddit
2.2 10
1.5x 10
7.9 10c
Finance
1.4x 10
2.7 10"
1.7 10²
Wiki
2.5 x 10
6.3 x 10
1.8 x 10²
5.2. Algorithms and Parameters
Twitter
7.0 10
1.3 x 10
2.7 x 107
We compare our results to both sequential and parallel al- gorithms from prior work. The sequential algorithms we compare against are PolicyGaussian (Gopi et al., 2020) and Greedy CreedyUpdate (Carvalho et al., 2022). Like our algorithm, both algorithms set an adaptive threshold T greater than the
Amazon
x.0 10
2.5 x 10
2.4 10
Clueweb
9 1
9.4 10
4.3 10
Common Crawl
2.9 x 10
1.8 x 10
7.8 x 10"
Table 1: Number of distinct users, distinct items, and total entries (user, item pairs). The number entries the sum of the sizes of all the users' sets.
'https: http//wwww.// wwtp:.coooonccaw..comm
7

---

Scalable Private Partition Selection via Adaptive Weighting
Parallel Algorithms
Sequential Algorithma
Dataset
MAD (ours)
MAD2R (ours)
Basic
DP-SIPS
VolicyGaussian
GreedyUpdate
Higgs
1,807 (4:13)
1,767
(4:15)
1,791 (1:18
1,743 (1:)
1,923 (1:18)
2,809 (1:11)
IMDb
2,516 (2:12)
3,369 (4:19)
2,504 (1:7
3,076 (4:16)
3,578 (1:19)
1,363 (4:11)
Reddit
4.162 (4:19)
6,215 (4:18)
4,062 (4:21)
5,784 (#:0)
7.170 (1:39)
6,340 (1:16)
Finance
12,759 (1:16)
17,785 (#:28)
12,412 (1:50)
16,926 (1:18)
20,100 (#:49)
23,556 (4:27)
Wiki
7,812 (412)
10,554 (#:41)
7.753 (4:66
9,795 (#21)
11,455 (#21)
4,739 (4:14)
Twitter
9.074 (4:23)
14,064 (4:33
8,859 (4:22)
13,499 (4:50)
15,907 (+:30
15,985 (4:29)
Amazon
35,797 (=63)
67,086 (#:00
35,315 (1:9)
66,126 126 (#:77)
77,846 (212
86,841 (#:55
Clueweb
34,692,178
34,533,524
34,603,077
14,889,208
Common Crawl
15,815,452
29,373,829
15,734,148
28,328.613
Table 2: Comparison of output size of DP partition selection algorithms with = 1, = 10- and Do = 100. A standard hyperparameter setting is fixed for each algorithm, other than DP-SIPS, where the best result is taken from privacy splits (0.1, 0.9] and [0.05, 0.15, 0.8). For smaller datasets, sequential algorithmss are also reported as oracles and results are averaged over trials with one standard deviation reported parenthetically. For each dataset, the best parallel result is bolded and the best sequential result is underlined.
true threshold p. They try to maximize weight assigned to items up to but not exceeding T. PolicyGaussian goes through each user set one by one and adds l2 bounded weight to minimize the lg distance between the current weight and the all T vector, wii) = T Vi E U. GreedyUp- date goes through each user set one by one and increments the weight of single item in the set by one, choosing an item whose weight is currently below 7.2 As observed be- fore (Swanberg et al., 2023), sequential algorithms can have arbitrary long adpativity chains (the processing of each user can depend on all prior users processed) thus allowing larger output sizes than parallel algorithms. This, however, comes at the cost of not being parallelizable (as we observe in our experiments on the larger datasets). The parallel base- lines we compare against are Basic (Korolova al., 2009; Gopi et al., 2020) and DP-SIPS (Swanberg et al., 2023). In DP-SIPS, the privacy budget is split into distribution over rounds. In each round, the basic algorithm is run with the corresponding privacy budget. Items found in previous rounds are removed from all user's sets for the next rounds.
set dmaz 50 and 2. For MAD2R, we the privacy split of [0.1, 6min = 0.5, bmaz = 2, Cb. 1, and Cub 3.
5.3. Computing Details
We perform experiments in two different computational settings. First we implement a sequential, in-memory ver- sion of all algorithms (including the parallel ones) using Python.Fo For PolicyGaussian and GreedyUpdate we use the Python implementations from prior work (Gopi et al., 2020; Carvalho et al., 2022). This allows us to fairly test the scala- bility of the algorithms not using parallelism. As we observe next, this approach does not scale to the two largest datasets we have (Clueweb, Common Crawl).
Then, we implement all parallel algorithms (MAD, MAD2R, Basic, DP-SIPS) using C++ in a modern multi-machine massively parallel computation framework our institution. This framework allows to use fleet of shared (x86 64) ar- chitecture machines with 2.45GHz clocks. The machines are shared by several projects and can have up to 256 cores and up to 512GB of RAM. The jobs are dynamically allocated RAM, machines and cores depending on need and availabil- ity. As we observe, all parallel algorithm are very scalable and run on these huge datasets within 4 hours of wall-clock time. On the other hand, both sequential algorithms cannot exploit this architecture and could not complete in 16 hours the Clueweb dataset (we estimate they would take sev- eral days to complete on the Common Crawl dataset even assuming access to enough memory).
We make parameter choices which are consistent with prior work and generally work well across datasets (see Ap- pendix D for more parameter settings). Unless otherwise specified, we use & = 1, ò = 10-5, and A. = 100.3 For PolicyGaussian and PreedyUpdatte we set the B = 4 to be the number of standard deviations of noise to add to the base threshold to set the adaptive threshold. For DP-SIPS, we take the best result of running with a privacy split of 0.99 and [0.05, 0.15, 0.8]*. For MAD and MAD2R, we
Unlike all of the other algorithm, this algorithm does not do a first step of bounding users' degrees by Au as it only assigns weight to single item per user by design.
5.4. Results
We report these privacy settings for consistency with prior work in the literature, but observe the results are consistent across various choices. For real production deployments on large-scale sensitive data, 8 usually smaller.
Algorithm Comparison Table 2 displays the output size of the DP partition selection algorithms (i.c., the number of privatized items output). Among parallel algorithms, MAD2R achieves the best result on seven out of nine datasets. The two exceptions are the Higgs dataset, where MAD per- forms the best, and the Clueweb dataset, where DP-SIPS
4 As this choice can have a significant effect on performance, we choose the best-performing to give this baseline the benefit of the doubt.
8

---

Scalable Private Partition Selection via Adaptive Weighting
performs the best. Both of these datasets have outlier statis- ties (see Table 1): the average size of user set in the Higgs dataset is less than 2 and the number of unique items in the Clueweb dataset is less than the number of users. Di- rectly comparing MAD with Bas c, MAD is always better, corroborating our proof of stochastic dominance. Compar- ing MAD2R with DP-SIPS, MAD2R is almost always signifi- cantly better, by up to a factor of 9.5% improvement on the IMDb dataset.
hand, 99.9% of users have least one outputted item and 97% of entries in the dataset belong to item in output by our algorithm. This dataset contains 61% singleton items, and many low frequency items. In Figure 1b, we break down the number of items total in the dataset and the num- ber output by MAD2R broken down by item frequency, Our algorithm returns an overwhelming fraction of items occur- ing in at least 200 user sets on a dataset with billions of users overall.
On the small scale datasets where we can run sequential algorithms, as expected from prior work (Swanberg et al., 2023), one of the two sequential algorithms yield the best re- sults across all algorithms with Policy GalissGa consistently outperforming all parallel baselines. GrreddUUpdate 's perfor- mance is heavily dataset dependent, sometimes performing the best and sometimes the worst out of all algorithms. This is not surprise as the sequential algorithms utilize much more adaptivity than even our adaptive parallel algorithm at the cost of limiting scalability. Our algorithm is still com- petitive, never outputting fewer than 86% of the items of PolicyGaussian (and outperforming Greedy SneedyUpdate Update on many datasets). For massive datasets, where it is simply infeasible to run the sequential algorithms, however MAD2R has the best results of all parallel algorithms.
10a
Natureed
10a-
Itm Couet
MAU LONA
101-
10a
(2.50)
1000
[2000,000
1500
Prequency Bucket
(a) Reddit Item Coverage
10"
Rom Count
Figures comparing output sizes while varying E, 8, Ao. and dmaz are included in Appendix D. The relative performance of the algorithms is the same across many choices.
10h
To understand the absolute utility of our algorithms (as opposed to relative to other baselines). we focus on the performance of MAD2R on the Reddit and Com- mon Crawl datasets. In order to understand the performance in real deployment rather than compare baselines across common parameter settings, we change the ó for the large scale Common Crawl dataset to 8 = 10-11
Absolute Utility
11.20
[2.50]
[50,100]
Prequency Sucket
(200.200)
[2005500] (505,1000) [1000..]
(b) Common Crawl Item Coverage
Figure 1: Comparison by item frequency of the output size of MAD2R to the total items on the Reddit and Common Crawl datasets. Parameters
1 and Ao 100 are fixed with 10- for Reddit and 10 for Common Crawl.
On the Reddit dataset, MAD2R outputs 6,340 out of 143,556 unique items (4.4%). On the other hand, 98% of users have at least one outputted item, and 45% of the entries (user-item pairs) belong to item which is output by our algorithm. The relatively small overall fraction of items output is due in part to the fact that the Reddit dataset has 58% singleton items (items only appearing in a single user's set). Any algorithm which outputs any singleton items is not private, as it is leaking private information belonging to single user. For any algorithm with acceptable privacy settings, outputting items with very small frequencies is also simply not possible. In Figure la, we break down the number of items total in the dataset and the number output by MAD2R broken down by item frequency. Our algorithm returns almost all of the items with frequency at least 100.
6. Conclusion
We introduce MAD and MAD2R, new parallel algorithms for private partition selection which provide state-of-the-ant re- sults, scale to massive datasets, and provably outperform baseline algorithms. Closing the remaining gap between parallel and sequential algorithms remains an interesting direction, as well as developing new ideas to adaptive route weight items below the privacy threshold while maintain- ing bounded sensitivity. While are able to prove ordinal theoretical results (our algorithm is at least good as an- other), it is an open challenge to develop a framework where we can prove quantitative results, perhaps comparing the competitive ratio of a private partition selection algorithm compared to some reasonably defined optimum.
On the Common Crawl dataset, MAD2R outputs 16,551,550 out of 1,803,720,630 unique items (0.9%). On the other

---

Scalable Private Partition Selection via Adaptive Weighting
Acknowledgements
Carvalho, R. S., Wang, K., and Gondara, L. S. Incorporat- ing item frequency for differentially private set union. In Proceedings of the AAAI Conference Artificial Intelli- gence, 2022.
Justin Chen supported by an NSF Graduate Research Fellowship under Grant No. 17453. Part of this work was done while he was student researcher at Google Research.
Dean, J. and Ghemawat, S. MapReduce: Simplified Data Processing on Large Clusters. In OSDI04: Sixth Sympo- sium on Operating System Design and Implementation, pp. 150, San Francisco, CA, 2004.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Desfontaines, D., Voss, J., Gipson, B., and Mandayam, C. Differentially private partition selection. In Proceedings on Privacy Enhancing Technologies, 2022.
References
Dwork, C. and Roth, A. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theo- retical Computer Science, 9(3 41:211)21011111 2014.
Aenlle, M. Daily financial news for 6000+ stocks. URL
https:// bttts::/www..r http:///wwwkggllee.. wtt.:kkggg.......iioooeeee. wwoo/mmiguue wwwmmmiiuelaeenllle datasets.
Ghazi, B., Huang, Y., Kamath, P., Kumar, R., Manurangsi, P., Sinha, A., and Zhang, C. Aparsity-preservinn differ- entially private training of large embedding models. In Thirty-seventh Conference Neural Information Pro- cessing Systems, 2023. URL https: tttttts::/opeeeeeeee /openevveeeeeee net htt./oorummddsss/cccc....
Amin, K., Gillenwater, J., Joseph, M., Kulesza, A., and Vassilvitskii, S. Plume: Differential privacy at scale. arXiv preprint arXiv:2201.16003, 2022.
Apache Software Foundation. Hadoop. URL URL https:// hadoop.. apache. org.
Axelbrooke, S. Customer support on twitter, 2017. URL https: / //ww./www. kaggle www.cooooooooooo dsv///vv/////// 8841.
Ghazi, B., Guzmán, C., Kamath, P., Kumar, R., and Manu- rangsi, P. Differentially private optimization with sparse gradients. arXiv preprint wrXiv:2404.0088) 2024.
Balle, B. and Wang, Y.-X. Improving the gaussian mecha- nism for differential privacy: Analytical calibration and optimal denoising. In International Conference Ma- chine Learning. PMLR, 2018.
Google. differential- com/ e / http://ffeeeeaaaaaaraaeaa//////e main cwtc/ommooocccccccccc http:ooooooo/pprrttioooeeeeeeeee md, May 2024.
Bavadekar, S., Boulanger, A., Davis, J., Desfontaines, D., Gabrilovich, E., Gadepalli, K., Ghazi, B., Griffith, T., Gupta, J., Kamath, C., et al. Google covid-19 vaccina- tion search insights: Anonymization process description. arXiv preprint ar arXiv:2107.01179 2021.
Gopi, S., Gulhane, P., Kulkarni, J., Shen, H., Shokouhi, M., and Yekhanin, S. Differentially private set union. In Proceedings of the 37th International Conference on Machine Learning. PMLR, 2020.
Boldi, P., Rosa, M., Santini, M., and Vigna, S. Layered label propagation: multiresolution coordinate-free or- dering for compressing social networks. In Srinivasan, S., Ramamritham, K., Kumar, A., Ravindra, M. P., Bertino, E., and Kumar, R. (eds.), Proceedings of the 20th inter- national conference World Wide Web, pp. 587-596.
Karloff, H., Suri, S., and Vassilvitski,, S. A model of com- putation for mapreduce. In Proceedings of the twenty-first annual ACM-SIAM symposium Discrete Algorithms, pp. 938-948. SIAM, 2010.
Kim, K., Gopi, S., Kulkarni, J., and Yekhanin. S. Differ- entially private n-gram extraction. Advances in neural information processing systems, 34:5102-5111,
ACM Press, 2011.
Boneh, D., Boyle, E., Corrigan-Gibbe Gibbss, H., Gilboa, N., and Ishai, Y. Lightweight techniques for private heavy hitters. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 762-776. IEEE, 2021.
Korolova, A., Kenthapadi, K., Mishra, N., and Ntoulas, A. Releasing search queries and clicks privately. In Proceed- ings of the 18th international conference on World wide web, 2009.
Cardoso, A. R. and Rogers, R. Differentially private his- tograms under continual observation: Streaming selection into the unknown. International Conference on Artifi- cial Intelligence and Statistics, pp. 2397-2419. PMLR, 2022.
Leskovec, J. and Krevl, A. SNAP Datasets: Stan- ford large network dataset collection. http::/ /naap. stanford. edu/ June 2014.
10

---

Scalable Private Partition Selection via Adaptive Weighting
Maas, A. L., Daly, R. E., Pham, P. TT., Huang, D., Ng. A. Y. and Potts, C. Learning word vectors for sen- timent analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguis- Human Language Technologies, pp. 142-150, Port- land, Oregon, USA, June 2011. Association for Com- putational Linguistics. URL http: http:::/wwwwwllllw.w. arg/anthology/PPNa (tt.oooyyyy11100000
Zhang, X., Zhao, and LeCun, Y. Character-level convolutional networks for text classification. In Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc.,
fics:
cC cccpppper_fffleeppppr////////111 neuripss 2300ffbsicc7335588ocbbee66662221 pdf.
2013. URL
McAuley, J. and Leskovec, J. Hidden factors and hid- den topics: understanding rating dimensions with re- view text. Proceedings of the 7th ACM conference on Recommender systems, 2013. URL https://app
Zhang. Z., Hu, X., Qu, L., Wang. Q. and Xu, Z. Feder- ated model decomposition with private vocabulary for classification. Empirical Methods in Natural Lan- guage Processing 2022, pp. 6413-6425. Association for Computational Linguistics (ACL), 2022.
wrtg//ooopst::440033 o 6440341.
OpenMined. OpenMined PipelineIDP Library. https: / //github. httpp//www....eeeeeeee///eeeepea 2024.
May
PyDP. PyDP Library: Partition Selection. https: / //pydp. readt httpeeccs...//e///aaee/////e/eee hpyddp. html Apariitio selectiion,n May 2024.
Swanberg, M., Desfontaines, D., and Haney, S. DP-SIPS: A simpler, more scalable mechanism for differentially private partition selection. In Proceedings on Privacy Enhancing Technologies, 2023.
Wijkhuizen, M. Simple/normal wikipedia ab- stracts v1. com http//ataoeessmarwtiiiiiiie http://wwww......./////// s simpleenoommlluuuliaaaaaaaassses
URL https:/ //ww://wwwwwwwwwww
Wilson, R. J., Zhang, C. Y., Lam, W., Desfontaines, D., Simmons- Marenno, D., and Gipson, B. Differentially private sqi with bounded user contribution. arXiv preprint 2019.
Wilson, R. J., Zhang, C. Y., Lam, W., Desfontaines, D., Simmons-Marenge D., and Gipson, B. Differentially pri- vate SQL with bounded user contribution. In Proceedings on Privacy Enhancing Technologies, 2020.
Zaharia, M., Xin, R. S., Wendell, Das, T., Armbrust, M.. Dave, A., Meng, X., Rosen, J., Venkataraman, S., Franklin, M. J., Ghodsi, A., Gonzalez, J., Shenker, S., and Stoica, Apache Spark: a unified engine for big data processing. Commun. ACM, (9(1))55-655 oct 2016. ISSN 0001-0782, doi: 10.1145/2934664, URL https: ////oi.org/1/// //doi. org 10/ 1et.l11445225555
Zhang, B., Doroshenko, V., Kairouz, P., Steinke, T., Thakurta, A., Ma, Z., Apte, H., and Spacek, J. Differen- tially private stream processing at scale. arXiv preprint arXiv:2303. 18086, 2023.

---

Scalable Private Partition Selection via Adaptive Weighting
A. Algorithm Pseudocode
A.1. Basic Pseudocode
Algorithm 3 Basic
Input: User sets S = {(u, Su))u(
Output: w + R weighting of the items
1: Initialize weight vector w with zeros
2: for all u E [n] do
3: me(i) += 1/v [ua] for i E Su
Add hasic bounded weight.
4: end for
5:
return
A.2. MAD and MAD2R Pseudocode
See Algorithm in the main text for the pseudocode of MAD. Here, we include the pseudocode for the subroutine UserWeights and our two-round algorithm MAD2R.
Algorithm 4 User UserWeightss (S.,, b, brin dmaz)
Input: User set S., C U, biases b : U > [0, 1]. minimum bias bmii E [0.5, 1J. maximum bias bmaz E [1, oc]
Output: wp S. - R weighting of the items
1: Initialize weight vector with zeros
2: Sbiased = {i S.
b(t) < 1)
3: Sunbiased = S. \ Sbiased
4: (i) (axx((men.d(t)) for E Stiased
>> Set biased weights, respecting min bias
vis.l
LicSbiaed (h)()² Sunbiused
5: (1) + min
bmaz VISAT*
for E Sunbiased
> Allocate remaining & budget, respecting max bias
do 6: while ExEs. (i)²
7: Ssmall +
i S. wi)
1&
bman! S.
LiER, 10)())2
8: C
1
muNig S Smmall (x(
E Emal (2)
9: wi(()= +
w. for E Ssmall
D Increase small weights using remaining &g budget, respecting max bias
10: end while
11: return W/
12

---

Scalable Private Partition Selection via Adaptive Weighting
Algorithm 5 MAD2R(SS (E1, 61), (E2, 52), Ao: dmaas B, Cib, Cub, brnine bmax)
Input: User sets S = ((u, Sw)) uE(n], privacy parameters (81, and (62, 82), degree cap Ag. maximum adaptive degree dmaz. adaptive threshold excess parameter B3, lower bound constant Cit, upper bound constant Cub. minimum bias bminn maximum bias bmar
Output: Subset of the union of user sets -
1: For u E [n]], cap S, to at most Ag items by random subsampling
2: Select o, corresponding to the Gaussian Mechanism (Proposition 2.4) for (5r,6,/2)-DP with A for r E {1,2].
Round
4: Set threshold 01 max)e[Aol VI + f ( (11- 5) ())
5: + MAD(S, P1 + 101, dmaax T, 1,1)
D> Compute MAD (Algorithm 2) weights in the first round.
6: wi + wn +0(00,of1
t> Add noise Apply threshold
7: U1 + e 4 w1 (1) p1}
8: Round 2
Umax + oz 911-
9: Set threshold P2 maxre|Aol v2
10: wib max úi Ci -11
Weight lower bound from Round
11: Wab w1 + Cub .1
Weight upper bound from Round 1
12: Utow t ii El: Wab < P2)
13: S, + +S, (U/ Ulow) for E [n]
D> Remove items found in Round I or with small upper bound on the weight
14: + min 1, f,
Bias weights to not overshoot threshold
wa + MAD(S, P2 + 302, dyaax binnn Dmaax)
Compute MAD (Algorithm 2) second round
W2 w2 (00 o²
Add noise
17: U2 + {i E 4: (1(1)= P2}
Apply threshold
18: return U, UU2
13

---

Scalable Private Partition Selection via Adaptive Weighting
B. Proof of Privacy
B.1. Meta-algorithm
We start by proving the privacy of the meta-algorithm described in Section
Proof of Theorem 3.3. Let Went Σ + I be an extension of the weight vector w returned by ALG where
(i) if Tieu u
Weant (i)
TREENU
Note that Wast is exactly the result of applying the Gaussian Mechanism to Went- Furthermore, the & sensitivity (Defini- tion 3.1) of computing west is the same that of w items outside of U' do not contribute to the sensitivity they are O regardless of whether the input is S or S", By the choice of according to Proposition 2.4 with A S 1, releasing Went is (e. -DP
The privacy of releasing U depends on our choice of the threshold p. We will first show that the probability that any of t
i..d draws from Gaussian random variable (0, o²) exceeds o ((1 () 1r) is exactly g. Let A be the bad event,
Y (O, )²), and ~ (0,
(1- 1/2
Pr(A)= = Pr Y S cの -1
(1-2) 3/0
-1 Pr
S x
(1 (1-2) 2 1/t1
+
④
8'
2
8 2
By the condition that l<(() is an upper bound on A()), the choice of implies that, no matter how many items are novel (unique to the new user in a neighboring dataset), the probability that any of them belong to U is at most &. Conditioned on the release of Wext, releasing U is (0, -DP. By basic composition, the overall release is (e, 8)DD,, as required.
B.2. MADW and MADW2R
We now prove the privacy of our main algorithm by bounding its lg and novel loo sensitivities. Theorem B.1 (Privacy of MAD2R). Algorithm 5 is (61 E2, 81 DD)
The rest of this section will be devoted proving this theorem. We first state as corollary that MAD run in a single round without biases is also private.
Corollary B.2 (Privacy of MAD). Releasing the output U from Algorithm I run with unbiased MAD (Algorithm as the weighting algorithm and with h(t) v is (DP.).DP
Proof. This follows directly from Theorem B.1 by setting (E1, = (e and (E2, 62) = ().
To prove privacy, consider a weight vector w returned by Algorithm 2 for an input S = {u, Sw) T, dmars b, bmine bmax and the output w' for an input S' = S U {u, 5,)}, T, dmazz U' bmin bran which includes a new user v not in the original input. Let d, be the degree of the new user. Let = S. \ S be the subset of items which appear only in S, and not in any of the original user sets, and let = [T). The vectors of biases and b' are defined on the set of items UR S, and
14

---

Scalable Private Partition Selection via Adaptive Weighting
(U==1 U respectively. We remind the notation used in Algorithm for vector wg denote the biased weight vector the new user computes by calling Algorithm 4, i.e. UserWeights,
Lemma B.3 (Novel & sensitivity with biases), Assume that the adaptive threshold is T 2 1, and the maximum adaptive degree is dmaar& 2 4. Then, Algorithm 2 has novel too sensitivity bounded by
Umax
2o (1) S
VL
where L. [T] is the cardinality T, the set of novel items.
Proof. Unpacking Definition 3.2, suffices to show that
dmaa Vt
max w/ (1)
NET
Note that this is trivially true if d, |S,| dmar or dp < too low or high degree. We will proceed by assuming this is not the case.
since v does not participate adaptivity due its
(bmin)?
Consider the final weight of an item i in the set of novel items T C Sp:
w'(1) (1) werane + w/ werouue (1) + wg (1) (in
Note that for all novel items i T. (1) J. S as is the sole contributor the weight of item Therefore, weight is truncated or rerouted from these items: w/yune (i) = w/ (i) d., Expanding the definition of rerouted weight,
ac'y
W Wreroute (i)
Uman
Σ r(())
dy
JES.AT
W/nie (i) W'rano (
E
d
Wini (i)
jES.1T
a -t)
dman du
dmna d
Finally, note that wg (f) We can bound w/ (1)
<
bmax Vd,
by construction (this is the meaning bmaz).
w/ Wirane(() + Wreroute (i) + w/ (1) - w/mit (1)
a
dmax
+
1
-
+
dy
dmax
de
dd
de
a
binax
1
+
(I)
dman
d
ViT
In the rest of the proof, will show that the upper bound Equation (1) is maximized when d, 1, i.e., when the first term zero. Recall that t < d, dmax- Consider the partial derivative with respect de:
Od, dmaz (1- (1-
bmar dd
a
bman
d
dmaz
d?
20
15

---

Scalable Private Partition Selection via Adaptive Weighting
Consider the condition of the derivative being non-positive:
Umaz
dmax dy
2d-/2
2at
dmaz
dmax dp
20vE
bmaz 2
dmax
20
Umaz?
Vdmas
The final condition holds S 1 and by the assumption that dmaz 4. We note that bmar is always set to be at least 1. As the derivative is non-positive, the right side of Equation (1) is maximized when d, is minimized at de = t. Then,
(t) I bmaz as required.
V
Following we state some properties of the biased weights wa which will be helpful in the proof.
Lemma B.4. Let Su, b, dmins dmaz be valid inputs Algorithm 4, and let wh be the weight vector returned by the algorithm.
Let d = [ Then, the following hold:
(i) for all E EuV. S.
Aman S (t) I bmar for all E S.
va
||wbl22 <
Proof. The first claim holds as the weight vector is initialized with zeros and only indices E S,, are updated by the algorithm.
To simplify the notation, we define d [Sul Sbiased + Sanbiasedd
As b(t) for all e U, the initial weights given bmaz.
items in Shiased between boin and Vdl
We also know that Vd Vd The sum of squares of these weights will thus
Vd
be between 1 SStaredd and Sainned
Call this value k.
d
Weights of items in Sunbinsed are given by
Umaz Va V
1
min
Suntrissed
We show that the minimum of these terms is at least Va
The first term is at least Va since bmax 2 1. To observe the same the second term, one should plugg the upper bound of k s [Suared By construction, the weights are upper bounded by Amaz, /d Furthermore, note that the sum of squares of the entire weight vector at this point is upper
bmin
Vd
bounded by 1. In particular, it is equal to for the second term of the minimization:
Σ
1-k =
k + (1 - k)) =
S
SESaaneed
In the remainder of the algorithm, sum of the weights of items in Symall S. Sunbiosed may increase if the & norm of the weight vector is strictly less than 1. Consider the weights after any such update by a multiplicative factor C defined as
C = ==min bman / /dd
I-Eies, wE wr) EiEsomat W/ (i)
1+
mnaxessmaa w)(()
Note that C by definition of Ssmatt and the stopping criteria of the while loop. Therefore, none of the final weights will be less than bmin. Consider the first case of the minimization. Any updated weight C' wr(i) for Semall will be most Va
16

---

Scalable Private Partition Selection via Adaptive Weighting
Iagg vd
mmoz/ / Vd
mmax/ Vd ws((t)
(b(()) S
max 1 S*ESsmall
(16((") = bemaa//Ve /inz//Vd.
maxjeS (b(1)
Now, consider the second case of the maximization. Then, the squared E2 norm of the weight vector will be
1 1- -yEE,, wb(1)2
wa(i)²
Σ
1+ Ejeseman wb(j)² wb(1)²
Σ
wb)())
+ (1 Σ
wi(
1.
\. emaal
VESxmall
HESS
JESu
As C' is taken to be the minimum of these two values, the final weight vector will satisfy all of the required bounds.
We will prove a useful fact that Algorithm 2 is monotone in the sense that weights when run on S' will only increase compared to when run on only S. We apply this proposition in upper bounding the lo sensitivity of Algorithm 2 in Lemma B.6.
Proposition B.5 (Monotonicity), For all i Une ()........ Sw.
winit (1) Wenit
Werune
Wtrune
w Verootte Wreroute (i).
Proof. Fix any item i. As all increments to the initial l bounded weights are positive and non-adaptive,
Waii (1) Wimit()). (i).
In fact, the two weights are either equal or differ by a factor of 1/d, depending on whether E S,,. The calculations the fraction of excess weight that exceeds the threshold, the truncated weights, the excess weight returned each user, and the rerouted weights all monotonically non-decreasing with the initial weights. Therefore,
Wernne (1) 2 Wirane
and
Wreroute (i) 2 Wreroute:
Lemma B.6 (62 sensitivity with biased weights), Algorithm has Ez-sensitivity upper bounded by 1.
Proof. Note that this is trivially true by Lemma Bf4 [Sa] d, dmaz or d, in adaptivity in this case. We will proceed by assuming this is not the case.
since does not participate
[6man.)
Our goal is to bound the &g norm of the difference A w/ w, the difference in final weights with and without the new v. We will use the notation A subaeript w/ subscript Wsuhscript- Note that Areroute Wreroute Wreroute the additional rerouted weight after adding user and let Auser A Areroute be the rest of the difference.. Note that Auser is dy-sparse and only has nonzero entries on S.. the items of the new user. Our goal will be to bound the & norms of Areroute and A user, thus bounding the & sensitivity of the algorithm by triangle inequality.
We start by tracking the excess weight created by v which will be useful in bounding the & norms both A Aevoute and Auser. It is the total amount of weight added by e to items that exceed the thresholdS:
imit
Atrunella
(Note that this is not the same as el, which is the amount of weight from gets returned to reroute.)
'If if an item only exceeds threshold the addition of v, we only consider the allocated weight i above threshold.
17

---

Scalable Private Partition Selection via Adaptive Weighting
The total amount of weight that is returned users reroute equal the amount of weight truncated, i.e., the sum of Winit Wtrunci
Eu
=
Σ (1/1Sw)
Σ
r(1)
0=
#=1
iESu
Winit (i)
(1/1Su)
Σ max 0,
Wéniee (i)
==1
iESu
Winst (1)
Werunel (1)
(1/15w)
Winitt (2)
iESu
Winit (1) Werumel
(1/1Sw))
iESu E Emiies 1/15wb
(Winit (i)
Werane (i)) Eaiiss 1/15al
Emoie 1/1Swl
Winit (i) Werune())
EE
For notational parsimony, let 6, (as v does not appear in the original input S). Note that e, is monotonically increasing with Wontt if any coordinate of the initial weight increases, the excess ratio of any user will never decrease. With monotonicity of Wint from Proposition B.5, it follows that w W/rune 2 Wint Wtrune since the threshold in the capping formula (t) min (mmit (1), r) stays the same after adding the new user. Consequently, have:
? |1( Whrune) (Wanit Wttrnn))l
Σ Winit w'rune Nel
Σ iie
Winst
Werume
e's - ex.
WE (E(L....,,
Now, we will consider A Areroute- Recall that [Sul dynax for all participating in adaptivity, For all other users, the terms en and e, are zero.
A Areooteell ||1
Σ
Σ
(a//mmaz) ea)
wE (. tESu
Σ
|Sul (aul(a/ (a/dmaxx((e - ea)
aE n,
Σ
ale', =eu)
-ay.
Furthermore, we can bound the foo norm of Areooute as:
Wreroute (i) Wreroute (i) (a/ (a/dmax)
Σ
- or/ ar/dmmar-
we uE(I...m,,)
By Hölder's inequality,
Areroutella S IlAerrottlllllAAeeeee = /
/
an
(3)
ddmaz
Consider the rest of the difference Auser For S,, a single coordinate of A user will be comprised of the sum user (i) Atrnaa() (1) + w (i) 1/d,,
18

---

Scalable Private Partition Selection via Adaptive Weighting
Note that tranc (i) E [0, 1/d,]. so
A useer (i) E (1) 1/du, (o(()))
Furthermore, as (inie()) = 1/de.
Auserlll |||
Σ
wi((i) + Atruno(i) Ainir
Σ VEE
wi 7.
iES.
Let x: : Se + R and y : S. + R be two sets of weights over S. such that a<i) = wg 1/de, y(1) E [0, 1/d,]. and
Eies, a(i) + v(1) = (Eies, wi) 7. Then,
Auser ll2 S max || + yll2
y
as any valid Auser can be expressed as the sum of x and choice of y satisfying the above constraints. Note that
1ylla Σ (i)())
-7
Σ
x(1)
Σ
wo((t)
-7- - Σ
+1=1-
S.
EES.
RES.
and by Hölder's 's inequality,
1-7
1 - Vlllllllvloo
V
dn
Then.
|| v12
Σ
(i) 1/d, + v(1)2
iES.
Σ
(i))
+ d
1
+ u(1)²
(1)
+ +2y(i) w/
2y(1)
dp
d,
RE
2
2 |1a111
1 +
+ 11y112
2
| 1 + 2(y, wg)
d
dy
du
1
1 1-7
2
| || +22y, ((y,w() 2(1 - 7)
< 1 +
dg
dg
dg
d, ||wg|11 + 2
1 1+1
7
2(1 7)
2
=1 1
dp
d.
2
=1 -1 +
|ml [l + 2(y,
d.
dg
Every v(i can be written as 1/d,- xii for some non-negative residual =(1) with Eies, =(i) 7. So we continue the above equations follows:
|| + v112
< +
||w6| ||| + 2(y, w./)
d,
1 +
| |||
+ d
||
-2 2 Σ x(i)wF(()
d, d
SES.
= -1+ 7 2 Σ
(1)
d, i,
5 1 7 2
bmin
Σ z(i)
d,
dd ieS.
2bmin
+ 7
Vd
d.
19

---

Scalable Private Partition Selection via Adaptive Weighting
The last inequality holds because Lemma B.4 implies that (1)
Duiin vdz
We conclude that:
| useer ||2 S V1
2bmin vd
Y
+
du
We can now bound the f2-sensitivity of the entire algorithm as
||ل| <
A Aeroutelll + ||Auser Talla++IAussee I
ar Vdman
2bmin .Y
+ 7
vdl
de
As the expression
2bmin
vd, + d, is increasing for de
the right hand side is maximized with dy dmann
07 Vdmax
2bm
| S
+
Vdmaz
dmaax
Our goal is to choose [0, 1] such that the right hand side is upper bounded 1. We note that for y 0, the above inequality proves this desired upper bound. For other cases, 7 E (0, 1J, it is achieved when,
Vinas (1- (1-V1-
2bmin ?
a v
(4)
Vdmax dmaz
By Lemma B.8 with C 2bmin and using the restrictions dmaz and
1/2 S bmin S suffices to choose
a bmin 2 dmax
(5)
Proof of Theorem B.I. Note that both rounds of MAD2R (Algorithm 5) correspond to running the weighthnddTreehoold meta-algorithm (Algorithm 1) with privacy parameters (51, 61) and (Eg, 62), respectively. The only difference is that only materialize in rather than the entire vector Went from the first round. The functionality of our algorithm would be equivalent we instead materialized the full vector as we only query weights on items in U and we never output the vector. Therefore, we will invoke Theorem 3.3 twice and apply basic composition to prove the privacy of MAD2R. By Theorem 3.3, it suffices to show that the & and novel foo sensitivities of the weight algorithm MAD are bounded by and Amas, respectively. This follows directly from Lemma B.3, and Lemma B.6.
B.3. Technical Lemma
Proposition B.7 (Taylor expansion of V1 I as 0).
k) x.
lim v +
k=
(2
n!.
u=0
Lemma B.8. For constant 1 S C consider the following function of parameterized by auxiliary variable y:
V Cr
f(x;y)
1
+
(6)
x
V
For any > 1,
inf zE(0.1]
[(:1))
2
2
20

---

lim Scalable Private Partition Selection via Adaptive Weighting
Proof. To minimize S. we will evaluate the function at any stationary points (in terms of x)) as well the boundaries x: and 0. Consider the derivative
1
f(x;0) =
VI x²
1
Cr
I y
V
v0
dr
2
1
Cz //
+
9
Let A = 1
Cs
To look for stationary points and will set the derivative of f to zero:
v
C
1
d
-1
C
1
f(x 0 =
A)
9
2A(1 A)
dx
2A
V y
We expand A to get the simpler form:
C2 = 2A
(1 1 Cx
(1
+
-
0= 2-2A-2
-2
A +2 - 11
v
V
A=1.
From the definition of A,
Cx
= y= - 1 C2
4=1 =
=1 =
As C' 2 1, in the parameter regime y > 1, f has no stationary points.
remains to check the boundary point x and the function f in the limit as x 0. For x = 1, the claim is reduced to this simple inequality:
V8
C
+
1
2
C
1
= 2y
(1-V 11 Vy
11
c c+
CC
V
y
2
2/v
1/
(1-C+ +
C
+ (2y - C/V 1)² 4y²
+0+++++++400// 4y 2C 41² 4CVVV +4y - 1+C
which holds for any value of y. In the rest of the proof, we focus on the limit as + Via the Taylor expansion of Proposition B.7,
T 1
k)
Cx
x
lim f(: lim +10
+
x x0
x
n!!
y
y
n
k)
Cr
n
2
n!!
Note that the coefficients in the summation are upper bounded in magnitude by 1 as the sequence of terms the descending factorial in the numerator is dominated by the sequence in the factorial in the denominator. We also note that the absolute value of the coefficient of the first term is constant, i.c. 1. So, in the limit, the summation is dominated by the lowest order terms with respect to z which correspond to n = 1. In this case, the coefficient is 1 and the limit evaluates to
Cx
x
C
lim [(; y) z-40
x
2/4
2y
2
2/4
21

---

Scalable Private Partition Selection via Adaptive Weighting
C. Utility
C.1. Stochastic Dominance Proof
Theorem C.1. Let 3 z be the parameter controlling the adaptive threshold excess. Let U be the set of items output when using Basic as the weighting algorithm and let U be the set of items output when using unbiased MAD as the weighting algorithm. Then, items U.
Pfrr(i EU (5)), then Pr(i EU) Pr(ieU)
Otherwise, Pr(i E U*) 2 (5))
Proof Theorem C. Let w and w be the weights produced by Basic c and MAD, respectively. Let Iadapt = {u E [m] |Su] S dmaz) be the items which participate in adaptive rerouting, For any item Ut we will consider it's initial weight under the adaptive algorithm:
W (inie(()
Σ
[ual
We will proceed by cases.
wi (1) S r. In this case, (1) 2 w((). In the adaptive algorithm, no weight is truncated from the initial weights, and so each user contributes to the final weight of an item vis.. plus rerouted weight from other items. As the weight on item i only increases for the adaptive algorithm compared to the basic algorithm, the probability of outputting i also can only increase.
Case 1:
Wini (1) > r. this case the adaptive algorithm, the initial weight is truncated to т, excess weight rerouted, 1 is added. As [Sa| 2 1, the final weight w" (i) r. Then, i U if the added Gaussian and final addition of V.s.i [S.T noise does not drops the weight below the threshold p. i.e., if the noise is greater than or equal to
Case 2:
r = p (p + (0) = -30.
As the noise has zero mean and standard deviation a, this probability is exactly 1 - + (
C.2. Example showing gap between MAD and Basic DP SIPS
While Theorem C.1 bounds the worst-case behavior of our algorithm compared the basic algorithm, MAD increases the weight of items below compared to the basic algorithm, will often have larger output. We show simple, explicit example where our algorithm will substantially increase the output probability of all but one item.
Here, we demonstrate an explicit setting where MAD outperforms the baselines. There are n users each with degree 3 as well as a single heavy item and m light items. Each user's set is comprised of i as well as two random light items. Under the basic algorithm, each user will contribute 1/v3 to each their items. Therefore, the weights under Basic are
n
i
wii)
v3
2n
1.16n
O.W.
73m
On the other hand, assuming n >> т, MAD will reroute almost all of the initial weight on the heavy item back to the users, so each user will have excess weight approximately 1/3. For dmaz = 3, we get discount factor a >> 0.5. So, each user will send approximately 1/18 weight to each of its items. The weights under MAD are
T
+
18
if i-=
2n
1.27m
18
O.W.
In this setting, our algorithm will assign close to 10% more weight to the light items (resulting in substantially higher probability of output) compared to the basic algorithm. a/m is close to the true threshold p. this gap will have large
22

---

Scalable Private Partition Selection via Adaptive Weighting
effect the final output size. We empirically validate this for n 15,000, m 1000, 1, 10-5 Our algorithm returns 610 items average. The basic algorithm returns 519 items while DP-SIPS with a privacy split of 5%, 15%, 80% or 10%, 90% returns 332 or 514 items, respectively. In all cases, expected, our algorithm has significantly higher average output size.
23

---

Scalable Private Partition Selection via Adaptive Weighting
D. Additional Figures
Basic
12000
DP-SIPS
MAD
10000
MAD2R
Output Size
8000
6000
4000
2000
0.0
0.5
1.0
1.5
2.0
2.5
3.0
Figure 2: Comparison of output size across parallel algorithms while varying privacy parameter the Reddit dataset. Other parameters are fixed as described Section with fixed privacy split of (0.1,0.9) 0.9] for DP-SIPS and MAD2R. The relative performance algorithms does not change with this parameter. Increasing E significantly improves performance at the cost of privacy by lowering the required noise and threshold.
Basic
9000
DP-SIPS
MAD
8000
MAD2R
7000
Output Size
6000
5000
4000
3000
2000
10
10-9
10-8
10-7
10-6
10
10
10
Figure 3: Comparison output size across parallel algorithms while varying privacy parameter ō on a log-scale on the Reddit dataset. Other parameters are fixed as described in Section with a fixed privacy split of 00.9 for DP-SIPS and MAD2R. The relative performance of algorithms does not change with this parameter. Increasing 5 significantly improves performance at the cost of privacy by lowering the required noise and threshold.
24

---

Scalable Private Partition Selection via Adaptive Weighting
6000
5500
Output Size
Basic
5000
DP-SIPS
MAD
4500
MAD2R
4000
3500
25
50
75
100
125
150
175
200
Ao
Figure 4: Comparison of output size across parallel algorithms while varying maximum set size parameter 6g on the Reddit dataset. Other parameters are fixed as described in Section with fixed privacy split of [0.1, 0.9] for DP-SIPS and MAD2R. The relative performance of algorithms does not change with this parameter, and good results are achieved long is too small.
6000
5500
Output Size
Basic
DP-SIPS
MAD
5000
MAD2R
4500
4000
60
80
100
dmax
Figure 5: Comparison of output size across parallel algorithms while varying the parameter dmea of algorithms the Reddit dataset. As this parameter only used by MAD and MAD2R, the performance the baselines is fixed. Other parameters fixed described in Scction with a fixed privacy split of 10.1, 0.9) for DP-SIPS and MAD2R. The performance of our algorithm relatively insensitive to this parameter.
25


Reviews:
[{"review_id": "DuCuvLz6cz", "reviewer": "Reviewer_jHbQ", "summary": "This work studies the problem of private partition selection, giving two new, highly parallelizable algorithms for privately outputting as large a subset of the union of user datasets as possible under the constraints of user-level privacy (MAD and MAD2R). They prove that their algorithms satisfies approximate differential privacy and argue utility through a “stochastic dominance” theorem, showing that \nany elements of the union output by a simple reference algorithm with probability greater than some threshold will also be output with good (but possibly lower) probability by MAD\nAny elements of the union output by the simple reference algorithm with probability below that threshold will be output by MAD with probability at least as high. \n\nThey empirically evaluate the performance of their algorithms on Higgs, IMDb, Reddit, Finance, Wiki, Twitter, Amazon, Clueweb, and Common Crawl datasets, comparing their utility to similarly parallelizable baselines as well as sequential (but higher utility) algorithms.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper!\n\n### When to use MAD2R vs. DP SIPS (from Questions) and theoretical justification compared to DP SIPS\n\n**MAD2R should always be preferred to DP SIPS** by practitioners as it is strictly better (both for fundamental theoretical reasons and confirmed in experiments). Below, we emphasize the justifications in the paper that we provide for this claim.\n\n**Theoretical justification**:\n\nIn the design of MAD2R, we made two key independent contributions: (1) the novel single round adaptive algorithm MAD and (2) the ability to reuse noisy weights from previous rounds in a private way to boost utility. The main theorems of our paper prove that both of these design choices preserve $(\\varepsilon, \\delta)$-DP. Furthermore, we show that MAD stochastically dominates the Basic algorithm (which is the one used in DP SIPS in each step). Directly comparing MAD2R and DP SIPS, since MAD2R uses MAD in the first round and DP SIPS uses Basic, MAD2R will provably outperform DP SIPS in the first round. In the second round, MAD2R is also strictly superior to DP SIPS in an information theoretic sense: thanks to our privacy proof, our algorithm has access to and utilizes strictly more information from the private data than DP SIPS, all with *no* privacy loss. DP SIPS only gets binary information about whether noisy item weights from the prior round were extremely large (i.e., above a very high threshold). MAD2R uses **all** of the noisy item weights from the prior round (not just whether they are above threshold). To summarize, MAD2R is designed to always improve upon DP SIPS by being more adaptive in two ways while maintaining the same privacy guarantees. Doing some without affecting the privacy analysis (and for instance requiring more noise) is a novel contribution of our work.\n\nFor further theoretical justification, in Appendix C.2, we show a constructive  example where MAD (even with just one round) will outperform DP SIPS. The theoretical intuition is that if users has a popular item (present in all users) and a normal item (present in only a fraction of the users), DP SIPS will use the same fixed amount of budget in its first round on the popular item and the normal items even though the weight of the popular item may far exceed the threshold. On the other hand, MAD will adaptively reroute weight from the popular item to the normal items within a single round, thus outperforming Basic and DP SIPS. Heterogeneous item frequencies appear in real data (see response to reviewer 9UnS) where we observe both very popular items and many less popular items (i.e., data has a heavy tail distribution).\n\n\n**Empirical justification**:\n\nWe verify this claim experimentally by showing that MAD2R outperforms DP SIPS in **every case** we test. It outperforms DP SIPS for each of the 9 datasets and for every parameter setting of $\\varepsilon$, $\\delta$, $\\Delta_0$, and $d_{\\max}$.\n\n### More intuition about parameters\n\nThanks for the suggestion to provide more intuition about parameters. Here, we discuss some key parameters of our algorithm, how they affect privacy and utility, and how we chose to set them.\n\nMaximum bias $b_{\\max}$: A larger maximum bias allows for the algorithm to more aggressively increase weights in the second round to items which didn’t receive very large noisy weights in the first round. It directly affects the novel $\\ell_\\infty$ sensitivity of the algorithm, thus increasing the threshold. Consider a neighboring dataset with a novel user with some items which don’t appear in any of the existing users’ sets. In the worst-case scenario, this novel user can assign up to $b_{\\max}/\\sqrt{d}$ weight to any of its novel items.\n\nMinimum bias $b_{\\min}$: A smaller minimum bias allows for the algorithm to more aggressively decrease weights in the second round on items which received very large noisy weights in the first round. In order to prove that MAD maintains privacy, we only do adaptive rerouting for users with degrees at least $1/b_{\\min}^2$. See the response to Reviewer bvMj for more details.\n\nMaximum adaptive degree $d_{\\max}$: Raising the maximum adaptive degree increases the set of users which can participate in adaptive rerouting in MAD. On the other hand, it reduces the amount of weight which is rerouted for each of those users. It is very challenging to design an algorithm which maintains privacy while being adaptive. To do so, we limit the adaptive users to rerouting weight inversely proportional to $1/d_{\\max}$ rather than $1/d$. See the response to Reviewer bvMj for more details.\n\nDiscount factor $\\alpha$: The reason for our choice of the discount is simply to satisfy a technical condition. We set the discount as a variable and perform the $\\ell_2$ sensitivity analysis in Lemma B.6. At the end of the analysis, we have a bound on the sensitivity involving this variable (see lines 1005-1020), and we set the variable to be as large as possible so that the upper bound is 1.", "claims_and_evidence": "The claims made in the paper are primarily supported via proof, with the exception of claims of improvement in utility over an alternative parallel algorithm (DP-SIPS). This is evaluated empirically, and through a constructed example on which MAD can be argued to have higher utility.", "methods_and_evaluation_criteria": "Yes, the benchmarks make sense for this application, to the best of my knowledge.", "theoretical_claims": "I read the proofs of privacy and utility contained in the appendices and found no issues.", "experimental_designs_or_analyses": "I did not check the validity of the experimental design.", "relation_to_broader_scientific_literature": "The paper is very clear about how its contributions relate to prior work. The authors identify two approaches to partition selection in prior work: parallel and sequential algorithms, and compare their proposed algorithms to prior algorithms in both categories, focusing on parallel algorithms (as their new algorithms are parallelizable).", "essential_references_not_discussed": "To the best of my knowledge there are no references that are not discussed.", "other_strengths_and_weaknesses": "Strengths: the paper is well-organized and comparison to prior work is clear. The evaluation demonstrates that their proposed approach to private partition selection may yield improved utility compared to existing parallel algorithms. \n\nWeaknesses: while the authors describe the new algorithmic approach in some detail, the description is largely in terms of parameters of the algorithm and manipulation of weights. I would have benefited from some additional intuition for what these parameters are \"doing\" (e.g. what is the discount factor, why is it set the way it is?). \n\nIn addition, the lack of theoretical justification for utility improvement compared to DP-SIPS makes it hard to assess the significance of the contribution. None of the parallel algorithms, MAD and MAD2R included, improve upon the sequential algorithms, and within the class of parallel algorithms, DP-SIPS outperforms MAD and seems competitive with MAD2R on many datasets. MAD2R does appear to outperform DP-SIPS on average, but I think a more thorough analysis of when a practitioner may want to use MAD2R over DP-SIPS and vice versa would help to contextualize the results.", "other_comments_or_suggestions": "Page 2: \"And outputting\"\n\nPage 4. Sigma is used in the pseudocode before it's defined in the text. \n\nPage 6. \"For parameters $C_{lb}$, $C_{ub} \\geq 0$, Let\"\n\nPage 20. \"To look for stationary points and will set the derivative of f to zero\"", "questions_for_authors": "See comments in strengths and weaknesses. What guidance would you offer practitioners on when to use your algorithms as opposed to others?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "S766Tq2T7x", "reviewer": "Reviewer_Jbgz", "summary": "The paper deals with the problem of differentially private set union.\nEach user holds a subset of items from an unbounded universe, and the goal is to output as many items from the union of all the users' sets while maintaining user-level privacy.\nUseful intuition for the problem is that items held by a single user should not be output, whereas items held by many users are fine to output, motivating weighting-based algorithms.\nSuch algorithms work in the following way: 1) each user contributes a weight vector over the items they hold, 2) all weights are summed together centrally, 3) each item is privately checked to be above a threshold, 4) item above the threshold are released.\n\nThe processes in which these weights are derived from users' sets distinguishes these algorithms.\nOne approach is to greedily produce weights by sequentially interacting with each user and letting their weight update depend on every past weight update (Gopi et al., 2020; Carvalho et al., 2022).\nThis approach produces good results, but is not apt for massively parallel computation.\n\nA more scalable approach is to interact with each user in rounds.\nThe first such scalable algorithm was uniform weighting (Korolova et al., 2009) where each user's items contribute uniformly to the weight, and this was performed for one round.\nLater DP-SIPS (Swanberg et al., 2023) made the amendment of splitting the privacy budget over multiple rounds, and running uniform weighting in each round.\nItems selected in preceding rounds got removed in future rounds, and finally the union of the private unions from each individual round is released.\n\nThis paper improves on the uniform weighting procedure.\nSimplified, they show that it is possible to make it adaptive (Algorithm 2, MAD).\nAfter running uniform weighting, they truncate weights $w(i) \\geq \\tau$, where $\\tau$ is a parameter, to $\\tau$, and re-route these weights back to users, proportionally to how much they contributed.\nThe intuition is that items with large weights are likely to exceed the private threshold check, so by re-allocating weight to other items (if that is possible to do at no cost in privacy) we can expect to be able to release more items.\nThe authors show that, indeed, this re-routing is possible to perform without increasing the sensitivity of the procedure (Lemma 4.1 and Lemma 4.2), and that it stochastically dominates uniform weighting (Theorem 1.2).\n\nThey also consider a biased 2-round version of MAD (Algorithm 5, MAD2R), where the weights of items not released in the first round are re-used for the second round.\nEssentially, items with very low weights in the first round are removed from the second round (because they are unlikely to be output, and so the weight can be better spent elsewhere), and items with very large weight are biased to not overshoot the threshold by as much (also allowing for shifting weights around).\n\nThe paper supports the theoretical results with empirical work (Section 5, Table 1).\nThe authors demonstrate that their single and 2-round algorithms (MAD and MAD2R) improve on existing parallel algorithms for all shown datasets.\nSequential algorithms consistently outperform the parallel algorithms, which makes sense and is well-explained.\n\n## update after rebuttal\n\nI find that the authors have adequately addressed questions raised by the reviewers, and I appreciate the additional experiments they have run in support of their rebuttal. For my own questions, the privacy budget split for DP-SIPS and the source of the improvement for MAD2R is now clearer to me. I have upgraded my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper! We respond to your comments and questions below.\n\n### Number of rounds for MAD2R and DP SIPS (Question 3)\n\nFor this problem, using more rounds does not necessarily translate to better performance. There is a fixed privacy budget and more rounds means less budget per round and therefore more noise and higher thresholds. We address the specific question of more rounds for MAD2R and DP SIPS separately below.\n\n**DP SIPS:**\n\nIn our paper, we report the best performance of DP SIPS with either 2 or 3 rounds (also with 1 round as then DP SIPS is equivalent to Basic). We do this in order to give this baseline a more favorable comparison compared to our results (notice that we allow DP SIPS to non-privately use the best parameter setting, something we do not do for our algorithms). We used 2 or 3 rounds for DP SIPS following the suggestions of the DP SIPS paper which uses three rounds as a standard choice. In our experimentation, we confirm  that 2 or 3 rounds of DP SIPS with a good privacy split (such as [0.05, 0.15, 0.8]) generally performs well without seeing benefits from more rounds. Below, we report many choices of privacy splits for 4 and 5 rounds on the Reddit dataset for context confirming that no improvement is observed. We report the number of rounds, the privacy split across rounds, and the output size. The best result is achieved in 3 rounds and the second best at 2 rounds.\n\n1 round, [1.0]: 4059\n\n2 rounds, [0.10, 0.90]: 5731\n\n**3 rounds, [0.05, 0.15, 0.80]: 5797**\n\n4 rounds, [0.10, 0.10, 0.20, 0.60]: 5037\n\n4 rounds, [0.10, 0.10, 0.10, 0.70]: 5199\n\n4 rounds, [0.05, 0.05, 0.05, 0.85]: 5404\n\n4 rounds, [0.05, 0.10, 0.15, 0.70]: 5423\n\n4 rounds, [0.01, 0.04, 0.05, .90]: 5598\n\n5 rounds, [0.05, 0.10, 0.15, 0.20, 0.50]: 4452\n\n5 rounds, [0.10, 0.10, 0.10, 0.10, 0.60]: 4666\n\n5 rounds, [0.05, 0.05, 0.05, 0.05, 0.80]: 5239\n\n**MAD2R:**\n\nWe designed MAD2R to utilize two rounds. From any given round, MAD2R is able to use strictly more information than DP SIPS. DP SIPS only gets binary information about whether noisy item weights from the prior round were extremely large (enough to pass a very high threshold). MAD2R uses **all** of the noisy item weights from the prior round. In order to optimize this information, we want to minimize the noise in prior rounds. We choose 2 rounds in order to maximize the privacy budget in each round to get accurate noisy estimates from the first round and then to minimize the threshold in the second round when we make use of those noisy estimates.\n\nAn intuition as to why 3 rounds is a good choice for DP SIPS is that the first round captures very frequent elements, the second round captures the next tier of quite frequent elements, and the third round captures remaining moderate frequency elements. Because of our innovation of using noisy weights from prior rounds, we can achieve better results in two rounds by getting and utilizing all of the information about frequent/moderately frequent elements in one shot.\n\n### Breaking down the performance of MAD2R (Questions 1 and 2)\n\nThanks for the suggestion of running MAD2R with $d_{\\max}=0$ to understand the impacts of adaptivity via MAD vs. adaptivity via reusing noisy weights. We stress that both of these uses of adaptivity are key innovations in this work. The ability to re-use weights from prior rounds is a technical innovation of our work which was not present in prior work and thus should be considered a contribution of our paper. The conceptual idea of reusing weights and the proof that this is private are important parts of our work and a key enabler of additional performance gains.\n\nWe ran the numbers for the Reddit dataset and get the following result:\n\nDP SIPS: 5784\n\n**MAD2R: 6215**\n\nMAD2R ($d_{\\max}=0$): 6197\n\nOur contribution of using noisy weights from prior rounds to bias MAD2R in the second round constitutes the majority of the improvement over DP SIPS. Utilizing MAD with $d_{\\max} > 0$ has added benefit at no cost (as using MAD with adaptivity stochastically dominates the Basic algorithm). On the same dataset, for single round algorithms, MAD beats Basic by 100 items. (for the larger common crawl datasets we output 100,000+ more items). The main effect of MAD within the two round MAD2R is in the first round where we know nothing about the distribution of item weights. In the second round, because we are biasing weights, it is unlikely that many item weights will be significantly overallocated and therefore the amount of wasted weight to reroute is less. Though we only use a 10% privacy budget in the first round, utilizing MAD2R with $d_{\\max}=50$ still contributes more than 10% of the benefit of MAD over Basic.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The intuition conveyed in the main paper is mostly clear, and I checked that proofs existed in the appendix, but I did not check any proofs in detail.", "experimental_designs_or_analyses": "Yes, the experiments look sound to me.", "relation_to_broader_scientific_literature": "The paper improves on existing parallel algorithms for parallel private partition selection (Korolova et al., 2009; Swanberg et al., 2023) and compares against sequential algorithms for the same problem (Gopi et al., 2020; Carvalho et al. al., 2022).\nI am not familiar with other related work in the literature that warrant mentioning in this context.", "essential_references_not_discussed": "None that I am aware of.", "other_strengths_and_weaknesses": "Strengths:\n1. Well-written paper with good structure.\n2. The idea of shifting around weight for items to increase the chance of more items exceeding the threshold is natural and makes sense. The fact that it is possible to do without increasing the sensitivity of the weighting procedure is surprising to me, and nice.\n3. The stochastic dominance of MAD over Basic is a nice property of the paper.\n4. The empirical work supports the paper well.\n\nWeaknesses:\n1. The choice of number of rounds in the experiments for DP-SIPS, and only considering a 2-round version of MAD, seem like arbitrary choices.\n2. The improvement MAD2R achieves over DP-SIPS is not that large.\n3. From the experiment, it is unclear what drives the improvement, and it is not easily inferred from the paper.\nIn particular, the improvement MAD2R achieves over DP-SIPS is not obviously as much due to MAD, as much as it is from re-using the weights across rounds.", "other_comments_or_suggestions": "Typos:\n363r: adpativity", "questions_for_authors": "I ask the following questions to better understand the empirical results in Section 5.\n\nQuestions:\n1. Can you comment on what you believe drives the improvement shown in Table 1? Since MAD slightly improves over Basic, it could be that the improvement MAD2R achieves over DP-SIPS comes largely from using weights from the first round in the second round, rather than the improvement \"within\" each round, i.e. MAD's improvement over uniform weighting.\n2. If I understand it correctly, MAD2R with $d_{max}=0$ is essentially running 2-round DP-SIPS and re-uses weights in the second round. Did you try running DP-SIPS combined with re-using the weights across rounds?\n3. Is there any reason why you only consider a 2-round version of MAD (and why DP-SIPS only goes up to 3 rounds)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PHDivCTh1U", "reviewer": "Reviewer_9UnS", "summary": "This paper studies private partition selection (or set union) under the constraint of differential privacy (DP). Here, they consider user-level DP (UDP), where each user is allowed to contribute multiple points to the dataset. It provides both theoretical and experimental results to to show that their work improves on the prior work. Also, there is more computational efficiency in this work owing to being able to parallelize the algorithm. This is the first paper that is able to achieve both utility and the ability to be parallelized at the same time. They test on 9 different datasets, including on those used in recent prior work. It provides two algorithm, $MAD$ and $MAD2R$, where the latter is a multi-round version of the former, and provides better guarantees, as well. The techniques rely on weighting and reweighting the items privately in order to recover items closer to the tail ends of the dataset.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper!\n\n### Absolute utility (Question 1)\n\nYour intuition that the raw number of items output by our algorithm (and any private algorithm) is affected by the long tails of the dataset is absolutely correct! We report some interesting new results on how the frequency of the items in the raw data affect their output probability. We will include these in our paper. \n\nIt is widely-known that in many user-provided datasets, items have a heavy-tailed distribution where many items are infrequent and some items are highly prevalent. It is a requirement of any DP algorithm that **items belonging to few users cannot be output**. Thus, privacy can prevent outputting the majority of items in heavy-tailed datasets. On the other hand, while fewer in number, the more frequent items are often the most important, especially for downstream applications. Hence, it is essential to output as many items as possible among the ones that are possible to be output with privacy protections.\n\nWe demonstrate that MAD2R is doing a good job of covering high frequency items that can actually be safely output, showing that most of the loss comes from items that (essentially) cannot be output due to privacy by any private algorithm. Below, we analyze the Reddit dataset and the very large Common Crawl dataset.\n\n**Reddit**\n\nThe Reddit dataset has 143,556 unique items, of which 83,313 (58%) are singleton items–they only appear in a single user’s set. Any algorithm which outputs any of these singleton items is *not private* by definition, as it is leaking private information belonging to a single user. For any private algorithm with acceptable privacy settings, outputting items with very small frequencies is also simply not possible.\n\nMAD2R outputs 6,340 items (4.4%) on the Reddit dataset with the standard parameter settings in our paper. On the other hand, 98% of users have at least one item output by MAD2R. And 45% of the entries (user-item pairs) belong to an item which is output by MAD2R.\n\nWe break down the number of items of different frequencies which our algorithm returns. Notice that MAD2R outputs the vast majority of items with large enough frequency (as expected, very few low frequency items are output and no singleton items are output). The numerator is the number of such items returned by MAD2R and the denominator is the number of items in the dataset in the frequency range:\n\nFraction of items returned with frequency in [1,2): 0/83313 = 0.0000\n\n… in [2,50): 28/134765 = 0.0002\n\n… in [50,100): 878/3207 = 0.2738\n\n… in [100,200): 2007/2274 = 0.8826\n\n… in [200,500): 1668/1680 = 0.9929\n\n… in [500,infinity): 1630/1630 = 1.0000\n\n**Common Crawl**\n\nThe results for Common Crawl are very similar to the ones in Reddit. MAD2R outputs 28,967,624 out of 1,803,720,630 (distinct) items. That is 1.6% of the total. However, as we can see in the table below 61% of all items are unique (and can’t be output by any private algorithm). Moreover, our algorithm covers the majority of items that appear in at least 200 users (out of billions of users). More importantly, 99.9% of users are covered by at least one item and 98+% of entries in the dataset belong to an item in output by our algorithm. \n \nFraction of items returned with frequency in [1,100000000000): 28967624/1803720630 = 0.016\n\n… in [1,2): 21/1109806713 = 0.000\n\n… in [2,50): 251364/627294180 = 0.000\n\n… in [50,100): 1445285/21404804 = 0.068\n\n… in [100,200): 4100448/14714470 = 0.279\n\n… in [200,500): 7366701/12902081 = 0.571\n\n… in [500,1000): 5105166/6326548 = 0.807\n\n… in [1000,100000000): 10697894/11271089 = 0.949\n\nThis suggests that the utility is very high for downstream applications and a large fraction of the loss is on items that should not be output by a private algorithm (as they are unique to a small number of users).\n\nThank you for suggesting this analysis. We will add more details about this in the final paper.\n\n### More rounds for low-weight items (Question 2)\n\nAs you suggest, spending more resources on moderate weight items is the key challenge to improve performance for this problem (we say moderate as opposed to low as very low weight items simply cannot be output while maintaining privacy). However, there are two challenges with the general concept of spending more rounds on moderate weight items.\n\nFirst, we do not know what items are going to have moderate weight apriori. This is why our contribution of using noisy weights from prior rounds is so useful and opens up a new design space for parallel algorithms. Second, using more rounds does not necessarily translate to better performance. There is a fixed privacy budget and more rounds means less budget per round and therefore more noise and higher thresholds.  For MAD2R, we choose 2 rounds in order to maximize the privacy budget in each round to get accurate noisy estimates from the first round and then to minimize the threshold in the second round when we make use of those noisy estimates.", "claims_and_evidence": "The claims that are made in the paper are as follows.\n1. Their work satisfies $(\\varepsilon,\\delta)$-DP.\n2. Their algorithms show statistical dominance over the prior work.\n3. Their work can be run on a distributed system whilst being parallelized.\n4. Their work also performs better empirically on different datasets than the prior work.", "methods_and_evaluation_criteria": "They do. The experimental results compare the right form of utility with that of the prior work for different datasets and privacy parameters.", "theoretical_claims": "I vaguely skimmed through the proofs as they were all part of the appendix, as opposed to the main body. They looked alright in that read.", "experimental_designs_or_analyses": "As said above, the experimental design was simple and relevant for this problem. The conclusions drawn from the experiments were sound. I checked the plots in the appendix, in addition to the table in the main body.", "relation_to_broader_scientific_literature": "This is a very relevant problem in ML. This can fit as a building block for privacy-preserving ML applications. This certainly improves significantly on the prior work, but the problem by itself wouldn't be as interesting, if it didn't have applications in other areas. All in all, it does help in larger applications, so I don't have any complaints with the problem being solved and the practicality of their solutions.", "essential_references_not_discussed": "None that I can think of.", "other_strengths_and_weaknesses": "Strengths:\n1. This is the first paper that is both accurate and computationally efficient in the sense that the algorithm could be parallelized. This is a big win in terms of practicality.\n2. The utility dominates that of the prior works, including on the datasets that were being previously used to test those relevant algorithms.\n3. They have used 9 datasets to test their algorithms, which is comprehensive enough.\n\nWeaknesses:\n1. Whilst their results have improved on the prior work, often the percentage of improvement isn't that high, especially given that the prior works weren't super high utility either. It's good though that their work is consistently better than all the prior work for all the datasets.\n2. One more thing that I'm not entirely sure about is the absolute utility. I'm referring to the percentage of the items recovered by their algorithms. For example, the Common Crawl dataset has over 1.8 billion items, but you're managing to recover only about 29 million. Whilst that is an improvement over the prior work, it still doesn't get to recovering even 50% of the total items.", "other_comments_or_suggestions": "Nothing major. I would address my comment in Weakness 2 above in the paper, for sure. Also, indicating how many items that were missed were actually at the tail end of the dataset, and why they were missed by the algorithm.", "questions_for_authors": "1. Is my assessment in Weakness 2 correct? If so, what was the reason so many items were missed?\n2. Can we get even more utility by having more rounds for the very low-weight items? In DP statistics, often multi-round algorithms are used, for example, for Gaussian covariance estimation by Kamath et al 2019 and Kamath et al 2020. Here, we could repeatedly remove heavy items, and look at lighted items in the next round. Could that kind of an idea help? Maybe it won't just be post-processing though.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5YgvFRp3Rj", "reviewer": "Reviewer_bvMj", "summary": "This work focuses on differentially private partition selection problem, which is very crucial for many underlying applications like NLP. In this problem, the system would like to extract the data as much as possible it can do from users while preserving users’ privacy. It proposes an adaptive and non-uniform weighting algorithm (MAD) with ability of parallelization to tackle the problem. In addition, it also proposes MAD2R to maximize the output in the second round of mad.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper! We respond to your comments and questions below.\n\n### Organization with the appendix and conclusion section\n\nThanks for the comment and suggestions! We agree that it would be a preferable reading experience to bring more content from the appendix into the main body but are limited by the page limits. We will address your specific suggestions in terms of what content to move into the main body in the final paper. Likewise, we will include a conclusion in the final paper.\n\n### Reason for limit on adaptive degree (from Questions)\n\nThis is a good question: the reasons for the upper and lower degree bounds for which users can be adaptive are to ensure that the sensitivity of MAD is bounded, and we elaborate on the technical reasons below.\n\nUpper bound: In the initial $\\ell_1$ bounded allocation of MAD, we limit the adaptive users to rerouting weight inversely proportional to $1/d_{\\max}$ rather than $1/d$. If we allowed users with degree more than $d_{\\max}$ to be adaptive, this allocation would have an $\\ell_1$ norm more than $1$. The choice to use $1/d_{\\max}$ weights is used throughout the proof of Lemma B.6 regarding the $\\ell_2$ sensitivity of MAD. Without this restriction, the algorithm would not be private as a novel high degree user could cause many low degree users to reroute their weight which could be overly concentrated on a few items. By using $1/d_{\\max}$, we limit the amount low degree users can reroute to any given item.\n\nLower bound: The lower bound on the degree of adaptive users is used on line 1001 in order to ensure that the final $\\ell_2$ sensitivity of MAD can be bounded by 1. For users with too small degrees, we cannot bound the expression at the end of Lemma B.6.", "claims_and_evidence": "Claims made in this work are well expresses in the Algorithm 2 and 5 for MAD and MAD2R respectively. With the purple statements in those algorithms, each step is clarified with easy understanding.", "methods_and_evaluation_criteria": "MAD and MAD2R are clear with detailed pseudo codes, which are easy to reproduce for the future research and datasets selected are diverse from small scale to large size to demonstrate scalability and parallelization of this work.", "theoretical_claims": "The theory mentioned in the paper looks convincing (with reading appendix), but authors hide too many details in the appendix, such as proofs to the theorems. I think authors can shorten the narrative parts in the contribution section and put add some more details for Theorem 1.1 and 1.2 instead of saying they are informal version of the things they discuss in the appendix.", "experimental_designs_or_analyses": "The experimental designs in this work is great because it first compares with sequential algorithms like PolicyGaussian in Gopi et al., 2020 and GreedyUpdate in Carvalho et al., 2022, and then with parallel approaches like DP-SIPS and proposed algorithms in this work. All experimental settings are well explained. If authors can put some figures from Section E in the appendix into Section 5, it would provide a better visual sense to audiences.", "relation_to_broader_scientific_literature": "1. Korolova et al., 2009 pioneered the DP partition selection problem by constructing the sampling-and-weighting format, which is the closest works for the problem on massively parallel computation, but they are based on uniform weighting strategy, which is considered loss in privacy. \n2. Prior algorithms like Gopi et al., 2020 and Carvalho et al., 2022 only run on a single machine storing data in the memory while this work can efficiently work for massively parallel computation systems with constant rounds. \n3. Swanberg et al., 2023 is the most related work to this work. DP-SIPS in that paper is the pioneering work with weighting other than basic weighting and a parallel setting. This work also compares with DP-SIPS deeply in MAD2R section.", "essential_references_not_discussed": "To my best knowledge, authors covered most essential works related to this topic.", "other_strengths_and_weaknesses": "Strengths:\n\n1. Compared to prior works, this work can be better to allocate weights instead of using same noise and threshold for a certain privacy parameters.\n\nWeakness:\n\n1. As mentioned in the previous sections, authors put too many details in the appendix and point audience to read everything back and forth. The reading experience will lower down by this kind of management.", "other_comments_or_suggestions": "Can you provide a comprehensive conclusion section by concluding the work and also providing some future work according to private partition selection?", "questions_for_authors": "Why does users with a too small or large cardinality use non-adaptive approach in MAD?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a new DP algorithm for partition selection (a.k.a. set union), with an emphasis on parallelization. The proposed algorithm is provably better than the naive parallel baseline, and empirically outperforms a prior parallel algorithm. Its utility is weaker compared to earlier non-parallel algorithms. One nice aspect of their analysis is the idea of shifting weights without increasing sensitivity - this is somewhat reminiscent of the "waterfill" algorithm by Gopi et al., though that approach was sequential and didn't involve routing weights back to users. All the reviewers agree that this is an interesting paper that would make a solid contribution to ICML.
Decision: Accept (poster)