Venue: NeurIPS 2022 Conference

Reviews:

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: A sketching algorithm for the distinct elements problem maps a stream of elements from some universe into a small space data structure (the sketch), such that an approximation to the number of distinct elements in the stream can be recovered from the data structure with high probability. Sketches thus compress the data, and it stands to reason that the task of designing a good sketch is aligned with the goal of preserving privacy with respect to the data in the stream. Recent work has confirmed this intuition, and shown that some specific randomized sketches for the distinct elements problem preserve differential privacy, provided that 

* the randomness used by the sketch is hidden from the adversary;
* the data stream contains sufficiently many elements: this can be achieved by padding.

The analyses in prior work are sketch-specific, and sometimes require modifying the existing sketch in ways that may affect its practicality. 

The present paper unifies this line of work, and, in a way, shows that the privacy preserving properties of distinct element sketches are a deeper property, common to a large class of sketches. Namely, all sketches based on random hashing that are invariant under permuting and duplicating elements satisfy differential privacy, and the privacy parameter depends on two quantities associated with the sketch. One of these quantities is automatically bounded when the stream contains enough elements, and the other is usually small enough with high probability, and, in any case, can be made small enough by subsampling the stream. This unified analysis gives improved bounds, in some cases, and allows ensuring privacy for the most efficient and practical variants of the sketches.
strengths_and_weaknesses: The unified analysis in the paper seems to get to the core of why distinct element sketches preserve privacy. The authors have found a good abstraction that allows isolating what makes a sketch private. Thus the proofs are simple, but give strong results for a wide class of algorithms. This makes the paper much more satisfying than papers that analyze just one sketch, even though there are some nice ones in that category as well.

One minor weakness may be that the unity of the results is somewhat undermined by the fact that $\pi(s)$ is not always bounded, which necessitates either a sketch-specific analysis, or preprocessing the stream by subsampling. The fix is simple, however, and does not affect error much. Also, even boiling down the privacy properties of a sketch to just one or two parameters is already quite interesting. 

A weakness of this line of work is that the proof of privacy requires the random hash to be secret, which means that the privacy properties do not hold in a distributed setting. I do not hold this against this paper in particular, however.
questions: The explanation on lines 177-184 is not very clear. The last sentence of the paragraph is a little puzzling. Looking at the supplementary material mostly clears this up.

There are some typos in the supplementary material: at least one missing reference, one typo that says “n < n_0” rather than “n > n_0” while referencing (23). Please proofread this part of the paper.

Do you think it’s possible to prove privacy for these sketches if the hash function is public but the stream is preprocessed in some random way?


limitations: I think limitations are addressed adequately.
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 proposes a general technique for proving that hash-based,
order-invariant sketching algorithms for cardinality (which encompasses most
known sketching algorithms for the problem) satisfy DP. The DP parameters depend
on an unconditional upper bound on the probability that a new element causes the state
of the algorithm to change, as well as a condition that the number of unique
elements in the stream be higher than some value. When the sketching algorithm
do not satisfy the conditions, they propose a lightweight, blackbox algorithm
that downsamples the stream and adds in "fake" unique elements, and show this
has no utility drawback and will satisfy privacy.

They derive tighter privacy guarantees for specific streaming algorithms and
validate their privacy and utility results.
strengths_and_weaknesses:   + The results are general: they are able to make sketching algorithms for 
  cardinality satisfy DP

  + The privacy overhead is small in terms of utility cost and computational
  cost

  + Their algorithm is even able to take non-private sketches which are costly
  to recompute and combine them
  with private sketches such that the entire computation will satisfy DP. 

  - One possible drawback is that the problem
    intuitively seems slightly ``easy'', see the limitations section.
questions: In the introduction, what are the paramters b,k? They should be explained here.
Is the privacy analysis close to being optimal or can a more fine-grained approach be
made, such as not having an unconditional upper bound on the stream update chance
\pi_0 but rather a time-dependent one?
limitations:     Sketching algorithms by their very nature seem to store a tiny amount of
    data and heavily use randomness. Thus, they should be close to being
    ``private'' already. It would be helpful if the authors could private a toy
    example where blatant non-privacy of the sketching algorithm is
    exposed. 

    This also raises the issue that perhaps the privacy analysis and techniques
    only work in this particular sketching setting. It would be
    helpful if the authors could compare and contrast these methods to other
    privacy work in sketching in related works section.
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: The paper studies the general problem of cardinality estimators in insertion only streams with differential privacy. The authors present a novel and general analysis framework that establishes the privacy property of a vast set of algorithms. The framework shows that any algorithm that is order invariant, based on a purely random hash,  limited in space, and with some sensitivity property is DP.  They show that many standard algorithms respect this property with a simple analysis. This results in improved approximation/privacy tradeoffs. More precisely they show that existing algorithms (not designed for privacy) are private on large enough streams or can be made private with a simple downsampling of the input. This is very useful in practice as it allows to reuse original implementations. The analysis framework seems easy to use and general. The authors also experiment with the algorithms derived.
The results hold a slightly relax setting for DP that involves cryptographic assumptions but this framework seems very reasonable.
strengths_and_weaknesses: + general framework for the analysis of algorithms
+ results hold for well known algorithm with no or limited modifications to their implementations
- slightly less strong setting for DP (requires cryptographic assumptions on secrecy of hash functions and indistinguishability from random distribution).
- works in the single release model not in the continual release model which is more applicable in stream settings.

questions: Would it be possible to clarify in a table what novel (or improved) tradeoffs between accuracy and privacy the method allows for the algorithms presented (vs the best known result)?

Do you think the work can be adapted to the continual release model?

Can you add a short statement that the algorithm gets better bound than simply running the non-private algorithm and then perturbing the output?
limitations: No negative impact to society
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 authors prove that nearly all **hash-based**, **order-invariant** cardinality estimators are differentially private once combined with a down-sampling procedure. This class includes several well-celebrated cardinality streaming algorithms such as Flajolet-Martin, HyperLogLog, and Bottom-k.
strengths_and_weaknesses: I really enjoyed reading the paper. The text is well-organized and the authors did a good job explaining the tedious math proof in an intuitive and easy-to-follow way. Overall I think the paper makes solid contribution and passes the bar of acceptance. Concrete strengths and weaknesses are listed below and I am willing to further improve the score if the authors can address most of the weaknesses in their rebuttal.

**Strength**:
1. The paper considers a class of cardinality estimators and proves DP for them as long as they satisfy several conditions, compared to prior works only considering one specific sketching algorithm.
2. The paper evaluates the update time and space ratio which exhibits the superiority of the proposed algorithm.

**Weakness**:
1. I am a little bit worried about the accuracy of the proposed sketching with down-subsampling. In Section 5, only update time and space ratio are evaluated. However, it is unclear how QLL and PHLL compares in terms of accuracy. If QLL is much better in accuracy, then a more thorough discussion of the different trade-offs between QLL and PHLL is needed. 
2. Subsampling is also known to provide privacy amplification for DP guarantees. In the proposed algorithm, down-sampling is used to eliminate the $\delta$ term. Does it also contribution to privacy amplification?
3. The related work section ignores some recent progress on DP streaming algorithms. These works consider a broader class of streaming algorithms in which cardinality estimation is a special case of order 0. Specifically [1]-[3] consider another special case of order 2 and [5] considers cases of real orders from 0 (exclusive) to 1.

[1] "The johnson-lindenstrauss transform itself preserves differential privacy." Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. FOCS 2012.

[2] "Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing." Jalaj Upadhyay.  CoRR, abs/1410.2470, 2014.

[3] "Differentially private ordinary least squares." Or Sheffet. ICML 2017.

[4] "Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space." Lun Wang, Iosif Pinelis, and Dawn Song. ICLR 2022.

4. The title needs change. Maybe "Nearly all hash-based order-invariant cardinality estimators are differentially private"? The current one seems to be an overclaim.
5. Line 135: The sentence "By further conditioning on the total number of items $K_r$ that can be removed without changing the sketch" seems misleading. $K_r$ is the total number of items that change the sketch once removed if I understand correctly according to Equation (2)?
questions: Please address the below questions in the rebuttal.
1. Give an empirical comparison of accuracy between QLL and PHLL. Discuss the reason for different trade-offs between space, update time and accuracy.
2. Change the title to avoid overclaim.
3. Discuss the relevant works mentioned above in Related Work section.
4. Fix line 135.
5. (Optional) Discuss whether the down-sampling procedure can be used for privacy amplification.
limitations: The authors should exhibit accuracy evaluation results and discuss the limitations if it is worse than QLL.
review_title: null

Meta-review: metareview: Differentially privacy is often an important design constraint in algorithms, and previous work has studied the question of designing streaming algorithms that satisfy DP in addition to other typical streaming algorithm desiderata (small space, small update time). For the problem of cardinality estimation, previous work has shown that specific streaming algorithms are, or can be modified to be, differentially private. This work shows a general result saying that any streaming algorithm for cardinality estimation, under mild assumptions, is differentially private. This is a clean unified result that the reviewers found appealing. I am in agreement and recommend acceptance.

confidence: Certain
Decision: Accept