Counting Distinct Elements Under Person-Level Differential Privacy

Summary

Suppose a data set consists of (user, item) pairs. The paper provides an estimate of the count of the number of distinct items that satisfies user level differential privacy. This differs from existing work in two ways. Existing work 1) considers item streams with item, not user, level differential privacy and 2) is highly concerned about computation costs and uses data sketches which have bounded size. It solves the problem by generating lower bounds with bounded sensitivity by converting the distinct count to a max flow problem.

Strengths

The paper introduces a novel user-level privacy formulation of the distinct count problem. The main ideas are presented well, and it is technically sound.

Weaknesses

1. The title could better describe the key feature of the problem, providing user level privacy. Since most distinct counting papers are about approx distinct counting and streaming/distributed algorithms, I think readers have an expectation that this paper would address this given the title and it's a bit of a let down when it doesn't. 2. The related work section is somewhat inaccurate in its descriptions. E.g. * Desfointaine et al is a universal result about any distinct counting method which is mergeable. Changing the algorithm design can't get around this. But the results only imply that you can't merge many times and preserve both privacy and accuracy, not that you can't build a private sketch. * Smith et al doesn’t actually analyze the Flajolet-Martin (a.k.a. PCSA) sketch but their own tweak of the LogLog sketch (by Durand and Flajolet). (Though this inaccuracy is totally understandable given their title.) * Dickens et al is also a universal result for any order invariant sketch. * Both Smith et al and Dickens et al are pan private in the streaming setting as well * Note neither claim to provide privacy under merges. 3. There is also some related work on private multiparty computation for distinct counts. e.g. "Privacy-Preserving Secure Cardinality and Frequency Estimation" Kreuter et al 2020 4. The empirical results for the greedy algorithm are nice, but the bound is quite bad for this application since it only gives you an estimate of the correct order of magnitude. It's also not clear what to do in large scale distributed data settings. These are fairly minor weaknesses given the paper's scope though.

Questions

1. What is the distinction between maximal and maximum bipartite matching? A quick search seems to regard these descriptions as the same problem. Does the greedy algorithm generate the maximal matching that approximates the maximum matching? 2. I'd be happy to increase the rating if the weaknesses 1 & especially 2 are addressed.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

yes

Summary

The authors study the fundamental problem of counting the number of distinct elements in a dataset in a user-level DP setting, where a user can contribute an unbounded number of items. The main contribution of the paper is an approach to obtain lower bounds through a bounded sensitivity count and a bias-variance perspective. The authors give interesting algorithms to compute it quite efficiently, and show a linear time version which trades off efficiency with accuracy. The algorithms are evaluated empirically and show good performance.

Strengths

The problem is very natural and well motivated. The approach considered in the paper, in terms of bounded sensitivity, seems quite natural, and is connected to a big literature on Lipschitz extension. The authors give rigorous bounds on the bounds achieved by their algorithms. The empirical results are also interesting, and show reasonable performance. The greedy algorithm is also shown to perform quite well. The presentation is quite good.

Weaknesses

The basic ideas in the paper, and the techniques used in the algorithms are fairly simple. The experiments section could be strengthened

Questions

In line 51, what is the motivation for considering M_{\ell,\epsilon}(D) - \frac{\ell}{\epsilon}\log(1/2\beta)? Is it assumed that there is a fixed \ell_{max} for all the data (line 58)? It appears as an input in procedure DPDISTINCTCOUNT, and in the bounds in Theorem 1.1. This should be clarified earlier in that case. The algorithm needs to know \ell_{max} in that case. Is there a way to specify it? Line 13 of algorithm 1 and line 10 of Algorithm 2: it might be helpful to make GEM consistent with the name "Generalized Exponential Mechanism" used in Algorithm 3 The baseline sampling algorithm mentioned in lines 131-134 is not really related work, but just a baseline, and could be in the experiments section. line 176: "three" should be "four" line 191: is the sampling done with replacement? What is the \epsilon value in Fig 1? Does the "Person Contribution Bound" refer to \ell_{max}? The plots are quite interesting. Is there an explanation for why the gap between the algorithms and the true counts decreases as in the figure? Tables 2 and 3 are not very easy to interpret. It might be easier to compare the counts as fractions or visually. How do the results vary with \epsilon? What is the motivation for considering \epsilon=1 in the person contribution for the baseline?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

To some extent. There are no negative social impacts

Summary

Edit: Overall decision recommendation changed from borderline reject to borderline accept under the expectation that limitations and future work directions as discussed in the reviewer discussion are incorporated into the manuscript. The manuscript studies the problem of approximating the number of unique items in a multiset under (user-level) differential privacy (DP). Unlike in prior work users can contribute arbitrarily many items to the multiset. The authors propose to select for each user a subset of contributed items that maximises the total number of unique items. The maximisation problem is solved exactly in polynomial-time via bipartite maximum matching or alternatively a 2-approximation is found in linear-time via a greedy algorithm.

Strengths

S1) Non-trivial results: Sensitivity analysis of approximate DC(D;l) and application of generalized exponential mechanism is interesting. S2) Could be useful: Probability that noisy count is a lower bound can be calibrated and lower bound can be useful to check if certain thresholds are exceeded. S3) Improvement over naive baselines: Computing/approximating DC(D;l) seems clearly preferable to selecting l random items for each user.

Weaknesses

W1) Heavily biased estimator. A DP count would seem to prohibit deterministic lower/upper bounds. While a lower bound w.h.p. could still be useful, most settings would seem to call for an unbiased estimator (see also Q1a & Q1b). W2) Quality of solution unclear. Apart from the poorly presented tables that do not clearly indicate the correct count, there is also no analysis of how much more utility could potentially be possible for this problem under a given DP regime. Thus, it is difficult to appreciate the solution in terms of how practically useful it is or how much utility is potentially lost due to the method (see also Q2a & Q2b). W3) Reproducibility While the datasets seem to be specified, the submission does not seem to provide code for experiments (see also Q3). W4) Minor: Some parts of the paper are hard to understand. Particularly, Section 3 could focus more on explanations related to the Generalized Exponential Mechanism (GEM) rather than well-known basics. It would be better to move the basics of DP and basic Exponential/Laplace mechanism to the appendix and instead provide more explanations/intuitions on how the GEM is used in this work, why it is needed and some intuitions how it leads to better results. W5) Minor: Sensitivity analysis of DC(D;l) is missing. It could be stated more explicitly why if a user is added that contributes X items DC(D;l) can increase by at most X, i.e., the added user cannot improve the solution for the previous users (e.g., due to optimal solution for previous users). That would also make it clearer why the sensitivity analysis for the approximation of DC(D;l) is non-trivial where an added user could potentially improve the solution for the previous users and removing a user could lead to less optimal solutions for the rest of users.

Questions

Q1a) Presuming number of distinct items per user cannot be arbitrarily large, is it possible to derive an unbiased estimator using the proposed method or is there some strong indication that any unbiased estimator would be inherently impossible (presuming upper limit on items per user) or could not provide good enough accuracy in this setting? Q1b) Is there some indication that the released noisy counts correlate with the correct counts sufficiently to rank multiple noisy counts somewhat accurately? Q2a) What is correct count for each table and what is the achieved count with the proposed method? Q2b) Is there any strong indication that the proposed solution could not be easily improved upon? Q3) Do the authors plan to release the code that was used for the experiments?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Some limitations do not seem to be mentioned (see Weaknesses W1) and there is generally no discussion of limitations in the abstract or an explicit paragraph in the main paper or appendix.

Summary

This paper proposes an algorithm to count the maximum number of unique items one can get from considering from every individual in a dataset at most l items, while preserving differential privacy.

Strengths

The paper offers an (as far as I know) original contribution, which is simple and nice. The explanation is clear. The result may be significant to the extent one can cast applications needing to count the number of unique items into the relaxation considered in the current paper. The paper performs an interesting empirical evaluation, even if it doesn't fully succeed to bring up a convincing application.

Weaknesses

The paper also proposes a linear time algorithm, which is very nice, but which makes a second approximation, making it even more unclear how to determine whether it is suitable for a specific application.

Questions

--

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The paper doesn't have a conclusions section, and doesn't mention limitations nor societal impact.