cs.LGOct 30, 2026

A Unified Framework for Probability Estimation of Data-Dependent Events

Authors: Vitaly Feldman, Satyen Kale, Vinod Raman, Kunal Talwar, Ambuj Tewari

Organizations: Apple · University of Michigan, Ann Arbor

Abstract

We study the general problem of estimating D(\dde(S))D(\dde(S)), the probability that an unknown distribution DD assigns to an event determined by a sample SS of nn i.i.d.\ draws from DD through a known mapping \dde\dde. The estimation algorithm knows \dde\dde and SS but does not have access to any additional samples from DD. 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 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.

Explore similar work

Sep 17, 2026

Next-token functional estimation

Suppose we observe the first nn points of a sequence of random variables having length n+1n+1, and wish to estimate a functional of the unobserved final point and the empirical measure of the nn observed training points. Such next-token functionals include the probability that the next token is novel (also known as the surprise probability), the tail probability of the minimum distance between the next token and training points, and the test error of a classifier trained on the observed points. All of these quantities are classically estimated by the leave-one-out method, which is inconsistent under temporal dependence. We propose a leave-a-window-out estimator, which deletes a window of length ττ after each index before forming the empirical measure and reduces to leave-one-out at τ=1τ= 1. Under natural assumptions, we show that the error of our estimator decays at a parametric rate for any stationary ββ-mixing process that also admits a Marton coupling. Our results thus cover several natural functionals on a large class of stochastic processes. We complement these upper bounds with a sharp minimax lower bound for estimating the surprise probability on mixing Markov chains. Simulations on Markov chains, moving-average processes, and autoregressive processes show that our estimator succeeds in many scenarios where leave-one-out and add-constant baselines fail.
Apr 21, 2026

Separating Geometry from Probability in the Analysis of Generalization

The goal of machine learning is to find models that minimize prediction error on data that has not yet been seen. Its operational paradigm assumes access to a dataset SS and articulates a scheme for evaluating how well a given model performs on an arbitrary sample. The sample can be SS (in which case we speak of in-sample'' performance) or some entirely new $S'$ (in which case we speak of out-of-sample'' performance). Traditional analysis of generalization assumes that both in- and out-of-sample data are i.i.d.\ draws from an infinite population. However, these probabilistic assumptions cannot be verified even in principle. This paper presents an alternative view of generalization through the lens of sensitivity analysis of solutions of optimization problems to perturbations in the problem data. Under this framework, generalization bounds are obtained by purely deterministic means and take the form of variational principles that relate in-sample and out-of-sample evaluations through an error term that quantifies how close out-of-sample data are to in-sample data. Statistical assumptions can then be used ex post to characterize the situations when this error term is small (either on average or with high probability).
Oct 8, 2026

Marformer: A Transformer for Predicting Missing Data Distributions

Real decisions are made under incomplete information. If we observe only some of the random variables we need, we can predict the others. The conditional marginals over the missing variables are the key ingredient for computing Bayes risk and Value of Information (VOI), the expected gain from acquiring one more observation before deciding. We present the Marformer, a Transformer trained to directly predict conditional marginals given any set of observed values. Like BERT, which is trained to predict missing words from context, the Marformer constructs a hidden-vector representation for each distribution p(Xi)p(X_i) and iteratively refines it through attention to other distributions p(Xj)p(X_j). Unlike generative approaches, the Marformer does not model the full joint distribution, requires no domain knowledge of the data-generating process, and makes all predictions in a single forward pass. We evaluate across three synthetic domains with missing data---Bayesian networks, discretized multivariate Gaussians, and structured annotation data. The Marformer can match or outperform classical missing-data methods, even when those methods are given the true model family and prior that generated the synthetic data. We also evaluate on a real annotation dataset, where the Marformer outperforms the evaluated baselines at the largest training size. In both cases, the Marformer is substantially faster than the evaluated generative baselines.