On the Impossibility of Learning the Missing Mass
From MaRDI portal
Minimax procedures in statistical decision theory (62C20) Characterization and structure theory of statistical distributions (62E10) Nonparametric estimation (62G05) Asymptotic properties of nonparametric inference (62G20) Statistics of extreme values; tail inference (62G32) Survival analysis and censored data (62N99)
Abstract: 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 "missing mass". The impossibility result can then be stated as: the missing mass is not distribution-free PAC-learnable in relative error. The proof is semi-constructive and relies on a coupling argument using a dithered geometric distribution. This result formalizes the folklore that in order to predict rare events, one necessarily needs distributions with "heavy tails".
This page was built for publication: On the Impossibility of Learning the Missing Mass
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6259896)
