How Much is Unseen Depends Chiefly on Information About the Seen
Authors: Seongmin Lee
Marcel Boehme
Venue: ICLR 2025 Spotlight (2025)
Keywords: Good-Turing frequency estimation
Multinomial probability estimation
Unseen events
Missing mass
Probability mass
Primary area: learning theory
TL;DR: Given a random sample from an unknown multinomial distribution, we develop a distribution-free methodology to generate a distribution-specific estimator for the proportion of data that belong to classes not observed in the training sample.

Abstract: The *missing mass* refers to the proportion of data points in an *unknown* population of classifier inputs that belong to classes *not* present in the classifier's training data, which is assumed to be a random sample from that unknown population.
We find that *in expectation* the missing mass is entirely determined by the number $f_k$ of classes that *do* appear in the training data the same number of times *and an exponentially decaying error*.
While this is the first precise characterization of the expected missing mass in terms of the sample, the induced estimator suffers from an impractically high variance. However, our theory suggests a large search space of nearly unbiased estimators that can be searched effectively and efficiently. Hence, we cast distribution-free estimation as an optimization problem to find a distribution-specific estimator with a minimized mean-squared error (MSE), given only the sample.
In our experiments, our search algorithm discovers estimators that have a substantially smaller MSE than the state-of-the-art Good-Turing estimator. This holds for over 93\% of runs when there are at least as many samples as classes. Our estimators' MSE is roughly 80\% of the Good-Turing estimator's.

Published as a conference paper at ICLR 2025
How MUCH IS UNSEEN DEPENDS CHIEFLY ON INFORMATION ABOUT THE SEEN
Seongmin Lee and Marcel Böhme
MPI for Security and Privacy, Germany (seongmin lee, marcel. boehme @mp1 -sp. org
ABSTRACT
The missing mass refers to the proportion of data points in an unknown popula- tion of classifier inputs that belong to classes not present in the classifier's training data, which is assumed to be a random sample from that unknown population. We find that in expectation the missing mass is entirely determined by the number fy of classes that do appear in the training data the same number times and exponentially decaying error. While this is the first precise characterization of the expected missing mass in terms of the sample, the induced estimator suf- fers from an impractically high variance. However, our theory suggests large search space of nearly unbiased estimators that can be searched effectively and efficiently. Hence, we cast distribution-Fii estimation as an optimization prob- lem to find distribution-sper speccifc estimator with minimized meen-ssuareed error (MSE), given only the sample. In our experiments, our search algorithm discovers estimators that have a substantially smaller MSE than the state-of-the-ar Good- Turing estimator. This holds for over 93% of runs when there are at least as many samples as classes. Our estimators' MSE is roughly 80% of the Good-Turing estimator's.
INTRODUCTION
How can we extrapolate from properties of the training data to properties of the unseen, underlying distribution of the data? This is fundamental question in machine learning (Orlitsky et al., 2003 Orlitsky& & Suresh, 2015 Painsky 2022 Acharya et al., 2013) Hao & Li 2020). The probability that data point belongs to class that does not exist in the training data is also known as the missing probability mass since empirically the entire probability mass is distributed over classes that do exist in the training data. For instance, the missing mass measures how representative the training data is of the unknown distribution. If the missing mass is high, the training is not very representative, and trained classifier is unlikely to predict the correct class. If we manually label training data, the missing mass also measures safuration. We may decide that the labeling effort has been sufficient and saturation has been reached when the missing mass is below a certain threshold.
1.1 BACKGROUND
Consider a multinomial distribution p = (p1. .P.) over a support set X' where support size S = |x and probability values are unknown. Let X = (..,... ".......),, be set of independent and identically distributed random variables representing the sequence of elements observed in samples from p- n,
Let N₂ be the number of times element æ E &' is observed in the sample X". For k let 4y be the number of elements appearing exactly & times in X" i..i..., N₂ Σ 1(X; = x) and
k Exex 1(N= kt. Let (n) be the expected value of & (Good) 1953), i.e.,
fk(n)
Σ TEX
(1 pm)) pmr)"> F
Estimating rare/unobserved pa- We cannot expect all elements to exist in X", While the empirical estimator Fmp Nz/n is generally unbiased, ,Emp distributes the entire probability mass only

---

Published as a conference paper at ICLR 2025
the observed elements. This leaves "missing probability mass" over the unobserved elements. In particular, pr given that Nr 0 overestimates Pz, i.c., for observed elements
E
Nx
N₂
P2
px)
We notice that the bias increases as par decreases. Bias maximized for the rarest observed element.
Missing mass, realizability, and natural estimation. Good and Turing (GT) (Good) 1953) dis- covered that the expected value of the probability M₁- = EmExPa Pe (Nx, = k) that the (n + 1)-th observation Xx+1 is an element that has been observed exactly & times in X (incl. k = 0) is a func- tion of the expected number of colors fi++1 (n + 1) that will be observed + times in an enlarged sample X Xn+1, i.e, E [M + *+tfs+1 f (n 1). We also call M2 as total probability mass over the elements that have been observed exactly & times. Since our sample X is only of size n, GT suggested to estimate Mg using 4k+11 Concretely, Mi #x+1
For k 0, Mo gives the "missing" " (probability) mass over the elements not in the sample. In genetics and biostatistics, the complement 1 My measures sample coverage, i.e. the proportion of individuals in the population belonging to species not observed in the sample (Chao & Jost 2012). In the context of supervised machine learning, assuming the training data is a random sample, the sample coverage of the training data gives the proportion of all data (seen or unseen) with labels not observed in the training data.
A natural estimator of Pa assigns the same probability to all elements appearing the same number of times in the sample X" (Orlitsky& & Suresh (013). For > 0, f= = Mg/44 gives the hypothetical best natural estimator of pr: for every element that has been observed & times.
Bias of GT. In terms of bias, Juang & Lo 1994) observe that the GT estimator M = k+1 #x+1 is
x
an unbiased estimate M₂(X" ), i.e. where the n-th sample was deleted from X" and find:
E
My = E [M -M(cx")) M
k +
(3)
T +
Convergonc/ooppctiiveessss of GT. McAllester & Schapire (2000) analyzed the convergence,
which is then improved by Drukh & Mansour (2004) and more recently by Painsky 2022). They
showed that, with high probability, ME converges at rate of O(L/ TT) for all k based on worst- case mean squared error analysis. Using the Poisson approximation, Orlitsky & Suresh (2015)
showed that natural estimators from GT, i.e., p MN. N&,,, performs close to the best natural estimator. Regret, the metric of the competitiveness of an estimator against the best natural estimator, is measured as KL divergence between the estimate and the actual distribution p. Dx (Pllp). Their study also showed that finding the best natural estimator for p is same as finding the best estimator for M (M& V7 HM
Poisson approximation. The Poisson approximation with parameter A = Pen has often been used to tackle a major challenge in the formal analysis of the missing mass and natural estimators (Olltskk & Suresh 2015 Orlitsky et al. [2016] Acharya et al. 20133) Efron & Thisted 1976 Valiant & Valiant] 2016;; Good [953] Good & Toulmin 1956 Hao & Li 2020). The challenge is the dependencies between fertweenfrrqueee frequencies N₂ for different elements x E X. In this Poisson Product model, a continuous-time sampling scheme with S |x] independent Poisson distributions is considered where the frequency N² of an element x is represented as a Poisson random variable with mean pan. In other words, the frequencies N₂ are modelled as independent random variables. Consequently, the GT estimator is unbiased in the Poisson Product model (Orlitsky et al.) (2016); yet. it is biased in the multinomial distribution (Juang & Lo 1994). Hence, we tackle the dependencies between frequencies analytically, without approximation via the Poisson Product model.
1.2 CONTRIBUTION OF THE PAPER
In this paper, we reinforce the foundations of multinomial distribution estimation with precise characterization of the dependencies between N₂ = Σi 1(X; 2) across different X (rather than assuming independence using the Poisson approximation). The theoretical analysis is based on the expected value of the frequency of frequencies E [Ø,] (n) between different & and n, which
is
f fn +
( 1)
(4)
(*t1)
(2t1)
2

---

Published as a conference paper at ICLR 2025
Exploring this new theoretical tool, we bring two contributions to the estimation of the total proba- bility mass Mr for any k & k Σ n.. Firstly, we show exactly to what extent E [M&] can be estimated from the sample X and how much remains to be estimated from the underlying distribution p and the number of elements |.]. Specifically, we show the following.
Theorem 1.1.
カー k
(A (x+2)
[M
Σ
(-1)"-
n
(5)
where Ba, = (-) fn+1 (n + 1) the remainder
This decomposition shows that the GT estimator the firs term of E [Mg] using the plug-in estimator 1 for fi (m). Hence, it gives the exact bias of the GT estimator in the multinomial setting (which would incorrectly be identified as unbiased using the Poisson approximation), We discuss bias and variance for the estimator M (7) (-) 0x4s / ((4+)) that is induced by Theorem
Secondly, using our theory, cast the distribution estimation of M₁ as a search problem whose goal is to find distribution-specifi estimator with a minimized MSE. Using the rela- tionship in Eqn. 4 in Theorem 1.1 notice many representations of E [M&] all of which suggest different estimators for E [. We introduce deterministic method to construct unique estimator from representation, and show how to estimate the mean squared error (MSE) for such estima- tor. Equipped with a large search space of representations and a fitness function to estimate the MSE of candidate estimator,
finally define distribution-free free estimation methodology.
We compare the performance of the minimal-bias estimator M and the minimal-MSE estimators discovered by our genetic algorithm to the that of the widely used GT estimator on variety of multi- nomial distributions used for evaluation in previous work. Our results show that 1) the minimal-bin estimator has a substantially smaller bias than the GT estimator by thousands of order of magnitude, 2) Our genetic algorithm can produce estimators with MSE smaller than the GT estimator over 93% of the time when there are at least as many samples as classes; their MSE roughly 80% of the GT estimator. We also publish all data and scripts to reproduce our results.
DEPENDENCIES BETWEEN FREQUENCIES N₂
We propose new, distribution-fred methodology for reasoning about properties of estimators of the missing and total probability masses for multinomial distributions. The main challenge for the statistical analysis of Mr has been reasoning in the presence of dependencies between frequencies N₂ for different elements E X. As discussed in Section [.]] a Poisson approximation with param-
eter A2 = P often used to render these frequencies as independent (Orlitsky & Suresh 2015
Orlitsky et al.] 2016 Acharya et al. 2013 Efron & Thisted 1976 Valiant & Valiant [016]] Good,
1953 Good & Toulmin 1956 Hao Li 2020). In the following, we tackle this challenge by for-
malizing these dependencies between frequencies. Thus, we establish a link between the expected
values of the corresponding total probability masses.
2.1 DEPENDENCY AMONG FREQUENCIES
Recall that the expected value (n) of the number clements & that appear exactly & times in the sample X" is defined (n) Exex (1) (1pp((1 p=>""=k For convencience, let gu (n)) (()
We notice the following relationship among and m::
Sk (n 1) =
Px - pn) nn (1- (1-p2)= =z)== (e+1(n 1)
(6)
a k
(-1) 11)')++)(()) + (-1)m-k+) In+i(n +1)
A distribution- onalysis is free of assumptions about the shape of the probability distribution generating the sample. In this case, we make assumptions about parameters p or n.
3

---

Published as a conference paper at ICLR 2025
We now write the expected value [M&] of the total probability mass in terms of the frequencies with which different elements X' have been observed in the sample X" of size n as follows
R [Ma]
=
Σ
11 k
++1 (1 -Pa)" -==="====
11
(m (m+
=
Σ (-1)
(-1)""ontas(a) outi(a))
+ Ra. (8)
where R (-1) fn+1 (n + 1) is a remainder term. This demonstrates Theorem 1.1
Figure [ iillustrates the relationship between the expected frequency of frequencies fa(()) (n)) the frequency k. and the sample size n. The y- and x-axis represents the sample size и and the frequency k. respectively. As per Eqn. ( for every 2x2 lower triangle matrix, the value of the lower left cell (ox, (n + 1)) is value of the upper left cell (n)) minus the value of the lower right cell (gk+1(n (m+ 1)).
Beaf 2
RV(N)
We can use this visualization to quickly see how to rewrite Is (n) as an alternating sum of values the cells the up- per row, starting from the cell in the same column to the rightmost cell, and adding/subtracting the value of the right- most cell in the current row. For instance, the (13) in the bottom-leftmost red cell in Figure equivalent to the var- ious linear combinations of its surrounding cells: with 9o(12) and gi (13) (blue colored). with go(11), (11),, 94 (13) (purple colored), or with go(11), 91 (11). (13) (green colored).
8y00
MA
10
M
11
1
10
11
12
Figure 1: (n) lower triangle matrix
Missing Mass. The missing probability mass Mn gives the proportion of all possible observations for which the elements E X' have not been observed in x The expected value of Mo is
1 Σ
E Mo] = 91 (n + 1)
(-1)
(n(m)
+ +-11) fx+1
(9)
by Eqn. (8) The values in the second column of Figure [ (k= represents the expected values of missing mass; [Mo] being the cumulative sum of (-1)* (n) is intuitively clear from the figure (the red cell in the row n = 7). It is here where we observe that E [Mo] = gn(n + 1) almost entirely determined by the g- (n), the expected frequencies of frequencies in the sample X", and not by the number of elements ( or their underlying distribution p. In fact, the influence of p in
(e (c'-Rx) -n-1
the remainder term decays exponentially, i.e., fn+1(n + 1) EzEx p < ExEx
which is dominated by the discovery probability of the most abundant element max(p).
Total Mass. Similarly, the expected value of the total probability mass E [M&]] (the red cell in the row 10), which is equal to (Z) (r+ 1), is almost entirely determined by the expected frequencies of the sample x with remainder Ra,k (P) Exex +1
3 A LARGE CLASS OF ESTIMATORS
From the representation of E [Ma]] in terms frequencies in Eqn. 8 and the relationship across frequencies in Eqn. (6) we can that there is large number of representations of the expected total probability mass E [M,]. Each representation might suggest different estimators.
3.1 ESTIMATOR WITH EXPONENTIALLY DECAYING BIAS
We start by defining the minimal bias estimator M from the representation in Eqn. (8 and explore its properties. Let
Ppti
M
(10)
k
A=
4

---

Published as a conference paper at ICLR 2025
Table E [MR}] preserving identites and example representations.
E [M preserving identites
Initial representation Pa
Example representation
ax()) ((1 - (ta(()) + 6n:
for Land
forls + 13++ 0
and
Land
maa (eiti (1)
otherwise.
old
[:0) (0:160 - 6x-1
athawis:
Bias. For some constant & 0 < h < n and some constant с > 1, the bias of M
B is in the order
of c(n"c-"), i.e., | E M Mr] R
(2) ExE p=+1
(8) Exex cp" I
n EEEx c=", where Cæ 1 for all x X' constants.
Variance. The variance of M is given by the variances and covariances of the Ok+s for [1..n aj. Under the certain conditions, the variance of M also decays exponentially in n.
Theorem 3.1. Var (ME)) decreases exponentially with n if pmax 0.5 or (1-Paux)) (m-Pmi)) 1,
Pinas
where Pmax = max Pa and Pmin mingex pr. The proof is postponed to Appendix
Comparison to Good-Turing (GT). The bias of M not only decays exponentially in but is also smaller than that of GT estimator MC by exponential factor. For a simpler variant of GT estimator, M k+1 first term in the expected total probability mass E [ in Equ. (8). we show that its bias is larger by an exponential factor than the absolute bias of A To see this, we provide bounds on the individual sums and then on the bias ratio:
z 9x+1 (suggested in McAllester Schapire (2000)) which corresponds the
E Ma
Mr
2
k+2 Punin
(1
Pauin) )
(11)
k
Biass Biasg
Pmin Spt+3
Pmin m=-
E M Ms
S
Spmtak
(12)
Pmax
where S = 1.28. Noticing that (1 Pmin)/Pmmxx 1 for all distributions over X, except where $ = 2 and p = 0.5), the ratio decays exponentially in n for < n. The same can be shown for the original GT estimator M k+1 Φx+1 for sufficiently large sample size (see Appendix (A]. For instance, the missing mass Mo for the uniform distribution is overestimated by Mi on the average by (S - 11"--1/"" /S" while 2 has a bias of (-1)"/5² /s", which is lower by a factor of 1/(S - 1)"-
While the bias of estimator M is lower than that of My by exponential factor, the variance is higher. The variance of M depends on the variances of and covariances between 4
n n-k Σ 1=1
Var (NT
Var (0++s)
((-1)++ ceey Cov (Deti *x+s), (g1
(13)
where (2) (c+))- In contrast, the variance of MC depends only on the variance of P Later, empirically investigate the bias and the variance of the estimators.
3.2 ESTIMATION WITH MINIMAL MSE AS SEARCH PROBLEM
There are many representations of E [Ma] (2) 0 (n + 1) that can be constructed by recursively rewriting terms according to the dependency among frequencies we identified (cf. Eqn. (6 & D) The representation used to construct notice that the variance of M is too high to be practical.
minimal-bin estimator M one of them. However,
To find a representation from which an estimator with a minimal mean squared error (MSE) can be derived, we cast the estimation of Mj an optimization problem. We first define the search space of representations of [M&] and the filness function to estimate the MSE of a candidate estimator.
Search space. Let E [MM] be represented by suitable choice of coefficients {ais} such that [M+]] Σn E as,39;(i); the search space of our optimization problem is the set of all possible representations of [M₂]- One representation of TR. [M,] (2) (n 1) is ro in Table 1
5

---

Published as a conference paper at ICLR 2025
Different encodings can be used to express the search space. In Markov chain encoding, realize that the four identities (1-4) in the first column of Table T can be recursively applied to the initial representation ro in the second column of Table to explore the search space. For instance, applying identity (1) with 8 = 0.5 and identity (3) to 70. we obtain the representation eı in Table In continuous optimization problem encoding, realize that the coefficients orj must satisfy the following constraints: for v1 5 1,
n+In=1
{ (x) 10
(M
- (14)
where Cij
otherwise.
otherwise,
and any choice of og that satisfy Eqn. 14 is in the search space. Appendix provides proof of how each encoding expresses the search space.
Estimator instantiation. To construct unique estimator My of M2 from a representation r of [. we propose deterministic method. But first, we define our random variables on subsamples of x For any & n, let Na. (m)) be the number of times element E X is observed in the subsample x (X1, ... Xm) of X Let (m) the number of elements appearing exactly & times X" i.e, (m) = Ee ((x; x). (m) Erex (N)(mm) k). Note that N₂ N2(n) and
4 (n). Hence, given representation r, construct Mr as
Mr
200)
+
0g 24
(15)
(1+1)
Notice that 0/03/ /(:) is just the plug-in estimator for gi))).
Fitness function. To define the quantity to optimize, any optimization problem requires fitness (objective) function. Our fitness function takes a candidate representation r and returns an estimate of the MSE of the corresponding estimator Mr. We decompose the MSE as the sum of the squared bias, variances of, and the covariance between M,. and Mi For convenience, let fn+1(n) 0.
MSE(M))
Σ
71 ( +1)
Σ ISiSiS ISiSmSn
Be, Cov (9.(5), (m))
ISiSiSn
(16)
Var (Ms) 2
Br, Gov (#.()) Mc),
ISiSiSn
where B., the coefficient of +,()) in Mr. We expand on the MSE computation Appendix D The resulting estimator Mr minimizing the fitness function provides a estimator with a minimal MSE regarding the arbitrary sample of size from the underlying distribution.
Since the underlying distribution {r=] is unknown, we can only estimate the MSE. For any element that has been observed exactly & > 0 time in the sample X", we use Paz M 4 as natural estimator of pr. where Mr is the GT estimator. To handle unobserved elements (k 0), we first estimate the number of unseen elements E [2o] fo(n) using Chao's nonparamteric species richness estimator fo n-1 &f_ 24g (Chao 1984), and then estimate the probability of each such unseen element as Py = 6 f.s where My the GT estimator. Finally, we plug these estimates into Eqn. (16) to estimate the MSE. It is interesting to note that it is precisely the GT estimator whose MSE our approach supposed to improve upon.
Optimization algorithm. With the required concepts in place, different optimization algorithms can be used to find the representation of [My] that minimizes the MSE the estimator. The per- formance guarantee for the discovered estimator inherently depends the optimization algorithm.
We develop a genetic algorithm (GA) (iicchell 1998) for the optimization problem encoded with the Markov chain encoding. Appendix D provides the GA in detail. Here, we briefly sketch the general procedure. Starting from the initial representation ro in Table T our GA iteratively im- proves population of candidate representations Pg, called individuals. For every generation g. GA selects the m fittest individuals from the previous generation Pz-1- mutates them by randomly applying the E [Mr] preserving identites (1-4) in Table [ and creates the current generation P, by

---

Published as a conference paper at ICLR 2025
adding the Top-r. individuals from the previous generation, i..,, the elitism strategy that guarantees that the best individuals are not lost. The GA repeats this process for the iteration limit G5, and outputs the best evolved estimator F Later, empirically evaluate the performance of the discovered estimator 2 against the GT estimator aig.
Another approach one could use is quadratic programming (Nocedal & Wright 2006) on the con- tinuous optimization problem encoding. The fitness function, Eqn (16), quadratic in the coeffi- cients $. and the constraints, Eqn (14), are linear. Also, the search space is convex as the quadratic term in the fitness function (i.e., the sum of the variance and the square of the expected value of the estimator) is non-negative. By Ye & Tse (189). quadratic programming finds the optimal solution in number of iterations that is polynomial in the sample size n. However, we notice that the fit- ness evaluation is prohibitively high, in the order of Onn") due to the number of covariance terms in Eqn (I6), which makes using quadratic programming less practical for large n. Unlike quadratic programming, we found our GA is more practical for large n as only the variance and covariance terms that are needed to compute the fitness function are computed.
Adapting to a larger sample. The estimator M discovered by the optimization for samples of size n can be converted to an estimator for a sample of arbitrary size m 2 n. Notice that the representation of E. [M&] of the sample of size can be converted to a representation of E [MV]] of a larger sample of size m by multiplying the coefficients a.j by (z)) /()) Especially for the missing mass (k 0), the representation is valid for any sample size 2 without modification. This property can be used to easily derive the missing mass estimator for a larger sample size m > n. Given the coefficients oi, discovered by the optimization for the missing mass of sample X" p, the estimator of the missing mass for any sample XT p is given as
n Σ
n
aij+n-m 2,0)
9:000
+
Σ Oin++1 D (n+t)
(17)
It is worth noting that the adapted estimator from the minimal- estimator for a sample of size to a sample of size m is not necessarily the minimal-MSS estimator for the sample of size m. Yet, it lessens the computational burden of finding the minimal- MSEE estimator for larger sample size and may have a lower MSE (than the GT estimator) if the (relative variance of the) frequencies & similar in the extended sample. We empirically investigate this property in our experiments.
Distribution-free. While our approach itself distribution-free the output is distributionnspeecffe,, i.e., the discovered estimator has a minimal MSE on the specific, unknown distribution.
EXPERIMENT
We design experiments evaluate the performance (i) of our minimal-biaa estimator M and (ii) of our the minimal- -MSE estimator Ev that is discovered by our genetic algorithm against the perfor- mance of the widely-used Good-Turing estimator M (Good 1953).
Distibutions. We use the same six multinomial distributions that are used in previous evalua- tions (Orlitsky & Suresh 2013 Orlitsky et al. 2016) [Hao & Li] 2020): a uniform distribution (uniform), a half-and-half distribution where half of the elements have three times of the proba- bility of the other half (half&half), two Zipf distributions with parameters I and 0.5 (zipf-1, zipf-0.5), and distributions generated by Dirichlet-1 prior and Dirichlet-0.5 prior (diri-1, diri-0.5, re- spectively).
Open Science and Replication. For scrutiny and replicability, we publish all our evaluation scripts at: htttss://gitt
4.1 EVALUATING OUR MINIMAL-BIAN ESTIMATOR
ROL. How does our estimator for the missing mass MB compare to the Good-Turing estimator My in terms of bias as a function of sample size n??
RQ2. How does our estimator for the total mass M, compare to the Good-Turing estimator MC in terms of bias function of frequency k?
RQ3. How do the estimators compare in terms of variance and mean-squared error?
7

---

Published as a conference paper at ICLR 2025
model
GT
uniform half&half
Zip4-1 2004-0.5
dri-1 dir-0.5
Mo
Bias
Var
MSB
our
GT
3.6973c-003 2.3372c-03
2.3508c-03
04-50
Dev03:
ours
1.0000e-200
2.3515c-03
2.3515e-03
1e-04
-2ww03
GT
6.6369e-005 1,1430e-05
1,1434g-05
500
logro
20-04
100
ours
< 1.00e-200
1.1445c-05
1.1445c-05
(a)
GT
4.3607e0007
4,3439c.08
4.3439e.08
1000
2000
5000
7500
10000
1000
1930
2000
ours
< 1.00e-200
4.3441e-08
4.3441e-08
Figure 2: Absolute bias of MD and M6 (a) as function of for k and (b) as a function of for 2000 (S 1000, scale.
Table 2: Bias, variance, and MSE of M6 and Mg for three values n. (uniform, S 100). More results are in Appendix
We focus specifically on the bias of ME. i.e., the average difference between the estimate and the expected value E [Max. We expect that the bias of the missing mass estimate M as function of n across different distributions provides empirical insight for our claim that how much is unseen chiefly depends on information about the seen.
RQ.1. Figure aa illustrates how fast our estimator M and the baseline estimator M (GT) ap- proach the expected missing mass E [AMo] function of sample size As it might difficult for the reader to discern differences across distributions for the baseline estimator, we refer to Appenddi F where we zoom into relevant region. The magnitude of our estimator's bias is significantly smaller than the magnitude of GT's bias for all distributions (by thousands of orders of magnitude). Fig- ure 2[a) also nicely illustrates the exponential decay of our estimator in terms of and how our estimator is less biased than GT by an exponential factor.
In terms of distributions, closer look the performance differences confirms suspicion that the bias of our estimator is strongly influenced by the probability Pmax of the most abun- dant element. In fact, by Eqn. (12) the absolute bias of our estimator minimized when pmax is minimized. If we ranked the distributions by values of Pmax with the smallest value first (uniform, half&half, zipf-0.5, zipf-1), we would arrive at the same ordering in terms of performance of our estimator as shown in Figure 2().. Similar observations can be made for GT, but the ordering different (check Appendix FD.
RQ2. Figure 2)c) illustrates for both estimators of the total mass Mj how the bias behaves as k varies between 0 and n = 2000 when = 1000. The trend is clear; the bias of our estimator strictly smaller than the bias of GT for all &s and all the distributions. The difference is the most significant for rare elements (small k) and gets smaller as & increases. The bias of our estimator is maximized when & = 1000 = 0.5n, the bias for GT when k 0.
RQ3. Table 2 shows variance and MSE of both estimators for the missing mass Mo for the uniform and three values of As GT. The reason is that the MSE is dominated by the variance. We make the same observation for all other distributions (see Appendix F. The MSES of both estimators are comparable.
see, the MSE of our estimator is approximately the same as that of
4.2 EVALUATING OUR ESTIMATOR DISCOVERY ALGORITHM
RQ1 (Effectiveness). How does our estimator for the missing mass M:. compare to the Good-
Turing estimator M in terms of MSE
RQ2 (Efficiency). How long does take for our GA generate estimator M
RQ3 (Larger Sample). How does Meo generated from sample of size n perform on sample of size m > n??
RQ4 (Distibutionnawareness) How well does an estimator discovered from a sample from one distribution perform another distribution in terms of MSE?
RQS (Empirical Application) How does our estimator perform in a real-world application?
"diri-1 and diri-0.5 are not considered because multiple distributions are sampled from the Dirichlet prior.
We also considered more recent related work that can be considered to estimate the missing mass (Painsky
2023
Valiant & Valiant 2017 Wu Yang. 2019; the results in Appendix G
8

---

Published as a conference paper at ICLR 2025
Table 3: The MSE of the best evolved estimator M and GT estimator My for the missing mass Mo. the success rate A12, and the ratio (Ratio, MSE (0 / for three sample sizes and six distributions with support size S = 100.
Dis.
MSSLM (()))
22 8/2
Ag2
Ratio
MSK(M)))
MSR(M
20
(M)
A12
Ratio
MSR (15)
MSR(MM)
1 25
A12
Ratio
uniform
1. 1.09e-02
7.94e-03
0.88
72%
6.05e-03
4.29e.033
0.97
70%
1.93e-03
1.73e-03
0.96
89%
halt&half
1. 1.14c-02
7.16c-03
0.90
63%
5,46e-05
4.07c-03
0.98
74%
1.57c-03
1.42c-03
0.93
90%
zipt-1
8.09e-03
7.37e-03
91%
3.42e-03
3.4e-13
0.89
88%
1.26e-03
1.08c-03
0.94
855
z.p--..5
I 008c-02
8.13c-03
0.91
75%
5.23-005
4.16c-05
0.96
79%
1.73c-03
1.5c-033
0.97
88%
dir-1
1.10e-02
7.97e-03
0.92
72%
4.36c-03
3.47o.03
0.92
79%
1.23c-03
1.05-033
0.91
85%
dir-0.5
9.90c-03
8.02c-03
0.87
81%
3.470-03
2.86o-03
0.88
82%
9.41c-04
8.08c-04
0.86
85%
Avg.
0.89
76%
0.93
79%
0.93
87%
cm 5
10
1--2
Dist.
Ratio
p < .05
Ratio
p. .05
Ratio
p .05
1.2
Evolved from
uniform
1.00
False
1.00
False
0.99
True
1.0
uniform
halr@half
half&half
0.95
True
0.96
True
0.98
True
zipf-0.5
0.97
True
01.88
True
0.99
Thue
zip+3
zipf-1
0.93
True
0.95
True
0.97
True
0.6
diri-1
0.91
True
0.93
True
0.95
True
diri-0.5
0.93
True
0.95
True 0.96
Thue
0.4
Table 4: The MSE comparison for the missing mass
uniform
half&half 2ip4-0.5
zipf-1
Mo (S = 100, n = 100) for extended samples [2, 5, 10)) between the GT estimator Me and the adapted estimator from the evolved estima- tor ME for X". 'Ratio' is the ratio of the MSE (MSE(M) M M/SS and 'p < .05' is the re- sult of the (one-sided) Wilcoxon signed -ank test.
Target distribution
(c x
Figure 3: The MSE of an estimator discov- ered using sample (S,n 100, 200) from one distribution (individual boxes) applied another target distribution (box clusters).
To handle the randomness our evaluation, we repeat each experiment we repeat the experiments 100 times, i.e., we take 100 different samples X of size n. More details about our experimental setup can be found in Appendix E
RQ.1 (Effectiveness). Table 3 shows average MSE of the estimator M discovered by our genetic algorithm and that of the GT estimator M/ for the missing mass My across three sample sizes. We measure effect size using Vurgha-Delaney A12 (Vargha & Delaney, 2000) (success rate), i.e., the probability that the MSE of the estimator discovered by our genetic algorithm has a smaller MSE measure the MSE of our estimator
than the GT estimator (larger is better). Moreover, proprtion of the MSE of GT, called ratio (smaller is better). Results for other S is in Appendix
Overall, the estimator discovered by our GA performs significantly better than GT estimator in terms of MSE (avg. A12 > 0.89; ratio < 87%). The performance difference increases with sample size n. When the sample size is twice the support size (n 25), in 93% of runs discovered estimator performs better. The average MSE of our estimator is somewhere between 76% and 87% of the MSE of GT. The high success rate and the low ratio of the MSE shows that the GA is effective in finding the estimator with the minimal MSE for the missing mass Mo. A Wilcoxon signed-rank test shows that all performance differences are statistically sigmificant at a < 1 In terms of distributions, the performance of our estimator is similar across all distributions, showing the generality of our algorithm. The worst performance is for the zipf-1 distribution, though it is still 85-91% % of the GT estimator's s MSE. The potential reason for this is due to the overfitting to the approximated distribution fa. Since the zipf-1 is the most skewed distribution, there are more elements unseen in the sample than in other distributions, which makes the approximated distribution P. less accurate.
RQ.2 (Efffciencyy. The time GA takes reasonable; to compute an estimator in Table 3, it takes 57.2 72 average (median: 45.3s). The average time per iteration is 0.19s (median: 0.1
RQ.3 (Larger Sample). Table shows how the estimator M55 that is discovered for a given sample
X" of size performs on an extended larger sample = (c {2, 5, 10}) by adapting the coefficients
as,y for the larger sample as described in Eqn. (17) To evaluate the performance, we sample x en- additional samples from the same distribution and compute the missing mass My for the extended sample x using the adapted estimator as well as the GT estimator M the entire process is repeated 10K times to calculate the MSE The results show that the adapted estimator performs

---

Published as a conference paper at ICLR 2025
better than the GT estimator for most distributions and sample sizes. The ratio of the MSE is between 0.91 and 1. 1.00, indicating that the adapted estimator performs better than the GT estimator the evolved estimator for the original sample X", as they are not genuinely
but not much designed for the larger sample. The performance of the adapted estimator degraded for the uniform distribution. The possible reason is that because unitorm has, technically, to find the unscen/rarely seen classes in the extended sample, making the relative variance between frequencies of frequencies (+) differ a lot from the original sample. For instance, when the variance of the number of singletons Var (#1 (100)) (se 23.37) is much larger than the variance of the number of doubletons Var (92 (100)) (<x 11.63) for the uniform distribution. However, the order already reverses when n 200 (Var (01 (200)) x 16.04 < Var (#2()00)) x 19.84), which becomes more significant when n = 1000 (Var (01 (1000)) x 0.043 < Var ($2(2000)) = 0.216).
rare classes, it easier
100,
RQ.4 (Distribution-wvareness)) Figure shows the performance of an estimator discovered from a sample from one distribution (source) when applied to another distribution (target). Applying an estimate from the zipf-1 on the zipf-1 gives the optimal MSE (right-most red box). However, applying an estimator from the zipf-1 on the uniform (left red box) yields a huge increase in variance. In terms of effect size, measure Vargha Delaney A12 > 0.95 between the "home" and "away" estimator. While the uniform also shows that the home estimator performs best on the home distribution (A12 = 0.61 (small)), the difference between the estimators from uniform, haff&half, and zipf-0.5 0.5 is less significant. Perhaps unsurprisingly, an estimator performs optimal when the source of the samples similar to the target distribution.
RQ.5 (Empirical Application). We briefly demonstrate the performance of our estimator in two real-world applications. We first use the Australian population-data-by
dataset (Arrvidsoon) 2023). S = 104) to estimate Mo for = 50 random data points. The ground truth Mo is 0.476. The GT estimator Mgg estimates My as [0.322, 0.638] with a 95% confidence interval (CI) demonstrating a huge variance. In contrast, our estimator Mi estimates My as [0.409, 0.565] (95%-C) demon- strating only 25% of the MSE of GT. We also apply our method to the Shakespeare dataset (Sha) (S = 995, |atatset| = 111, 196), commonly used in the literature (Efron & Thisted 1976), fo- cusing on missing mass for player frequency. For n = (100, 200, 500), the MSE of our estimator is (3.0x10 1x100 1,110118888800 8.8x10 1) compared to the GT estimator with (4.2x10 33, 2.6x100- 9.0x10 4)
respectively, showing that our method consistently outperforms the Good-Turie Turing estimator across all sample sizes. The result shows that approach lead substantial and significant decrease of the MSE in the real-world application.
Summary. To summarize, our GA is effective in finding the estimator with the minimal MSE for the missing mass Mo with the smaller MSE than GT estimator 16 for all distributions and sample sizes. The effect is substantial and significant and the average decrease of the MSE is roughly one fifth against GT estimator Mi We report results of additional experimental results, including the variance of the GA and probability mass estimation (k: > 0), in Appendix F & G
5 DISCUSSION
Beyond the General Estimator. In this study, we propose "meta" estimation methodology that can be applied to a set of samples from a specific unknown distribution. The conventional approach is to develop an estimator for arbitrary distribution. Yet, each distribution has its characteristics, and, because of that, the "shape" of the (frequencies of) frequencies of the classes in the sample differs across distributions (e.g., between the uniform and the Zipf distribution). In contrast to the conventional approach, we propose a distribution-free methodology to discover the distribution- specific estimator with low MSE (given only the sample). Note that, while we use the genetic algorithm to discover the estimator, any optimization method can be used to discover the estimator, for instance, a constrained optimization solver.
Estimating the probability to discover a new species if the sample was enlarged by one is a well-known problem many scientific fields, such as ecology, linguistics, and machine learning, and software testing (Lee et al., 2025 Liyanage et al. Lee & Böhme 2023) Böhme 2022
Extrapolation.
2018 Böhme et al.] [202]. Given a sample of size n, what is the expected number TE (t) of new species discovered if & times more samples were taken (E [U)))
fn(n) fo(n ntt) Good &
Toulmin (1956) proposed a seminal estimator based on Ly. Using the Poisson approximation, this
estimator has been improved in several ways (Hao & Li 2020). We believe that our analysis can be
extended to the moodm-Tolmin estimator seeking more accurate estimators for (t).
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank the anonymous reviewers for their valuable feedback. This work is partially funded by the European Union. The views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union the granting authority can be held responsible for them. This work is supported by ERC grant (Project AT SCALE, 101179366). This work is also par- tially funded by the Deutsche Torschungsgemeinschaft (DFG, German Research Foundation) under Germany's 's Excellence strategy EXC2092 Project #390781972.
REFERENCES
Shakespeare plays.
URL
phakss
Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Optimal probabil- ity estimation with applications to prediction and classification. In Shai Steinwart (eds.). Proceedings of the 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pp. 764-796, Princeton, NJ, USA, 12-14 Jun 2013. PMLR.
and Ingo
Joakim Arvidsson. 2023.
Australian population data by region (ce by 4.0), August URL https://ww// kaggla e. com da dawadaaatttseeeeeeeeeee (ww.sastttsssbbbcccccptaaaalalll
aust ra iaiinnn-poon popu at don-data -on--ata-b---eeee rew.-regioo onl (CC BY 4.0).
Marcel Böhme. STADS: Software testing as species discovery. ACM Transactions on Software Engineering and Methodology, 27(2) June 2018. doi: 10.1145/3210309
Marcel Böhme.
Statistical reasoning about programs. In Proceedings the ACM/IEEE 44th Inter- national Conference on Software Engineering: New Ideas and Emerging Results, ICSE-NIER '22, pp. 76-80, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450392242.
doi: 10.1145/311045533127966
URL /tttp:://dc..oo 10.11/.115/1
3510455. 3512796
Marcel Böhme, Danushka Liyanage, and Valentin Wüstholz. Estimating residual risk greybox fuzzing. ESEC/FSE 2021, pp. 230-241, New York, NY. USA, 2021. Association for Computing Machinery. ISBN 9781 4784450385 doi: 10.1145/3468264.34000 3468577.. URL httpss://ol..
org/10
3468570
Anne Chao. Nonparametric estimation of the number of classes in population. Scandinavian Journal of statistics, pp. 265-270, 1984.
Anne Chao and Lou Jost. Coverage-based rarefaction and extrapolation: standardizing samples by completeness rather than size. Ecology, 93 12:2533 47, 2012.
Evgeny Drukh and Yishay Mansour. Concentration bounds for unigrams language model. In John Shawe-Taylor and Yoram Singer (eds.), Learning Theory, pp. 170-185, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. ISBN 978-3-540-27819-11
Bradley Efron and Ronald Thisted. Estimating the number of unsen species: How many words did shakespeare know? Biometrika, 63(3):435 447, 1976. ISSN 00063444. URL http::/wwer
J. Good and G. H. Toulmin. The number of new species, and the increase in population coverage, when sample is increased. Biometrika, 43(1/2):45-633 1956. ISSN 00063444. URL http:
// www..wwkk jstor /tt.......o///ttaaee/333333
Irving Good. The population frequencies of species and the estimation of population parameters. Biometrika, 40(3-4):237-266 1953.
11

---

Published as a conference paper at ICLR 2025
Yi Hao and Ping Li. Optimal prediction of the number of unseen species with multiplic- ity. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 8553-8564 Curran Asso- ciates, Inc., 2020. URL 7177000a9711bb6660001000
neuripe ps. cc/ cc./paper/222//111e. pdf]
Biing-Hwang Juang and SH Lo. On the bias of the turing-good estimate of probabilities. IEEE Transactions on signal processing, 2(42):496-499) 1994.
Seongmin Lee and Marcel Böhme. Statistical reachability analysis. In Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2023, pp. 326-337, New York, NY, USA, 2023. Association for doi: 10.1 145/361 143.36 6266.. URL. https:
Computing Machinery. ISBN 9798400703270.
//doi.org//1 1145/ 36 3011//61134333 1ew.:111111..6166611111111111111
Seongmin Lee, Shreyas Minocha, and Marcel Böhme. Accounting for Missing Events in Statistical Information Leakage Analysis In 2025 IEEE/ACM 47th International Conference on Software Engineering (ICSE), pp. 217-228, Los Alamitos, CA, USA, May 2025. IEEE Computer Soci- URL /tI.http:://// //otps:://oi.. eeecompttersccc ety.
ety. doi: 10. 109/111E55337 202. 200200008.. org/ 1TTp:/101111000/C5555505
00011
Danushka Liyanage, Seongmin Lee, Chakkrit Tantithamthavom, and Marcel Böhme. Extrapolating Coverage Rate in Greybox Fuzzing. In Proceedings of the IEEE/ACM 46th International Confer- ence on Software Engineering, ICSE '24, pp. 1-12. Association for Computing Machinery. ISBN 9798400702174. doi: 10.1 145/35975033366999
URL https: / /dll acm. org www./org/ooooo..oooooo..oo..oooo /10.
1145/3597503 36391
David McAllester and Robert E. Schapire. On the convergence rate of good-Turing estimators. In Proceedings of the 13th Anmual Conference Computational Learning Theory, pp. 1-6. Morgan Kaufmann, San Francisco, 2000.
Melanie Mitchell. An introduction to genetic algorithms. MIT press, 1998.
Jorge Nocedal and Stephen J. Wright. Numerical Optimization, volume XXII, 664 of Springer Series in Operations Research and Financial Engineering. Springer New York, NY, edition, 2006. ISBN 978-0-387-40065-5 doi: 10.10079978---38744006----
Alon Orlitsky and Ananda Theertha Suresh. Competitive distribution estimation: Why is good-turing good. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Asso- ciates, Inc., 2015. URL https: htttps://prroeeedingg www.eeeewddd......e.eeeeeeee http://ww.................opoppa d759175de htw.:e/eaebbaaaaeeeee55555555999 Paper .dff
Alon Orlitsky, Narayana P. Santhanam, and Junan Zhang. Always good turing: Asymptotically op-
timal probability estimation. Science, 302(5644):427-431, 2003, doi: 10. htl.1////ccccc..0555
Alon Orlitsky, Ananda Theertha Suresh, and Yihong Wu. Optimal prediction of the number of un- species. Proceedings of the National Academy of (14 10.1073/pnas. 1607774113. 1tt.///maa..07771111.3 URL httt:::/www.ppss..rrr///////////
2016. doi: pnas.
1607774113
Amichai Painsky. Convergence guarantees for the good-turing est.iatto Journal of Machine Learn- ing Research, 23(279):1-37, 2022. URL http://mm...oo//ppppprss
html
Amichai Painsky. Generalized Good-Turing Improves Missing Mass Estimation. Journal of the American Statistical Association, 1 118554)):1890-1888 190--899, July 2023. ISSN 0162-1459, doi: 10. 1080/01621459, 00055922021222 20211200.65.....
Gregory Valiant and Paul Valiant. Instance optimal learning of discrete distributions. In Proceedings of the Forty-Eighth Annual ACM Symposium Theory of Computing, STOC '16, pp. 142-155, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341325. 10.1 10.1145/2897518. 28976411 URL htR.https:/// //doi wtt.:/...g/11000......11.11..... http://11.111/99999511 288777111188871111111
doi:
12

---

Published as a conference paper at ICLR 2025
Gregory Valiant and Paul Valiant. Estimating the Unseen: Improved Estimators for Entropy and Other Properties. J. ACM, 64(6), October 2017. ISSN 0004-5411. doi: 10.1145/3125633.
András Vargha and Harold D Delaney. A critique and improvement of the cl common language effect size statistics of megraw and wong. Journal of Educational and Behavioral Statistics, 25
(2):101-132, 2000.
Yihong Wu and Pengkun Yang. CHEBYSHEV POLYNOMIALS, MOMENT MATCHING, AND OPTIMAL ESTIMATION OF UNSEEN. The Annals of Statisties, 47(2) 857-883 2019. ISSN 00905364, 21688966.
Yinyu Ye and Edison Tse. An extension of karmarkar's projective algorithm for convex quadratic programming. Mathematical Programming, 44(1):157-179, 1989. doi: 10.1007/BF01587088
URL http::///ool..rrr/000000/////212
13

---

Published as a conference paper at ICLR 2025
A COMPARING THE BIAS OF THE ESTIMATORS
In Section 3.1 we have shown that the bias of simpler variant of GT, M k+t =- 2++1 is larger by an exponential factor than the absolute bias our minimal bias estimator Aig. this section, show that the bias of the original GT estimator My k+1 Φ8+1 is also larger by an exponential factor than the absolute bias of M for sufficienlly larger sample size, Recall that
Biaser R [ Mr]
+ k
fh- (n)
10 gk (n+ 11+1)=
Σ 2("
Pr 2
pa)) ) (18)
and
Biasc
=E ME Me
2k+2 (n +1)
k(k 1) n(n k)
(n)
(19)
to
n
2
9h 1
(20)
lo
k
Σ
Pr
1++
(1 px) n 1-1
k
Pr
1
(21)
Pr
k+2 (1 pz)
pr)
n k-1
(22)
k
Pa
k
Biase
(23)
Pmax
where
when n is sufficiently large. Above inequality leads to the following:
R-Pmii
Biasc Biasg'
k
Bias B Biase
k++2 Spmax k+2 p min
1 Pmii
-n+h+1
1
while
(24)
Pmax
Pmax
which proves our claim.
B BOUNDING THE VARIANCE OF ME
The variance of the linear combination of random variables given by
Var Σ E
Σ of (Xt) + Σ CgeCoov (X,,
(25)
Therefore, the variance and the covariance of (n)s are the missing pieces to compute the variance of M
Theorem B.1. Given the multinomial distribution p = (pi....,Ps) with support size S. the variance of o; *n(n) from samples X"h is given by
Var (2)(1)) [f((n)-f((n)) -f(n))2 + Em 20(n-2 (f((n) - f((n)2
al 2 n-2 if S n.
(26)
otherwise.
14

---

Published as a conference paper at ICLR 2025
Proof.
(1t)
E [2,]
(27)
27
Σ 1 =
IE
(28)
E
Σ 1 (Nx 1) Σ
I(N =iN==iAM =
(29)
ml [i(()) + Enpy JPMn Jin- Poppy (1
py)"- if m
(30)
(f((n)
otherwise.
[((())
Enty JP(n mz 2: pr py) 1z(11² if
A. (2t)
(31)
fi(()) fi(n)²
otherwise.
Now compute the upper bound of the variance of M Lemma B.2.
S Sfi(n) -i(n)² [s(n)) f((1))
2f S n. otherwise.
Var (Φ,)
(32)
Proof. From Theorem B.I
E
[s(1)) E
Σ 1(Nr Ni = ma
(33)
S fi(n) + (S 1)T
IN(N= -1)
(34)
S{((n)
(if 2i n).
(35)
(36)
The lemma directly follows from the above inequality.
Lemma B.3.
(n) < S 9mn Omaxx
where S = |2% Pmax maX Pa, Amin PPmin' and Ornax
Punax Pmax
Proof. T-m and a are increasing functions for (0, Therefore,
-n
(i(n) Σ pú(l -
Ba(1-pa)--E p=)= Σ
Pe
I |2
B Omax
Pr
Pr
Theorem B.4. The variance of the estimator MB is bounded as follows:
Var(Mr S
2k+1
C2
where ej S. (E)2t. 02 min I Piiin Pmnasl I -aaia) ) In other words, Var( 2k+1
Praax
b max(1, (finx))
15

---

Published as a conference paper at ICLR 2025
Proof. From Lemma B.2 in the supplementary, we have Var( (ar(#)) {{{(m)) f1(n)² Thus,
Pk+ti (++)
Sfk+i(n) fn+e(n)2
Dk+i(n)
52 8
k+i Omax
Var
(by Lemma B.3
(x41))
k+D (+1
(37)
enn2
11
k
Var
#btt (k+t)
S S
k
k+i max
53
k+i max
S 5
(en(k i)
1i2
Omax
k+i
k+i
(38)
n2
en 2h
S m
OM
3
O
where Oas max((n (mmax: mmax);
k2
1:
(39)
2
nー
4 x-+1
Var(Me)
=
Var
Σ
(-1 1)-
(40)
1:
(++1)
I (n
k)
Var
(41)
k
12 (6-1)
S S(n k)
A Om ((+2+11) g Om:
(42)
where equation 41 follows from -Shwwazz inequality (Var j-= X₁) M ΣØ= Var (X;)
The proof follows from dividing the variance of the estimator into two cases: Omax < 1 and Omax > 1: If Omax < 1, Om omax. and Var(M) O(n 2k+ 1 (mm) Var(M) On 28+1g g-n min omax).
If Omax > 1, OM Omax and,
Therefore, the variance exponentially decreases with n if pmax < 0.5 or
1 Pmax
< 1.
Pmaxx ( Panin))
Corollary B.5. There exists constant 1 such that
MSE(M S O(n
2k+1 ")
Proof. From Equ. 12 in the manuscript, the bias B(ME)) - M&l S S Pmax n² pmax.. The proof follows from the fact that MSE Var + Bias and the bound of the variance and the bias.
C CONSTRAINTS FOR THE COEFFICIENTS OF THE E [M&] REPRESENTATIONS IN THE SEARCH SPACE
n++ ai.5((() = E[MA] In this section, we proof that any coefficients ogj such that E Zy=
k+1 #t + 1) (2) + 1) should satisfy the following constraints:
m+nn=1
( 0
if = k +1 where otj
(7 0
if foskK-isntI-) (43) otherwise,
ΣΣ aijos
otherwise.
and vice versa.
Proof. Assume the coefficients (as.hhsisisnt] of the representation r >atisfy E E a13)9(i) [Ma]- The proof starts by recursively applying the identity 9.0i) = + 041 + 1) the linear combination of the coefficients from j to transmiting the coefficients to the downward (to the direction of increasing n) until all the coefficients 9i( where j S n become zero. The resulting coefficients r' = (oish the following linear combination of the coefficients of r:
n+1
a = jf < n, otherwise,
(44)
>=
16

---

Published as a conference paper at ICLR 2025
where ct,j is defined as in Equ. (43 This is because ay the coefficient of gv gr in is transmitted to aiy n-- the coefficient of ( 1) i as many times as the number of propagation paths from grr("") to ge (n + 1) through the identity gi(t) gi(i + 1) + 9i+1(i + 1). Everytime the coefficient transmitted, the coefficient moves either to the down (k increases by 1) or to the down and right (both n and increase by 1) in the 2x2 matrix. Therefore, the number of propagation paths from (J') to (:(n-1) 1) is equal to (x+1>") choosing i i- times to change & from i' to among n h++11 111 steps.
( 0
i and j n otherwise.
TO Dijj
The resulting coefficients of r' from is in fact the same as the coefficients of the initial rep- resentation ro due to the following reason: the final sum of the coefficients of r' becomes ΣxEl 1k,n+19kn + 1) = [M]]]] (x) + 1). This is true for any set of probabilities (pI....,PP) and n. Since, Bernstein basis polynomial of degree n + 1, for the vector space of polynomials of degree at most 1 with real coefficients, the only possible coefficients of the E [M&] representations where all the coefficients 9:()) where S become zero is the same as the coefficients of the for any set of probabilities (p.....,Ps) and due to the linear independence of the basis. Therefore, the constraints in Equ. are necessary for the coefficients of the [M&] representations in the search space.
pp)" for 0 S S forms the basis, i.e., the (n + 2)
Next, we show that any representation that satisfies the constraints in Equ. (43 is a valid repre- sentation of the E [Mg]- The proof is straightforward by reversing the above process. The sequence of identities from the above process to reach is reversible to reach from ru- Therefore, the constraints in Equ. (43) are both necessary and sufficient for the coefficients of the E [M&] represen- tations in the search space.
Following the above proof, any representation of the E [M&)] that is driven by the four identities,
oij . (s) o41 ((1 g) (i) 8g (i)
anj [9 + 1) + 9++ 1)) 0nj (9r() 1) 9i)(
o4. (9i-( - 1) 1())
from the initial representation ro satisfies the constraints in Equ. (43 and a valid representation of m1+1
the E [Ma], i.., Ei1 Ejz (1) = E [M&], and vice versa.
D COMPUTING THE VARIANCE AND THE MSE OF THE EVOLVED ESTIMATORS
The remaining part to compute the MSE of the evolved estimator AE is 1) the variance of the missing mass Mg. 2) the variance of the evolved estimator M and 3) the covariance between the evolved estimator Evo and the missing mass Mg.
D.I VARIANCE OF M₁
Var (M²) Var Σ (NooNN
(45)
Σ Var (1(Na = =k)) + Σ
PaPp Cov (1(Ns = k), 1(N, = k))
(46)
Var (1(Ng k)) = E (NVz = x)² - E[1(NN
b)j² = E[1 = E E = 1
(47)
n
ps (1 pr) p
n 1:
1z (1 - pm) p
(48)
k
17

---

Published as a conference paper at ICLR 2025
Cov (1 k), (NVg k))
= [ - b)](NNg = -a--[[[N=Bh)juut = k]]
BB( 229:--2-2E P2 1.-PP -Py) n- (2) p -P=)" -1)))))) if 2 2k.
n!.
(2x vE(11 p pyy)
otherwise.
D.2 VARIANCE OF THE EVOLVED ESTIMATOR
Same as Me the evolved estimators from the genetic algorithm are also linear combinations of 2y (n)s (while varying both & and unlike M Given the evolved estimator M >e c (m:), the expected value of M is given by substituting (x(n) with (ix(:):
B(M E Σ ((
(49)
Given the multinomial distribution p. the covariance between (n) and @g (n'), which is needed to compute the variance of 11 as Equ. 25) can be computed as follows:
Theorem D.1. Given the multinomial distribution be the set of Deotal samples from Let X and x" be the first n and n' samples from Nhstas respectively; WLOG, assume v'' I Teeotal- Then, the covariance of (b((n) (x()))
(Ps)...,PP) with support size S, let N
and 23 (n') 2x (1 & n, 1 k' S n') is given by following:
Cov (P (n) (1')) - fk(()) Sx-(n')
(50)
Σ 1(N= = -k)) (IuV==K')) Sac(n) - Se((n))
=E
(51)
ΣΣ I
E [1(NZ = -KAN k\) fa(n)) fwe(n'),
(52)
where N' 2² is the number of occurrences of at x"' Depending on the values of n, n', ki M, and
x', the T. (N = =k A N' x' = =])] can be computed Table 5
Table [I k KAN k3) for Cov (*x(n), (x)())
Va,nl
Va,a' st.
E[INN =AAN
x=x /
k- V
==n
(infoarsibee)
R+ 1/
k+ H >m
(infeasible))
Grink (1 pa) 12 22)o
K pe)
/
Mst
(infosstble)
in
p-- pv) in
x
(ngfeasible)
Proof.
The proof is straightforward from the definition of Nz and N'
D.3 COVARIANCE BETWEEN THE EVOLVED ESTIMATOR AND THE MISSING MASS
Note that Cov (E,,) = E; Covov (Xi, Y) for any random variables X; and Y. Therefore, the covariance between the evolved estimator Mr Evo = E, ci (14) and the missing mass M, is given by Cov (M M12 Σ, Cov (#h, (n4), Mr). Then, again, dx (n4) = Σ, 1(N% kj), where N₂ is the number of occurrences of in X and Mj E, PNN k). Therefore, the covariance be computed given Cov (1(N4 ka), I(N, k)). Cov (I(N2 ki), 1Ny k))
18

---

Published as a conference paper at ICLR 2025
E [122 = ky ^ N2 +)] E [1 k.] [ k)], where the first term is already computed and the second term (x)) p=)" m. (1-py)"~*;
Table 5
Having all the necessary components, the MSE the evolved estimator 2 naturally follows.
E DETAILS OF THE GENETIC ALGORITHM
Algorithm Genetic Algorithm
Input: Target frequency k, Sample X", Iteration limit G, mutant size me
1: Population Po = {mo)
Fitness prest = fo = fitness(ro)
3: Limit Ct. =
4: for from 1 to Cr. do
5: P selec[TopM
P' lapply( P. mutate)
7:
P. P' U {rot selecTTopM
8:
fa min(lapply(Pp, (p.tpess)
9:
(g = GL) (Ua fo) (feet 0.95 fo))
then
10:
G2 GL+G
11:
frem = pm
12: Estimator M Fvo
= instantiate (PPac
Output: Minimal-Mei -SE Estimator M
Evo
[egorithm[showw the general procedure of the genetic algorithm (GA) for discovering the estimator MfT00 with minimal MSE for the probability mass M2. Given target frequency (incl. 0), the sample X", an iteration limit G, and the number m of candidate representations to be mutated in every iteration, the algorithm produces an estimator Mev with minimal MSE. Starting from the initial representation ro (Eqn. I Line 1), our GA iteratively improves a population of candidate representations py. called indivicuals. For every generation g (Line 4), our GA selects the m fittest individuals from the previous generation P (Line 5), mutates them (Line 6), and creates the current generation Py by adding the initial representation ro and the Top-3 individuals from the previous generation (Line 7). The initial and previous Top-3 individuals are added to mitigate the risk convergence to local optimum. To mutate a representation r, our GA (i) chooses a random term (ii) applies the first identity in Sec. C where 8 is chosen uniformly at random, (iii) applies one the rest of the identities, and (iv) adjusts the coefficients for the resulting representation r' accordingly. The iteration limit Gz is increased if the current individuals do not improve the initial individual ro or substantially improve on those discovered recently (Line 9-12).
E. HYPERPARAMETERS
For evaluating Algorithm I we use the following hyperparameters:
Same as the Orlitsky's study (Orlitsky & Suresh 2015). which assess the performance of the Good-Turing estimator, we use the hybrid estimator ý of the empirical estimate and the Good- Turing estimate to approximate the underlying distribution {p=)aex for estimating the MSE of the evolved estimator. The hybrid estimator ý is defined as follows: If N₂ = k,
if < 4k+1
Pr
MC dh
(53)
c-
otherwise,
where is normalization constant such that EzEx P. 1.
The number of generations G 100. To avoid the algorithm from converging to local minimum, we limit the maximum number of generations to be 2000.
The mutant size m 40.
tournament selection with tournament size / = 3, i.c., we randomly choose three individuals with replacement and select the best one, and repeat this process times.
When selecting the individuals for the mutation,
19

---

Published as a conference paper at ICLR 2025
When choosing the top three individuals when constructing the next generation, use elitist selection, ie., choosing the top three individuals with the smallest fitness values.
To avoid the estimator from being too complex, we limit the maximum number terms in estimator to be 20.
The actual script implementing Algorithm I can be found at the publically available repository https: /taps:///ithhb http:///iooooeeeeee//eeeees...a.
F ADDITIONAL EXPERIMENTAL RESULTS
-3+000
0e+00
48+00
1og10 lbiasl
10 lbiasl
-18+04
5e+00
-2e+04
-6+000
(a)
(b)
-78+00
-3e404
2500
5000
7500
10000
2500
5000
7500
10000
n
0e+00
esti
model
1og1o lbiasl
-2e+03
GT
uniform
our
half&half
-4e+03
zipf-1
(c)
zipf-0.5
diri-1
-6e+03
diri-0.5
500
1000
1500
2000
k
Figure 4: Absolute bias of Mnf and 2i (a.b) as a function of for &: = and (c) as a function for 2000 (S 1000, log-scale).
Figure 4|a) a) also illustrates the exponential decay of our estimator in terms of and how our estimator less biased than GT by exponential factor. In Figure 4/b)) we can observe that GT's bias also decays exponentially, although not nearly at the rate our estimator.
In terms of distributions, closer look at the performance differences confirms suspicion that the bias of our estimator strongly influenced by the probability Pmax of the most abundant element, while the bias of GT is strongly influenced by the probability Pmin of the rarest element. In fact, by Eqn. (12 the absolute bias of our estimator is minimized when Pmax is minimized. By Eqn. (TT). GT's bias is minimized if Pain maximized. Since both is true for the uniform, both estimators exhibit the lowest bias for the uniform across all six distributions. GT performs similar on all dis- tributions apart from the uniform (where bias seems minimal) and zipf-1 (where bias is maximized), For our estimator, if we ranked the distributions by values of Pmax with the smallest value first (uniform, half&half, zipf-0.5, zipf-1), we would arrive the same ordering in terms of performance of our estimator as shown in Figure 4()).
20

---

Published as a conference paper at ICLR 2025
Table 6: The MSE of the Turing estimator My and the best evolved estimator Mj and for the missing mass My. the success rate A12 of the evolved estimator (X2) against the Good-Turing estimator (X1), and the ratio (Ratio, MSE Fro MS)(M))) for two support sizes = 100 and 200, three sample sizes and six distributions.
s
n/S
Distribution
MSB(M
MS)(
A12
Ratio
uniform
1.09e-02
7.94c-03
0.88
72%
half&half
1.14e-02
7.16e-03
0.90
63%
zipf-0.5
8.09e-03
7.37e-03
0.87
91%
0.5
zipf-1
1.08e-02
8.13e-03
0.91
75%
diri-1
1.10e-02
7.97c-03
0.92
72%
diri-0.5
9.90e-03
8.02c-03
0.87
81%
uniform
6.05e-03
4.29e-03
0.97
70%
half&half
5.46e-03
4.07e-03
0.98
74%
100
zipf-0.5
3.42e-03
3.04e-03
0.89
88%
1.0
zipf-1
5.23e-03
4.16e-03
0.96
79%
diri-1
4.36e-03
3.47c-03
0.92
79%
diri-0.5
3.47c-03
2.86c-03
0.88
82%
uniform
1.93e-03
1.73e-03
0.96
89%
half&half
1.57e-03
1.42e-03
0.93
90%
zipf-0.5
1.26e-03
1.08c-03
0.94
85%
2.0
zipf-1
1.73e-03
1.54e-03
0.97
88%
diri-1
1.23e-03
1.05e-33
0.91
85%
diri-0.5
9.41e-04
8.08e-04
0.86
85%
uniform
5.44e-03
4.23e-03
0.90
77%
half&half
5.65e-03
4.28e-03
0.92
75%
zipf-0.5
3.79c-03
3.64c-03
0.77
96%
0.5
zipf-1
5.29e-03
3.98e-03
0.95
75%
diri-1
5.45e-03
4.01e-03
0.92
73%
diri-0.5
4.95e-03
4.05e-03
0.86
82%
uniform
3.01e-03
2.46e-03
0.98
81%
half&half
2.73e-03
2.26e-03
0.96
82%
200
zipf-0.5
1.61e-03
1.47e-03
0.88
91%
1.0
zipf-1
2.58e-03
2.21e-03
0.96
85%
diri-1
2.18e-03
1.92e-03
0.84
87%
diri-0.5
1.74c-03
1.56c-03
0.79
89%
uniform
9.67c-04
9,21c-04
0.99
95%
halt&half
7.88e-04
7.37e-04
0.98
93%
zipf-0.5
6.01e-04
5.66e-04
0.91
94%
2.0
zipf-1
8.66e-04
7.99c-04
1.00
92%
diri-1
6.15e-04
5,56e-04
0.86
90%
diri-0.5
4.71e-04
4.25e-04
0.80
90%
Table 6 shows the MSE of the Good- -ord-Turing estimator M and the best evolved estimator Ar for the missing mass My. the success rate ÅΙ the evolved estimator (X2) against the Good-Turing estimator (X1), and the ratio (Ratio, (MF(M) M/M(((M for two support sizes S 100 and 200, three sample sizes n and distributions.
We evaluated the variance of the MSE of the evolved estimator Ar from GA due to its randomness. Using (S, n) (100, 100), we tested two distributions (uniform and zipf-1) on five sample datasets, running the GA 20 times per dataset. Table 7 shows the mean, median, and variance of the MSE for the evolved estimator as well as the MSE for the Good-Tun Turing estimator for comparison (in parentheses). It shows that the variance of the evolved estimators' MSE is small, indicating the GA's stability and the robustness of the evolved estimator, which consistently outperforms the Good- Turing estimator.
21

---

Published as a conference paper at ICLR 2025
Table Variance of the evolved estimator 5vo
Dataset Index
Uniform (MSE of Good- 6.0e-3)
Zipf (MSE of Good- Good-Turing = 3.4c-3)
Mean MSE
Median MSE
Variance
Mean MSE
Median MSE
Variance
3, 3.8c-03
3,9c-03
2.9e-06
2.7e-03
2,4e-03
1. 1.6e-07
2
5.1e-03
5.3e-03
5.4e-07
2.5e-03
2.4e-03
7.9c-08
3
5.6e-03
5.3e-03
1.6e-06
2.8e-03
2.9e-03
2.0e-07
3.8e-03
3.4e-03
2.0e-06
3.4e-03
3.2e-03
2.6e-07
5
6.5e-03
5.5e-03
4.6e-06
2.7e-03
2.6e-03
8.4e-08
Table 8: MSE comparison for the probabiltiy mass estimation, i.e., & > 0 (Distribution: uniform,
100, n 100).
MSE(MT)
M
2.3e-03
1.1c-03
1.9e-03
5.7e-04
3
1.0e-03
2.6e-04
3.5e-04
1.7e-04
We evaluated the probability mass estimation for 0 < à < 4 for uniform distribution with $ 200, n 200. The result shown below indicates that our method consistently outperforms the Good- Turing estimator across & values. We focus small k, as practical interest often lies in unseen and rare categories where empirical probability estimates are biased.
G RECENT RELATED WORK ON ESTIMATING MISSING MASS
In this section, we provide brief overview of the recent related work on estimating the properties of the underlying distribution from a sample (Painsky] 2023 Valiant & Valiant 2017 2019); those works can either directly indirectly be used to estimate the missing mass Mo- We first describe each method and how it can be used to estimate the missing mass Mo. Then, we conduct experiments comparing the performance of the methods against our estimator M in terms of the mean squared error (MSE).
| Wu & Yang
While our objective is to estimate the missing mass Mo. Wu & Yang (2019) focus estimating the support size S of multinomial distribution given a sample X" of size n. However, since there can be arbitrarily many unseen classes in the missing mass, they restrict their analysis to distributions whose min(p) 2 1/k for a given constant k. This implies, the estimand S is assumed to be upper- bounded by k. In their experiments, they compare their estimator SW against the estimator S ((n)/(1 - M where S(n) is the number of observed classes and MG is the Good-Turee -al-TTring estimator of the missing mass. Integrating both equations, we can construct estimator of the missing mass WrW from their estimate SW of the support size as M. = 1 S(n)/ for comparison with our estimator of the missing mass
Valiant & Valiant 2017) propose to estimate a "plausible" histogram from the frequencies of fre- quencies (FoF) and, from that, to compute functionals such as entropy or the support size. These metrics are more complex, higher-level metrics than the raw probability mass/missing mass, and the plausible histogram computed from Algorithm
this paper cannot be used directly to estimate the missing mass. Nevertheless, for the purpose of comparison, in their algorithm (Algorithm in Valiant & Valiant (2017) as the missing mass; æ; is the fine mesh of values that discretely approximate the potential support of the histogram. However, since they are not originally intended to represent the probability mass of the unseen samples, we expect the missing mass estimation to be not as accurate as method.
consider the 1 Σ, xy used
'oweeerr, note that S(n)/S * Mo for all distributions, except the uniform. Consider distribution p =< 0.9, 0.1 > and assume the first sample returns the first class. Then, S(n)/S 0.5 while Mo 0.1.
22

---

Published as a conference paper at ICLR 2025
Painsky 2023) considers the problem of finding coefficients ........ ,n in the missing mass estima- tor o Di=1 3 such that the worst-case l2 risk over all possible distributions P is minimized. Using an upper bound on the estimation risk for a given distribution, they define an algorithm that solves constrained programming problem find the first two coefficients 31 and 82 and thus generate estimator M of the missing mass with minimized risk across all distributions.
Our work makes several contributions over Painsky 2023
We generalize the estimation problem beyond the missing mass Mp to the estimation for the total probability mass Mj. across all elements that appear & times in the sample for any value of k v $ n.
Our (distribution-free) method searches for the (distributionnspeciifie) estimator, which min- imizes the risk for that particular (unknown) distribution given only the sample. We pro- pose genetic algorithm, define a search space of valid representations of B[Ms] which searched, and define method to instantiate representation into an estimator that is being evaluated for fitness.
Our of estimators parametric not only in 4; (n) but also the FoF of subsequences X = [X..... Xz) of X", i.e., we consider Σ Σラ= De (c.f the dependency be- tween FoF Figure D
We conducted 100 repetitions of the experiment with the same setting in the main paper calculated the MSE of each method. In particular for Wu & Yang (019 method, although min (p) not normally known, method for two support sizes $ = 100 and 200, three sample sizes n and six distributions. The bold values indicate the best performing estimator. Overall, our search-based method outperforms the other three methods in terms of mean squared error (MSE). This is because in contrast to ours, Wu Yang (2019) and Valiant & Valiant (2017) are not directly designed to estimate the missing mass, and while all are distribution-ire free estimation methodologies, only ours generates an estimator with a reduced MSE on that specific distribution.
1 = min(p) for experiment. Table shows the MSE of each
We found that the MSE of [u & Yang 2019) is roughly 6x higher than that our method median-wise. Yet, their method produces significantly inaccurate estimations for some cases; the MSE their method in those cases could be up to six orders of magnitude higher than that of our method. We use the implementation provided by the authors.
Same what we expect, find Valiant & Valiant (2017)'s 's MSE is orders of magnitude higher than that of our method (median: 128x higher). We use the code from the paper's appendix and convert it from MATLAB code to Python code.
Our empirical results confirm that our method outperforms Painssky (2023)ss 's in terms of MSE; shows that Painsky's method has higher MSE than that of our method (median: 10%, mean: 14%); although Painsky's 's method performs better than the Good-Turing esti- mator (where our method outperforms Good Good-Turing by 25%) as they intended, our method still outperforms it.
23

---

Published as a conference paper at ICLR 2025
Table 9: The MSE of the missing mass estimators for two support sizes $ = 100 and 200, three sample sizes and six distributions. The bold values indicate the best performing estimator.
S
dist
Chebyshev
Valiant
Painsky
Ours
diri-1
3.65c+01
2.27c-01
9.82e-03
7.97e-03
diri-0.5
1.05e+03
2.34c-01
7.46e-03
8.02e-03
half&half
4.67e-03
1.43e-01
1.01e-02
7.16e-03
50
uniform
9,40e-03
1.01e-01
7.97e-03
7.94e-03
zipf-1
4.36e-02
1.33e-01
7.90e-03
7.37e-03
zipf-0.5
4.73e-03
1.43e-01
8.51e-03
8.13e-03
diri-1
7.68e-02
4.28e-01
3.45e-03
3.47e-03
diri-0.5
6.02e+00
3.84c-01
2.63e-03
2.86c-03
100
half&half
8.41e-03
4.05c-01
5,49c-03
4.07e-03
100
uniform
5.08e-03
3.49e-01
7.11e-03
4.29e-03
zipf-1
5.87e-02
1.64e-01
3.40e-03
3.04e-03
zipf-0.5
8.82e-03
3.47c-01
3.94e-03
4.16e-03
diri-1
8.70e-02
6.05e-01
1.34e-03
1.05e-03
diri-0.5
1.29e+01
5.22e-01
1.01e-03
8.08e-04
half&half
6.70e-03
6.63e-01
1.73e-03
1.42e-03
200
uniform
3.89e-03
6.78e-01
2.27e-03
1.73e-03
zipf-1
4.98e-02
1.91e-01
1.59e-03
1.08e-03
zipf-0.5
6,24e-03
5.60c-01
1.73e-03
1.53e-03
diri-1
5.12e-02
2.44e-01
4.88e-03
4.01e-03
diri-0.5
3.03e+00
3.53e-01
5,02c-03
4.05e-03
half&half
1.88e-03
1.73e-01
6.16e-03
4.28c-03
100
uniform
9.78c-03
1.29c-01
6,54e-03
4.23e-03
zipf-1
1.07e-01
1.43e-01
2.93e-03
3.64e-03
zipf-0.5
2.45e-03
1.75e-01
4.42e-03
3.98e-03
diri-1
1.15e-01
4.88e-01
2.01e-03
1.92e-03
diri-0.5
2.28e+00
5.08e-01
1.75e-03
1.56e-03
200
half&half
5.10c-03
4.23c-01
2,42c-03
2.26e-03
200
uniform
3.12c-03
3.67c-01
2.58c-03
2.46e-03
zipf-1
1.16e-01
1.76e-01
1.17e-03
1.47e-03
zipf-0.5
5.84e-03
3.73e-01
2.12e-03
2.21e-03
diri-1
5,44e-01
6.56e-01
5.00e-04
5.56e-04
diri-0.5
1.94e+00
6.69e-01
4.68e-04
4.25e-04
half&half
4.77e-03
7.07e-01
7.62e-04
7.38e-04
400
uniform
1.48e-03
7.07e-01
8.63e-04
9.21e-04
zipf-1
8.45e-02
2.08e-01
5.06e-04
5.66e-04
zipf-0.5
4.94e-03
6.00e-01
1.03e-03
7.99e-04
24


Reviews:
[{"review_id": "MNoUIvzBYC", "reviewer": "Reviewer_JBVY", "summary": "The paper makes a contribution to the estimation of the missing mass probability by providing a distribution free estimator that minimizes the mean-squared error after formalizing it as a constrained optimization problem. The authors provide a genetic algorithm that numerically solves the program. They use synthetic and real data experiments on various distributions to compare the resulting estimator to the classically used Good and Turing estimator.", "questions": "- Are there any theoretical guarantees in terms of MSE when running the optimization on a smaller sample size to compute the estimator for a larger size using the provided formula ?\n\n- How does the proposed minimum MSE estimator perform compared to a distribution-aware estimator for different distributions?\n\n- How does the effectiveness of the proposed estimator look like for strictly positive values of $k$?\n\n- Given a fixed dataset, what is the variance of the resulting estimator's MSE output by the GA (given randomness in mutations)?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper clearly states the problem formulation (fitness function and search space) and proposes a numerical algorithm to solve it.\n- The resulting estimator shows a strong performance in terms of MSE and is relatively cheap to compute.\n- The presentation and the figures are very clear and well-explained.", "weaknesses": "- The empirical application is $\\textbf{insufficient}$, only one real world dataset was used and the experiments were done only on 50 datapoints. \n- No $\\textbf{theoretical guarantees}$ were given for the minimal MSE estimator of the missing mass probability. \n- Comparing the proposed genetic Aagorithm to some other optimization approaches  as well as studying the properties of the resulting estimators would be helpful.", "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": "", "extra_scores": {}}, {"review_id": "o1UP19iNm4", "reviewer": "Reviewer_QhE7", "summary": "This paper addresses the challenge of estimating the expected value of  $M_k$ , which represents the probability that the (n + 1)th observation is an element observed exactly $k$  times in the training data. By precisely characterizing the dependencies among frequency counts, the authors provide a detailed decomposition of $ \\mathbb{E} [M_k] $. They introduce a class of estimators that can be constructed using algorithm-based optimization. These proposed estimators outperform the well-known Good-Turing estimator in terms of accuracy.", "questions": "None.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is significant, since estimating the missing mass is a classic and fundamental problem in statistics with broad practical applications. Making advances over the widely used Good-Turing estimator is important, and such progress has the potential to bring substantial empirical improvements. This paper is also novel in its approach: their analysis do not rely on Poisson approximation, which allows for deeper and more flexible analysis. Additionally, the paper presents a thorough evaluation of the proposed algorithms, including theoretical insights and synthetic experiments that demonstrate the minimal-bias estimator’s substantially lower bias compared to the Good-Turing estimator across various distributions.", "weaknesses": "No obvious weakness is found.", "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": "", "extra_scores": {}}, {"review_id": "V4X1DTnbMQ", "reviewer": "Reviewer_Wyr2", "summary": "This paper studies the problem of estimating the probability of having test points that do not appear in the training data. A class of estimators is provided, and the method for finding an optimal estimator is discussed.", "questions": "1. As stated in the 'weakness', could the authors provide more explanations for why this is an important problem? When is it helpful to know in advance the probability of a test point being equal to one of the training/calibration data points?\n\n2. Specifically, what do the proposed method (or existing methods) advise practitioners to do with their datasets? For example, if one is given the training and calibration data along with test feature inputs, and the goal is to predict the test outcome, there can be various procedures with different approaches---how does the problem/method in this work affect the overall procedure? If we know that the test point is unlikely to be equal to (or drawn from the same distribution as) one of the observed points, what can we do with that information?\n\n3. I'm not sure if it is appropriate to call the proposed method a 'distribution-free' method. According to the footnote, the context in this work is that the method 'does not impose assumptions on the parameters $p$ or $n$,' but this seems more like a standard setting for a parametric (multinomial) model, and is quite different from the usual meaning of 'distribution-free' (such as in conformal prediction context).", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The paper is well-written: the setting discussed in this work, as well as the proposed methodology, is clearly stated, and relevant questions are answered.", "weaknesses": "I don't feel that the motivation for and usefulness of the problem are sufficiently explained.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)