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: This manuscript develops conformalized sketching: a method using conformal prediction to construct confidence intervals for frequency queries based on sketched data. The method works at any desired level, unlike the standard version of count-min sketch, and also incorporates conservative updates. Theoretical results and simulations (with both synthetic and real-life datasets) are provided which establish validity and showcase the appeal of the proposed method. 


UPDATE: after reading the author's response, I have increased my score to a 7 (accept).
strengths_and_weaknesses: Strengths: the paper is well written and appears to be up to date with the literature. A overview of conformal prediction is provided and the results are self-contained. 

Weakness: more theoretical results would be helpful. For example, some theoretical results concerning the length of the confidence intervals, and also performance when the exchangeability assumption does not hold would be helpful.

questions: Further discussions about the length of the confidence intervals, and also performance when the exchangeability assumption does not hold would be helpful. For example, why are the confidence intervals for conformalized sketching so short in the simulation results?
limitations: See questions and the weakness comment. Potential negative societal impact not applicable.
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 proposes a conformal method that, given a sketching function $\phi$, computes a confidence interval for the frequency of a random query sampled exchangeably from the data.
strengths_and_weaknesses: The paper's biggest strength is the sheer novelty of the combination of conformal prediction and data sketching. To my knowledge, the combination is completely new.

Unfortunately, the method has at least two significant limitations. First, it is unclear whether the type of theoretical guarantee that the method can provide is of interest for working with sketched data since the probability of coverage is with respect to the randomness of the query and not of the sketching. Second, for this guarantee to hold, the random queries must be exchangeable.
questions: 1. A coverage guarantee with respect to the sketching randomness feels natural for working with sketched data. By contrast, it is still not obvious to me that a coverage guarantee with respect to the draw of data points can be useful in many situations. Could you provide additional examples in which the latter guarantee is of equal or greater interest? The more concrete the examples, the better. Examples from prior applications would be excellent.

2. It looks like the proposed method and the comparison methods all have different theoretical guarantees. For example, for the classical method, the probabilistic statements are made with respect to the randomness of the hash functions, whereas for the proposed method, they are with respect to the sampling of the new query point and the sketched data. (I am not familiar with other comparison methods.) Should we exercise more caution in interpreting the experimental results if this is the case? To what extent are the proposed method and the comparison methods truly comparable?

3. On a related note, how should I interpret these different confidence intervals? I know how to interpret the classical bound when I have an approximate answer based on the sketched data, and I want to relate it to the exact answer based on the un-sketched data. However, I am struggling to find an interpretation for the conformal interval.

4. Minor
- Figure 1: too mall -> too small
- The captions for figures and tables could be made more informative. It was a bit annoying to keep flipping back and forth between an earlier figure and a later one to understand what the latter was about.
limitations: The authors appear to be aware of the limitations of their method (cf. Section 5). However, I think that these limitations deserve a more extensive treatment.
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 propose a method for constructing confidence intervals for counts based on approximate counts generated by a sketching algorithm.  The proposed method involves keeping track of exact counts for a sparse dictionary of items and computing conformity scores based on disparity between the sketched count and true count.  Using these scores, a prediction region is generated for a randomly selected element of the dictionary using conformal prediction.  The method is shown to be competitive on synthetic and real data examples. 
strengths_and_weaknesses: Strengths:
- The proposed method inherits the flexibility of conformal prediction and thus works for any sketching algorithm and for any performance measure i.e. conformity score.   
- The construction of the ordered pairs to transform the sketching problem into a supervised learning problem amenable to conformal prediction is novel. 
- The fact that it suffices to keep track of $m_0 \ll m$ counts in order to construct a prediction interval for the test object due to the exchangeability assumption is interesting. 

Weaknesses:
- One of the main arguments that the authors make in favor of conformal prediction over deterministic approaches is that the deterministic approaches are too conservative.  Yet, the procedures proposed use a deterministic upper bound.  Thus, these prediction intervals are also conservative in the sense that the probability that the true quantity is greater than the upper bound is 0. 
- While it is typically a mild assumption, exchangeability is a nontrivial one for sketching problems.  In fact, the 2-gram real data example does not appear to be exchangeable since consecutive 2-grams share a word and thus the joint distribution of 2-grams is not invariant under permutation.  The authors are instead treating the 2-grams as fixed and are sampling IID from them, but then the interpretation of the conformal prediction guarantee is less clear, as the probability statement includes this sampling variation.  In this setup, the prediction interval  covers a sampled frequency instead of the true one.
- Another typically benign feature of conformal prediction that may be problematic in this setting is that the test point is assumed to be exchangeable when combined with the training examples; this means that the one can only construct prediction intervals for randomly chosen items, which is quite restrictive particularly if the dictionary is large. 
- The technical contributions of the paper are not substantial.  This is not meant to be a major criticism since the combination of simplicity and generality is what makes conformal prediction useful in a wide variety of areas.
- The procedure becomes trivial if the element of interest appears in the warmup phase or if one is interested in a small number of elements, in which case one may just track these elements following the same reasoning used to justify the warmup phase. 
- While the writing is clear, I believe the exposition can be improved in places.  For example, the sketching problem should be first introduced in more generality before the count-min sketch is introduced, since the paper is not solely about CMS or CMS-CU.  Also, it is misleading to refer to the constructed prediction sets as one that “is as short as possible” on line 162 since optimality of prediction sets is a different topic that is not investigated here.

questions: - Is there a reason that you did not consider two-sided prediction intervals?  One would think that it is possible to simply treat all entries of the hash matrix that the item was mapped to as a covariate and then use a standard regression non-conformity score.
- Is there a reason that coverage for conformal prediction is (nearly) 100%?  When the non-conformity scores are distinct, conformal prediction is supposed to have the upper bound $1- \alpha + \frac{1}{n+1}$ on coverage as well.  Does randomizing the scores fix this?
limitations: The authors are forthright about exchangeability being potentially restrictive for sketching problems, but do not discuss the subtle issues with interpreting the sampled items in the real data examples.
review_title: null

Meta-review: metareview: The paper proposes a method based on conformal inference in order to obtain confidence intervals for the frequencies of queried objects in very large data sets, based on sketched data. The applicability of the method relies solely on the exchangeability assumption for the data, not on the sketching procedure nor on the data distribution, and is therefore very general, as emphasized by all reviewers.

The reviewers have done a great job and this should (and has been) acknowledged by the authors. There has been some objections concerning the applicability of the main assumption (exchangeability), the meaningfulness of the experimental comparison with prior work and the interpretation of the resulting plots, or on the amount of theoretical content of the paper. But the post-review discussion appears to have been very active and fruitful. It overall gives me the impression that the authors took very seriously the comments and will improve the manuscript accordingly, and that many objections could be answered by a more appropriate exposition.  Given that this paper lies of the edge of the acceptance threshold, this improvement is very important, as the reviewers concerns (which have some strong overlap) will otherwise be probably be shared by the wider audience of readers. This is especially true given the statistics flavor of the paper which does not target the main NeurIPS audience, implying that an even greater effort has to be put on the presentation. Very detailed, and I find meaningful from a layman perspective, answers have been provided by the authors, and not all their content will fit in the additional page. There is thus a important work of selection and re-writing ahead of the authors before publication.
confidence: Less certain
Decision: Accept