A Unified Framework for Probability Estimation of Data-Dependent Events
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.
Related
- A Framework to Quantify the Probability of Future Cyber Loss Events
- A Unified Framework for Training-Dataset Aggregation and Exact Machine Unlearning via Gibbs Probability Measures
- A Hybrid Spatial Statistical Learning Framework for Individualized Probability Estimation: Application to Multisite Autism Neuroimaging
- A Unified Framework for Scenario Coverage Estimation and Representative Selection in Simulation-Based Testing of Automated Vehicles
- A Unified Two-Stage Generative Diffusion Framework for Channel Estimation and Port Selection in Multiuser MIMO-FAS
BibTeX
@misc{feldman2026unified,
title = {{A Unified Framework for Probability Estimation of Data-Dependent Events}},
author = {Vitaly Feldman and Satyen Kale and Vinod Raman and Kunal Talwar and Ambuj Tewari},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41244},
eprint = {2610.41244},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41244},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Unified Framework for Probability Estimation of Data-Dependent Events
AU - Vitaly Feldman
AU - Satyen Kale
AU - Vinod Raman
AU - Kunal Talwar
AU - Ambuj Tewari
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41244
UR - https://arxiv.org/abs/2610.41244
AB - 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.
ER -