A Unified Framework Solves the Challenge of Estimating Probabilities of Data-Dependent Events

In the interdisciplinary field of machine learning and statistics, accurately estimating the probabilities of data-dependent events has always been a core challenge. A recent paper proposes a unified framework for estimating the probability that an unknown distribution D assigns to an event, where the event is determined by a known mapping from a sample S drawn i.i.d. from D. This research covers not only classical missing mass estimation but also extends to adaptive data analysis, post-selection inference, and error estimation for predictors trained on data.

Problem Definition: Estimating Probabilities of Data-Dependent Events

The paper studies the problem of estimating ( D(\dde(S)) ), i.e., the probability that an unknown distribution D assigns to an event determined by a sample S. The estimator knows the mapping ( \dde ) and the sample S but has no access to additional samples from D. This formalization captures classical missing mass, data-dependent targets in adaptive data analysis, post-selection inference, and the test error of predictors trained on data—the latter recently studied by Gastpar et al. (2024a,b).

The elegance of this framework lies in unifying several seemingly different problems. For example, missing mass estimation concerns unobserved probability mass, while test error estimation involves a model's performance on unseen data. By abstracting to data-dependent events, researchers can systematically analyze the properties of different estimation methods.

Classical Estimation Methods: Empirical Plug-in and Leave-One-Out

Within the framework, the paper examines two classical estimation methods. The error of the empirical plug-in estimator is exactly the generalization gap, so generalization bounds can be directly transferred to this estimator. This means that if the generalization performance of a model is known, one can infer the accuracy of the plug-in estimator.

The leave-one-out estimator recovers the Good-Turing estimator and is accurate for mappings that remain stable when a single sample point is removed (including structured examples such as sample neighborhoods and punctured sets). The Good-Turing estimator was originally used for estimating the probability of unseen words in language models, and here it is generalized to more general stable mappings.

The paper points out that the accuracy of leave-one-out depends on the stability of the mapping. For unstable mappings, leave-one-out may produce large bias. This finding provides theoretical guidance for choosing estimation methods in practical applications.

The Good-Turing estimator was originally proposed by Good and Turing during World War II for breaking ciphers, to estimate the probability mass of unobserved species. Its core idea is to use the frequency of samples appearing ( r ) times to adjust the estimated probability for events appearing ( r ) times, with particular attention to events appearing once (i.e., ( r=1 )) to estimate the probability of unseen events. In natural language processing, Good-Turing is widely used for smoothing the probability of unseen words in language models. Under the framework of this paper, the leave-one-out estimator is exactly equivalent to the Good-Turing estimator for stable mappings, because leave-one-out simulates the "unobserved" state by removing one sample point, thereby naturally estimating the mass of unseen events. This equivalence generalizes Good-Turing from discrete frequency estimation to more general stable mapping scenarios, providing a new perspective for understanding its statistical properties.

Core Application: Error Estimation for Predictors with Memorization Exceptions

The main application of the paper is error estimation for predictors that combine a base classifier with memorization exceptions—a structure common in both theory and practice. For such predictors, the test error is exactly the missing mass restricted to the error region of the base classifier, where the region is selected by the same sample. This leads to a new problem: adaptive missing mass estimation.

To address this dependence, the paper proposes a natural mixture estimator: the Good-Turing estimator restricted to the selected region. Intuitively, this amounts to applying the Good-Turing method to estimate the missing probability mass over the region where the base classifier may err.

However, the paper proves that the generalization performance of the base classifier alone does not guarantee the accuracy of this estimator. That is, even if the base classifier generalizes well, the mixture estimator may still be biased due to the dependence between region selection and the sample. This finding challenges intuitive beliefs and highlights the complexity of error estimation in adaptive settings.

Memorization exception is a common predictor structure: the model uses a simple rule (such as a base classifier) to predict most of the training data, but directly memorizes the labels of a few special samples (memorization exceptions). This structure is particularly common in overparameterized neural networks, where the model can perfectly fit the training set but err on the test set. In this paper, the test error of the predictor is exactly the missing mass over the error region of the base classifier—i.e., the probability of those samples that the base classifier cannot classify correctly and that are covered by memorization exceptions. Since this error region is selected by the same sample, the region and sample are dependent, necessitating adaptive missing mass estimation. This perspective connects the phenomenon of memorization in deep learning with classical missing mass estimation, providing a new tool for analyzing the generalization error of overparameterized models.

Theoretical Guarantees: VC Dimension and Mutual Information Bounds

For the error of the mixture estimator, the paper derives two bounds. The first bound is based on the VC dimension of the possible error region, reflecting the impact of region complexity. The higher the VC dimension, the more complex the region, and the larger the estimation error may be. The second bound is based on the mutual information between the selected region and the sample, capturing the strength of data dependence. The larger the mutual information, the stronger the association between region selection and the sample, and the larger the estimation error.

These two bounds characterize the factors influencing estimation error from different angles, providing a theoretical basis for risk control in practical applications. For example, when the error region is simple (low VC dimension) or strongly independent of the sample (low mutual information), the mixture estimator is more reliable.

The unified framework of the paper not only integrates multiple classical problems but also reveals the essential difficulties in adaptive missing mass estimation. Its theoretical results are of great value for understanding probability estimation of data-dependent events and point the way toward designing more robust estimation methods. Future work may explore tighter bounds or broader classes of stable mappings.

VC dimension (Vapnik-Chervonenkis dimension) is a classical measure of the complexity of a hypothesis class, defined as the size of the largest sample set that the hypothesis class can shatter. In this paper, the VC dimension of the possible error region characterizes the complexity of region selection: the higher the VC dimension, the more complex the region, and the looser the bound on estimation error. Mutual information measures the statistical dependence between the selected region and the sample; the larger the mutual information, the stronger the association between region selection and the sample, and the more severe the adaptive bias. These two bounds are complementary from different perspectives: the VC dimension bound focuses on the complexity of the region itself, while the mutual information bound focuses on the strength of data dependence. In practical applications, if the error region is simple (low VC dimension) or approximately independent of the sample (low mutual information), the mixture estimator is more reliable. These bounds provide theoretical guidance for designing robust adaptive estimation methods.

One-line Summary

A unified framework estimates probabilities of data-dependent events, covering missing mass, adaptive analysis, and predictor error, with VC dimension and mutual information bounds.

Paragraph Summary

This paper proposes a unified framework for estimating the probability that an unknown distribution assigns to a data-dependent event, where the event is determined by a known mapping from i.i.d. samples. The framework covers classical missing mass estimation, adaptive data analysis, post-selection inference, and error estimation for predictors trained on data. The paper analyzes two classical methods: the error of the empirical plug-in estimator is exactly the generalization gap, so generalization bounds transfer directly; leave-one-out is accurate for stable mappings and recovers the Good-Turing estimator. The core application is error estimation for predictors with memorization exceptions, whose test error is the missing mass restricted to the base classifier's error region, requiring adaptive missing mass estimation. The paper proposes a Good-Turing mixture estimator restricted to the selected region and proves that the base classifier's generalization performance alone does not guarantee its accuracy, then derives two error bounds based on VC dimension and mutual information, providing a theoretical basis for practical risk control.