Novel Bernstein-like Concentration Inequalities for the Missing Mass

Bahman Yari Saeed Khanloo Monash, Gholamreza Haffari Monash University
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:457-466, 2015.

Abstract

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) and Berend and Kontorovich (2013, 2012) for small deviations which is the most interesting case in learning theory. It is known that standard inequalities can not be used to analyze heterogeneous distributions i.e. distributions whose bins 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-monash15a, title = {Novel {B}ernstein-like Concentration Inequalities for the Missing Mass}, author = {Monash, Bahman Yari Saeed Khanloo and University, Gholamreza Haffari Monash}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {457--466}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/monash15a/monash15a.pdf}, url = {https://proceedings.mlr.press/r13/monash15a.html}, abstract = {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) and Berend and Kontorovich (2013, 2012) for small deviations which is the most interesting case in learning theory. It is known that standard inequalities can not be used to analyze heterogeneous distributions i.e. distributions whose bins 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Novel Bernstein-like Concentration Inequalities for the Missing Mass %A Bahman Yari Saeed Khanloo Monash %A Gholamreza Haffari Monash University %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-monash15a %I PMLR %P 457--466 %U https://proceedings.mlr.press/r13/monash15a.html %V R13 %X 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) and Berend and Kontorovich (2013, 2012) for small deviations which is the most interesting case in learning theory. It is known that standard inequalities can not be used to analyze heterogeneous distributions i.e. distributions whose bins 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. %Z Reissued by PMLR on 04 October 2026.
APA
Monash, B.Y.S.K. & University, G.H.M.. (2015). Novel Bernstein-like Concentration Inequalities for the Missing Mass. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:457-466 Available from https://proceedings.mlr.press/r13/monash15a.html. Reissued by PMLR on 04 October 2026.

Related Material