On the Impossibility of Learning the Missing Mass

Area of Science:

• Machine Learning
• Probability Theory
• Statistical Inference

Background:

• Accurate estimation of rare event probabilities is crucial in various fields.
• Current methods often rely on strong assumptions about data distribution.
• The challenge lies in learning probabilities outside the observed data range.

Purpose of the Study:

• To investigate the fundamental learnability of rare event probabilities.
• To determine if "missing mass" can be learned without distribution-specific assumptions.
• To analyze the implications for tail estimation and predictive modeling.

Main Methods:

• Developed a theoretical framework to analyze learnability.
• Employed a semi-constructive proof technique.
• Utilized a coupling argument with a dithered geometric distribution.
• Established a reduction from missing mass to tail estimation.

Main Results:

• Demonstrated that missing mass is not distribution-free learnable in relative error.
• Proved that this impossibility extends to both discrete and continuous tail estimation.
• Showcased that predicting rare events necessitates assumptions like heavy tails.

Conclusions:

• Fundamental limits exist in learning rare event probabilities without structural priors.
• The study formalizes the intuition that heavy-tailed distributions are essential for robust rare event prediction.
• Results have implications for risk assessment, anomaly detection, and statistical modeling.