On the concentration of the missing mass

By Daniel Berend, Aryeh Kontorovich. 2012

103 citations recorded by the source corpus.

A random variable is sampled from a discrete distribution. The missing mass is the probability of the set of points not observed in the sample. We sharpen and simplify McAllester and Ortiz's results (JMLR, 2003) bounding the probability of large deviations of the missing mass. Along the way, we refine and rigorously prove a fundamental inequality of Kearns and Saul (UAI, 1998).

Subfields: Artificial Intelligence, Statistics and Probability, Signal Processing

View Paper: https://www.semanticscholar.org/paper/aae172daf56b10dc2511a5304155916cafdf1d97

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Signal Processing

Citations in the corpus

On strict sub-Gaussianity, optimal proxy variance and symmetry for bounded random variables (2019, background): “Note that the study of the variations of h is observed by Berend and Kontorovich (2013) (cf.”
Uniform Hanson-Wright type concentration inequalities for unbounded entries via the entropy method (2018, methodology): “In the analysis that we present, there is a need to control the behaviour of ∇ZA(X) (or its analogs) and, as in Boucheron et al. (2003) and Adamczak (2015), we use a truncation argument to do so.”
On the sub-Gaussianity of the Beta and Dirichlet distributions (2017, background): “Recent interest focused on deriving the optimal proxy variance for discrete random variables like the Bernoulli distribution (Buldygin and Moskvichova, 2013; Kearns and Saul, 1998; Berend and Kontorovich, 2013) and the missing mass (McAllester and Schapire, 2000; McAllester and Ortiz, 2003; Berend a”
Concentration inequalities in the infinite urn scheme for occupancy counts and the missing mass, with applications (2014, background): “where CLS(p) = log((1 − p)/p)/(1 − 2p) (or 2 if p = 1/2) is the optimal logarithmic Sobolev constant for Bernoulli random variables with success probability p (this sharp and nontrivial result has been proven independently by a number of people: Kearns and Saul [30], Berend and Kontorovich [8], Ragi”