A Unified Framework for Probability Estimation of Data-Dependent Events

Vitaly Feldman, Satyen Kale, Vinod Raman, Kunal Talwar, Ambuj TewariarXiv 2026 · arXiv

TL;DR

This paper introduces a unified mathematical framework for estimating the probability of events that are themselves defined by the data—a common "double-dipping" scenario in machine learning. The authors propose a novel hybrid estimator that accurately predicts the test error for models that memorize exceptions, bridging the gap between classical generalization theory and the Good–Turing missing mass estimator.

What Problem Does This Paper Address?

In classical statistics, we usually want to estimate the probability of a fixed event. However, in modern machine learning, the event we care about often depends on the data we just saw. For example:

  • Test Error: The "event" is the set of points where our specific, data-trained model fails.
  • Missing Mass: The "event" is the set of all possible outcomes we didn't see in our sample.

The challenge is that using the same sample to both define an event and estimate its probability leads to bias. If a model perfectly memorizes its training data, its "training error" (empirical estimate) is zero, but its "test error" (true probability) is certainly not. This paper seeks to answer a fundamental question: When can we accurately estimate the probability of an event that was chosen based on the observed sample?

Methods

The authors formalize this as estimating $D(G(S))$, where $D$ is an unknown distribution, $S$ is a sample, and $G$ is a mapping that turns a sample into an event. They analyze three main approaches:

  1. Empirical Estimation: This is the standard "plug-in" approach (e.g., training error). The paper shows its accuracy is directly tied to generalization bounds (like VC dimension or stability).
  2. Leave-One-Out (LOO) Estimation: This recovers the famous Good–Turing estimator. It works well for "stable" mappings where removing one data point doesn't radically change the event.
  3. The Hybrid Estimator (Adaptive Missing Mass): This is the paper's primary innovation. It targets "exception-memorizing" learners—models that use a base rule but "patch" it by memorizing specific training errors. The hybrid estimator combines empirical estimation (for the base rule) with a restricted Good–Turing estimate (for the memorized parts).

Datasets

As a theoretical paper, it does not use standard empirical benchmarks like ImageNet. Instead, the authors use mathematical constructions and synthetic distributions to prove their bounds and demonstrate "limits of estimatability." Specifically, they construct hard-to-estimate scenarios involving:

  • High-dimensional binary coordinates (to show limits of post-selection inference).
  • Parity functions (to show limits related to algebraic structure).
  • Quadratic-sized domains (to show that even small domains can be non-estimatable if the event mapping is complex enough).

Key Insights and Ideas

  • The "Memorization" Gap: Standard tools fail for models that memorize. If you memorize your errors, your training error is 0. If you use Leave-One-Out, you have to retrain the model $n$ times, which is computationally expensive and often unstable. The Hybrid Estimator solves this by only requiring you to train the base model once.
  • Stability is the Key to Good-Turing: The authors show that the Good–Turing estimator is just a special case of a Leave-One-Out estimator applied to a specific "stable" mapping. They extend this to new "structured" versions of missing mass, like the probability of landing in the neighborhood of a seen point.
  • Complexity of the Selection Rule: The accuracy of the hybrid estimator doesn't depend on the whole model being "simple," but rather on the selection rule (the base classifier) having low complexity (low VC dimension or low Mutual Information with the sample).

Key Results

  • Universal Consistency: The authors prove that for any mapping stable under the deletion of one point, the LOO estimator has a mean squared error (MSE) of $O(1/n)$.
  • Hybrid Accuracy: For exception-memorizing learners, the hybrid estimator achieves an MSE of $O(d \log(n/d) / n)$, where $d$ is the VC dimension of the base classifier's error regions. This holds even when the model has zero training error.
  • Impossibility Proofs: They demonstrate that some events are fundamentally "non-estimatable." For instance, if you pick an event based on the maximum of exponentially many coordinates, no estimator can achieve an MSE below $1/64$.

Limitations and Future Work

  • Neighborhood-Correcting Learners: While the paper solves the case for simple memorization, it notes that proving bounds for "neighborhood-correcting" learners (where a memorized point fixes errors in its nearby vicinity) is much harder. The "adaptive step" in the proof currently lacks the necessary concentration inequalities for these complex sets.
  • Characterizing Estimatability: The authors acknowledge they haven't found a single "unified" structural property that perfectly separates estimatable events from non-estimatable ones.
  • Optimal Rates: The current work focuses on establishing that we can estimate these values; finding the mathematically "tightest" possible rates of convergence remains an open problem.

Summary updated

Abstract

We study the general problem of estimating $D(\dde(S))$, the probability that an unknown distribution $D$ assigns to an event determined by a sample $S$ of $n$ i.i.d.\ draws from $D$ through a known mapping $\dde$. The estimation algorithm knows $\dde$ and $S$ but does not have access to any additional samples from $D$. This formulation captures classical missing mass, the data-dependent targets of adaptive data analysis and post-selection inference, and the test error of a data-trained predictor, whose estimation was recently studied by \new{Gastpar et al.\ (2024a,b)}. Within this framework we examine the two classical approaches to estimation. The error of the empirical plug-in estimator is exactly a generalization gap, so generalization bounds transfer to it directly. The leave-one-out estimator, which recovers the Good--Turing estimator, is accurate for every mapping that is stable under the deletion of one sample point, including new structured examples such as neighborhoods of the sample and pierced sets. The main application of our framework is to error estimation for a predictor that combines a base classifier with memorized exceptions, a structure common in theory and in practice. For it, the test error is exactly the missing mass restricted to the error region of the base classifier, a region selected by the same sample. We formulate the general problem of \emph{adaptive missing mass estimation} to address such dependence and propose a natural hybrid estimator, the Good--Turing estimator restricted to the selected region. We show that the generalization of the base classifier alone does not guarantee the accuracy of this estimator, and derive two bounds on its error: the first one based on the VC dimension of possible error regions and another based on the mutual information of the selected region with the sample.
BibTeX
@misc{feldman2026unified,
  author = {Vitaly Feldman and Satyen Kale and Vinod Raman and Kunal Talwar and Ambuj Tewari},
  title = {{A Unified Framework for Probability Estimation of Data-Dependent Events}},
  year = {2026},
  eprint = {2610.41244},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41244},
}
Figure