On the Impossibility of Learning the Missing Mass

Abstract

This paper shows that one cannot learn the probability of rare events without imposing further structural assumptions. The event of interest is that of obtaining an outcome outside the coverage of an i.i.d. sample from a discrete distribution. The probability of this event is referred to as the “missing mass”. The impossibility result can then be stated as: the missing mass is not distribution-free learnable in relative error. The proof is semi-constructive and relies on a coupling argument using a dithered geometric distribution. Via a reduction, this impossibility also extends to both discrete and continuous tail estimation. These results formalize the folklore that in order to predict rare events without restrictive modeling, one necessarily needs distributions with “heavy tails”.

1. Introduction

Given data consisting of n i.i.d. observations $X_1,\cdots ,X_n$ from an unknown distribution p over the positive integers ${\mathbb{N}}_{+}$, we traditionally compute the empirical distribution:

$${\widehat{p}}_n\left(x\right):=\frac{1}{n}\sum _{i=1}^n\mathbf{1}\{X_i=x\}.$$

To estimate the probability $p\left(E\right):={\sum }_{x\in E}p\left(x\right)$ of an event $E\subset {\mathbb{N}}_{+}$, we could use ${\widehat{p}}_n\left(E\right):={\sum }_{x\in E}{\widehat{p}}_n\left(x\right)$. This works well for abundantly represented events, but not as well for rare events. An unequivocally rare event is the set of symbols that are missing in the data,

$$E_n:=\{x\in {\mathbb{N}}_{+}:\widehat{p}\left(x\right)=0\}.$$

The probability of this (random) event is denoted by the missing mass:

$$M_n(X_1,\cdots ,X_n):=p\left(E_n\right)=\sum _{x\in {\mathbb{N}}_{+}}p\left(x\right)\mathbf{1}\{\widehat{p}\left(x\right)=0\}.$$

The question we strive to answer in this paper is: “Can we learn the missing mass when p is an arbitrary distribution on ${\mathbb{N}}_{+}$?” Definition 1 phrases this precisely in the learning framework.

Definition 1.

An estimator is a sequence of functions ${\widehat{M}}_n(x_1,\cdots ,x_n):{\mathbb{N}}_{+}^n\to [0,1]$. We say that an estimator learns the missing mass in relative error with respect to a family $\mathcal{P}$ of distributions, if for every $p\in \mathcal{P}$ and every $ϵ,\delta >0$ there exists $n_0(p,ϵ,\delta )$ such that for all $n>n_0(p,ϵ,\delta )$:

$${\mathbf{P}}_p\left\{\left|\frac{{\widehat{M}}_n(X_1,\cdots ,X_n)}{M_n(X_1,\cdots ,X_n)}-1\right|<ϵ\right\}>1-\delta .$$

The learning is said to be distribution-free, if $\mathcal{P}$ consists of all distributions on ${\mathbb{N}}_{+}$.

In this framework, our question becomes whether we can distribution-free learn the missing mass in relative error. It is obvious that the empirical estimator $\widehat{p}\left(E_n\right)$ gives us the trivial answer of 0, and cannot learn the missing mass. A popular alternative is the Good–Turing estimator of the missing mass, which is the fraction of singletons in the data:

$$G_n:=\sum _{x\in {\mathbb{N}}_{+}}\frac{1}{n}\mathbf{1}\{n\widehat{p}\left(x\right)=1\}.$$

The Good–Turing estimator has many interpretations. Its original derivation by Good [1] uses an empirical-Bayes perspective. It can also be thought of as a leave-one-out cross-validation estimator, which contributes to the missing set if and only if the holdout appears exactly once in the data. Fundamentally, $G_n$ derives its form and its various properties from the simple fact that:

$$\mathbf{E}\left[G_n\right]=\sum _{x\in {\mathbb{N}}_{+}}p\left(x\right){(1-p\left(x\right))}^{n-1}=\mathbf{E}\left[M_{n-1}\right].$$

A study of $G_n$ in the learning framework was first undertaken by McAllester and Schapire [2] and continued later by McAllester and Ortiz [3]. Some further refinement and insight was also given later by Berend and Kontorovich [4]. These works focused on additive error. Ohannessian and Dahleh [5] shifted the attention to relative error, establishing the learning property of the Good–Turing estimator with respect to the family of heavy-tailed (roughly power-law) distributions, e.g., $p\left(x\right)\propto x^{-1/\alpha }$ with $\alpha \in (0,1)$. This work also showed that Good–Turing fails to learn the missing mass for geometric distributions, and therefore does not achieve distribution-free learning. More recently, Ben-Hamou et al. [6] provide a comprehensive and tight set of concentration inequalities, which can be interpreted in the current framework, and which further demonstrate that Good–Turing can learn with respect to heavier-than-geometric light tails, e.g., the family that includes $p\left(x\right)\propto 2^{-x^{\gamma }}$ with $\gamma \in (0,1)$ (see the definition in Section 4.3 and Remark 4.3 in that paper), in addition to power-laws.

These results leave open the important question: does there exist some other estimator that can learn the missing mass in relative error for any distribution p? Our contributions are:

• We prove that there are no such estimators, thus providing the first such “no free lunch” theorem for learning about rare events. The first insight to glean from this impossibility result is that one is justified to use further structural assumptions. Furthermore, the proof relies on an implicit construction that uses a dithered geometric distribution. In doing so, it shows that the failure of the Good–Turing estimator for light-tailed distributions is not a weakness of the procedure, but is rather due to a fundamental barrier. Conversely, the success of Good–Turing for heavier-than-geometric and power laws shows its universality, in some restricted sense. In particular, in concrete support to folklore (e.g., [7]), we can state that for estimating probabilities of rare events, heavy tails are both necessary and sufficient.
• We extend this result to continuous tail estimation.
• We show, on a positive note, that upon restricting to parametric light-tailed families learning may be possible. In particular, we show that for the geometric family the natural plug-in estimator learns the missing mass in relative error. As an ancillary result, we prove an instance-by-instance convergence rate, which can be interpreted as a weak sample complexity. For this, we establish some sharp concentration results for the gaps in geometric distributions, which may be of independent interest.

The paper is organized as follows. In Section 2, we present our main result, with a detailed exposition of the proof. In Section 3 we discuss questions of weak versus strong learnability, we give an immediate extension to continuous tail estimation, show that parametric light-tailed learning is possible, comment further on the Good–Turing estimator, and concisely place this result in the context of a chief motivating application, that of computational linguistics. Lastly, we conclude in Section 4 with a summary and open questions.

2. Main Result

Our main result is stated as follows. The rest of this section is dedicated to its detailed proof.

Theorem 1.

There exists a positive $ϵ>0$ and a strictly increasing sequence ${\left(n_k\right)}_{k=1,2,\cdots }$, such that for every estimator ${\widehat{M}}_n$ there exists a distribution $p^{\star }$, such that for all k:

$${\mathbf{P}}_{p^{\star }}\left\{\left|\frac{{\widehat{M}}_{n_k}}{M_{n_k}}-1\right|>ϵ\right\}>ϵ.$$

(1)

In particular, it follows that it is impossible to perform distribution-free learning of the missing mass in relative error.

Remark 1.

Our proof below implies the statement of the theorem with $ϵ={10}^{-4}$ and $n_k=6.5\times 2^k$, but we did not make an honest effort to optimize these parameters.

2.1. Proof Outline

Consider the family ${\mathcal{P}}_{\beta ,m}$ of $\beta ,m$-dithered geometric$\left(\frac{1}{2}\right)$ distributions, where the mass of each outcome beyond a symbol m of a $\mathrm{geometric}\left(\frac{1}{2}\right)$ random variable is divided between two symbols, with a fraction $\beta$ in one and $1-\beta$ in the other. The individual distributions in this family differ only by which of each pair of such symbols gets which fraction. More precisely:

Definition 2.

The $\beta ,m$-dithered geometric$\left(\frac{1}{2}\right)$ family, for a given choice of $\beta \in (0,\frac{1}{2})$ and $m\in {\mathbb{N}}_{+}$, is a collection of distributions parametrized by the dithering choices $\theta \in {\{\beta ,1-\beta \}}^{{\mathbb{N}}_{+}}$, $\theta :=({\theta }_1,{\theta }_2,\cdots ,{\theta }_j,\cdots )$, as follows:

$$\begin{array}{c}{\mathcal{P}}_{\beta ,m}=\left\{p_{\theta }:p_{\theta }\left(x\right)=\frac{1}{2^x},x=1,\cdots ,m;\right.\hfill \\ \left.p_{\theta }(m+2j-1)=\frac{{\theta }_j}{2^{m+j}},p_{\theta }(m+2j)=\frac{1-{\theta }_j}{2^{m+j}},j\in {\mathbb{N}}_{+},\theta \in {\{\beta ,1-\beta \}}^{{\mathbb{N}}_{+}}\right\}.\hfill \end{array}$$

(2)

The intuition of the proof of Theorem 1 is that within such light-tailed families, two distributions may have very similar samples and thus estimated values, yet have significantly different true values of the missing mass. This follows the general methodology of many statistical lower bounds. We now state the outline of the proof. We choose a subsequence of the form $n_k=C{2}^k$. We set $\beta =1/4$, $m=1$, and $C=6.5$. The value of $ϵ>0$ is made explicit in the proof, and depends only on these choices. We proceed by induction.

• We show that there exists ${\theta }_1^{\star }$ such that for all $\theta$ with ${\theta }_1={\theta }_1^{\star }$ we have for $n=n_1$:

  $${\mathbf{P}}_{p_{\theta }}\left\{\left|\frac{{\widehat{M}}_n}{M_n}-1\right|>ϵ\right\}>ϵ.$$

  (3)
• Then, at every step $k>1$:

  (H)

  We start with $({\theta }_1^{\star },\cdots ,{\theta }_{k-1}^{\star })$ such that for all $\theta$ with $({\theta }_1,\cdots ,{\theta }_{k-1})=$$({\theta }_1^{\star },\cdots ,{\theta }_{k-1}^{\star })$, Inequality (3) holds for $n=n_1,\cdots ,n_{k-1}$.

  (*)

  We then show that it must be that for at least one of $\tilde{\theta }=\beta$ or $\tilde{\theta }=1-\beta$, for all $\theta$ with $({\theta }_1,\cdots ,{\theta }_k)=({\theta }_1^{\star },\cdots ,{\theta }_{k-1}^{\star },\tilde{\theta })$, Inequality (3) holds additionally for $n=n_k$. We select ${\theta }_k^{\star }$ to be the corresponding $\tilde{\theta }$.

• This induction produces an infinite sequence ${\theta }^{\star }\in {\{\beta ,1-\beta \}}^{{\mathbb{N}}_{+}}$, and the desired distribution in Theorem 1 can be chosen as $p^{\star }=p_{{\theta }^{\star }}$, since it is readily seen to satisfy the claim for each $n_k$, by construction.

2.2. Proof Details

We skip the proof of the base case, since it is mostly identical to that of the induction step. Therefore, in what follows we assume that $({\theta }_1^{\star },\cdots ,{\theta }_{k-1}^{\star })$ satisfies the inductive hypothesis (H), and we would like to prove that the selection in (*) can always be done. Let us denote the two choices of parameters by

$$\theta :=({\theta }_1^{\star },\cdots ,{\theta }_{k-1}^{\star },\beta ,{\theta }_{k+1},\cdots ),$$

and

$${\theta }^{\prime }:=({\theta }_1^{\star },\cdots ,{\theta }_{k-1}^{\star },1-\beta ,{\theta }_{k+1}^{\prime },\cdots ),$$

and let us refer to $({\theta }_{k+1},\cdots )$ and $({\theta }_{k+1}^{\prime },\cdots )$ by the trailing parameters. What we show in the remainder of the proof is that with two arbitrary sets of trailing parameters, we cannot have two simultaneous violations of Inequality (3) (for both $\theta$ and ${\theta }^{\prime }$). That is, we cannot have both:

$${\mathbf{P}}_{p_{\theta }}\left\{\left|\frac{{\widehat{M}}_{n_k}}{M_{n_k}}-1\right|>ϵ\right\}<ϵ\mathrm{and}{\mathbf{P}}_{p_{{\theta }^{\prime }}}\left\{\left|\frac{{\widehat{M}}_{n_k}}{M_{n_k}}-1\right|>ϵ\right\}<ϵ.$$

(4)

This is stated in Lemma 3, in the last portion of this section. To see why this is sufficient to show that the selection in (*) can be done, consider first the case that Inequality (3) with $n=n_k$ is upheld for both $\theta$ and ${\theta }^{\prime }$ with any two sets of trailing parameters. In this case we can arbitrarily choose ${\theta }_k^{\star }$ to be either $\beta$ or $1-\beta$, since the induction step is satisfied. We can therefore focus on the case in which this fails. That is, for either $\theta$ or ${\theta }^{\prime }$ a choice of trailing parameters can be made such that Inequality (3) with $n=n_k$ is not satisfied, and therefore one of the two cases in (4) holds [say, for example, for $\theta$]. Fix the corresponding trailing parameters [in this example, $({\theta }_{k+1},\cdots )$]. Then, for any choice of the other set of trailing parameters [in this example, $({\theta }_{k+1}^{\prime },\cdots )$], Lemma 3 precludes a violation of Inequality (3) for $n=n_k$ by the other choice [in this example, ${\theta }^{\prime }$]. Therefore this choice can be selected for ${\theta }_k$ [in this example, ${\theta }_k=1-\beta$.]

By using the coupling device and restricting ourselves to a pivotal event, we formalize the aforementioned intuition that the estimator may not distinguish between two separated missing mass values, and deduce that both statements in (4) cannot hold simultaneously.

2.2.1. Coupling

Definition 3.

A coupling between two distributions p and $p^{\prime }$ on ${\mathbb{N}}_{+}$ is a joint distribution q on ${\mathbb{N}}_{+}^2$, such that the first and second marginal distributions of q revert back to p and $p^{\prime }$ respectively.

Couplings are useful because probabilities of events on each side may be evaluated on the joint probability space, while forcing events of interest to occur in an orchestrated fashion. Going back to our induction step and the specific choices $\theta$ and ${\theta }^{\prime }$ with arbitrary trailing parameters, we perform the following coupling. For $(x,x^{\prime })\in {\mathbb{N}}_{+}^2$, let

$$q(x,x^{\prime })=\left\{\begin{array}{ccc}{p}_{\theta }\left(x\right)=p_{{\theta }^{\prime }}\left(x^{\prime }\right)\hfill & ;& \mathrm{if}x=x^{\prime }<m+2k-1;\hfill \\ \beta /2^{m+k}\hfill & ;& \mathrm{if}x=x^{\prime }=m+2k-1,\mathrm{or}\mathrm{if}x=x^{\prime }=m+2k,\hfill \\ (1-2\beta )/2^{m+k}\hfill & ;& \mathrm{if}x=m+2k\mathrm{and}{x}^{\prime }=m+2k-1;\hfill \\ p_{\theta }\left(x\right)p_{{\theta }^{\prime }}\left(x^{\prime }\right)/2^{m+k}\hfill & ;& \mathrm{if}x,x^{\prime }>m+2k;\hfill \\ 0\hfill & ;& \mathrm{otherwise}.\hfill \end{array}\right.$$

(5)

It is easy to verify that q in Equation (5) is a coupling between $p_{\theta }$ and $p_{{\theta }^{\prime }}$ as in Definition 3. Now let us observe the consequences of this choice. If $X,X^{\prime }$ are generated according to q, then if either is in $\{1,\cdots ,m+2k-2\}$ then both values are identical. If either is in $\{m+2k+1,\cdots \}$ then so is the other, but otherwise the two values are conditionally independent. If either is in $\{m+2k-1,m+2k\}$, so is the other, and the conditional probability is given by:

	$x^{\prime }$	$m+2k-1$	$m+2k$
x
$m+2k-1$		$\beta$	0
$m+2k$		$1-2\beta$	$\beta$

Now consider coupled data ${(X_i,X_i^{\prime })}_{i=1,\cdots ,n}$ generated as i.i.d. samples from q. It follows that, marginally, the X-sequence is i.i.d. from $p_{\theta }$, and so is the $X^{\prime }$-sequence from $p_{{\theta }^{\prime }}$. Any event B that is exclusively X-measurable or $B^{\prime }$ that is exclusively $X^{\prime }$-measurable has the same probability under the coupled measure. That is,

$${\mathbf{P}}_{p_{\theta }}\left(B\right)={\mathbf{P}}_q\left(B\right):=q^n(B\times {\mathbb{N}}_{+}^n)$$

and

$${\mathbf{P}}_{p_{{\theta }^{\prime }}}\left(B^{\prime }\right)={\mathbf{P}}_q\left(B^{\prime }\right):=q^n({\mathbb{N}}_{+}^n\times B^{\prime }).$$

In what follows we work only with coupled data, and use simply the shorthand $\mathbf{P}$ to mean ${\mathbf{P}}_q$.

2.2.2. Pivotal Event

The event we would like to work under is that of the coupled samples being identical, while exactly covering the range 1, ⋯, $m+2k-1$. Let’s call this the pivotal event and denote it by:

$$A_k:=\bigcap _{i=1}^{n_k}\{X_i=X_i^{\prime }\}\cap \left\{\{X_1,\dots ,X_{n_k}\}=\{1,\cdots ,m+2k-1\}\right\}.$$

(6)

The reason $A_k$ interests us is that it encapsulates the aforementioned intuition.

Lemma 1.

Under event $A_k$, the coupled missing masses are distinctly separated,

$$\frac{M_{n_k}}{M_{n_k}^{\prime }}=\frac{2-\beta }{1+\beta },$$

while any estimator cannot distinguish the coupled samples,

$${\widehat{M}}_{n_k}={\widehat{M}}_{n_k}^{\prime }.$$

Proof. 

The confusion of any estimator is simply due to the fact that under $A_k$, the coupling forces all samples to be identical $X_i=X_i^{\prime }$, for all $i=1,\cdots ,n_k$.

Thus ${\widehat{M}}_{n_k}={\widehat{M}}_{n_k}^{\prime }$, since estimators only depend on the samples and not the probabilities.

The missing masses, on the other hand, do depend on both the samples and the probabilities and thus they differ. But the event $A_k$ makes the set of missing symbols simply the tail $m+2k,m+2k+1,\cdots$, so we can compute the missing masses exactly:

$$M_{n_k}=p_{\theta }(m+2k)+{\sum }_{x=m+2k+1}^{\infty }{p}_{\theta }\left(x\right)=\frac{1-{\theta }_k}{2^{m+k}}+\frac{1}{2^{m+k}}=(2-\beta )2^{-m-k},\mathrm{and}$$

$$M_{n_k}^{\prime }=p_{{\theta }^{\prime }}(m+2k)+{\sum }_{x=m+2k+1}^{\infty }{p}_{{\theta }^{\prime }}\left(x\right)=\frac{1-{\theta }_k^{\prime }}{2^{m+k}}+\frac{1}{2^{m+k}}=(1+\beta )2^{-m-k},$$

where $\frac{1}{2^{m+k}}$ follows from the usual geometric sum. The claim follows. □

We now show that $A_k$ has always a positive probability, bounded away from zero.

Lemma 2.

For $\beta =1/4$, $m=1$, $C=6.5$ and $n_k=C{2}^k$, there exists a positive constant $\eta >0$ that does not depend on θ, such that for all k, $\mathbf{P}\left(A_k\right)>\eta$. We can explicitly set $\eta =2·{10}^{-4}$.

Proof. 

Please note that $A_k$ in Equation (6) overspecifies the event. In fact, only forcing the exact coverage of $1,\cdots ,m+2k-1$ is sufficient, since this implies in turn that the coupled samples are identical. Recalling the coupling of Equation (5), this is immediate for symbols in $1,\cdots ,m+2k-2$, and follows for $m+2k-1$ since $m+2k$ is not allowed in this event. We can then write $A_k=A_{k,1}\cap A_{k,2}$, dividing the exact coverage to the localization in the range and the representation of each symbol by at least one sample:

$$\begin{array}{cc}{A}_{k,1}=\left\{{\bigcup }_{i=1}^{n_k}\left\{X_i\right\}\subseteq \{1,\cdots ,m+2k-1\}\right\}\hfill & \left(\mathrm{localization}\right),\hfill \\ A_{k,2}=\left\{{\bigcup }_{i=1}^{n_k}\left\{X_i\right\}\supseteq \{1,\cdots ,m+2k-1\}\right\}\hfill & \left(\mathrm{representation}\right).\hfill \end{array}$$

Let $\alpha$ be the probability of $(X_i,X_i^{\prime })$ for a given i being in $\left\{\right(1,1),\cdots ,(m+2k-1,m+2k-1\left)\right\}$. From the coupling in Equation (5) and the structure of the dithered family in Equation (2), we see that for up to $m+2k-2$ this probability sums up to the $m+k-1$ first terms of a geometric$\left(\frac{1}{2}\right)$, and for $(m+2k-1,m+2k-1)$ the coupling assigns it $\beta /2^{m+k}$, thus:

$$\alpha ={\sum }_{x=1}^{m+2k-1}q(x,x)=1-\frac{1}{2^{m+k-1}}+\frac{\beta }{2^{m+k}}.$$

We can then explicitly compute:

$$\mathbf{P}\left(A_{k,1}\right)={\alpha }^{n_k}={\left(1-\frac{1}{2^{m+k-1}}+\frac{\beta }{2^{m+k}}\right)}^{n_k}=:{\eta }_1\left(k\right).$$

Meanwhile, the complement of $A_{k,2}$ is the event that at least one of $\left\{\right(1,1),\cdots ,(m+2k-1,m+2k-1\left)\right\}$ does not appear, that is $A_{k,2}^{\mathsf{c}}={\bigcup }_{x=1}^{m+2k-1}\left\{x\notin \cup \left\{X_i\right\}\right\}$. Conditionally on $A_{k,1}$, the occurrence probabilities of these symbols are simply normalized by $\alpha$, that is $\mathbf{P}(x\notin \cup X_i|A_{k,1})={\left[1-q(x,x)/\alpha \right]}^{n_k}$. Thus, by a union bound, we have:

$$\begin{array}{ccc}\hfill \mathbf{P}\left(A_{k,2}\right|A_{k,1})& =& 1-\mathbf{P}\left(A_{k,2}^{\mathsf{c}}\right|A_{k,1})\hfill \\ \hfill & \ge & 1-{\sum }_{x=1}^{m+2k-1}\mathbf{P}(x\notin \cup X_i|A_{k,1})\hfill \\ \hfill & =& 1-{\sum }_{x=1}^{m+2k-1}{\left[1-q(x,x)/\alpha \right]}^{n_k}\hfill \\ \hfill & \ge & 1-{\sum }_{x=1}^{m+2k-1}{\left[1-q(x,x)\right]}^{n_k}\hfill \\ \hfill & =& 1-{\sum }_{x=1}^m{\left(1-\frac{1}{2^x}\right)}^{n_k}\hfill \\ \hfill & & -{\sum }_{j=1}^{k-1}\left[{\left(1-\frac{\beta }{2^{m+j}}\right)}^{n_k}+{\left(1-\frac{1-\beta }{2^{m+j}}\right)}^{n_k}\right]-{\left(1-\frac{\beta }{2^{m+k}}\right)}^{n_k}\hfill \\ \hfill & \ge & 1-{\sum }_{x=1}^m{\left(1-\frac{1}{2^x}\right)}^{n_k}-2{\sum }_{j=1}^{k-1}{\left(1-\frac{\beta }{2^{m+j}}\right)}^{n_k}-{\left(1-\frac{\beta }{2^{m+k}}\right)}^{n_k}=:{\eta }_2\left(k\right),\hfill \end{array}$$

where the last inequality follows from the fact that $\beta <\frac{1}{2}$. Therefore,

$$\mathbf{P}\left(A_k\right)=\mathbf{P}(A_{k,1}\cap A_{k,2})=\mathbf{P}\left(A_{k,1}\right)\mathbf{P}\left(A_{k,2}\right|A_{k,1})\ge {\eta }_1\left(k\right){\eta }_2\left(k\right)\ge \underset{k\ge 1}{inf}{\eta }_1\left(k\right){\eta }_2\left(k\right)=:\eta .$$

We now use our choices of $\beta =1/4$, $m=1$, $C=6.5$, and $n_k=C{2}^k$, to bound this worst-case $\eta$. In particular, we can verify that $\eta \ge 2·{10}^{-4}$, and it follows as claimed that the pivotal event has always a probability bounded away from zero. □

2.2.3. Induction Step

We now combine all the elements presented thus far to complete the proof of Theorem 1 by establishing the following claim, which we have shown in the beginning of the detailed proof section to be sufficient for the validity of the induction step. In particular, we restate Equation (4) under the coupling of Equation (5).

Lemma 3.

Let

$$\theta :=({\theta }_1^{\star },\cdots ,{\theta }_{k-1}^{\star },\beta ,{\theta }_{k+1},\cdots ),\mathit{and}{\theta }^{\prime }:=({\theta }_1^{\star },\cdots ,{\theta }_{k-1}^{\star },1-\beta ,{\theta }_{k+1}^{\prime },\cdots ),$$

with arbitrary trailing parameters $({\theta }_{k+1},\cdots )$ and $({\theta }_{k+1}^{\prime },\cdots )$. Let q be the coupling of Equation (5), and let $B_k=\left\{\left|{\widehat{M}}_{n_k}/M_{n_k}-1\right|>ϵ\right\}$ and $B_k^{\prime }=\left\{\left|{\widehat{M}}_{n_k}^{\prime }/M_{n_k}^{\prime }-1\right|>ϵ\right\}$. Then given our choices of $\beta =1/4$, $m=1$, $C=6.5$ and $n_k=C{2}^k$, if $ϵ<{10}^{-4}$ we cannot simultaneously have

$${\mathbf{P}}_q\left(B_k\right)<ϵ\mathit{and}{\mathbf{P}}_q\left(B_k^{\prime }\right)<ϵ.$$

Proof. 

Please note that this choice of $ϵ$ means that $ϵ<\eta /2$, where $\eta$ is as in Lemma 2. Recall the pivotal event $A_k$, and assume, for the sake of contradiction, that both probability bounds $\mathbf{P}\left(B_k\right)<ϵ$ and $\mathbf{P}\left(B_k^{\prime }\right)<ϵ$ hold. Please note that if $B_k^{\mathsf{c}}$ holds, it means that

$${\widehat{M}}_{n_k}/M_{n_k}\in (1-ϵ,1+ϵ),$$

(7)

and similarly if $B_k^{\prime \mathsf{c}}$ holds, it means that

$${\widehat{M}}_{n_k}^{\prime }/M_{n_k}^{\prime }\in (1-ϵ,1+ϵ).$$

(8)

By making our hypothesis, we are asserting that these events have high probabilities, $1-ϵ$, under both $p_{\theta }$ and $p_{{\theta }^{\prime }}$ distributions, and that thus the estimator is effectively $(1\pm ϵ)$-close to the true value of the missing mass. Yet, we know that this would be violated under the pivotal event, which occurs with positive probability. We now formalize this contradiction.

By Lemma 2, we have that:

$$\left.\begin{array}{cc}\hfill \mathbf{P}\left(B_k\right|A_k)& =\frac{\mathbf{P}(A_k\cap B_k)}{\mathbf{P}\left(A_k\right)}\le \frac{\mathbf{P}\left(B_k\right)}{\mathbf{P}\left(A_k\right)}\le \frac{ϵ}{\eta }\hfill \\ \hfill \mathbf{P}\left(B_k^{\prime }\right|A_k)& =\frac{\mathbf{P}(A_k\cap B_k^{\prime })}{\mathbf{P}\left(A_k\right)}\le \frac{\mathbf{P}\left(B_k^{\prime }\right)}{\mathbf{P}\left(A_k\right)}\le \frac{ϵ}{\eta }\hfill \end{array}\right\}\Rightarrow \mathbf{P}(B_k^{\mathsf{c}}\cap B_k^{\prime \mathsf{c}}|A_k)\ge 1-2\frac{ϵ}{\eta }>0,$$

(9)

where the last inequality is strict, by the choice of $ϵ<\eta /2$.

On the other hand, recall that by Lemma 1 under $A_k$ we have:

$${\widehat{M}}_{n_k}={\widehat{M}}_{n_k}^{\prime }\mathrm{and}\frac{M_{n_k}}{M_{n_k}^{\prime }}=\frac{2-\beta }{1+\beta }=\frac{7}{5}.$$

By combining this with Equations (7) and (8), we can now see that if $\frac{1+ϵ}{1-ϵ}<\frac{7}{5}$, which is satisfied by any choice of $ϵ<1/6$, in particular ours, then if $B_k^{\mathsf{c}}$ occurs, then $B_k^{\prime }$ occurs, and conversely if $B_k^{\prime \mathsf{c}}$ occurs then $B_k$ occurs. For example, say $B_k^{\mathsf{c}}$ occurs, then ${\widehat{M}}_{n_k}/M_{n_k}<(1+ϵ)$:

$$\frac{{\widehat{M}}_{n_k}^{\prime }}{M_{n_k}^{\prime }}=\frac{{\widehat{M}}_{n_k}}{\frac{7}{5}{M}_{n_k}}<\frac{5}{7}(1+ϵ)<1-ϵ,$$

implying that Equation (8) is not satisfied, thus $B_k^{\prime }$ occurs. The end result is that under event $A_k$, $B_k^{\mathsf{c}}$ and $B_k^{\prime \mathsf{c}}$ cannot occur at the same time, and thus:

$$\mathbf{P}(B_k^{\mathsf{c}}\cap B_k^{\prime \mathsf{c}}|A_k)=0.$$

This contradicts the bound in (9), and establishes the lemma. □

3. Discussions

3.1. Weak Versus Strong Distribution-Free Learning

Arguably, a more common notion of learning is a strong version of Definition 1, where the sample complexity is a function of the distribution class rather than the instance. Formally:

Definition 4.

We say that an estimator learns the missing mass in relative error strongly with respect to a family $\mathcal{P}$ of distributions, if for every $ϵ>0,\delta \in (0,1)$ there exists $n_0(\mathcal{P},ϵ,\delta )$ such that for all $p\in \mathcal{P}$ and all $n>n_0(\mathcal{P},ϵ,\delta )$:

$${\mathbf{P}}_p\left\{\left|\frac{{\widehat{M}}_n(X_1,\cdots ,X_n)}{M_n(X_1,\cdots ,X_n)}-1\right|<ϵ\right\}>1-\delta .$$

The learning is said to be strongly distribution-free, if $\mathcal{P}$ consists of all distributions on ${\mathbb{N}}_{+}$.

The distinction here is similar to that of uniform versus pointwise convergence. Clearly, the existence of a strong learner implies the existence of a weak learner. Conversely, as we have shown that there is no weakly distribution-free learner, there is also no strongly distribution-free learner. However, the ability to choose a different distribution at every sample size n makes it very easy to show this corollary directly. For example, we can consider two distributions p and q with $p\left(1\right)=1-\frac{1}{n^2}$ and $q\left(1\right)=1-\frac{1}{100n^2}$, both of which would result with overwhelming probability in a length-n sequence consisting entirely of this first symbol. Thus any estimator would need to predict the same missing mass with high probability. However, the rest of the symbols would have probabilities differing by a factor of 100 between the two models, and thus any estimator would be misguided for at least one of the two cases.

The relevance of the current contribution is rooted in the plausible yet misguided optimism that although we may not do well in such a worst-case paradigm, there is more hope if we first fix the instance and then study asymptotics. Our “no free lunch” theorem indeed shows the more subtle fact that there are always bad instances for every estimator, and thus even such weak learning is fundamentally impossible.

Such a contrast between weak/strong learning has also been appreciated in the classical learning literature, notably in the work of Antos and Lugosi [8]. The notions there are framed in the negative, which is why the weak/strong terminology is reversed. A traditional minimax lower bound in that context states that for any sequence of concept learners ${\widehat{g}}_n$ at each n we can find a distribution for which the expected cumulative classification error is lower bounded by the complexity of the concept class. Analogously, not being able to strong learn as in Definition 4 means that for any estimator ${\widehat{M}}_n$ at each n we can find a distribution for which the relative error stays away from zero. By demanding a strong performance from a learner/estimator, we are able to give only a weak guarantee. In particular, it could be too loose for a fixed distribution that doesn’t vary with n. [8] contributes by giving lower bounds that hold infinitely often for any sequence of concept learners ${\widehat{g}}_n$ but for a distribution choice that is adversarial in advance, fixed for all n. Analogously, not being able to (weak) learn as in Definition 1 means that for any estimator ${\widehat{M}}_n$ there exists a distribution, fixed for all n, for which the relative error stays away from zero for infinitely many n. The lower bounds of Antos and Lugosi [8] can now be tighter, which is why they call their results strong minimax lower bounds. In the context of the present paper, of course, the lower bounds correspond to the impossibility result, which is thus stronger since it doesn’t even hold for a fixed distribution.

3.2. Generalization to Continuous Tails

A closely related problem to learning the missing mass is that of estimating the tail of a probability distribution. In the simplest setting, the data consists of $Y_1,\cdots ,Y_n$ that are i.i.d. samples from a continuous distribution on $\mathbb{R}$. Let F be the cumulative distribution function. The task in question is that of estimating the tail probability

$$W_n=1-F\left(\underset{i=1}{\overset{n}{max}}{Y}_i\right),$$

that is the probability that a new sample exceeds the maximum of all samples seen in the data.

One can immediately see the similarity with the missing mass problem, as both problems concern estimating probabilities of underrepresented events. We can use essentially the same learning framework given by Definition 1, and prove a completely parallel impossibility result.

Theorem 2.

There exists $ϵ>0$ and a subsequence ${\left(n_k\right)}_{k=1,2,\cdots }$, such that for every estimator ${\widehat{W}}_n$ of $W_n$ there exists a continuous distribution $F^{\star }$, such that for all k:

$${\mathbf{P}}_{F^{\star }}\left\{\left|\frac{{\widehat{W}}_{n_k}}{W_{n_k}}-1\right|>ϵ\right\}>ϵ.$$

In particular, it follows that it is impossible to perform distribution-free learning of the tail probability in relative error.

Proof. 

(Sketch) The discrete version of this theorem is a trivial extension of Theorem 1, since in the proof of the latter the pivotal event forced the missing mass to be a tail probability. The potential strengthening of Theorem 2 comes from insisting on a continuous $F^{\star }$. The same techniques may be adapted in this case, such as by dithering an exponential distribution, where a base exponential density is divided into intervals, and mass is moved between pairs of adjacent intervals by scaling the density the same way as $\beta$ dithers the geometric. The adversarial distribution for a given estimator can then be chosen from this family. In order not to repeat the same aguments, however, we instead prove this result via a reduction. The details can be found in the Appendix A. Namely, we show that discrete tail estimation can be reduced to continuous tail estimation. Since the former is impossible, so is the latter. □

Theorem 2 gives a concrete justification of why it is important to make regularity assumptions when extrapolating distribution tails. This is of course the common practice of extreme value theory, see, for example [9]. Some impossibility results concerning the even more challenging problem of estimating the density of the maximum were already known [10], but to the best of our knowledge this is the first result asserting it for tail probability estimation as well.

3.3. Learning in Various Families

Ben-Hamou et al. [6] (Corollary 5.3) gives a very clean characterization of a sufficient learnable family, which encompasses the one covered by Ohannessian and Dahleh [5].

Theorem 3

([6]).Denote the expected number of single-occurrence and double-occurrence symbols by ${\mathsf{\Phi }}_{n,1}$ and ${\mathsf{\Phi }}_{n,2}$ respectively:

$${\mathsf{\Phi }}_{n,1}:=\mathbf{E}\left[\sum _{x\in {\mathbb{N}}_{+}}\mathbf{1}\{n{\widehat{p}}_n\left(x\right)=1\}\right]=\sum _{x\in {\mathbb{N}}_{+}}np\left(x\right){[1-p\left(x\right)]}^{n-1},\mathit{and}$$

$${\mathsf{\Phi }}_{n,2}:=\mathbf{E}\left[\sum _{x\in {\mathbb{N}}_{+}}\mathbf{1}\{n{\widehat{p}}_n\left(x\right)=2\}\right]=\sum _{x\in {\mathbb{N}}_{+}}\frac{n(n-1)}{2}p{\left(x\right)}^2{[1-p\left(x\right)]}^{n-2}.$$

Let $\mathcal{H}$ be the family defined by:

$$\mathcal{H}:=\left\{p:{\mathsf{\Phi }}_{n,1}\to \infty \mathit{and} \frac{{\mathsf{\Phi }}_{n,2}}{{\mathsf{\Phi }}_{n,1}}\mathit{remains} \mathit{bounded} \mathit{as} n\to \infty \right\}.$$

The Good–Turing estimator learns the missing mass in relative error with respect to $\mathcal{H}$.

The proof relies on power moment concentration inequalities (such as Chebyshev’s). The ${\mathsf{\Phi }}_{n,1}\to \infty$ property embodies the heavy-tailed nature, since it says that rare events occur often. The condition that $\frac{{\mathsf{\Phi }}_{n,2}}{{\mathsf{\Phi }}_{n,1}}$ (i.e., its lim sup) remains bounded is a smoothness condition, since ${\mathsf{\Phi }}_{n,2}$ roughly captures the variance of the number of singletons (see [6], Proposition 3.3). For us, this is instructive because one could readily verify that the condition of Theorem 3 fails for geometric (and dithered geometric) distributions. We can thus see that in some sense Good–Turing captures a maximal family of learnable distributions. In particular, we now know that the complement of $\mathcal{H}$ is not learnable.

Considering how sparse the dithered geometric family is, the failure of any estimator to learn the missing mass with respect to it may seem discouraging. (Please note that Theorem 1 holds even if the estimator is aware that this is the class it is paired with.) However, if we restrict ourselves to smooth parametric families within light tails then the outlook can be brighter. We illustrate this with the case of the geometric family.

Theorem 4.

Let $\mathcal{G}$ be the class of geometric distributions, parametrized by $\alpha \in (0,1)$:

$$p_{\alpha }\left(x\right)=(1-\alpha ){\alpha }^{x-1},\mathit{for}x\in {\mathbb{N}}_{+}.$$

Let ${\widehat{\alpha }}_n=1-\frac{n}{\sum X_i}$ be the maximum likelihood estimator of the parameter, and define the plug-in estimator:

$${\check{M}}_n=\sum _{x\in {\mathbb{N}}_{+}}(1-{\widehat{\alpha }}_n){\widehat{\alpha }}_n^x\mathbf{1}\{n{\widehat{p}}_n\left(x\right)=0\}$$

Then ${\check{M}}_n$ learns the missing mass in relative error with respect to $\mathcal{G}$.

Proof. 

(Sketch) The proof consists of pushing forward the convergence of the parameter to that of the entire distribution using continuity arguments, and then specializing to the missing mass. The details can be found in the Appendix B. □

3.4. Learning the Missing Mass in Additive Error and Learning Other Related Quantities

As mentioned in the introduction, a good part of the work on learning the missing mass focused on additive error [2,3,4]. Recently, minimax lower bounds were given for the additive error in [11] and [12]. Note however that relative error bounds cannot be deduced from these (nor any other way, given the impossibility established here.) A related problem to learning the missing mass in relative error is that of learning a distribution in KL-divergence loss. This averages all log-relative errors (missing or otherwise). This averaging scales the log-relative errors by the rare probability and attenuates the kind of gaps discussed in our present context. One thus hopes to have more optimistic results. Indeed, the Good–Turing estimator was recently shown to be adaptive/competitive for distribution learning in KL-divergence [13]. A similar result in the context of distribution learning in total variation was given in [14]. In the language of Section 3.2, being competitive can be understood as an intermediate characterization between weak and strong learning. Lastly, one could be interested in learning other properties of distributions that are intimately related to the rare component. Entropy and support size are two of these. In [15] a traditional minimax bound was established for these quantities, which was then further distilled in [16]. Another related problem is predicting the growth of the support as more observations are made. This was characterized very precisely in [17], where one can find further pointers on this very old problem. Some of these results may give the impression that nothing further can be gained from structural assumptions. However, rates can generally be refined whenever such structure exists. See for example [18] for refined competitive rates in distribution estimation and [19] for similar results in the predictive/compression setting. These results use tail characterizations, similar to those in extreme value theory [10].

3.5. N-Gram Models and Bayesian Perspectives

One of the prominent applications of estimating the missing mass has been to computational linguistics. In that context, it is known as smoothing and is used to estimate N-gram transition probabilities. The importance of accurately estimating the missing mass, and in particular in a relative-error sense, comes from the fact that N-grams are used to score test sentences using log-likeliehoods. Test sentences often have transitions that are never seen in the training corpus, and thus in order for the inferred log-likelihoods to accurately track the true log-likelihood, these rare transitions need to be assigned meaningful values, ideally as close to the truth as possible. As such, various forms of smoothing, including Good–Turing esimation, have become an essential ingredient of many practical algorithms, such as the popular method proposed by Kneser and Ney [20].

In the context of N-gram learning, a separate Bayesian perspective was also proposed. One of the earliest to introduce this were [21] using a Dirichlet prior. This was shown to not be very effective, and we now understand that it is due to the fact that (1) the Dirichlet process produces light tails while language is often heavy-tailed and, even if it were; (2) rare probabilities are hard to learn for large light-tailed families. The natural progression of these Bayesian models led to the use of the two-parameter Poisson-Dirichlet prior [22], which was suggested initially by [23]. Despite employing sophisticated inference techniques, the missing mass estimator that resulted from these models closely followed the Good–Turing estimator (for a sharp analysis of this correspondence, see Falahatgar et al. [18].) In light of the present work, this is not surprising since the two-parameter Poisson-Dirichlet process almost surely produces heavy-tailed distributions, and any two algorithms that learn the missing mass are bound to have the same qualitative behavior.

4. Summary

In this paper, we have considered the problem of learning the missing mass, which is the probability of all unseen symbols in an i.i.d. draw from an unknown discrete distribution. We have phrased this in the probabilistic framework of learning. Our main contribution was to show that it is not possible to learn the missing mass in a completely distribution-free fashion.

In other words, no single estimator can do well for all distributions. We have given a detailed account of the proof, emphasizing the intuition of how failure can occur in large light-tailed families. We have also placed this work in a greater context, through some discussions and extensions of the impossibility result to continuous tail probability estimation, and by showing that smaller, parametric, light-tailed families may be learnable.

An initial impetus for this paper and its core message is that assuming further structure can be necessary in order to learn rare events. Further structure, of course, is nothing more than a form of regularization. This is a familiar notion to the computational learning community, but for a long time the Good–Turing estimator enjoyed favorable analysis that focused on additive error, and evaded this kind of treatment. The essential ill-posedness of the problem was uncovered by studying relative error. But lower bounds cannot be deduced from the failure of particular algorithms. Our result thus completes the story, and we can now shift our attention to studying the landscape that is revealed.

The most basic set of open problems concerns establishing families that allow learning of the missing mass. We have seen in this paper some such families, including the heavy-tailed family learnable by the Good–Turing estimator, and simple smooth parametric families, learnable using plug-in estimators. How do we characterize such families more generally? The next layer of questions concerns establishing convergence rates, i.e., strong learnability, via both lower and upper bounds. The fact that a family of distributions allows learning does not mean that such rates can be established. This is because any estimator may be faced with arbitrarily slow convergence, by varying the distribution in the family. In other words we may be faced with a lack of uniformity. How do we control the convergence rate? Lastly, when learning is not possible, we may want to establish how gracefully an estimator can be made to fail. Understanding these limitations and accounting for them can be critical to the proper handling of data-scarce learning problems.