Scalable Private Partition Selection via Adaptive Weighting

Thank you for taking the time to review our paper! We respond to your comments and questions below.

Organization with the appendix and conclusion section

Thanks 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.

Reason for limit on adaptive degree (from Questions)

This 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.

Upper 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.

Lower 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.

Thank you for taking the time to review our paper!

Absolute utility (Question 1)

Your 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.

It 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.

We 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.

Reddit

The 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.

MAD2R 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.

We 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:

Fraction of items returned with frequency in [1,2): 0/83313 = 0.0000

… in [2,50): 28/134765 = 0.0002

… in [50,100): 878/3207 = 0.2738

… in [100,200): 2007/2274 = 0.8826

… in [200,500): 1668/1680 = 0.9929

… in [500,infinity): 1630/1630 = 1.0000

Common Crawl

The 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.

Fraction of items returned with frequency in [1,100000000000): 28967624/1803720630 = 0.016

… in [1,2): 21/1109806713 = 0.000

… in [2,50): 251364/627294180 = 0.000

… in [50,100): 1445285/21404804 = 0.068

… in [100,200): 4100448/14714470 = 0.279

… in [200,500): 7366701/12902081 = 0.571

… in [500,1000): 5105166/6326548 = 0.807

… in [1000,100000000): 10697894/11271089 = 0.949

This 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).

Thank you for suggesting this analysis. We will add more details about this in the final paper.

More rounds for low-weight items (Question 2)

As 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.

First, 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.

Thank you for taking the time to review our paper! We respond to your comments and questions below.

Number of rounds for MAD2R and DP SIPS (Question 3)

For 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.

DP SIPS:

In 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.

1 round, [1.0]: 4059

2 rounds, [0.10, 0.90]: 5731

3 rounds, [0.05, 0.15, 0.80]: 5797

4 rounds, [0.10, 0.10, 0.20, 0.60]: 5037

4 rounds, [0.10, 0.10, 0.10, 0.70]: 5199

4 rounds, [0.05, 0.05, 0.05, 0.85]: 5404

4 rounds, [0.05, 0.10, 0.15, 0.70]: 5423

4 rounds, [0.01, 0.04, 0.05, .90]: 5598

5 rounds, [0.05, 0.10, 0.15, 0.20, 0.50]: 4452

5 rounds, [0.10, 0.10, 0.10, 0.10, 0.60]: 4666

5 rounds, [0.05, 0.05, 0.05, 0.05, 0.80]: 5239

MAD2R:

We 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.

An 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.

Breaking down the performance of MAD2R (Questions 1 and 2)

Thanks 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.

We ran the numbers for the Reddit dataset and get the following result:

DP SIPS: 5784

MAD2R: 6215

MAD2R ($d_{\max}=0$): 6197

Our 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.

Thank you for taking the time to review our paper!

When to use MAD2R vs. DP SIPS (from Questions) and theoretical justification compared to DP SIPS

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.

Theoretical justification:

In 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.

For 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).

Empirical justification:

We 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}$.

More intuition about parameters

Thanks 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.

Maximum 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.

Minimum 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.

Maximum 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.

Discount 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.