Conformal Frequency Estimation with Sketched Data
Authors: Matteo Sesia
Stefano Favaro
Venue: NeurIPS 2022 Accept (2022)
Keywords: Sketching
conformal inference
memory constraints
privacy
frequency estimation

Abstract: A flexible conformal inference method is developed to construct confidence intervals for the frequencies of queried objects in very large data sets, based on a much smaller sketch of those data. The approach is data-adaptive and requires no knowledge of the data distribution or of the details of the sketching algorithm; instead, it constructs provably valid frequentist confidence intervals under the sole assumption of data exchangeability. Although our solution is broadly applicable, this paper focuses on applications involving the count-min sketch algorithm and a non-linear variation thereof. The performance is compared to that of frequentist and Bayesian alternatives through simulations and experiments with data sets of SARS-CoV-2 DNA sequences and classic English literature.

Conformal Frequency Estimation with Sketched Data
Matteo Sesia
Stefano Favaro
Department of Data Sciences and Operations
Department of Economics and Statistics
University of Southern California Los Angeles, California, USA sesia@marshall. usc.
University of Torino and Collegio Carlo Alberto
Torino, Italy
stefano wwvaro@enito..tt.
Abstract
A flexible conformal inference method is developed to construct confidence in- tervals for the frequencies of queried objects in very large data sets, based on a much smaller sketch of those data. The approach is data-adaptive and requires no knowledge of the data distribution of the details the sketching algorithm: instead, it constructs provably valid frequentist confidence intervals under the sole assumption of data exchangeability. Although our solution is broadly applicable. this paper focuses on applications involving the count-min sketch algorithm and non-linear variation thereof. The performance compared to that of frequentist and Bayesian alternatives through simulations and experiments with data sets of SARS-CoV-2 DNA sequences and classic English literature.
1 Introduction
1.1 Frequency queries from sketched data
An important task in computer science is to estimate the frequency of an object given a lossy com- pressed representation, or sketch, of big data set [1, 2]: this task has real-world relevance in diverse fields including machine learning [3], cybersecurity [4], natural language processing [5], genet- ies [6]. and privacy [7]. Practically, sketching may be motivated for example by memory limitations, as large numbers of distinct symbols may otherwise be computationally expensive to analyze [6], or by privacy constraints, situations where the original data contain sensitive information [8]. There exist many sketching algorithms, several of which are specifically designed to enable efficient ap- proximations of the empirical frequencies the compressed objects. refer to monograph of [9] for recent review of sketching. Building upon this literature, paper studies the problem of precisely quantifying the uncertainty of empirical frequency estimates obtained from sketched data without making strong assumptions about the inner workings of the sketching procedure, which may be complex and even unknown. The key ideas of the described solution are in principle applicable regardless of how the data are compressed, but the exposition of this paper will focus for simplicity on a particularly well-known sketching algorithm and some widely applied variations thereof.
1.2 The count-min sketch
The count-min sketch (CMS) of [10] is renowned algorithm for compressing data set of m objects 71,..., 7m E Z, with 2 being discrete (and possibly infinite) space, into a representation with reduced memory footprint, while allowing simple approximate queries about the observed frequency of any possible z E Z. At the heart of the CMS lie d' 2 1 different w-wide hash functions 1. Each hash
h; Z [w] := {1,... w). for all j E [d] := {l....,d d} and some integer function maps the elements of into one of w possible buckets, and it is designed to ensure that distinct values of populate the buckets uniformly. Hash functions typically chosen random from a pairwise independent family H. which ensures the probability (over the randomness in the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

choice of hash functions) that two distinct objects 21, E 2 are mapped by two different hash functions into the same bucket equal 1/w². The data set Zi.... Zm is then compressed into a sketch matrix C' Ndxw with row sums equal to m. The element in the j-th row and k-th column of C' counts the number of data points mapped by the j-th hash function into the k-th bucket:
C,,k= = 1 = k]
jE j
(1)
Because d and wo are such that d w & m, the matrix C' loses information compared to the full data set, but has the advantage of requiring much less space store.
Given a sketch C' from (1), one may want to answer queries about the original data. A fundamental instance of this problem consists in estimating the true empirical frequency of an object E 2:
m
fm (2)
Σ iz: = 2]
One solution is to return the smallest count among the d buckets into which is mapped:
P (z) -min (ann((())) 2 fm(2).
jE(d]
This procedure is outlined in Algorithm A1 (Appendix A1) and it provides a deterministic upper bound for (z) [10]. Of course, (CMS((2) tends to overestimate J' (z) due to possible hash colli- sions. But the independence of the hash functions ensures collisions not too common, leading to a classical probabilistic lower bound for fm(2).
Theorem 1 ([10)). Fix any ô, e E (0, 1). Suppose d d= [- log 87 and w [e/e]] Then, (x)
RCMS (z) em] 2 6 for any fixed z E Z, where fCMS(2) (z) is as in (1) and depends on d, w.
For example, d 3, this says that a 95% lower bound on fm((2) is fCMS (2) [e- m/w) The subscript H in Theorem I clarifies that the randomness is with respect to the hash functions, while Z1,..., Zm and z are fixed. The above bound can be useful to inform the choices of d and w prior to sketching. but it is not fully satisfactory as a way of quantifying the uncertainty about the true frequency of a given query. First, it is often too conservative [11] if the data are randomly sampled from some distribution opposed to being fixed. Second, it is not flexible: d cannot be chosen by the user because it is fixed by d, and e is uniquely determined by the hash width. Thus, in general Theorem cannot give reasonably tight confidence interval for fm()) at an arbitrary level. As we will discuss below, these limitations can be overcome by assuming the data are sampled randomly.
1.3 Uncertainty estimation for sketching with random data
An alternative approach to computing probabilistic lower and upper bounds for J' (z) was proposed by [11] in order to address the often excessive conservativeness of the classical bounds described above. The approach of [11] is based on bootstrapping ideas and departs from classical analysis of the CMS as it leverages randomness in the data instead of randomness in the hash functions. Precisely, [11] assumes the data and the queried object are independent and identically distributed (i.idd) random samples from some unknown distribution. These assumptions may not always be justified in practice, but they are useful because they can lead to much more informative confidence intervals. In fact, the confidence intervals described by [11] are nearly exact and optimal for the CMS, up to possible finite-sample discrepancy between the bootstrap and population distributions.
A limitation of the bootstrap method of [11] is that it relies on the specific linear structure of the CMS-the sketch matrix C' in (3) can be written as a linear combination of the true frequencies of all objects in the data set-and thus the idea is not easily extendable to other sketching algorithms that may perform better than the CMS in practice. One issue with the CMS is that it is relatively sensitive to random hash collisions, which can result in overly conservative deterministic upper bounds. This challenge has motivated the development of alternative non- non-linear sketching algorithms, such as the CMS with conservative updates (CMS-CU, Whenever a new object Z; is sketched, the CMS-CU only updates the row of C' with the smallest value of Cj,,,(=). leaving the other counters unaltered. Then, the same CMS deterministic upper bound in (3) remains valid. This procedure outlined in Algorithm A2. This non-linear approach can lead to much higher query accuracy compared to the vanilla CMS [12), but the theoretical analysis of the CMS-CU beyond a deterministic upper bound is more challenging, and it appears to be a relatively less explored topic.

---

1.4 Contributions
This paper develops novel method for constructing valid and reasonably tight frequentist confi- dence intervals for frequency queries based on sketched data. Our method works seamlessly with the CMS-CU as well as with any possibly unknown sketching algorithm. The solution assumes the data and the query are random samples from some unknown population, making only minimal ex- changeability assumptions about this data generating process. Although our method requires higher computational power and memory usage compared to pure sketching. the additional cost of our uncertainty estimates will be negligible compared to the typical size of the data sets involved.
1.5 Related work
Different types of lower bounds have been developed for the CMS [9], although most treat the data as fixed and only utilize the hashing randomness, similarly to Theorem 1. More recently, uncertainty estimation for the CMS based on data randomness has been studied by [11] from frequentist perspective, as mentioned in Section 1.3, and by [13, 14] from a Bayesian perspective. More precisely, [13] and [14] model the data with a prior distribution and compute the posterior of the queried frequencies given the sketch. Our work is closer to [11] in that we treat the data as random while seeking frequentist probabilistic guarantees. However, our approach is very different from that of [11]: the latter exploits the specific linear structure of the CMS, while we view the sketch as black box and utilize conformal inference to obtain exact finite-sample inferences.
Conformal inference was pioncered by Vovk and collaborators [15] and brought to the statistics spot- light by [16]. Although primarily conceived for supervised prediction [17-21], conformal inference has found many other applications including outlier detection [22]. causal inference [23], and sur- vival analysis [24]. To the best of our knowledge, its potential for sketching remained untapped until now. There exist many algorithms for using sketches to compute approximate frequency queries; some are similar to the CMS [9, 25 25-27], while others are more complicated and may involve com- plex learning algorithms [28, 29]. In theory our method is applicable to all of them, but here we focus more on the CMS and variations thereof because it is classic algorithm and it provides familiar example that facilitates the exposition. As we will make use of conformal inference, a brief review of the relevant technical background is provided in the next section.
2 Preliminaries on conformal prediction
Conformal prediction is typically concerned with supervised learning, in which the data samples are pairs (X,, Y.). with X, indicating a vector of features for the i-th observation and Y; denot- ing the corresponding continuous (or discrete) label. In supervised learning, the goal is to the information contained in that allow one to predict accurately as possible the unseen label Y Y of a new sample with features Xm-1- In particular, conformal prediction assumes that (Xi, Yi),.., (Xm+1, Ym+1) are exchangeable random samples from some unknown joint distribution over (X, Y) and then con- structs prediction interval (Xm+))) Úm, (Xm+1)] with guaranteed marginal coverage:
(Xm, Yn) to learn a mapping between features and labels
PlLm, (Xmmm Yn+11
2 11-aa aa,
(4)
for any fixed a E (0, 1). Conformal prediction is flexible, as it can leverage any machine learning
algorithm to approximately reconstruct the relation between X and Y, thus yielding relatively short intervals satisfying (4). Note that, while it is appropriate to focus on conformal intervals in this paper, similar techniques can also be utilized to construct more general prediction sets [30, 31].
The simplest version of conformal prediction begins by randomly splitting the available observations into two disjoint subsets, assumed for simplicity have equal size n m/2. The first n samples are spent to fit a black-box machine learning model for predicting Y given X; e.g., neural network or a random forest. The oft-leesample predictive accuracy of this model is then measured in terms of a conformity score for each of the n hold-out data points. In combination with the model learnt from the first half of the data, the empirical distribution of these scores is translated into a recipe for constructing prediction intervals for future test points as function of X Xm+1; these intervals are guaranteed to cover Yn+1 with probability at least a, treating all data as random. The details of this procedure will be clarified shortly. Importantly, the coverage holds exactly in finite samples,
3

---

regardless of the accuracy of the machine learning model, as long as Xm+1 is exchangeable with the n hold-out data points, Note that it is unnecessary for the training data to be also exchangeable, as these may be seen as fixed, but it is sometimes easier to say all data points are exchangeable.
The implementation of conformal inference depends on the choice of conformity scores. While several different options exist, an intuitive and general explanation is the following, Imagine that associated with the fitted machine learning model there exists a nested sequence [32] of prediction intervals (a Um. (z; t]] for each possible x. This sequence indexed by t T S R. which may be either discrete or continuous, and it is increasing: ( 12) S (m;a((;t11) and Uma (1:; 12) 2 Uma (m; (1;(1) for all 12 2 4. Further, assume there exists loc T such that Lim. (x; 100) S Y S Üm. (2;; (60) almost surely for all x. For example, one may consider sequence (m))) + t. where t'm is a regression function for bounded label Y given X learnt by the black-box machine learning model and t plays the role of predictive standard error. Then, the conformity score for a data point with features X = z and label Y = y can be defined as the smallest index such that y is contained in the sequence of prediction intervals corresponding to
EXX, = min {t E TYEE E [Lm.a(;;)) t), Um. (2; (z;
(5)
The conformal prediction rule is then casily stated. Let Iealib C. {L...., m) be the subset of hold-out data points, assumed without loss of generality to have size the [(1 - (n + 1)] smallest value among the n conformity scores E(X,, Y2) evaluated for all i E Zealib The conformal prediction interval for a new data point with features Xm+1 is:
m/2. Let 1n be
[Lmma (Xm+13 Qn, (X (1 Qn.1-a)]-
(6)
Intuitively, this satisfies (4) because m is outside (6) if and only if E(Xm+1, 11) > Qn.1-a- The rest of the proof is a simple exchangeability argument; see [20] or the proof of Theorem 2.
3 Conformalized sketching
3.1 Exchangeable queries and marginal coverage
Assume the m data points to be sketched, Zi...., Zm E 2, are exchangeable random samples (a weaker condition than i.i.d.) from some distribution Pz on Z. Although Pz may be arbitrary and un- known, our framework is more restrictive compared to the classical setting reviewed in Section 1.2, which treats the data as fixed and thus can also handle non-stationary streams or adversarial cases. Yet, imagining the data approximately i.i.d. samples from some distribution is not unprece- dented idea in the context of sketching [11, 13, 14], and it may be justified when objects from large data set are processed in random order; see Sections 4 and 5, As we shall see below, data exchange- ability can be an extremely useful assumption because allows one to obtain powerful inferences while taking a completely agnostic view of the inner workings of the sketching algorithm.
Consider an arbitrary sketching function Ø : [2] -> C, where C space with lower dimensions compared to _ For example, ø may represent the sketching performed by the CMS or CMS-CU, in which case C = Ndxw for some d, w such that d w & m. In general, we will treat e as a black box and allow technique. The goal is to leverage the data exchangeability and the information in of ZZ Zm) to estimate the unobserved true empirical frequency (2) of some object 2 Z. defined as in (2), while accounting for uncertainty. More precisely, although still informally speaking, we would like to construct a confidence interval [imm (z), Um,a(2) guaranteed to contain (2) "with probability at least 1 - a", where the randomness here is with respect to the random data sampling.
be anything, possibly involving random hashing
any other data compression
One way to address the above problem is to imagine the query z is also randomly sampled ex- changeably with Z : ..m- This is convenient but quite strong assumption that will be partly relaxed later. With this premise, we refer to 2 as Zm+1 and focus on computing a confidence interval
[Emm,a ( 11) Uma (2m+1)l depending on of (Z...... Zm) that is reasonably short and guarantees marginal coverage of the true unknown frequency:
Plima (Zm+1) S fm (2 S (m.almmtz) (Zm+z)) 2 1 a,
4

---

where the probability is with respect to the data in Zi...., Zm as well as to the randomness in the query Zm+ The interpretation of (7) as follows: the interval will cover the true frequency fm (Z) for at least fraction 1 - of all future test points Z on average, if the queries and the sketched data are sa-sadlled exchangeably. In Section 3.3, we will develop a method for constructing reasonably tight confidence intervals satisfying (7) exactly. This is already a non-trivial result on its own, but marginal coverage is not fully satisfactory because some objects may be queried more often than others, and therefore not all of our distinct inferences are equally reliable. In particular, the confidence intervals for rare queries may have lower coverage, as illustrated by the following thought experiment. Imagine Pz has support
2 {0. 1, 2, ..... 10!00), with P ZZ, 0] = 0.95 and i = 2] = 0.05/ [005/(]2] 1) for all 2 E Z \ {0} and i 2 1. Then, a 95% confidence interval satisfying (7) may be completely unreliable for all but one specific query about fm (0).
3.2 Beyond full exchangeability with approximate
condencc-conditionall coverage
To begin addressing the limitations of marginal coverage, Section 3.3 will develop a more refined method for constructing confidence intervals that are simultaneously valid for both rare and common random queries. Our approach re-purposes relevant ideas from Mondrian conformal inference [33], which have been utilized before to construct prediction sets with label-conditional coverage for clas- sification problems [15, 30, 34]. However, departing from the typical approach in classification, we will not seek perfect coverage conditional on the exact true frequency of the queried object. In fact, that problem would be impossible to solve without stronger assumptions [35], because fm (Zm+1) can take very large number of possible values when the sketched data set is big. Instead, will focus on achieving a relaxed concept of frequency-conditional conditional coverage which groups together different queries of objects that appear similar number of times within the sketched data set. Pre- cisely, let us fix any partition B = (BI..... Br) of {l...., m) into L bins such that each B₁ is sub-interval of {I...., m). for some relatively small integer L. In theory, this partition should be fixed prior to seeing the data and may not depend on the new query Zm+1. Our goal is to con- struct a confidence interval [f.m.a 11), Úm, ( (7m+1) )] depending on of (Z 7m and B that reasonably short and satisfies the following notion of frequency- range conditional coverage:
[P[ [Tmma (7m+1) ) S Jm (2m+1) S (7m+1) fm (7m+1) E B] 2 11
-a a, BB E B. (8)
The choice of B involves some trade-offs: finer partitions (larger L) yield more reliable theoretical
guarantees but possibly wider confidence intervals; in particular, intervals associated with a bin B may tend to be wider if P [Z E B] is small. In practice, we will adopt [B] = 5 later in this paper, but much larger [B] can be utilized when working with very big data, as it will become clear below.
3.3 Conformalization methodolody
In the attempt of adapting conformal inference address our sketching problem, the first difficulty is that the latter is a data recovery problem, not supervised prediction task. We propose to overcome this challenge by storing in memory the true frequencies for all objects in the first mo observations, with mo < m but sufficiently large subject to memory constraints. Without loss of generality, assume My < m; otherwise, the problem becomes trivially easy. Let n S my indicate the number of distinct objects among the first mo observations. The memory required to store these frequencies (n).. which will typically be negligible as long as my is also small compared to the size of the sketch, (C]. This approach turns our problem into supervised prediction one, as detailed below
During an initial warm-up phase, the frequencies of the distinct objects among the first ma obser- vations from the data stream, Zi,..., Zmo. are stored exactly into:
mhg
f fwo (z)
1 [Z, = 2]
Next, the remaining m- mi data points streamed and sketched, storing also the true frequencies for all instances of objects already seen during the warm-up phase. In other words, the following counters are computed and stored along with the sketch Φi (Zmotl...... 7
mo 1 1 1Z, = =]. [ww > 0,
JSY mm- (2) ==
(10)
10,
otherwise.
5

---

Again, this requires only (n) memory. Now, let us define the variable Y, for all i E {l.....mo! {m + 1) as the true frequency of Z, among mmo+l.....
mo} U
Zm:
Y =
Σ 2==m--
1 1 Zi]
(1I)
Note that Y; is observable for E moo. in which case Y; = fm my (Zz). For a new query, 7 is the target of inference-in truth, the target is fmi(Z) Y; mm Zz), but the second term is already known exactly. To complete the connection between sketching and supervised conformal prediction, one still needs to define meaningful features X, and this where the sketch
((Zma+l,.... Zm) comes into play. For each i E {I..... mo) U {m + I,...J. define X, as the vector containing the object the query as well as all the information in the sketch:
X; (Zz: O Zmo+l........................... Zm)).
(12)
The following result establishes that the pairs (X,Y1)). (Xmg: m: ): (Xm+1, Ym+1) are ex- changeable with one another. This anticipates that conformal prediction techniques can applied to the supervised observations (X1, Y1)...., (X Ymo)) to predict Yn+1 given Xm+1, guarantee- ing the marginal coverage property (7). All mathematical proofs are in Appendix A2.
Proposition 1. If the data Zi....y Zm+1 are exchangeable, then the pairs of random variables (X1, Yi),.., (X Ymol, (Xm+1, 1)) defined in (11)-(12) are exchangeable with one another.
Confidence intervals satisfying frequency-rann range coverage (8) can be obtained by modifying the stan- dard conformal inference procedure as outlined in Algorithm A3, whose details are deferred to Ap- pendix Al for lack of space. First, each point (X,, Y,) in Zealib {1..... mo } is assigned to the appropriate frequency bin based on Y. Define ny as the number of calibration points in bin Bi, for all l E {l...., L}. Then, 1 (Bi) is defined as the [(1 (m + 1)1 smallest value among the nı scores assigned to bin Br. Finally, the confidence interval for a new random query Xm-1 is:
[Lm -a, Um (X (X 17,1-a))
where
10 = max (E(I.....)
and (: (= is a rule for computing a nested sequence of intervals depending on Zm+1 and of o(Zmo+1,... Zm,, assumed by convention to be increasing in t. Examples of such rules in the next section. Importantly, these rules may involve parameters to be fitted on a subset of mirain supervised data points (X;, Y.) for E (1..... . .mjraim), J. as long as the scores are only evaluated on the remaining my train points. The following result states that the confidence interval output by Algorithm A3 has the desired frequency-range conditional coverage.
Theorem 2. If the data Zi...., Zm+1 are exchangeable, the confidence interval output by Algo- rithm A3 satisfies the frequency-rarg conditional coverage property defined in (8).
Theorem 2 also implies that confidence intervals satisfying the weaker marginal coverage property defined in (7) can be obtained by applying Algorithm A3 with the trivial partition B dividing the range of possible frequencies into a single bin of size m. because (7) is a special case of (8). Note also that Algorithm A3 could be trivially modified output perfect "singleton" confidence intervals for any new queries that happen to be identical to an object previously observed during the warm-up phase. We will not take advantage of this fact in the experiments presented in this paper to provide a fairer comparison with alternative methods which do not involve similar warm-up up phase.
3.4 Conformity scores for one-sided confidence intervals
Algorithm A3 can accommodate virtually any data-adeptive rule for computing nested confidence intervals, which may depend on Zm+1 and on the sketch Φ := of Zmooml..... Zm.. Two concrete options are presented here. For simplicity, we focus on one-sided confidence intervals; that is, we seek a a lower bound for fm (Xm+1). This is useful when a deterministic upper bound fup (Zm+)) 2 fm (2m+1) is already available, as it is the case with the CMS CMS-CU. Then,

---

one can simply set Um,(((2,))) Q): := (2) and focus on computing (m;((t:t) t). The construction of two-sided confidence intervals is explained in Appendix A1.4 due to lack of space.
To construct the lower bound Lm, (::t) of one-sided interval, the first option is to use a fixed rule:
i fixcod ((z, 0);t) == (O, uup fup(2 (2m+1) - -t,, E (o.
(13)
In words, the lower bound for fm (Z in (14) is defined by shifting the deterministic upper bound downward by constant L. The appropriate value of guaranteeing the desired coverage for future random queries calibrated by Algorithm A3. This approach intuitive, and very similar to the optimal solution of [11] for the special case of the CMS. Further, it does not need training data, so all mo observations with tracked frequencies can be utilized for computing conformity scores.
The second option involves training but has the advantage of being more flexible; this is inspired by the methods of [36, 37] for regression. Concretely, consider a machine learning model that takes as input the known upper bound fup (Z)) and estimates the conditional distribution of Sup fm (Z,) given fup (Z.). For example, think of a multiple quantile neural network [38] or a quantile random forest [39]. After fitting this model on the mo traiin supervised data points (X;, Y.) allocated for training, let de be the estimated lower quantile of the of Sup Zz) (Z,) fup Zz), for all
t E [1, [I..... : T and some fixed sequence = an < ... < oT O. Without loss of generality,
assume the machine learning model is that qu = 0 and Qr = m. Then, define Lm,a(o; as:
i Fadaptive ()) == max {0, Iup - qe (Xup(X=+1)) "ma
LE {0, (0,1,...,m), m). (14)
This second approach can lead to lower bound whose distance from the upper bound is adaptive. This is an advantage because some sketching algorithms may introduce higher uncertainty about common queries compared to rarer ones, or vice versa, and such patterns can be learnt given suffi- cient data. Of course, the two above examples of (= t) are not exhaustive. Algorithm A3 can be applied in combination with any rule for computing nested sequences of lower bounds, and it can leverage all high-dimensional information contained in d( 6m Zm,, not just the determin- istic upper bound for the CMS and CMS-CU. However, the applications in this paper focus on the CMS and CMS-CU, so other families of lower bounds are not discussed here.
4 Applications
4.1 Experiments with synthetic data sets
Conformalized sketching is applied with the two types of conformity scores described in Section 3.4, focusing on the construction of one-sided confidence intervals. Additional experiments involving two-sided intervals are described Appendix A4. The adaptive scores utilized this section are based on an isotonic distributional regression model [40]. The goal is to compute lower frequency bounds for random queries based on simulated data compressed by the CMS-CU, implemented with d = 3 hash functions of width w = 1000. In particular, m = 100, 000 observations are sampled i.i.d. from some distribution specified below. The first my = 5000 observations are stored without loss during the warm-up phase, as outlined in Algorithm A3, while the remaining 95, 000 are compressed by the CMS-CU. The conformity scores are evaluated separately within L = frequency bins, seeking the frequency-range conditional coverage property defined in (8). The bins are determined in data-driven fashion so that each contains approximately the same probability mass; in practice, this is achieved by partitioning the range of frequencies for the objects tracked exactly by Algorithm A3 according to the observed empirical quantiles. Lower bounds for new queries are computed for 10, 000 data points also sampled i..d. from the same distribution. The quality of these bounds is quantified with two metrics: the mean length of the resulting confidence intervals and the coverage the proportion of queries for which the true frequency is correctly covered, or empirical coverage. The performance is averaged over 10 independent experiments.
Experiments are performed on synthetic data sampled from two families of distributions. First, we consider a Zipf distribution with P [Z, = =] = ><((( for all E 21, where C is the Riemann Zeta function and a > 1 is control parameter affecting the power-law tail behavior. Second, synthetic data are generated from a random probability measure distributed as the Pitman- Yor prior [41] with a standard Gaussian base distribution and parameters À > 0 and E [0, 1). as
7

---

explained in Appendix A1.5. The parameter À is set to À = 5000, while is varied. For = 0 the Pitman- Yor prior reduces to the Dirichlet prior [42], while o > 0 results in heavier tails.
Three benchmark methods are considered. The first one is the classical 95% lower bound Theo- rem 1. The second one is the Bayesian method of [13], which assumes non-parametric Dirichlet process prior for the distribution of the data stream, estimates its scaling parameter by maximizing the marginal likelihood of the observed sketch, and then computes the posterior of the queried fre- quencies conditional on the observed sketch. The performance of the lower 5% posterior quantile is compared to the lower bounds obtained with the other methods according the frequentist metries defined above. The third benchmark is the bootstrap method of [11], which is nearly exact and opti- mal for the vanilla CMS (up to some possible mnie--sample discrepancy between the bootstrap and population distributions) but is not theoretically valid for other sketching techniques.
Figure compares the performance of the conformal method to those of the three benchmarks the Zipf data. All methods achieve marginal coverage (4), with the exception of the Bayesian approach which in this case based on misspecified prior. The length of the confidence intervals indicates the classical bound is very conservative, while the bootstrap and conformal methods provide relative informative bounds, particularly when larger and hash collisions become rarer. The conformal intervals can be the shortest ones, especially if implemented with the adaptive conformity scores. This should not be surprising because the bootstrap may not optimal for the CMS-CU. Indeed, as shown in Figure 2, the machine learning model deployed by our adaptive scores can take advantage of the fact that this non-linear sketch allows increased precision for more common queries.
Coverage
Length
Method
1000
Classical
0.7
100
+ Bayesian
+ Bootstrap
0.5
10
Conformal (fixed)
Conformal (adaptive)
1.00
1,25
1.50
1.75
1.00
1.25
1.50
1.75
Parametera
Figure 1: Coverage and length of 95% confidence intervals with data from Zipf distribution, sketched with CMS-CU, The results are shown as function of the Zipf tail parameter a. Standard errors would be too mall to be clearly visible in this figure, and are hence omitted.
Low frequencies
High frequencies
1.0
Coverage
0.7
Method
0.5
Classical
Bayesian
Bootstrap
1000
Conformal (fixe)
100
Conformal (adaptive)
10
1.00
1.25
1.50
1.25
1.50
1.75
Parameter
Figure 2: Performance confidence intervals stratified by the true query frequency. Left: frequency below median; right: frequency above median. Other details are in Figure 1.
Supplementary results reported in Appendix A3 show the CMS-CU leads to more precise queries with all methods compared to the vanilla CMS; see Figure A1. Figure A2 confirms that conformal lower bounds no longer have a clear advantage over the bootstrap ones if the data are sketched with the vanilla CMS instead of the CMS-CU, In fact, although the conformal intervals obtained with the

---

adaptive conformity scores can be little shorter than the bootstrap ones even for the vanilla CMS, the latter have the advantage of (approximately, in the limit of large samples) satisfying an even stronger frequency-conding conditioonl coverage property equivalent to (8) with bins of size 1 [11]. Analogous results for the experiments with Pitman- Yor process data are also in Appendix A3; see Figures A3-A6.
4.2 Analysis of 16-mers in SA SARS-CoV-2 DNA sequences
This application involves data set of nucleotide sequences from SARS-CoV-2 viruses made pub- licly available by the National Center for Biotechnology Information [43]. The data include 43,196 sequences, each consisting of approximately 30,000 nuclcotides. The goal is to estimate the em- pirical frequency of each possible /6-mer, a distinct sequence of 16 DNA bases in contiguous nu- cleotides. Given that each nucleotide has one of 4 bases, there are 4 4.3 billion possible 16-mers. Thus, exact tracking of all 16-mers is not unfeasible, which allows us to validate the ceetch-based queries. Sequences containing missing values are removed during pre-processing for simplicity.
The experiments are carried out as in Section 4.1 (processing the 16-mers in a random order to ensure their exchangeability), but larger sample of size 1,000,000 is sketched, and the width w of the hash functions is varied. Figure 3 compares the performances of all methods as a function of the hash width, in terms of marginal coverage and mean confidence interval width. All methods achieve the desired marginal coverage, except for the Bayesian approach when w is large. For small w, all methods return intervals of similar width, because the distribution of SARS --V--C 16- mers frequencies is quite concentrated with relatively narrow support (Figure A7), which makes it especially difficult to compress the data without much loss. By contrast, the proposed conformal methods yield noticeably shorter confidence intervals if w is large. Figure A8 reports the same results stratified by the frequency the queried objects, while Figure A9 confirms the advantage of sketching with the CMS-CU as opposed to the vanilla CMS. Table A1 lists 10 common and 10 rare queries along with their corresponding deterministic upper bounds for w 50, 000, comparing the lower bounds obtained with each method. Table A2 shows analogous results with 5, 000.
Coverage
Length
Method
300
Classical
100
Bayesian
0.7
30
Bootstrap
10
3
Conformal (fixed)
0.5
1000
3000
10000
30000
1000
3000
10000
30000
Conformal (adaptive)
Hash width
Figure 3: Performance of confidence intervals based on sketched SARS-CoV-2 sequence data, The results are shown function of the hash width. Other details are in Figure 1.
Figure A10 compares the performances of different frequeney point-estimates in terms of mean absolute deviation from the true frequency. With the classical method, we take the midpoint of the 95% confidence interval other methods, the point estimate is the lower confidence bound at level = 0.5; in the Bayesian case, this is the posterior median. Although a conformal lower bound at level a = 0.5 is not always a reliable estimator of conditional medians [44], because the conformal coverage guarantees treat the query as random, this approach outperformed the benchmarks in all our experiments.
point estimate, although other approaches are also possible [9]. For the
4.3 Analysis of 2-grams in English literature
This application is based on a data set consisting of 18 open-domain classic pieces of English liter- ature downloaded using the NLTK Python package [45] from the Gutenberg Corpus [46]. The goal to count the frequencies of all 2-grums-consest After some basic preproccessing to remove punctuation and unusual words (only those in dictio- nary of size 25,487 common English words are retained), the total number of 2-grams left in this data set is approximately 1, 1,700,000 (although the total number of all possible 2-grams within this dictio-
pairs of English words-acros this corpus.

---

nary is approximately 650,000,000). The same experiments are then carried out as in Section 4.2, sketching 1,000,000 randomly sampled 2- 2-grams and querying 10,000 independent 2- 2-grams. As in the previous experiments, the 2-grams are processed in random order to ensure exchangeability.
Figure shows the conformal intervals with adaptive scores achieve the desired coverage and tend to have the shortest width, while the Bayesian intervals are not valid unless the hashes are very wide. The conformal approach has a larger advantage here because these data can be compressed more efficiently compared to the one in the previous section because the frequency distribution of English 2-gr E-grams has power-law tails; see Figure A7. Additional results along the lines of those in the previous section are in Appendix A3; see Figures A11-A13 and Tables A1-A2.
Coverage
Length
Method
1.0
300
Classical
100
Bayesian
0.7
30
Bootstrap
10
Conformal (fixed)
0.5
1000
3000
10000
30000
1000
3000
10000
30000
Conformal (adaptive)
Hash width
Figure 4: Performance of confidence intervals for random frequency queries, for a sketched data set of English 2- 2-grams in classic English literature. Other details are as in Figure 3.
5 Discussion
Conformalized sketching is non- non-parametric and data-adaptive statistical method for quantifying uncertainty in problems involving frequency estimation from sketched data. This paper has revolved around the CMS because that is a prominent technique for which several benchmarks are available. However, our method is very broadly applicable because it operates under the sole assumption of data exchangeability, without requiring any knowledge of the sketching algorithm. Of course, ex- changeability is not always appropriate assumption, and thus one may sometimes need to rely on more conservative bounds based on hashing randomness. Yet there are situations in which the sketched data can be seen exchangeable random samples from population. For example, in nat- ural language processing one may wish to count the frequencies non-contiguous tuples of words co-occurring in the same sentence within large corpus, expanding the example of Section 4.3. In that case, it would be unfeasible to keep track of all frequencies exactly, but our approach would be applicable long as the tuples are sketched and queried in random order. One limitation of con- formalized sketching is that it does not provide guarantees about the expected proportion of correct unique queries. In fact, if the queries points, some of them may be redundant. Even though the expected proportion of incorrect unique queries is sometimes below a (Figures A14-A15), this is not always the case (Figure A16). It may be possible to modify our procedure to achieve this additional guarantee, but we leave this problem for future work. Future research may also study theoretically, in some settings, the length of our conformal confidence intervals, following for example an approach similar to those of [16, 47).
randomly sampled exchangeably with the sketched data
Accompanying software and data are available online at https:// http::///gthhbbb com com/msesia// conf ormalized- sketchin.. Experiments were carried out in parallel using a computing clus- ter; each experiment required less than few hours with standard CPU and less than 5GB of memory (20 GB of memory are needed for the analysis of the SARS-CoV-2 DNA data).
Acknowledgements
M. S. is supported by NSF grant DMS 2210637 and by an Amazon Research Award. S. F. is also affiliated to IMATI-CNR "Enrico Magenes" (Milan, Italy), and received funding from the European Research Council under the European Union's Horizon 2020 research and innovation programme under grant No 817277. The authors are grateful to three anonymous reviewers for helpful comments and an insightful discussion.
10

---

References
[1] Jayadev Misra and David Gries. Finding repeated elements. Science of computer programming, 2(2):143-152, 1982.
[2] Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming, pages 693-703, Springer, 2002.
[3] Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alex Smola, and SVN Vish- wanathan. Hash kernels for structured data. Journal of Machine Learning Research, 10(11), 2009.
[4] Stuart Schechter, Cormac Herley, and Michael Mitzemmacher. Popularity is everything: A new approach to protecting passwords from {Statistical "StatistiallGGuessnng/ attacks. In 5th USENIX Workshop on Hot Topics in Security (HotSec 10), 2010.
[5] Amit Goyal, Hal Daumé III, and Graham Cormode. Sketch algorithms for estimating point queries in nlp. In Proceedings of the 2012 joint conference on empirical methods in natural language processing and computational natural language learning, pages 1093-1103, 2012.
[6] Qingpeng Zhang, Jason Pell, Rosangela Canino-Koning, Adina Chuang Howe, and C Titus Brown. These are not the k-mers you are looking for: efficient online k-mer counting using a probabilistic data structure. PloS one, 9(7):e10227, 2014.
[7] Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tianhao Wang. Privacy at scale: Local differential privacy in practice. In Proceedings of the 2018 International Conference on Management of Data, pages 1655-1658, 2018.
[8] Can Kockan, Kaiyuan Zhu, Natnatee Dokmai, Nikolai Karpov, M Oguzhan Kulekci, David Woodruff, and S Cenk Sahinalp. Sketching algorithms for genomic data analysis and querying secure enclave. Nature methods, 17(3):295-30) 2020.
[9] Graham Cormode and Ke Yi. Small summaries for big data. Cambridge University Press, 2020.
[10] Graham Cormode and Shan Muthukrishnan. An improved data stream summary: the count- min sketch and its applications. Journal of Algorithms, 55(1):58-775 75, 2005.
[11] Daniel Ting, Count- Optimal estimation and tight error bounds using empirical error dis- tributions. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2319-2328, 2018
[12] Cristian Estan and George Varghese. New directions in traffic measurement and accounting, In Proceedings of the 2002 conference on Applications, technologies. architectures, and protocols for computer communications,, pages 323-336 2002.
[13] Diana Cai, Michael Mitzenmacher, and Ryan P Adams. Bayesian nonparametric view on count-min sketch. In Advances in Neural Information Processing Systems 31, pages 8782- 8791, 2018
[14] Emanuele Dolera, Stefano Favaro, and Stefano Peluchetti. A Bayesian nonparametric approach to count-min sketch under pawer-law data streams. In International Conference Artificial Intelligence and Statistics, pages 226-234. PMLR, 2021.
[15] Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer, 2005.
[16] Jing Lei. Max G'Sell, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry Wasserman. Eestribution-free predictive inference for regression. Journal of the American Statistical Asso- ciation, (1135523):19441111 2018.
[17] Vladimir Vovk, Ilia Nouretdinov, and Alex Gammerman. On-line predictive linear regression. Annals of Statistics, 1566):1566-1599 2009.

---

[18] Vladimir Vovk. Cross-conformal predictors. Annals of Mathematics and Artificial Intelligence, 74(1-2):9-28) 2015.
[19] Jing Lei and Larry Wasserman. Distribution-fre prediction bands for non-parametric regres- sion. Journal of the Royal Statistical Society: Series B (Statistical Methodology,, 76(1):71-96 2014.
[20] Yaniv Romano, Evan Patterson, and Emmanuel Candès. Conformalized quantile regression. In Advances in Neural Information Processing Systems, pages 3538-3548, 2019.
[21] Rafael Izbicki, Gilson T Shimizu, and Rafael B Stemn. Flexible distribution frrere conditional predictive bands using density estimators. preprini at arXiv:1910.05555, 2019.
[22] Stephen Bates, Emmanuel Candès, Lihua Lei, Yaniv Romano, and Matteo Sesia. Testing for outliers with conformal p-values. preprint at arXiv:2104408279, 2021.
[23] Lihua Lei and Emmanuel Candès. Conformal inference of counterfactuals and individual treat- ment effects. Journal of the Royal Statistical Society: Series B (Statistical Methodology).
[24] Emmanuel Candès, Lihua Lei, and Zhimei Ren. Conformalized survival analysis. arXiv preprint arXiv:2103.0976. 2021.
[25] Li Fan, Pei Cao, Jussara Almeida, and Andrei Z Broder. Summary cache: a scalable wide-area web cache sharing protocol. IEEE/ACM transactions on networking. 8(3):281-22) 1-93,, 2000.
[26] Amit Goyal and Hal Daumé. Lossy conservative update (Icu) sketch: Succinct approximate count storage. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 25, pages 178-883. 2011.
[27] Guillaume Pitel and Geoffroy Fouquier. Count-min-log sketch: Approximately counting with approximate counters. arXiv preprint arXiv:1502, 04885, 2015.
[28] Chen-Ye Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning baase frequency estima- tion algorithms. In International Conference on Learning Representations, 2019.
[29] Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P Woodruff. Leaming-augmmented data stream algorithms. In International Conference on Learning Representations, 2019.
[30] Yaniv Romano, Matteo Sesia, and Emmanuel Candès. Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems, 33:3581-3591, 2020.
[31] Anastasios Angelopoulos, Stephen Bates, Jitendra Malik, and Michael Jordan. Uncertainty sets for image classifiers using conformal prediction, arXiv preprint arXiv:2009.14199 2020.
[32] Chirag Gupta, Arun K Kuchibhotla, and Aaditya K Ramdas. Nested conformal prediction and quantile out-of-bag ensemble methods. preprint at 1rXiv:1910.10562. 2019.
[33] Vladimir Vovk, David I Lindsay, Ilia Nouretdinov, and Alex Gammerman. Mondrian confidence machine. Technical report, Royal Holloway, University of London, 2003.
[34] Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):223-25:) 2019.
[35] Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan Tibshirani. The limits of distribution-fred conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2):455 482, 2021.
[36] Victor Chernozhukov, Kaspar Wüthrich, and Yinchu Zhu. Distributional conformal prediction. Proceedings of the National Academy of Sciences, 118(48), 2021.
[37] Matteo Sesia and Yaniv Romano. Conformal prediction using conditional histograms. Ad- vances in Neural Information Processing Systems, 34, 2021.
12

---

[38] James W. Taylor. A quantile regression neural network approach to estimating the conditional density of multiperiod returns. Journal of Forecasting, 19(4):299-31, 2000.
[39] Nicolai Meinshausen. Quantile regression forests. Journal of Machine Learning Research, 7: 983-999, 2006.
[40] Alexander Henzi, Johanna F. Ziegel, and Tilmann Gneiting. Isotonic distributional regression. Journal of the Royal Statistical Society: Series (Statistical Methodology), 83(5):963- 993399933999 2021.
[41] Jim Pitman and Mare Yor. The two parameter poisson-dirichlet distribution derived from stable subordinator. The Annals of Probability, 25:855-900, 1997.
[42] S. Thomas Ferguson. A Bayesian analysis of some nonparametric problems. The Annals of Statistics, 1:209-230, 1973.
[43] Eneida Hatcher, Sergey A Zhdanov, Yiming Bao, Olga Blinkova, Eric P Nawrocki, Yuri Ostapchuck, Alejandro A Schäffer, and J Rodney Brister. Virus variation resource resource-inproved response to emergent viral outbreaks. Nucleic acids research, 45(D1))D482-D490 2017.
[44] Dhruv Medarametla and Emmanuel Candès. Distribution-free conditional median inference. Electronic Journal of Statistics, 15(2):462544658, 2021.
[45] Steven Bird, Ewan Klein, and Edward Loper. Natural language processing with Python: ana- lyzing text with the natural language toolkit. O'Reeill Media, Inc.", 2009.
[46] Project Gutenberg. Project Gutenberg. www www.guenbeegg.o org. Accessed: 2022-02-05.
[47] Matteo Sesia and Emmanuel J Candès. A comparison of some conformal quantile regression methods. Stat, 9(1):e261, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (c.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
13

---

(d) Did you discuss whether and how consent was obtained from people whose data you re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "dPQ2-h_x4K", "reviewer": "Reviewer_HNPK", "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. \n\n\nUPDATE: after reading the author's response, I have increased my score to a 7 (accept).", "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.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nWeakness: 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "X1X0smeWk6f", "reviewer": "Reviewer_gvFV", "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.", "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.\n\n2. 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?\n\n3. 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.\n\n4. Minor\n- Figure 1: too mall -> too small\n- 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.", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nUnfortunately, 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Ild25872VD", "reviewer": "Reviewer_vGGR", "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. ", "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.\n- 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. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- 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.   \n- The construction of the ordered pairs to transform the sketching problem into a supervised learning problem amenable to conformal prediction is novel. \n- 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. \n\nWeaknesses:\n- 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. \n- 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.\n- 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. \n- 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.\n- 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. \n- 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept