Learning-based Support Estimation in Sublinear Time
Authors: Talya Eden
Piotr Indyk
Shyam Narayanan
Ronitt Rubinfeld
Sandeep Silwal
Tal Wagner
Venue: ICLR 2021 Spotlight (2021)
Keywords: support estimation
sublinear
learning-based
distinct elements
chebyshev polynomial

Abstract: We consider the  problem of estimating the number of distinct elements in a large data set (or, equivalently, the support size of the distribution induced by the data set) from a random sample of its elements. The problem occurs in many applications, including biology, genomics, computer systems and linguistics. A line of research spanning the last decade resulted in algorithms that estimate the support up to $ \pm \varepsilon n$ from a sample of size $O(\log^2(1/\varepsilon) \cdot n/\log n)$, where $n$ is the data set size.  Unfortunately, this bound is known to be tight, limiting further improvements to the complexity of this problem. In this paper we consider estimation algorithms augmented with a machine-learning-based predictor that, given any element, returns an estimation of  its frequency.  We show that if the predictor is correct up to a constant approximation factor, then the sample complexity can be reduced significantly,  to
$$ \ \log (1/\varepsilon) \cdot n^{1-\Theta(1/\log(1/\varepsilon))}. $$
We evaluate the proposed algorithms on a collection of data sets, using the neural-network based estimators from {Hsu et al, ICLR'19} as predictors. Our experiments  demonstrate substantial (up to 3x) improvements in the estimation accuracy compared to the state of the art algorithm.

Published as a conference paper at ICLR 2021
LEARNING-BASED SUPPORT ESTIMATION IN SUBLINEAR TIME
Talya Eden', Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld & Sandeep Silwal Computer Science and Artificial Intelligence Laa Massachusetts Institute of Technology Cambridge, MA 02139, USA {teden, indyk, shyamsn, ronitt, si silwal] @mit edu
Tal Wagner
Microsoft Research Redmond, WA 98052, USA
talw@mit.ent edu
ABSTRACT
We consider the problem of estimating the number of distinet elements in a large data set (or, equivalently, the support size of the distribution induced by the data set) from a random sample of its elements. The problem occurs in many applica- tions, including biology, genomics, computer systems and linguistics. A line of research spanning the last decade resulted in algorithms that estimate the support up to +en from a sample of size (log" (1/E) n/ n), where n is the data set size. Unfortunately, this bound is known to be tight, limiting further improve- ments to the complexity this problem. In this paper we consider estimation algorithms augmented with machine-learning-banr ement, returns an estimation of its frequency. We show that if the predictor is correct up a constant approximation factor, then the sample complexity can be reduced significantly, to
predictor that, given any el-
log(1/E) (())o)()))))
We evaluate the proposed algorithms collection of data sets, using the neural- network based estimators from Hsu al, ICLR' 19 as predictors. Our experiments demonstrate substantial (up 3x) improvements in the estimation accuracy com- pared to the state of the art algorithm.
INTRODUCTION
Estimating the support size of distribution from random samples is a fundamental problem with applications in many domains. In biology, it is used to estimate the number of distinct species from experiments (Fisher et al., 1943); genomics to estimate the number distinct protein encoding re- gions (Zou et al., 2016); in computer systems to approximate the number of distinct blocks disk drive (Harnik et al., 2016), etc. The problem has also applications in linguistics, query optimization in databases, and other fields.
Because its wide applicability, the problem has received plenty attention in multiple fields!. including statistics and theoretical computer science, starting with the seminal works of Good and Turing Good (1953) and Fisher et al. (1943). A more recent line research pursued over the last decade (Raskhodnikova al., 2009; Valiant Valiant, 2011; 2013; Wu & Yang, 2019) focused the following formulation of the problem: given access to independent samples from a distribution
Authors listed in alphahetical order
A partial bibliography from 2007 contains over 900 references. It is available at https: courses. cit. cornel eedu/jabllllee / wig.bbogghhhh...ooooooooo html.

---

Published as a conference paper at ICLR 2021
P over discrete domain {O..... 1) whose minimum non-zero mass is at least 1/n, estimate the support size of P up to FEn. The state of the art estimator, due to Valiant & Valiant (2011) 1); Wu & Yang (2019), solves this problem using only O(n/ logn) samples (for constant E). Both papers also show that this bound is tight.
A more straightforward linear-time algorithm exists, which reports the number of distinct elements seen in a sample of size N = On loge-") (which is O(n) for constant E), without accounting for the unseen items. This algorithm succeeds because each element i with non-zero mass (and thus mass at least 1/n) appears in the sample with probability at least 1 - (1 - 1/n)* / > 1 é, so in expectation, most E n elements with non-zero mass will not appear in the sample. Thus, in general, the number of samples required by the best possible algorithm (i.e., n/ log n) is only logarithmically smaller than the complexity of the straightforward linear-time algorithm.
A natural approach to improve over this bound is to leverage the fact that in many applications, the input distribution is not entirely unknown. Indeed, one can often obtain rough approximations of the element frequencies by analyzing different but related distributions. For example, in genomics, frequency estimates can obtained from the frequencies genome regions of different species; in linguistics they can be inferred from the statistical properties of the language (e.g., long words are rare), or from a corpus of writings of different but related author, etc. More generally, such esti- mates can be learned using modern machine learning techniques, given the true element frequencies in related data sets. The question then becomes whether one can utilize such predictors for use in support size estimation procedures in order to improve the estimation accuracy.
Our results In this paper initiate the study of such "learning-based" methods for support size estimation. Our contributions are both theoretical and empirical. On the theory side, we show that given a "good enough" predictor of the distribution P, one can solve the problem using much fewer than n/ log samples. Specifically, suppose that in the input distribution P the probability of element i Pt. and that we have access to a predictor II(:) such that I[i)= S ps S b- I[(i) for some constant approximation factor b 2 1. Then we give an algorithm that estimates the support size up to eeen using only
log(1/s)- - log(1/s))
samples, assuming the approximation factor b is a constant (see Theorem for more detailed bound). This improves over the bound of Wu & Yang (2019) for any fixed values of the accuracy parameter e and predictor quality factor Furthermore, we show that this bound is almost tight.
Our algorithm is presented in Algorithm 1. On high level, it partitions the range of probability values into geometrically increasing intervals. We then use the predictor to assign the elements observed in the sample to these intervals, and produce Wu-Yang-lii Specifically, our estimator is based on Chebyshev polynomials (as in Valiant & Valiant (201 1): Wu & Yang (2019)), but the finer partitioning into intervals allows to polynomials with different, carefully chosen parameters. This leads to significantly improved sample complexity the predictor is sufficiently accurate.
estimate within each interval.
On the empirical side, we evaluate the proposed algorithms on a collection of real and synthetic data sets. For the real data sets (network traffic data and AOL query log data) based predictors from Hsu et al. (2019). Although those predictors do not always approximate the true distribution probabilities up to small factor, our experiments nevertheless demonstrate that the new algorithm offers substantial improvements (up to 3x reduction in relative error) in the estimation accuracy compared the state of the art algorithm of Wu & Yang (2019).
neural-network
1.1 RELATED WORK
Estimating support size As described in the introduction, the problem has been studied exten- sively in statistics and theoretical computer science. The best known algorithm, due to Wu & Yang
This constraint is naturally satisfied e.g., .. if the distribution P is an empirical distribution over data set of items. In fact, in this case all probabilities are multiples of 1/n so the support size is equal the numher of distinct elements in the data set.
*Our results hold without change if we modify the assumption to - -TT())) r. br.bTT() TT1). for any > 0. We use for simplicity.
2

---

Published as a conference paper at ICLR 2021
(2019), uses (1log"(1/3) .n/log samples. Because of the inherent limitations of the model that uses only random samples, Canonne & Rubinfeld (2014) considered an augmented model where an algorithm has access to the exact probability of any sampled item. The authors show that this augmentation is very powerful, reducing the sampling complexity to only ((1/e²). More recently, Onak & Sun (2018) proved that Canonne and Rubinfeld's algorithm works long the probabil- ities accessed are accurate up to a (1 + muulippiccatie factor. However, this algorithm strongly relies on the probabilities being extremely accurate, and the predicted probabilities even being off by small constant factor can cause the support size estimate to become massively incorrect. As a result, their algorithm is not robust to mispredicted probabilities, as our experiments show.
A different line of research studied streaming algorithms for estimating the number of distinct el- ements. Such algorithms have access to the whole data set, but must read it in a single pass using limited memory. The best known algorithms for this problem compute (1 + e)-approximate esti- mation to the number of distinct elements using O(1/E² + log n) bits of storage (Kane al., 2010). See the discussion in that paper for a history of the problem and further references.
Learning-based algorithms Over the last few years, there has been a growing interest in using machine learning techniques to improve the performance of "classical" algorithms. This method- ology found applications in similarity search (Wang et al., 2016; Sablayrolles et al., 2019; Dong et al., 2020), graph optimization (Khalil et al.. 2017; Balcan et al., 2018), data structures (Kraska et al., 2018; Mitzenmacher, 2018), online algorithms (Lykouris & Vassilvitskii, 2018: Purohit et al., 2018), compressed sensing (Mousavi et al., 2015; Baldassarre et al., 2016; Bora et al., 2017) and streaming algorithms (Hsu et al., 2019; Jiang et al., 2019). The last two papers are closest to our work, as they solve various computational problems over data streams, including distinct elements estimation in Jiang et al. (2019) using frequency predictors. Furthermore, in our experiments we are using the neural-network-basee predictors developed in Hsu al. (2019). However, our algorithm operates in a fundamentally different model, using a sublinear (in n) number of samples of the input, as opposed to accessing the full input via a linear scan. Thus, our algorithms run in sublinear time, in contrast to streaming algorithms that use sublinear space.
Distribution property testing This work can be seen more broadly in the context of testing prop- erties of distributions over large discrete domains. Such questions are studied at the crossroads of social networks, statistics, information theory, database algorithms, and machine learning al- gorithms. Examples of specific properties that have been extensively considered include testing whether the distribution is uniform, Gaussian, high entropy, independent or monotone increasing (see e.g. Rubinfeld (2012); Canonne (2015); Goldreich (2017) for surveys on the topic).
2 LEARNING-BASED ALGORITHM
2.1 PRELIMINARIES
Problem setting and notation. The support estimation problem is formally defined follows. We are given sample access to an unknown distribution P over a discrete domain of size n. For simplicity, we identify the domain with [n] (I....,n). Let p. denote the probability of element i. Let S(P) = {i: P, > 0} be the support of P. Our goal is to estimate the support size S = [P)) using as few samples as possible. In particular, given 0, the goal is to output an estimate Š that satisfies S E [S EN, S + En].
We assume that the minimal non-zero mass of any element is at least 1/n, namely, that p. 2 1/n for every i E S(P). This is standard promise in the support estimation problem (see, e.g., Raskhod- nikova et al. (2009); Valiant & Valiant (2011); Wu & Yang (2019)), and as mentioned earlier, naturally holds in the context of counting distinct elements, where p; is defined as the count of ele- ment i the sample divided by n. Furthermore, a lower bound on the minimum non-zero probability is a necessary assumption without which no estimation algorithm is possible, even if the number of samples is allowed to be an arbitrarily large function of n. i.e., not just sublinear algorithmss The reason is that there could be arbitrarily many elements with exceedingly small probabilities that would never be observed. See for example the discussion in the supplementary Section 5 of Orlitsky et al. (2016).
3

---

Published as a conference paper at ICLR 2021
In the learning-bast based setting, we furthermore assume have predictor II that provide in- formation about p;- In our analysis, we will assume that II(i) is a constant factor approximation of each P;. In order to bound the running time of our algorithms. we assume to a ready-made predictor and (as in Canonne & Rubinfeld (2014)) that evaluating (i) takes unit neural network based predictors from Hsu et al. (2019). In general,
are given access
time. In experiments, predictors need to be trained (or otherwise produced) in advance. This happens in a preprocessing stage, before the input distribution is given to the algorithm, and this stage is not accounted for in the sublinear running time. We also note that training the predictor needs to be done only once for all future inputs (not once per input).
The Wu & Yang (2019) estimator. In the classical setting (without access to predictor), Wu & Yang (2019) gave a sample-optimal algorithm based on Chebyshev polynomials. We now describe it briefly, as it forms the basis for our learning- based algorithm.
Suppose we draw samples, and let N, be the number of times element is observed. The output estimate of Wu & Yang (2019) is of the form
SwY E(1+f(N))
*E|m]
where f(N)) is a correction term intended to compensate for the fact that some elements in the support do not appear in the sample at all. If p; 0. then necessarily N₂ 0 (as i cannot appear in the sample). Thus, choosing f(() = -1 ensures that unsupported elements contribute nothing to Swy. On the other hand, if p; > log
No then by standard concentration we have N; >> 2(log n) with high probability; thus choosing f(N,) = 0 for all N₂ > L = 22log n) ensures that high-mass elements are only counted once in SwY. It remains to take care of elements with y; E ( N
log ].
By a standard Poissonization trick, the expected additive error |S [[[Sx]] can be bounded by Eie(a) (p()), where PL is the degree-L polynomial
E k!
Pa(x)= =
f(1)
K=
To make the error as small as possible, we would like to choose (px)) on the interval pt E [ I, under the constraint (0) -1 (which is equivalent to f()) = -).. This is a well-known extremal problem. and its solution given by Chebyshev polynomials, whose coefficients have known explicit formula. Indeed, Wu & Yang (2019) show that choosing f())..., (TL) such that F|N = (Ik) are the coefficients of an (appropriately shifted and scaled) Chebyshev polynomial leads to optimal sample complexity of (1/e)"(1/))))) /// m/looggnonnn n).
so to minimize
2.2 OUR ALGORITHM
Our main result is a sample-optimal algorithm for estimating the support size of an unknown distri- bution, where we are given access to samples as well as approximations to the probabilities of the elements we sample. Our algorithm is presented in Algorithm 1. partitions the interval [1 xx)
into geometrically increasing intervals {1 -+++ j 0, .), where is fixed constant that we refer to as the base parameter (in our proofs this parameter upper bounds the approximation factor of the predictor, which is why studied in detail in the next section). The predictor assigns the elements observed in the sample to intervals, and the algorithm computes Chebyshev polynomial estimate within each interval. Since the approximation quality of Chebyshev polynomials is governed by the ratio between the interval endpoints (as well as the polynomial degree), this assignment can be leveraged to get more accurate estimates, improving the overall sample complexity. Our main theoretical result is the following.
the same letter denote both; its setting in practice is
Theorem 1. Let b > 1 be a fixed constant. Suppose we have a predictor that given i E [n] sampled from the input distribution, outputs II(i) such that II(i) S p: < b I[(i). Then, for any > n -1/2 if we set L = ([og((/ss) and draw N ~ Poisson (L n 1114) samples, Algorithm reports an estimate S that satisfies S [S -evns, S 5 + eVnS) with probability at least 9/10. In other words,
4

---

Published as a conference paper at ICLR 2021
Algorithm 1: Learning-Baaseee Based Support Estimation
Input: Number of samples N, domain size ni base b, polynomial degree predictor
Output: Estimate $ of the support size
Partition [, 1] into intervals I
1/' 64+1
for O,.... log, n
n n
Let do, d1, . dr be the coefficient of the Chebyshev polynomial (r(2) from Equation (1)
(Note that 0* O for all k > T.) Draw N random samples
N₂- = # of times we see element in samples
for every interval 15 do
to _ 0.5 then
8, Σ iein):
(1+ ON; (3) N+.)
else
$, = # E [n] No 2 (T) 1
10
end
11 end
12 return
5 5= -5= 53
log,
using
o (log (1/e) ((1/lo((1/))
samples, approximate the support size S up an additive error of EVnS, with probability at least 9/10.
Note that sample complexity of Wu Yang (2019) (which is optimal without access a predictor) is nearly linear in while Theorem gives bound that is polynomially smaller than n for every fixed > 0. Also, note that vn. n, our estimate is also within e n of the support size S.
We also prove a corresponding lower bound, proving that the above theorem essentially tight.
Theorem 2. Suppose we have access a predictor that returns I[(i) such that II(i) S Pt S 2 2-II(i) for all sampled Then any algorithm that estimates the support size to an En additive error with probability least 9/ 10 needs (
1011/100g (lo//l/)//)) samples.
We prove Theorems and 2 in Appendix A. We note that while upper bound proof follows similar approach to Wu & Yang (2019), our lower bound follows a combinatorial approach differing from their linear programming arguments.
The Chebyshev polynomial. For completeness, we explicitly write the polynomial coefficients used by Algorithm The standard Chebyshev polynomial of degree I. on the interval [-1, 1] given by
Q2(x)= = cos(L- arccos(z)).
For Algorithm I, we want polynomial as follows:
(L(x) = Σ aaaa satisfying PL(0) = - and PL(x) E [-c,e] for all 1 < S b².
k=
This is achieved by shifting and scaling QL. namely, this polynomial can be written as
220- (oe-(62+)) QL
(B2 (b2-1)
PL(x)
Qr
*The fact this is indeed polynomial is proven in standard texthooks, e.g., Timan al. (1963).

---

Published as a conference paper at ICLR 2021
where e equals Qr (- +1
which decays as e- if b is constant. Thus it suffices to choose L ([lo([]/s) in Theorem 1.
2.3 ASSUMPTIONS ON THE PREDICTOR'S ' ACCURACY
In Theorems and 2, we assume that the predictor IT is always correct within a constant factor for each element As we will discuss in the experimental section, the predictor that we use does not always satisfy this property. Hence, perhaps other models of the accuracy of II are better suited, such as a promised upper bound on (II P). i... the total variation distance between II and P. However, it turns out that if we promised that TV (II, P) S E, then the algorithm of Canonne & Rubinfeld (2014) can in fact approximate the support size of P up to error (Ee) n using only O(e-²) samples. Conversely, if we only promised that (II P) S 7 for some ? > E, the algorithm of Wu & Yang (2019), which requires (n/ log n) samples to approximate the support size of P, is optimal. We formally state and prove both of these results in Appendix A.3.
Our experimental results demonstrate that our algorithm can perform better than both the algorithms of Canonne & Rubinfeld (2014) and Wu & Yang (2019). This suggests that our assumption (a point- wise approximation guarantee, but with an arbitrary constant multiplicative approximation factor), even if not fully accurate, is better suited for our application than total variation distance bound.
EXPERIMENTS
In this section we evaluate our algorithm empirically on real and synthetic data.
Datasets.
We use two real and one synthetic datasets:
AOL: 21 million search queries from 650 thousand users 90 days. The queries
keywords for the AOL search engine. Each day is treated as a separate input distribution. The goal is estimate the number of distinct keywords.
Packets collected a backbone link of Tierl ISP between Chicago and Seattle in 2016 over 60 minutes.' Each packet is annotated with the sender IP address, and the goal is to estimate the number of distinct addresses. Each minute treated as a separate distribution.
IP:
Zipfian: Synthetic dataset of samples drawn from finite Zipfian distribution over {1.... 100} with the probability of each element proportional to --0.5
The AOL and IP datasets were used in Hsu et al. (2019), who trained a recurrent neural network (RNN) predict the frequency of given element for each of those datasets. We use their trained RNNs predictors. For the Zipfian dataset we use the empirical counts of an independent sample as predictions. A more detailed account of each predictor is given later in this section. The properties of the datasets are summarized in Table 1.
Baselines.
We compare Algorithm 1 with two existing baselines:
The algorithm of Wu & Yang (2019), which is the state the art for algorithms without predictor access. We abbreviate its name WY.5
The algorithm of Canonne & Rubinfeld (2014), which is the state of the art for algorithms with access to a perfect predictor. We abbreviate its name as CR.
Error measurement. We measure accuracy in terms of the relative error |1 Š/S), where S is the true support size and 5 is the estimate returned by the algorithm. We report median errors over 50 independent exccutions of each experiment, + one standard deviation.
$ From CAIDA
internet
traces
2016,
https://wwwt ca' www.cca.............. da..og/ddaa//oooooonnonooo
passi ve-eeuiin ch cago. xm1.
'Apart from their tight analysis, Wu & Yang (2019) also report experimental results showing their algorithm empirically superior previous baselines.

---

Published as a conference paper at ICLR 2021
Table 1:
Datasets used in our experiments. The listed values of n (total size) and support size (dis- tinct elements) for AOL/IP are per day/minute (respectively), approximated across all days/minutes.
Name
Type
# Distributions
Predictor
Support size
AOL IP Zipfian
Keywords
90 (days)
RNN
~ 4 4.10 ~ 10
2 10
IP addresses
60 (minutes)
RNN
~ 106
Synthetic
Empirical
10
Summary of results. Our experiments show that the predictor to get significantly improved accuracy compared to WY. On the other hand, our al- gorithm is robust to different predictors: while the CR algorithm performs extremely well on one dataset (AOL), it performs poorly on the other two (IP and Zipfian), whereas our algorithm is able to leverage the predictors in those cases too and obtain significant improvement over both baselines.
hand, algorithm can indeed leverage
3.1 BASE PARAMETER SELECTION
Algorithm uses two parameters that need to be set: The polynomial degree L, and the base param- eter b. The performance of the algorithm not very sensitive to L, and for simplicity we use the same setting as Wu & Yang (2019), L = [0.45 log.... The setting of requires more care.
Recall that b is constant used as the ratio between the maximum and minimum endpoint of each interval I, in Algorithm 1. There are two reasons why b cannot be chosen too small. One is that the algorithm is designed to accommodate a predictor that provides a b-approximation of the true probabilities, so larger b makes the algorithm more robust to imperfect predictors. The other reason is that small means using many small intervals, and thus a smaller number of samples assigned to each interval. This leads to higher noise in the Chebyshev polynomial estimators invoked within each interval (even if the assignment of elements to intervals is correct), and empirically impeees performance. On the other hand, if we set to be too large (resulting in one large interval the covers almost the whole range of p. s), we are essentially not using information from the predictor, and thus do not expect to improve over WY.
To resolve this issue, we introduce a sanity check in each interval Ij. whose goal is to rule out bases that are too small. The sanity check passes if S, E [0, 1/4j], where I is the left endpoint of I, (i.e., I, ry),, and Sy is defined in Algorithm The reasoning is as follows. On one hand, the Chebyshev polynomial estimator which we use to compute Š, can in fact return negative numbers, leading to failure modes with S; < O. On the other hand, since all element probabilities in I₁ are lower bounded by 1,. it can contain at most 1/1, elements. Therefore, any estimate S, of the number of elements in I, which is outside [o, 1/45] is obviously incorrect.
In our implementation, we start by running Algorithm with b = 2. If any interval fails the sanity check, we increment b and repeat the algorithm (with the same set of samples). The final base we use is twice the minimal one such that all intervals pass the sanity check, where the final doubling is to ensure we are indeed past the point where all checks succeed.
The effect of this base selection procedure on each of our datasets is depicted in Figures 1, 3, and 5.? For fixed sample size, we plot the performance of our algorithm (dotted blue) as the base increases compared to WY (solid orange, independent of base), as well as the fraction of intervals that failed the sanity check (dashed green). The plots show that for very small bases, the sanity check fails on some intervals, and the error is large. When the base is sufficiently large, all intervals pass the sanity check, and we see sudden plunge in the error. Then, as the base continues to grow, our algorithm continues to perform well, but gradually degrades and converges to WY due to having single dominating interval. This affirms the reasoning above and justifies our base selection procedure.
In those plots, for visualization, in order compute the enror whenever sanity check fails in 15. we replace S, with a naive estimate, defined as the number of distinct sample elements assigned to Ij. Note that our implementation never actually uses those naïve estimates, since it only uses bases that pass all sanity checks.
7

---

Published as a conference paper at ICLR 2021
Dataset: ADL Day 10, 10%
Dataset: ADL Day 10
Our Aig
Our Aig
Fall %
Alg
Error
02
0.-
0.0
10
25
10
Sample %
Figure 1: Error by base, AOL, sample size 10%-1
Figure 2: Error per sample size, AOL
2.00
Our Aig WY
1.50
Fail %
1.25
Our Alg
1.00
A/g
0.75
Alg
200
400
600
Sample size: % of 25
Base
Figure 3: Error by base, IP, sample size 1%
Figure 4: Error per sample size, IP
Dataset: Ziflian. 5%
Dataset: Ziplian
Our Alg
WY Alg
Fail %
Our
WY
Alg
0.4
0.
0.0
20
80
100
120
10
20
50
Base
Sample size: %
Figure 5: Error by base, Zipfian, sample size 5%m
Figure 6: Error per sample size, Zipfian
3.2 RESULTS
AOL data. As the predictor, we use the RNN trained by Hsu et al. (2019) to predict the frequency of given keyword. Their predictor is trained on the first 5 days and the 6th day is used for validation. The results for day #10 are shown in Figure (The results across all days are similar; see more below.) They show that algorithm performs significantly better than WY. Nonetheless, CR (which relies on access to perfect predictor) achieves better performance on a much smaller sample size. This is apparently due highly specific traits of the predictor; as we will see presently, the performance of CR is considerably degraded on the other datasets.
IP data. Here too use the trained RNN of Hsu et al. (2019). It is trained on the first 7 minutes and the 8th minute used for validation. However, unlike AOL, Hsu et al. (2019) trained the RNN to predict the log of the frequency of the given IP address, rather than the frequency itself, due to training stability considerations. To use it as a predictor, we exponentiate the RNN output. This inevitably leads to less accurate predictions.
8

---

Published as a conference paper at ICLR 2021
Dataset: AOL, 5%
Dotaset: AOL, 10%
0.23
05
Our Aig
WY Aig
0.30
Our Alg
0-4
CR Alg
0.23
WY A/g
Alg
0.20
0.15
0.30
0.25
0.30
76
80
30
75
Day
Day
(a) Sample size: 5% TL
(b) Sample size: 10% Y2
Figure 7: Error across the different AOL days
IP,
Our Aig
WY A/g
0.6
Our Aig
A/g
CR Alg
03
Alg
0.3
0.3
0.-
20
Minute
Minute
(a) Sample size:
1% n
(b) Sample size: 2.5%
Figure 8: Error across the different IP minutes
The results for minute 59 shown in. Figure 4. (As in the AOL data, the results across all minutes are similar, see more below). Again we see significant advantage to our algorithm over WY for small sample sizes. Here, unlike the AOL dataset, CR does not produce good results.
Zipfian data. To form predictor for this synthetic distribution, 10% n, and used the empirical count of each element in this fixed sample as the prediction for its frequency. If the predictor is queried for an element that did not appear in the sample, its predicted probability is reported as the minimum 1/n. We use this fixed predictor in all repetitions of the experiment (which were As with the IP data, our algorithm significantly improves over WY for small sample sizes, and both algorithms outperform CR by a large margin.
drew a random sample of size
fresh independent samples). The results reported in Figure 6.
AOL and IP results over time. Finally, present accuracy results the days/minutes of the AOL/IP datasets (respectively). The purpose is to demonstrate that the performance our algorithm remains consistent over time, even when the data has moved away from the initial training period and the predictor may become 'stale'. The results for AOL are shown in Figures 7a, 7b, yielding median 2.2-fold and 3.0-fold improvement over WY (for sample sizes 5% n and 10% n, respectively). The results for IP are shown in Figures Sa and 8b, yielding a median 1.7-fold and 3.0- fold improvement over WY (for sample sizes 1% n and 2.5% n, respectively). As before, CR performs better than either algorithm on AOL, but fails by large margin on IP.
ACKNOWLEDGMENTE
This research was supported in part by the NSF TRIPODS program (awards CCF-1740751 and 2MS-2202448); NSF awards CCF-1535851, CCF-2006664 and IIS- 17711:77; Fintech@ CSAIL; Simons Investigator Award; MIT-IBM Watson collaboration; Eric and Wendy Schmidt Fund for

---

Published as a conference paper at ICLR 2021
Strategic Innovation, Ben-Gurion University of the Negev; MIT Akamai Fellowship: and NSF Grad- uate Research Fellowship Program.
The authors would like to thank Justin Chen for helpful comments draft of this paper, well as the anonymous reviewers.
REFERENCES
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In International Conference on Machine Learning, pp. 353-362, 2018.
Luca Baldassarre, Yen-Huan Li, Jonathan Scarlett, Baran Gözcü, Ilija Bogunovic, and Volkan Cevher. Learning-based compressive subsampling. IEEE Journal of Selected Topics in Signal Processing, 10(4):809-82) 822, 2016.
Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using genera- tive models. In International Conference on Machine Learning, pp. 537-546, 2017.
Clément Canonne and Ronitt Rubinfeld. Testing probability distributions underlying aggregated data. In International Colloquium on Automata, Languages, and Programming, pp. 283-295. Springer, 2014.
Clément I.. Canonne. A survey distribution testing: Your data is big. but is blue? Electron. Colloquium Comput. Complex., 22:63, 2015.
Yihe Dong, P. Indyk, llya P. Razenshteyn, and T. Wagner. Learning space partitions for nearest neighbor search. In ICLR, 2020.
Ronald A Fisher, A Steven Corbet, and Carrington B Williams, The relation between the number of species and the number of individuals in random sample of an animal population. The Journal of Animal Ecology, pp. 42-58, 1943.
Oded Goldreich. Introduction Property Testing. Cambridge University Press, 2017.
Irving Good, The population frequencies of species and the estimation population parameters. Biometrika, 40(3-4):237-264, 1953.
Danny Harnik, Ety Khaitzin, and Dmitry Sotnikov. Estimating unseen deduplication-ffrnn theory to practice. In 14th {USENIX) Conference on File and Storage Technologies ({FAST} 16), pp.
277-290, 2016.
Chen-Yo Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In International Conference Learning Representations, 2019.
Tanqiu Jiang. Yi Li, Honghao Lin, Yisong Ruan, and David P Woodruff.
Learning samniigg data stream algorithms. In International Conference Learning Representations, 2019.
Daniel M Kane, Jelani Nelson, and David Woodruff. An optimal algorithm for the distinct ele-
ments problem. In Proceedings of the twenty-ninth ACM SIGMOD-SIGACTSSICART symposium on Principles of database systems, pp. 41-52, 2010.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial op- timization algorithms over graphs. In Advances in Neural Information Processing Systems, pp- 6348-6358, 2017.
Tim Kraska, Alex Beutel, Ed Н Chi, Jeffrey Dean, and Ncoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, pp. 489-504, 2018.
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In International Conference Machine Learning, pp. 3302-3311, 2018.
V. A. Markov. On functions of least deviation from zero in given interval. St. Petersburg, 1892.
10

---

Published as a conference paper at ICLR 2021
Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Advances in Neural Information Processing Systems, pp. 464-473, 2018.
Ali Mousavi, Ankit B Patel, and Richard G Baraniuk. A deep learning approach to structured signal recovery. In Communicaaiin, Control, and Computing (Allerton), 2015 53rd Annual Allerton Conference on, pp. 1336-1343. IEEE, 2015.
Krzysztof Onak and Xiaorui Sun. Probability reveelin samples. In International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pp. 2018-2026. PMLR, 2018.
Alon Orlitsky, Ananda Theertha Suresh, and Yihong Wu. Optimal prediction of the number of unseen species. Proceedings of the National Academy of Sciences, 113(47):13233-12288 2016. ISSN 0027-8424. doi: 0t0033//naas.007741111 URL https: www. pnas org/ content
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Advances Neural Information Processing Systems, pp. 9661-9670, 2018.
Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam Smith. Strong lower bounds for approx- imating distribution support size and the distinct elements problem. SIAM Journal on Computing, 39(3):813888) 842, 2009.
Ronitt Rubinfeld. Taming big probability distributions. XRDS, 19(1):24-28, 2012.
Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, and Hervé Jégou. Spreading vectors for similarity search. In International Conference on Learning Representations, 2019. URL https: openreviewww net. wtt.eviwwwwee/.uunteeteee /
AF Timan, M Stark, IN Sneddon, and S Ulam. Theory of approximation of functions of real variable. 1963.
Gregory Valiant and Paul Valiant. Estimating the unseen: an n/log (n)-sample estimator for entropy and support size, shown optimal via new clts. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 685-694, 2011.
Paul Valiant and Gregory Valiant. Estimating the unseen: improved estimators for entropy and other properties. In Advances Neural Information Processing Systems, pp. 2157-2165, 2013.
Jun Wang, Wei Liu, Sanjiv Kumar, and Shih-Fu Chang. Learning to hash for indexing big data survey, Proceedings of the IEEE, 104(1):34-57, 2016.
Yihong Wu and Pengkun Yang. Chebyshev polynomials, moment matching, and optimal estimation of the unseen. The Annals of Statistics, 47(2)88578883, 2019.
James Zou, Gregory Valiant, Paul Valiant, Konrad Karczewski, Siu On Chan, Kaitlin Samocha, Monkol Lek, Shamil Sunyaev, Mark Daly, and Daniel MacArthur. Quantifying unobserved protein-coding variants in human populations provides a roadmap for large-scale sequencing projects. Nature communications, 7(1):155, 2016.

---

Published as a conference paper at ICLR 2021
A OMITTED PROOFS
A.1 ANALYSIS OF THE UPPER BOUND
In this subsection, we prove Theorem 1, which provides the upper bound for the sample complexity of Algorithm
Proof of Theorem 1. Consider some E [ni]. The predictor II gives us an estimate II( E [pe. b pil of the unknown true probability Let ji be the integer for which I1(i) E | 14 J. assigned by the predictor the interval 1;.- Observe that as a consequence, have
We treat as
82 b4++2
P:
(2)
Suppose i is observed l times in the sample. Define,
+ ag (mi)
kt N
if b
0.5 log N
5(1)
if bi
0.5 logn and k: 2
N
if P 0.5 n
and & 0
The ag 's are the Chebyshev polynomial coefficients as per Algorithm 1. Note that as we drew a total of Pois(N) samples, the number of times each element appears in the sample is distributed as N = Pois(N p:) times, and the values N; are independent across different i's (this is the standard
Poissonization trick). Thus the ((1)'s are also independent. Moreover, note that the value S, defined
in Algorithm satisfies $, = E (i). Finally, by eq. (2) we have pi
n px E [1, b2). Thus, log we compute the expectation of S(i) as (letting = ji to ease notation),
N
B[$(1)) = 1+
Σ
P(N: = k) ak
n2
k!
65
N
k=0
L
NDi NoNNiiNNN (Npx)*
k
k!
= =1+
k!
b5
N
k=0
=1 1 Npc
Σ
Pi
b
k=
1 -1+e Np.
PL
Pi
E [1 1-,,+++))
since p. # E [1, 6P] and since e- -Np: S 1. However, if Mi 0.5 log
then E[Š(i)
equals the 0.5 have
N bdt 72
probability that is sampled, which is 1 (1 N. But since ps 0.5 log N
that 1 2 B[$(1)
1 (0.5 n/N =
We note that if í is
never seen (which is possible even if p. * 0), we do not know j:. However, in this case, š(1) = regardless of the value of j,. Therefore, we get an estimator 5(1) such that Š(i) = if p; = 0 and E[Š(1) E [1 e, 1 + E] otherwise, assuming s > n -1/2
Next we analyze the variance of (()). For i with Otherwise, if be 0.5 N then S(i) is always between 0 and 1, Var(š(i)) 1. Finally, if
0, Š(i) = 0 always, so Var Var(š(i)) = 0.
12

---

Published as a conference paper at ICLR 2021
bi: 0.5 log then Var(S(i)) - [[(((i) 1)²] and write (again with j j.)
12 n
Bi(((i) - 1) Σ
P(N: 1b)-
ak (p.
65 )
km
Np: (NDi)*
k
k!
h!
OKk
N
max ok
ps
11
71
k!
OSASL
bi
N
k=0
12
k
n
0%
(3)
OSkSL
N
where for the last incquality noted that k! S KR, P:
+ S b², and b > 1.
Now, it is a well known consequence the Markov Brothers' inequality that all the coefficients of the standard degree Chebyshev polynomial Qr.(z) are bounded by co(L) (Markov, 1892).
Since Pt Σ ag*x is just e Q [ + +x. = we have that for any fixed b O the coefficients og are all bounded by eOLL) as well. Therefore, for C. 12 L n²-1/LL for some constant C, we have that 12 k n/N S n2/L /C, so we can bound Equation (3) by
O(L)
n (O')
k=
for some other constant C".
In summary, if P. + O, have that B[$(i)] E [1- + and Var($(i)) < n2n if choose C to be sufficiently large constant, since O(L) for constant for hitt no since e > 1. However, we know that Š = E) 5 Σ (i)), since by the definition of Sj. S₁ Em S(1). Therefore, since the estimators S(1) are independent, have that [ = Σi= [[S(i)] E (1 (1-e, - and Var($) = Eiprzo Var Var(š(i)) < s² - n S, where we use the independence the ((i)'s. Therefore, since S S n, with probability at least 0.9, |Š - S = O(E) vn- 5 by Chebyshev's inequality.
S ((). This is true even
N
Remark. We note that our analysis actually works (and becomes somewhat simpler) even if the algorithm is modified to define S, ExE(n))n(0),,, (1+ (N) S.N..N -NNE) for all intervals, as (z)), opposed to S, = # [n]: N, Z I,I1( E 13} for the intervals 1y with >> 0.5 logg However, because we can decrease the bias as well as the variance for these larger intervals, we modify the algorithm accordingly. While this does not affect the theoretical guarantees, demonstrated improvement in practice This threshold was also used in Wu Yang (2019) (the choice of leading constant 0.5 in the threshold term 0.5 is arbitrary, and for simplicity we have adopted the value they used).
N
A.2 ANALYSIS OF THE LOWER BOUND
In this subsection, we prove Theorem 2, which proves that the sample complexity of Algorithm 1 is essentially tight.
Proof of Theorem3 2. In order to prove the lower bound, shall define two distributions P and Q for which the first & moments are matching, but their support size differs on at least En elements. Furthermore, both distributions will be supported {0} & k+1 2k n so that 2-factor ap- proximation predictor does not provide any useful information to an algorithm trying to distinguish the two distributions.
13

---

Published as a conference paper at ICLR 2021
We start with overview of the definition of the two distributions and then explain how to formalize the arguments, following the Poissonnization and rounding techniques detailed in Raskhodnikova et al. (2009).
Let -A: -ks 2 (2h) (22) ) for some integer 2 Note that =()(kk) In order define the
@(k)
distributions, we define k + 1 real numbers 0p..... Ab as (-1)-(() (k++)) for every E {0...... k)- k)).
Suppose for now that n a multiple the least common multiple of 2 k 2k, so that 0g n an integer for every i. We define P and Q follows:
The distribution P: For every such that a; 0, the support of P contains a, elements j that have probability Pj = a, ketz each.
The distribution Q: For every a; such that < O, the support of Q contains -a; elements j that have probability q = - n
k+i
each.
First prove that P and Q are valid distributions and that all of their non-zero probabilities greater than 1/n..
Claim A.1. P and Q as defined above are distributions. Furthermore, their probability values are either O or greater than 1/n.
Proof. The second part of the claim follows directly from the definition of P and Q. We continue to prove the first part, that P and Q are indeed distributions. It holds for P that
Σ (nay)
k +i
1
1:
kti
1
1.
2
1
n1
2
a:/a:50
f=0
Similarly, for Q
k+
k
k +1
(n(-a;))
1.
1:
2
2
50
(=0
f=0
odd
odd
We continue to prove that the first i moments of P and Q are matching, and that their support size differs by en.
Claim A.2. Let ai,...,,0; ag defined as above. Then
For any E (l,...,k,, it holds that Ei - (k + i)r O.
El Ei=0 a==0
Proof. By plugging the a;'s 's defined above,
(-1)(()
a. (k +i" = Σ Σ 1
(k +1)"
1)'
(k + ())=
2k-1 2k-1.
2 1=0
1=0
Hence, letting r' -- 1, it suffices to prove that E ())
0 for all 0 5 S S For any fixed kt note that since (I: + i)" is a degree r' polynomial (I + i)" can be written as a linear combination of ()) for 0 S s E r' with coefficients bo.... by Therefore, we would like to prove that: (-1( Ex'o 6, () 0. Fix some s in (O...., r'}: : suffices to show that for
any integer k. Et (t)( (*) 0 for all 0 < <
14

---

Published as a conference paper at ICLR 2021
Since (9) (c)
(A
k
(0)
(:=3)) by setting k' = k - and i' = - get
k
k
(
k 8
ht
K
Σ
(-1)
(-1)
1)
x
k
(-1)* (1 1)d²
where the last equality is since k' k - 2 1. This concludes the proof of the first item.
We continue to prove the second item in the claim:
Σ
ai =
(4)
1=0
(-)) ()+ and that k 2 (2
Recall that 0;
so plugging these into Equation (4)
and multiplying both sides by 2 (2M) this is equivalent to proving
(-1)²
(7))
2k
(5)
k +
Since (9) (2)
(2++)
the right-hand side of Equation (5) equals
-
Σ
(-1) 2k
k +
Σ( (-1)
( 2k
(ktt))
(k+i-l)
(k 1-1
1) 1
k
+
h:
+ i)
km0
0=0
Multiplying by k. it suffices to show that
( k: (x+i) ) k 4-1
k + (k+i-t) 1
(-1)
(6)
1=0
To do this, let = le + i. Then, note that (( = (+-)) ( (-1))-1 I+1) which a degree
[k- (1-1))
k - 1 polynomial in j. For S j < k - 1 the polynomial equals O, but for j = 0 the polynomial
equals (-1)*-1, Therefore, the right hand side of Equation (6) equals
2kk Σ 1-11 (2,)
(j 1)................ (j k + 1+(-1) Σ (k 1)!
(-10. 22 (j 1)... ... (j le +
(k - 1)!
As proven in the first part of this proof, for any P(j) of degree 0 < r < 2h 1, E)=o( (1) P(j) = O. Therefore, the summation on the right hand side is 0, so this simpli- fies to 1, as required.
The following corollary follows directly from the definition of P and Q and the previous claim. Corollary A.1. The following two items hold for P and Q as defined above.
E P'] = E[["" for all r E kk.
TV(P,Q) = En.
The above corollary states that indeed P and Q defined above have matching moments for to kt and that they differ by en in their support size. This concludes the high level view of the construction of the distributions P and Q. In order to finalize the proof we rely the standard Possionization and rounding techniques.
First, by Theorem 5.3 in Raskhodnikova et al. (2009), any sammpes algorithm can be simulated by an Poisson algorithm. Hence, we can assume that the algorithm takes Poi(s) samples, rather than arbitrary number Second, can alleviate the assumption that the a; values (similarly
15

---

Published as a conference paper at ICLR 2021
-a, n) are integral for all i, by rounding down the value in case it is not integral, and choosing Eiz [a ni] additional elements in P so that each has probability 1/n (and analogously for Q). By Claim 5.5 in Raskhodnikova et al. (2009) this process increases the number of values in P and Q by at most O(k2). Hence, the distributions are now well defined, and we can rely on the following theorem from Raskhodnikova et al. (2009).
Theorem 3 (Corollary 5.7 in Raskhodnikova et al. (2009), restated.). Let P and Q be random variables over positive integers bj <... < bR-1, thut have matching moments 1 through k 1. Then for any Poission-s algorithm A that succeeds to distinguish P and Q with high probability,
= 1(n
Therefore, plugging the value of e, we get an 9(n lower bound as claimed.
A.3 BOUNDS WHEN THE PREDICTOR IS ACCURATE UP TO Low TOTAL VARIATION DISTANCE
In this section, we consider estimating support size when we are promised a bound on the total variation distance. or & distance, between the prediction oracle and the true distribution. First, we show that if the predictor accurate up to extremely low total variation distance, then the algorithm of Canonne & Rubinfeld (2014) is optimal.
Theorem 4. Let IT represent our predictor, where for each sample we are given a random sample i ~ P along with II)... If we define p(i) == P(i ~ P),, then if [|P-II]]> = E lp(i) - ((()) S 2' then using ( samples, the algorithm of Canonne and Rubinfeld can approximate the sample size up to an & n additive error.
Proof. The algorithm of Canonne & Rubinfeld (2014) works as follows. For each sample (i, (()). it computes 1/II(i). and averages this over O(= samples.
From now on, we also make the assumption that 11(i) 2 1/n for all i. This is because we know p(i) 2 1/n whenever is sampled, so the predictor 11' max I/n) is a strict improvement over II for any that is sampled.
If we draw ~ P, then E p(t)
p()) = S, where S is the support size. Also, Ei mm 1], which, if II(i) 1, is bounded in S n -1())) < 2 So, Empl ( [S 35-E- E n.-., S +..n).
= Σ =00 p(i)
E E
p() E +0 p(i) (nO) p())
absolute value by Σ
p(8)
(T(A)
Since have made sure that II(i)= 2 whenever is sampled, Var( m()) S n². Therefore, by
a basic application of Chebyshev's inequality, an average of (s--2) samples of [( is sufficient to L
estimate S up to a E additive error.
The Canonne and Rubinfeld algorithm has been shown to be far less robust to the error of our predictor, even when given an equal number of samples as our main algorithm. This suggests that an s-total variation distance bound assumption is a less suitable assumption in our context.
Conversely, if the predictor is only promised be accurate up to not-as-low total variation distance, we show that no algorithm can do significantly better than Wu & Yang (2019).
Theorem 5. Let represent our predictor, and recall that p(t) = Pii ~ PP) Suppose the only promise we have on II is that ||P- II|| = -i=1 M' lp(i) - (i)) S Y for some 7 2 Ce, where C is some sufficiently large fixed constant and & > Then, there does not exist algorithm that can learn the support size o P up to an E n additive error using o(n/ log samples.
Proof. Consider some unknown distribution over [n] that we want learn the support size of, with only samples and no frequency predictor. Moreover, assume that for all i E [n], D(i) 2 1/n whenever D(t) > O, where D(i) P(i D). Now, let m n n/y, and consider the following distribution P on [m]. For < i S m. let p(i)
2 and for < i S n, let p(i) 7 (()).
Let II be the uniform distribution
[n + 1 m), i.e., II(1) 0 if S and I[i: m if
i > n + 1. It is clear that P and IT are both distributions over [m] (i.e., the sum of the probabilities
16

---

Published as a conference paper at ICLR 2021
equal 1), the minimum nonzero probability of P is at least 2 and that (V(P, II) S y. Finally, the support size of P is precisely m n more than the support size of D.
trying prove is false. Then, there is algorithm that, given A ol log mn random samples (i, II(i)) where each i i~ P, can determine the support size P up to an e m factor. Then, since the support size of exactly m n less than the support size D, one learn the support size of DD up e S g S ? additive enror using samples (i, [[))) for P.
Assume the theorem
Now, using only θ(7 k)) samples from D, it is easy to simulate k samples from (i, II(2)), where i P. This because generate sample (i, (i)); we first decide if latter occurring with probability 7). In the former case, we draw i uniformly at random and let II()) m-n the latter case, we know that P conditioned on i S has the same distribution as D, so we just draw D and I1(i) = O, since Il is supported only on [n + : m). With very high probability (by simple application of the Chernoff bound), we will not more than O(7 k) samples from D.
or n (the
log 73 samples (since 2 2 1/n) from D, have learned the support size of D up to an T additive error. This algorithm works for an arbitrary D and the predictor II does not actually depend on D. Therefore, for sufficiently large C, this violates the lower bound of Wu & Yang (2019), who show that one samples.
Overall, this means that using only ( k)
Tog 79
log mT
cannot learn the support size of DD up to δ additive error using
Ing
17


Reviews:
[{"review_id": "xj4hL2Od8WF", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper studies the following problem: suppose there is a distribution $P$ over $n$ class {$0, 1, \\dots n-1$},  and one has access to a set of samples drawn from $P$. The goal is to estimate $k$, the number of classes whose probability mass is non-zero.\n\nFirst of all, it seems the literature addresses the problem by assuming each $p_i \\geq 1/n$, where $p_i$ is the mass for class $i$. Thus, by Chernoff bound it is not surprising to see that taking $O(n)$ samples suffices. However, recent progress showed that a bound of $O(n / \\log n)$ can be achieved.\n\nIn this paper, by assuming that there exists some fairly good estimate of $p_i$, i.e. we have $\\Pi_i$ on hand with $1 \\leq \\Pi_i / p_i \\leq b$ for some known constant $b$, authors show that the above sample complexity can be further improved to $\\log(1/\\epsilon) \\cdot \\frac{n}{n^{\\log(1/\\epsilon)}}$.\n\nMy major concern is such assumptions might be too strong.\n- Authors simply cite couple of related works and say: (A1) $p_i > 1/n$ is mild condition. I am not convinced by such argument. If we drop such assumption, is there any fundamental challenge to well define the problem?\n- On top of it, authors further argue that: (A2) there are good estimates of $p_i$ available to us, and the approximation parameter $b$ is also known. It looks fairly artificial for such two-sided approximation condition to hold, and it is not even of theoretical interest.\n\nOn the algorithmic end, it looks interesting to draw a more careful analysis on top of [WY19]. However, the unrealistic assumption (A2) does diminish the contribution.", "extra_scores": {}, "extra_text": {}}, {"review_id": "gvWCbHwIDt", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper considers the problem of estimating the support of a discrete distribution, when provided access to samples and an oracle that approximately predicts the probability of the observed sample.\n\nThey propose an algorithm based on Chebyshev polynomials  and also show that the proposed algorithm is optimal. They evaluate the algorithm on two public datasets and a synthetic dataset and show that the algorithm performs reasonably well. The results are interesting and I recommend acceptance.\n\nThe main technical contribution is to use the approximate probability of the sample to divide the interval [0, log n /n] into exponential bins and use the best Chebyshev approximation within each interval.\nI strongly encourage authors to add technical comparisons between their work and that of Canonne and Rubinfeld 2014 and other relevant papers e.g.,\n1. Optimal Bounds for Estimating Entropy with PMF Queries\n2. Probability–Revealing Samples\n\nI am also curious to know if similar results hold for unseen species estimation (e.g., https://www.pnas.org/content/113/47/13283.short)?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Z0r7bsxSDlf", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper considers the support size estimation problem using a random sample from the unknown distribution and access to some predictor of the element frequency. Under that setting, the paper improves the estimator by Wu & Yang (2019) by refining the approximation interval promised by the predicted frequency. A theoretical upper bound on the sample complexity is proved in Theorem 1 using the proposed algorithm, and it is nearly optimal as shown by the lower bound in Theorem 2. The algorithm is empirically evaluated by both real and synthetic datasets. The empirical performance improves existing algorithms of WY and CR in most cases. \n\nThe algorithmic design and analysis are based on the Chebyshev polynomials by Wu & Yang (2019). Given access to the estimated element frequency, the proposed algorithm uses a smaller approximation interval that yields a smaller approximation error and thus a smaller bias. The performance improves WY which has no access to any frequency predictor, and also improves CR that requires perfect frequency information. Overall I think this paper is theoretically sound and empirically convincing. I will recommend for acceptance after the concerns below are addressed.\n\nOne major concern is the claim of sublinear time in the title. This seems to be not justified in the paper. From my understanding, given a dataset, the computation time consists of the following: train a frequency predictor, incrementally test the base parameter, construct estimators in each interval, collecting samples, call the frequency predictor, compute each estimator and report the sum. I can see some steps are easy to compute (such as computing a linear estimator), but the overall time complexity should be justified.\n\nAnother concern is the theoretical guarantee of the frequency predictor. Estimating element frequency seems not an easy problem by itself given such a small amount of samples relative to $n$. The theorem requires $\\Pi(i)\\le p_i \\le b\\Pi(i)$ for a constant $b$. Please comment on how realistic is this assumption. I understand this is not the main concern of the current paper, and empirically predictors indeed help. But I think some proper introduction or literature review on the frequency predictor should be included, as this is the major side information for improvement. Minor comment: it might be better to write something like $\\Pi(i)/\\sqrt{b}\\le p_i \\le \\sqrt{b}\\Pi(i)$ which tolerates error in both upper and lower bounds.\n\nIn the theory part, some statements should be more rigorous. In Theorem 1, it is unclear what is a precise meaning of \"with high probability\", and what is the o(1) term with respect to. In Section 2.1, for $N_i> \\Omega(\\log n)$ with high probability, it seems to require $p_i > \\Omega(\\log n/N)$. I think by \"random sample\" this paper refers to a random sample with replacement, so in the last line on page 1, one needs $O(n\\log n)$ samples to see all elements (coupon collector problem).\n\nIn the experiment part, it seems the base parameter $b$ is pretty large for some datasets (like more than 400 for IP). It seems that the proposed algorithm reduces to WY once $b$ is moderately large such that one interval suffices. Please explain the large values of $b$. Also, please specify how do you increment the base parameter $b$ when the interval fails the sanity check. The improvement over WY is not surprising as WY doesn't have access to the extra predictor, but CR seems to completely fail in some cases which deserves further discussions.", "extra_scores": {}, "extra_text": {}}, {"review_id": "CJMuQVzqZoX", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Estimation of the size of the support of a distribution over a discreet domain is a fundamental problem. In the standard setting, this problem is theoretically well-understood with matching upper and lower bounds. The authors assume additional access to a constant approximation of the density function at each point, and then show that this can provably reduces the sample complexity. In particular, they offer matching upper and lower bounds in this setting. While the upper bound is a twist on the existing state-of-the-art method, the lower bound seem to deviate from that. \n\nOne may say that the problem of density estimation is harder than estimating the size of the support of a distribution, and therefore assuming access to such oracle is not natural. However, the authors provide practical evidence that in some cases this is reasonable. In particular, the authors use a learning-based method for estimation of the density function and plug it in as the oracle for their support estimation method. The results are promising, and seem to be more robust than a previous method that assumed access to an accurate pdf oracle.\n\nIt will be quite interesting to discuss the kind of structure that is present in the data sets that allows to improve over the WY method. For example, is it the case that WY method performs poorly compared to the proposed method for light-tails distributions (and not so much for heavy tailed distributions)?\n\nThe paper is well written and the background work is adequately discussed. \n\nFor some reason the submission format does not allow selecting/highlighting text in the pdf file. Please check this.\n  ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper gives a learning-augmented algorithm for estimating the support size of a discrete distribution. The proposed algorithm is evaluated experimentally, showing significant improvements in the estimation accuracy. The reviewers unanimously agreed that the contributions are strong and relevant. I recommend accept.
Decision: Accept (Spotlight)