# Novel Bernstein-like Concentration Inequalities for the Missing Mass

arXiv: https://arxiv.org/abs/1503.02768 · HTML: https://mlsanity.com/paper/1503.02768/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2015.

## Built on by (most cited first, 1 of 1)

- [Nonlocal Hamiltonian Dynamics on Sparse L'evy Graphs: Spectral Analysis and Multimodal Sampling](https://mlsanity.com/paper/2610.06904/) (2026)

## Abstract (arXiv)

We are concerned with obtaining novel concentration inequalities for the missing mass, i.e. the total probability mass of the outcomes not observed in the sample. We not only derive - for the first time - distribution-free Bernstein-like deviation bounds with sublinear exponents in deviation size for missing mass, but also improve the results of McAllester and Ortiz (2003) andBerend and Kontorovich (2013, 2012) for small deviations which is the most interesting case in learning theory. It is known that the majority of standard inequalities cannot be directly used to analyze heterogeneous sums i.e. sums whose terms have large difference in magnitude. Our generic and intuitive approach shows that the heterogeneity issue introduced in McAllester and Ortiz (2003) is resolvable at least in the case of missing mass via regulating the terms using our novel thresholding technique.