{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T22:28:36Z","timestamp":1775687316689,"version":"3.50.1"},"reference-count":24,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2019,1,2]],"date-time":"2019-01-02T00:00:00Z","timestamp":1546387200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS 1106999"],"award-info":[{"award-number":["DMS 1106999"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1320105"],"award-info":[{"award-number":["CCF 1320105"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1737944"],"award-info":[{"award-number":["DMS-1737944"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["t N00014-14-1-0823"],"award-info":[{"award-number":["t N00014-14-1-0823"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-16-1-2227"],"award-info":[{"award-number":["N00014-16-1-2227"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>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 \u201cmissing mass\u201d. 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 \u201cheavy tails\u201d.<\/jats:p>","DOI":"10.3390\/e21010028","type":"journal-article","created":{"date-parts":[[2019,1,3]],"date-time":"2019-01-03T03:36:30Z","timestamp":1546486590000},"page":"28","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["On the Impossibility of Learning the Missing Mass"],"prefix":"10.3390","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7812-7886","authenticated-orcid":false,"given":"Elchanan","family":"Mossel","sequence":"first","affiliation":[{"name":"Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02142, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mesrob I.","family":"Ohannessian","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago, Chicago, IL 60637, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,1,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1093\/biomet\/40.3-4.237","article-title":"The population frequencies of species and the estimation of population parameters","volume":"40","author":"Good","year":"1953","journal-title":"Biometrika"},{"key":"ref_2","unstructured":"McAllester, D.A., and Schapire, R.E. (2000). On the Convergence Rate of Good\u2013Turing Estimators, COLT."},{"key":"ref_3","first-page":"895","article-title":"Concentration inequalities for the missing mass and for histogram rule error","volume":"4","author":"McAllester","year":"2003","journal-title":"J. Mach. Learn. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1214\/ECP.v18-2359","article-title":"On the concentration of the missing mass","volume":"18","author":"Berend","year":"2013","journal-title":"Electron. Commun. Probab."},{"key":"ref_5","first-page":"21.1","article-title":"Rare Probability Estimation Under Regularly Varying Heavy Tails","volume":"23","author":"Ohannessian","year":"2012","journal-title":"JMLR Proc."},{"key":"ref_6","first-page":"249","article-title":"Concentration inequalities in the infinite urn scheme for occupancy counts and the missing mass, with applications","volume":"23","author":"Boucheron","year":"2017","journal-title":"Bernoulli"},{"key":"ref_7","unstructured":"Taleb, N.N. (2008). The Black Swan: The Impact of the Highly Improbable, Random House."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1023\/A:1007454427662","article-title":"Strong minimax lower bounds for learning","volume":"30","author":"Antos","year":"1998","journal-title":"Mach. Learn."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Beirlant, J., Goegebeur, Y., Segers, J., and Teugels, J. (2004). Statistics of Extremes: Theory and Applications, Wiley.","DOI":"10.1002\/0470012382"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/S0167-7152(98)00246-6","article-title":"On the impossibility of estimating densities in the extreme tail","volume":"43","author":"Beirlant","year":"1999","journal-title":"Stat. Probab. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Rajaraman, N., Thangaraj, A., and Suresh, A.T. (2017, January 25\u201330). Minimax risk for missing mass estimation. Proceedings of the IEEE International Symposium on Information Theory (ISIT), Aachen, Germany.","DOI":"10.1109\/ISIT.2017.8007085"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Acharya, J., Bao, Y., Kang, Y., and Sun, Z. (2018, January 17\u201322). Improved Bounds for Minimax Risk of Estimating Missing Mass. Proceedings of the IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437620"},{"key":"ref_13","unstructured":"Orlitsky, A., and Suresh, A.T. (2018). Competitive distribution estimation: Why is Good\u2013Turing good. Advances in Neural Information Processing Systems, MIT Press."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Valiant, G., and Valiant, P. (2016, January 19\u201321). Instance optimal learning of discrete distributions. Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, Cambridge, MA, USA.","DOI":"10.1145\/2897518.2897641"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Valiant, G., and Valiant, P. (2011, January 6\u20138). Estimating the unseen: an n\/log (n)-sample estimator for entropy and support size, shown optimal via new CLTs. Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, San Jose, CA, USA.","DOI":"10.1145\/1993636.1993727"},{"key":"ref_16","unstructured":"Wu, Y., and Yang, P. (arXiv, 2015). Chebyshev polynomials, moment matching, and optimal estimation of the unseen, arXiv."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"13283","DOI":"10.1073\/pnas.1607774113","article-title":"Optimal prediction of the number of unseen species","volume":"113","author":"Orlitsky","year":"2016","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_18","unstructured":"Falahatgar, M., Ohannessian, M.I., Orlitsky, A., and Pichapati, V. (2017). The power of absolute discounting: All-dimensional distribution estimation. Advances in Neural Information Processing Systems, MIT Press."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"4948","DOI":"10.1109\/TIT.2015.2455058","article-title":"About adaptive coding on countable alphabets: Max-stable envelope classes","volume":"61","author":"Boucheron","year":"2015","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","unstructured":"Kneser, R., and Ney, H. (1995, January 9\u201312). Improved smoothing for m-gram language modeling. Proceedings of the International Conference on Acoustics, Speech and Signal Processing (ICASSP), Detroit, MI, USA."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1017\/S1351324900000218","article-title":"A hierarchical Dirichlet language model","volume":"1","author":"MacKay","year":"1995","journal-title":"Nat. Lang. Eng."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"855","DOI":"10.1214\/aop\/1024404422","article-title":"The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator","volume":"25","author":"Pitman","year":"1997","journal-title":"Ann. Probab."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Teh, Y.W. (2006, January 17\u201318). A hierarchical Bayesian language model based on Pitman-Yor processes. Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics (ACL), Sydney, Australia.","DOI":"10.3115\/1220175.1220299"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1538","DOI":"10.1016\/j.disc.2007.04.012","article-title":"On gaps and unoccupied urns in sequences of geometrically distributed random variables","volume":"308","author":"Louchard","year":"2008","journal-title":"Discret. Math."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/1\/28\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:23:15Z","timestamp":1760185395000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/1\/28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,2]]},"references-count":24,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2019,1]]}},"alternative-id":["e21010028"],"URL":"https:\/\/doi.org\/10.3390\/e21010028","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,2]]}}}