Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper shows that the Count (Median) Sketch and the Count Min sketch for frequency estimation can be made differentially private by adding a small amount of Gaussian noise. The sketches are then used for quantile estimation, similarly to how the non-private sketches are used for the same problem.
strengths_and_weaknesses: For better or worse, this is a very straightforward application of textbook differential privacy techniques. The small dimension of the sketch leads to a good bound on the ell_2 sensitivity, which allows adding a small amount of Gaussian noise to achieve privacy. This is a useful tool to have, but, in my opinion, a straightforward application of the Gaussian noise mechanism to a well-known sketch is not enough to meet the bar for publication.  The paper needs either a tighter analysis (note that a recent preprint by Pagh and Thorup claims a tighter bound on the error of the Count Sketch with added Gaussian noise), or a more impressive application.
questions: I would suggest giving either an improved analysis or a proof that your analysis is tight for either sketch. Alternatively, a less immediate application of the private sketches can also strengthen your paper.
limitations: No comment.
review_title: null

final_score: 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.
review_content: summary: This paper demonstrates that linear sketches can be made differentially private by adding a small amount of Gaussian noise at initialization. Experimental results on Zipf and the real CAIDA dataset show that the utility is less influenced by this modification.
strengths_and_weaknesses: Strengths:

- Trendy topic
- Well-organized paper
- The improvement is simple yet effective

Weaknesses:

- The assumption limits the application scenarios
- Lack of analysis

Detailed Weakness Comments:

This paper points out that linear sketches can be made differentially private and provide useful information while maintaining their original properties. Specifically, contrary to the standard operation that initializes each counter with 0, the authors initialize each counter with a noise sampled from certain Gaussian distribution, whose parameters are determined by the accuracy parameter, failure probability, and budget for zCDP.

I like this idea overall, though this modification is small, the authors prove that this could make the linear sketches differentially private. However, this paper also has some flaws, such as the assumption, and lacking analysis of the case where the adversary is actively involved. I list my concrete concerns in the following:

W1. The assumption limits the application scenarios. In section 2.2, the authors briefly introduce linear sketches, they assume that item x has value v equals either -1 or 1, which limits the application scenarios of linear sketches. However, from algorithms 1 and 2, I didn’t see any operation that relies on this assumption. Therefore, I would like to know whether this is a redundant assumption, or if this assumption is required to make sure the private linear sketches satisfy differential privacy. If this assumption is only needed to achieve the DP guarantee, I think the trade-off between privacy and applicability should be discussed.

W2. It would be nice if the authors could provide a brief illustration about why vanilla linear sketch does not hold differential privacy property, which may make the improvement intuition clearer in this paper.

W3. Lack of analysis. The key idea to making existing linear sketches private is to initialize counters with random noise, as shown In algorithm 3. And the authors provide a series of analysis to prove that the modified scheme satisfies the DP definition, which is nice. However, I wonder whether these properties still hold when the private linear sketches are attacked. For example, the authors initialize counter C with E plus noise sampled from a gaussian distribution (for count-min case), yet, the attacker could eliminate this E in the initialization step, since E is determined once the accuracy parameter, failure probability, and budget for zCDP are fixed. I would like to know would the scheme still satisfy the DP requirement?  


questions: W1 and W3.
limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper present differentially private variants of linear sketches such as Count Min and Count Median sketches. The differential privacy guarantees are provided using a recent notion of differential privacy: zDP  [Dwork and Rothblum, 2016, Bun and Steinke, 2016]. The only change from vanilla sketches is the initialization provided in algorithm 3, which when combined with the update (Algorithm 1) and query (Algorithm 2) components of Count Min and Count median sketches leads to the differentially private versions of these sketches. The initialization itself adds Gaussian noise to each array item. Any other noise source satisfying zCDP would also suffice. The analysis of the algorithms directly follows by combining the analysis for vanilla sketches with the recent differentially privacy results.

 Building on the Differentially Private Count Median Sketch, the authors propose a Dyadic Count-Median sketch that can estimate all the quantiles simultaneously while ensuring differential privacy. The experimental evaluations validate the practicality of the algorithms.

Overall, while the algorithms presented, as well as their analysis, are not novel. The paper does a good job of reviewing the literature in two disjoint fields and providing a comprehensive set of differential private linear sketches, which need to be documented. Therefore, I recommend acceptance. 
strengths_and_weaknesses: 
1) The authors systematically study the literature on linear sketches and differential privacy and provide a comprehensive set of differentially private linear sketches
 2) The paper is well written and easy to follow.
3) However, there isn't any novelty either algorithmically or in the theoretical analysis of the algorithms: The only real change from an algorithm standpoint is the initialization phase of the linear sketches. The proofs follow by bootstrapping the standard proofs for linear sketches and using the recent differentially privacy results.
4) This would be a solid paper had the authors presented some sort of impossibility result for frequency estimation under privacy guarantees. 

questions: Can the authors comment on the lower bounds for the various problems considered? If not, can the authors comment on the challenges in coming up with such a result?
limitations: Yes.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper considers differential privacy for some standard sketches, determining their differential privacy bounds under Gaussian noise.  
strengths_and_weaknesses: Strength:

Natural problem from differential privacy.
Analysis + experiments.  
Good set of experimental results.

Weaknesses:
Analysis is straightforward.
Doesn't get same one-sided error bounds just a "with high probability" variant.

Originality:  I'm concerned about the originality.  In some sense, similar results (with perhaps weaker or incomparable results?, it's hard to tell) appear in other papers, such as 
Mir, D., Muthukrishnan, S., Nikolov, A., and Wright, R. N. Pan-private algorithms via statistics on
sketches. In Proceedings of Symposium on Principles of database systems (PODS), pp. 37–48,
2011. (which is cited in this paper)
and
Melis, L., Danezis, G., and Cristofaro, E. D. Efficient private statistics with succinct sketches. In
Annual Network and Distributed System Security Symposium (NDSS). The Internet Society, 2016. (which is not).  
The results seem to follow just by applying the standard Gaussian mechanism and then applying composition theorems from other work.  (Lemmas 2.7-2.9).  Perhaps nobody has written this down before, but I have trouble believing it was not known as it seems a straighforward composition.  

Quality:  Given the originality concerns above, the quality is OK.

Clarity:  The writing is generally good and clear.

Significance:  See the originality issues above.
questions: I believe there are other similar (contemporaneous?) works on the arxiv.  See https://arxiv.org/abs/2205.08397.
Perhaps you can compare with this paper.  
limitations: n/a
review_title: null

Meta-review: metareview: This work constructs differentially private linear sketches for frequency estimation and related problems. It shows that count min/median sketch can be made DP by adding noise. This is an interesting contribution.
The reviewers had concerns about the novelty of the paper. The (updated version of the) paper does a reasonable analysis of the algorithm. The authors point out in the rebuttal how their bounds are incomparable to a concurrent work. I am not convinced that the incomparable parts are interesting in the sense that closeness to the non-private count sketch does not seem like a useful goal in itself, and the target of interest is always the original frequencies.
The authors do an empirical analysis and show that the algorithm works well under reasonable privacy budgets. Overall, I think this paper may be a reasonable one to accept.
confidence: Less certain
Decision: Accept