A Bennett Inequality for the Missing Mass
This work addresses a fundamental statistical problem in learning theory, providing incremental improvements to existing bounds for missing mass concentration.
The paper tackles the problem of deriving concentration inequalities for the missing mass, which is the total probability of unobserved outcomes in a sample, by obtaining distribution-free deviation bounds with sublinear exponents. It improves upon prior work, particularly for small deviations, which are crucial in learning theory.
Novel concentration inequalities are obtained for the missing mass, i.e. the total probability mass of the outcomes not observed in the sample. We derive distribution-free deviation bounds with sublinear exponents in deviation size for missing mass and improve the results of Berend and Kontorovich (2013) and Yari Saeed Khanloo and Haffari (2015) for small deviations which is the most important case in learning theory.