数据依赖事件概率估计的统一框架

# A Unified Framework for Probability Estimation of Data-Dependent Events
Source: [https://arxiv.org/html/2610.41244](https://arxiv.org/html/2610.41244)
Satyen KaleAffiliation:AppleVinod Raman††thanks:Work done when the author was an intern at Apple and a student at the University of Michigan, Ann Arbor\.Affiliation:University of Michigan, Ann ArborKunal TalwarAffiliation:AppleAmbuj TewariAffiliation:University of Michigan, Ann Arbor

###### Abstract

We study the general problem of estimatingD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\), the probability that an unknown distributionDDassigns to an event determined by a sampleSSofnni\.i\.d\. draws fromDDthrough a known mapping𝒢\\mathcal\{G\}\. The estimation algorithm knows𝒢\\mathcal\{G\}andSSbut does not have access to any additional samples fromDD\. 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 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 empirical estimator is identically zero and the leave\-one\-out estimator can fail\. 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\.

## 1Introduction

Estimating the probability mass assigned by an unknown distribution to a data\-dependent set is a basic problem that appears in several guises across probability, statistics, and learning theory\. In supervised learning, for example, a training sample determines a classifier, and hence determines an*error region*whose probability under the data distribution is the test error\. In classical missing mass estimation, the sample determines the set of unseen outcomes, and the goal is to estimate the probability of drawing a new point from this unseen set\. Although these examples are usually studied with different tools, they share a common structure: the target of estimation is not a fixed functional of the distribution alone, but a random quantity chosen as a function of the observed sample\.

The classical theory has developed powerful estimators for several important special cases\. Uniform\-convergence and stability arguments justify the empirical plug\-in estimator for many learning\-theoretic error estimates\. Good–Turing\-style estimators, and their leave\-one\-out variants, estimate the missing mass and relatedkk\-occurrence or heavy\-hitter functionals, even in regimes where the empirical plug\-in estimator is identically zero or badly biased\([Good, 1953](https://arxiv.org/html/2610.41244#bib.bib38);[McAllester and Schapire, 2000](https://arxiv.org/html/2610.41244#bib.bib57);[McAllester and Ortiz, 2003](https://arxiv.org/html/2610.41244#bib.bib56)\)\. These successes raise a natural broader question:When can one estimate the probability of an event that is itself chosen as a function ofthe observed sample?

In this work, we study this question through a unified framework for*data\-dependent probability estimation*\. Given i\.i\.d\. samplesS∼DnS\\sim D^\{n\}from an unknown distributionDDover a domain𝒳\\mathcal\{X\}, and a known mapping

𝒢:𝒳⋆→\{0,1\}𝒳\\mathcal\{G\}:\\mathcal\{X\}^\{\\star\}\\to\\\{0,1\\\}^\{\\mathcal\{X\}\}that assigns to each sample an event, specified by its\{0,1\}\\\{0,1\\\}\-valued indicator function on𝒳\\mathcal\{X\}\(and, more generally, a\[0,1\]\[0,1\]\-valued query\), the goal is to estimate the random quantityD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)\. The estimator is given𝒢\\mathcal\{G\}andSS, but not any additional fresh samples fromDD\. Thus the same sample both determines the event and is used to estimate its probability \(given fresh samples, the fraction of them that lies in𝒢⁡\(S\)\\mathcal\{G\}\(S\)would be an accurate estimate\)\. This formulation subsumes classical missing mass estimation, heavy\-hitter estimation, and test\-error estimation for learning algorithms\.

For the error of a classifier produced by a known learning algorithm, this question was recently posed by[Gastpar et al\. \(2024a\)](https://arxiv.org/html/2610.41244#bib.bib36);[Gastpar et al\. \(2024b\)](https://arxiv.org/html/2610.41244#bib.bib37), who refer to the existence of an accurate estimator of the error as*estimability*of the algorithm and use it to study when generalization bounds can be tight\. The error region of a classifier is a data\-dependent event and, conversely, every data\-dependent event is the error region of a classifier over a suitably labeled domain, so the notion of learning algorithm estimability and our notion of event estimatability point to the same fundamental problem\. In Section[3\.3](https://arxiv.org/html/2610.41244#S3.SS3)we give a detailed comparison and discuss some of the differences in the specific formulation we use\.

Our guiding example and the main application of our framework is estimation of the error of a predictor that combines structured generalization with memorization\. Such predictors are classical in learning theory, where memorizing exceptions is used to derive Occam \(compressing\) algorithms from PAC learning\([Board and Pitt, 1990](https://arxiv.org/html/2610.41244#bib.bib13);[Blumer et al\., 1987](https://arxiv.org/html/2610.41244#bib.bib12)\), and common in practice, where deployed models are augmented with local patches, residual memories, and edit modules populated by specific errors\([Kauschke and Fürnkranz, 2018](https://arxiv.org/html/2610.41244#bib.bib47);[Yang et al\., 2023](https://arxiv.org/html/2610.41244#bib.bib85);[Mitchell et al\., 2022](https://arxiv.org/html/2610.41244#bib.bib58)\)\. For such exception\-memorizing predictors both classical approaches to error estimation fail\. The empirical estimator is identically zero and therefore does not give useful information about the true error\. The leave\-one\-out estimate, in turn, requires retraining the base learnernntimes and comes with no guarantee when that learner is unstable\. The quantity to be estimated nonetheless has a clean description: the true error is exactly the*missing mass restricted to the error region of the base classifier*, the probability that a fresh point is unseen and falls into a region that was itself selected by the sample\. To address this problem, in Section[6](https://arxiv.org/html/2610.41244#S6), we formulate this more generally as an*adaptive missing mass estimation*task and give a hybrid estimator that combines the empirical and leave\-one\-out estimator\. We show that the generalization of the base classifier alone does not guarantee the accuracy of the hybrid estimator, but prove guarantees for it when either the error region of the base classifier has limited mutual information with the sample or the class of possible error regions has low VC dimension\.

Sample\-dependent regions whose missing mass is of interest arise well beyond this example\. A deployed language model may decline to answer prompts that fail a filter trained on the same data, so that hallucination in the sense of[Kalai and Vempala \(2024\)](https://arxiv.org/html/2610.41244#bib.bib45), the mass of facts unseen in training, must be measured on a region chosen by the data\. An analyst may ask how many distinct values remain unseen in a subpopulation defined by a predicate chosen after inspecting the sample\([Haas et al\., 1995](https://arxiv.org/html/2610.41244#bib.bib39);[Charikar et al\., 2000](https://arxiv.org/html/2610.41244#bib.bib18)\)\.

### 1\.1Overview

We summarize our contributions below\.

##### A framework for data\-dependent probability estimation\.

We define the estimatability of a mapping𝒢\\mathcal\{G\}in terms of the worst\-case mean squared error of an estimator ofD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)\(Definition[3\.2](https://arxiv.org/html/2610.41244#S3.Thmdefinition2)\), and extend the definition to\[0,1\]\[0,1\]\-valued queries, to randomized mappings, and to restricted, possibly sample\-size\-dependent, classes of distributions \(Definition[3\.3](https://arxiv.org/html/2610.41244#S3.Thmdefinition3)\)\. In Section[3\.3](https://arxiv.org/html/2610.41244#S3.SS3)we show how this framework captures several known problems, including estimation of the test error or risk of a trained predictor, the estimability of learning algorithms, missing mass and heavy\-hitter estimation, the Bayesian version of adaptive data analysis, point estimation of the targets of post\-selection inference, and estimation of the realized miscoverage of conformal prediction sets\. We discuss other related work in Section[2](https://arxiv.org/html/2610.41244#S2)\.

##### Empirical estimation\.

We observe that the error of the empirical estimator*is*the generalization error of𝒢\\mathcal\{G\}viewed as a learning algorithm\. Therefore every generalization bound for𝒢\\mathcal\{G\}\(e\.g\. one based on the VC dimension, algorithmic stability, differential privacy, max\-information, or mutual information\) is a sufficient condition for estimatability \(Section[4](https://arxiv.org/html/2610.41244#S4)\)\.

##### Leave\-one\-out estimation\.

We observe that the classical hypothesis\-stability bound for the leave\-one\-out estimate applies to any data\-dependent event, so that the leave\-one\-out estimator has vanishing mean squared error for every mapping that is stable under the deletion of one sample point \(Theorem[5\.1](https://arxiv.org/html/2610.41244#S5.Thmtheorem1)\)\. Computing the stability of specific mappings recovers the classical missing mass and heavy\-hitter guarantees, with the leave\-one\-out estimator coinciding with the Good–Turing estimator, and extends them to new structured examples \(Section[5](https://arxiv.org/html/2610.41244#S5)\)\. Specifically, for every neighborhood function on the domain, the mass of the union of the neighborhoods of the sample points isO⁡\(1/n\)O\(1/n\)\-estimatable, although this set can be much larger than the sample \(Theorem[5\.3](https://arxiv.org/html/2610.41244#S5.Thmtheorem3)\)\. The same holds for the intersection of these neighborhoods, which includes the missing mass, and for the seen and the unseen parts of a fixed region\. For the union of the neighborhoods of the points that occur exactlykktimes in the sample, we obtain the rateO⁡\(\(k\+log⁡n\)/n\)O\(\(k\+\\log n\)/n\), again for every neighborhood function \(Theorem[5\.7](https://arxiv.org/html/2610.41244#S5.Thmtheorem7)\)\.

##### Adaptive missing mass estimation\.

As the main application of our framework, in Section[6](https://arxiv.org/html/2610.41244#S6)we formulate the problem of*adaptive missing mass estimation*\(Definition[6\.2](https://arxiv.org/html/2610.41244#S6.Thmdefinition2)\) and propose a hybrid estimator for it\. In this problem a selection rule chooses a region of the domain using the sample \(such as the error region of the base classifier\), and the goal is to estimate the missing mass of the selected region\. Our estimator is based on writing this missing mass as the difference between the mass of the selected region and the mass of its part that is seen in the sample\. We estimate the first term empirically \(for the error region of a base classifier this gives its training error\) and the second by the leave\-one\-out estimator in which the region is held fixed at its value on the full sample\. The difference of the two estimates is the fraction of the sample made up of points that lie in the selected region and occur in the sample exactly once\. Thus our estimator is the Good–Turing estimator restricted to the selected region \(Definition[6\.3](https://arxiv.org/html/2610.41244#S6.Thmdefinition3)\)\. For the error of an exception\-memorizing classifier, computing it requires training the base classifier once rather thannntimes\.

For a region fixed in advance, the restricted Good–Turing estimator has mean squared errorO⁡\(1/n\)O\(1/n\)\(Corollary[5\.5](https://arxiv.org/html/2610.41244#S5.Thmtheorem5)\)\. However, here the region is selected using the same sample on which the estimator is evaluated\. We show that this dependence can make the hybrid inaccurate even when the empirical mass of the selected region estimates its true mass with mean squared errorO⁡\(1/n\)O\(1/n\)under every distribution \(Proposition[6\.2](https://arxiv.org/html/2610.41244#S6.Thmtheorem2)\)\.

At the same time, we show that the hybrid is accurate whenever the selected region has limited mutual information with the sample or the class of possible regions has low VC dimension\. Specifically, its mean squared error isO⁡\(\(I\+1\)/n\)O\(\(I\+1\)/n\), whereIIis the mutual information between the selected region and the sample, andO⁡\(d​log⁡\(n/d\)/n\)O\(d\\log\(n/d\)/n\), whereddis the VC dimension of the class of possible regions \(with no restriction on how the region is chosen from this class\)\. See Theorem[6\.3](https://arxiv.org/html/2610.41244#S6.Thmtheorem3)for a formal statement\.

To prove the bound in terms of the mutual information we first show that for a region fixed in advance the error of the restricted Good–Turing estimator is sub\-Gaussian at scale1/n1/\\sqrt\{n\}\. The restricted Good–Turing estimate concentrates by McDiarmid’s inequality, and the missing mass of the region by an extension of the results of[McAllester and Ortiz \(2003\)](https://arxiv.org/html/2610.41244#bib.bib56)\. We then use the Donsker–Varadhan variational inequality to decouple the selected region from the sample at the cost of an additiveO⁡\(I/n\)O\(I/n\)term\. To prove the bound in terms of the VC dimension we replace the selected region by a nearby element of a suitable finite cover of the class of possible regions\. We control the effect of the replacement using uniform convergence over the symmetric differences of possible regions and a union bound over the cover together which, again, relies on the concentration of the restricted Good\-Turing estimator\.

As a consequence, we get that the error of an exception\-memorizing learner is estimatable whenever the base learner’s hypothesis class has bounded VC dimension \(Corollary[6\.4](https://arxiv.org/html/2610.41244#S6.Thmtheorem4)\), even though the empirical estimator is identically zero\. Specifically, if the base learner outputs binary classifiers from a class of VC dimensiondd, then the hybrid estimates the error of the memorizing learner with mean squared errorO⁡\(d​log⁡\(n/d\)/n\)O\(d\\log\(n/d\)/n\)under every distribution and every labeling of the data \(which need not belong to the class\)\. We also give an example of a learner for which the hybrid has errorO⁡\(1/n\)O\(1/n\)while both standard estimators have constant error \(Proposition[C\.1](https://arxiv.org/html/2610.41244#A3.Thmtheorem1)\)\.

##### Limits of estimatability\.

In Section[7](https://arxiv.org/html/2610.41244#S7)we give three constructions of data\-dependent events that cannot be consistently estimated by any procedure\. The first of them is new and is a particularly simple instance of post\-selection inference\. Here the event consists of the points that are equal to11at the coordinate with the largest empirical mean \(among2n\+12^\{n\}\+1binary coordinates\), and its mass is the true mean of the selected coordinate\. We consider distributions in which one coordinate is always11and all other coordinates are independent and uniform\. With constant probability, exactly one other coordinate is then also equal to11on all sample points\. If the special coordinate is chosen uniformly at random, then given such a sample the two coordinates are equally likely to be the special one\. The true mean of the selected coordinate is then equally likely to be11and1/21/2\. Thus no estimator achieves mean squared error below1/641/64\(Theorem[7\.1](https://arxiv.org/html/2610.41244#S7.Thmtheorem1)\)\.

The other two constructions are close to those of[Gastpar et al\. \(2024a\)](https://arxiv.org/html/2610.41244#bib.bib36);[Gastpar et al\. \(2024b\)](https://arxiv.org/html/2610.41244#bib.bib37)and use the same approach on progressively smaller domains\. The last of these has quadratic innnsize and also shows that*finiteness*of the VC dimension of the image class does not suffice\. Its image class hasVC⁡\(ℋn\)≤n\+1\\operatorname\{VC\}\(\\mathcal\{H\}\_\{n\}\)\\leq n\+1, whereas the empirical estimator is consistent as soon asVC⁡\(ℋn\)=o⁡\(n\)\\operatorname\{VC\}\(\\mathcal\{H\}\_\{n\}\)=o\(n\)\(Corollary[4\.1](https://arxiv.org/html/2610.41244#S4.Thmtheorem1)\)\.

## 2Related Work

Estimating the test error of a data\-trained predictor has a long history in statistical learning theory; see the textbooks\([Shalev\-Shwartz and Ben\-David, 2014](https://arxiv.org/html/2610.41244#bib.bib70);[Mohri et al\., 2012](https://arxiv.org/html/2610.41244#bib.bib59);[Anthony and Bartlett, 2009](https://arxiv.org/html/2610.41244#bib.bib4)\)for an overview\. Several of the problems related to ours, namely prediction\-error estimation, missing mass estimation, adaptive data analysis, post\-selection inference, and conformal prediction, are easier to compare with our setting once our definitions are in place, and we describe how each of them maps to our framework in Section[3\.3](https://arxiv.org/html/2610.41244#S3.SS3)\. In this section we discuss the lines of work most closely related to our results\.

The closest line of work to ours is the study of*estimability*by[Gastpar et al\. \(2024a\)](https://arxiv.org/html/2610.41244#bib.bib36);[Gastpar et al\. \(2024b\)](https://arxiv.org/html/2610.41244#bib.bib37)\. Motivated by the empirical finding that many of the generalization bounds proposed for neural networks are far from tight\([Jiang et al\., 2020](https://arxiv.org/html/2610.41244#bib.bib44)\),[Gastpar et al\. \(2024a\)](https://arxiv.org/html/2610.41244#bib.bib36)observe that a generalization bound that is tight for every distribution is an estimator of the test error, and define a hypothesis class or a learning algorithm to be estimable if such an estimator exists\. They show that for a fixed, known algorithm there may exist a trade\-off between the algorithm’s ability to learn a class and the estimability of its error\. Specifically, this trade\-off applies to algorithms that learn parity functions and linear functions over finite fields\.[Gastpar et al\. \(2024b\)](https://arxiv.org/html/2610.41244#bib.bib37)then study which algorithms are estimable\. They give lower bounds for algorithms with an inductive bias towards a class of nearly orthogonal functions, or towards a suitable subset of a class of VC dimensionddwhenn≤d/10n\\leq\\sqrt\{d\}/10\. They also show that an algorithm that is stable under the deletion of a block ofkksample points is estimable via a holdout estimator that trains on the remainingn−kn\-kpoints\. Their algorithm\-dependent notion of estimability coincides with ours when specialized to the error regions of classifiers, up to the error criterion \(Section[3\.3](https://arxiv.org/html/2610.41244#S3.SS3)\)\. In contrast, the main focus of our work is the unified framework that naturally incorporates a variety of existing problems as well as new upper bounds that rely on tools developed for different problems\.

The estimation of the error of a learning algorithm via leave\-one\-out and cross\-validation has been analyzed through algorithmic stability since the work of[Rogers and Wagner \(1978\)](https://arxiv.org/html/2610.41244#bib.bib68)and[Devroye and Wagner \(1979\)](https://arxiv.org/html/2610.41244#bib.bib20)\.[Kearns and Ron \(1999\)](https://arxiv.org/html/2610.41244#bib.bib48)give sanity\-check bounds for the leave\-one\-out estimate under hypothesis stability,[Bousquet and Elisseeff \(2002\)](https://arxiv.org/html/2610.41244#bib.bib15)relate several notions of stability to generalization and to the leave\-one\-out estimate, and[Kale et al\. \(2011\)](https://arxiv.org/html/2610.41244#bib.bib46)and[Kumar et al\. \(2013\)](https://arxiv.org/html/2610.41244#bib.bib49)bound the error ofkk\-fold cross\-validation via mean\-square and loss stability\.

The study of missing mass estimation dates back to the work of[Good \(1953\)](https://arxiv.org/html/2610.41244#bib.bib38)and more recently[McAllester and Schapire \(2000\)](https://arxiv.org/html/2610.41244#bib.bib57)\. Refinements of the missing\-mass concentration bounds of[McAllester and Schapire \(2000\)](https://arxiv.org/html/2610.41244#bib.bib57);[McAllester and Ortiz \(2003\)](https://arxiv.org/html/2610.41244#bib.bib56)appear in[Berend and Kontorovich \(2012\)](https://arxiv.org/html/2610.41244#bib.bib9);[Berend and Kontorovich \(2013\)](https://arxiv.org/html/2610.41244#bib.bib10), and[Maurer \(2022\)](https://arxiv.org/html/2610.41244#bib.bib55)extends them to metric spaces\. A parallel line of work investigates minimax rates for missing mass estimation\. Near\-tight upper and lower bounds were developed in\([Rajaraman et al\., 2017](https://arxiv.org/html/2610.41244#bib.bib65);[Acharya et al\., 2018](https://arxiv.org/html/2610.41244#bib.bib1)\), alongside information\-theoretic lower bounds based on classical techniques such as Fano’s and Le Cam’s methods\([Paninski, 2003](https://arxiv.org/html/2610.41244#bib.bib64);[Fano, 1966](https://arxiv.org/html/2610.41244#bib.bib28);[Le Cam, 1973](https://arxiv.org/html/2610.41244#bib.bib50);[Yu, 1997](https://arxiv.org/html/2610.41244#bib.bib87)\)\. Complementary work by[Valiant and Valiant \(2011\)](https://arxiv.org/html/2610.41244#bib.bib78);[Valiant and Valiant \(2017\)](https://arxiv.org/html/2610.41244#bib.bib79)studies the estimation of the unseen portion of the distribution, leading to near\-optimal estimators for entropy, support size, and other distributional properties\. We refer the reader to\([Orlitsky et al\., 2016](https://arxiv.org/html/2610.41244#bib.bib63);[Balocchi et al\., 2026](https://arxiv.org/html/2610.41244#bib.bib6)\)for a more comprehensive overview of works related to missing\-mass, unseen\-species, and support\-size estimation\.

Our framework is motivated by and explores data\-dependent estimation tasks that require combining distinct estimation principles\. A number of existing works on generalization have relied on combinations of different approaches to generalization:[Foster et al\. \(2019\)](https://arxiv.org/html/2610.41244#bib.bib35)combine hypothesis\-set stability with complexity bounds for data\-dependent hypothesis sets, while[Rivasplata et al\. \(2018\)](https://arxiv.org/html/2610.41244#bib.bib66),[Dziugaite and Roy \(2018\)](https://arxiv.org/html/2610.41244#bib.bib24), and[Awasthi et al\. \(2020\)](https://arxiv.org/html/2610.41244#bib.bib5)develop PAC\-Bayes guarantees for distribution\- or sample\-dependent priors using various notions of stability such as differential privacy\. See also\([Hellström et al\., 2025](https://arxiv.org/html/2610.41244#bib.bib43)\)for a broader survey of information\-theoretic and PAC\-Bayes approaches to generalization\.

## 3Preliminaries

### 3\.1Notation

Let𝒳\\mathcal\{X\}be a countable space, and letΔ​𝒳\\Delta\\mathcal\{X\}denote the set of all distributions over𝒳\\mathcal\{X\}\. For a setA⊆𝒳A\\subseteq\\mathcal\{X\}, we useAcA^\{c\}to denote its complement and\|A\|\|A\|to denote its cardinality\. For a distributionD∈Δ​𝒳D\\in\\Delta\\mathcal\{X\}and a subsetA⊆𝒳A\\subseteq\\mathcal\{X\}, we useD⁡\(A\)D\(A\)to denote the cumulative mass thatDDplaces onAA\. That is,D\(A\):=ℙx∼D\[x∈A\]D\(A\):=\\mathop\{\\mathbb\{P\}\}\_\{x\\sim D\}\\left\[x\\in A\\right\]\. We also define sets using their indicator functions and more generally consider real\-valued functions on𝒳\\mathcal\{X\}\. For a functionh:𝒳→ℝh:\\mathcal\{X\}\\to\\mathbb\{R\}, we defineD⁡\(h\)=𝔼x∼D\[h⁡\(x\)\]D\(h\)=\\mathop\{\\mathbb\{E\}\}\_\{x\\sim D\}\[h\(x\)\]\. For a single pointxxwe abbreviateD⁡\(\{x\}\)D\(\\\{x\\\}\)byD⁡\(x\)D\(x\)\.

As usual, forn∈ℕn\\in\\mathbb\{N\}, we define\[n\]:=\{1,…,n\}\.\[n\]:=\\\{1,\\dots,n\\\}\.We define𝒳⋆\\mathcal\{X\}^\{\\star\}as the set of all finite sequences of examples in𝒳\\mathcal\{X\}\. We denote a sample ofnnexamplesx1,…,xn∈𝒳x\_\{1\},\\dots,x\_\{n\}\\in\\mathcal\{X\}bySS, and, abusing notation, also writeSSorT⁡\(S\)T\(S\)for the set\{x1,…,xn\}\\\{x\_\{1\},\\dots,x\_\{n\}\\\}of its points \(so thatScS^\{c\},S∩AS\\cap A, and\|S\|\|S\|refer to that set\)\. A mapping𝒢\\mathcal\{G\}defined on𝒳⋆\\mathcal\{X\}^\{\\star\}is*symmetric*if𝒢⁡\(S\)=𝒢⁡\(π​S\)\\mathcal\{G\}\(S\)=\\mathcal\{G\}\(\\pi S\)for every sampleSSand every permutationπ\\piof its coordinates, i\.e\. if𝒢⁡\(S\)\\mathcal\{G\}\(S\)depends onSSonly through its multiset of points\. Unless stated otherwise, the mappings considered in this paper are symmetric\. For a sampleS∼DnS\\sim D^\{n\}and indexi∈\[n\]i\\in\[n\], we writeS−iS^\{\-i\}for the samplex1,…,xi−1,xi\+1,…,xnx\_\{1\},\\dots,x\_\{i\-1\},x\_\{i\+1\},\\ldots,x\_\{n\}with theiith point removed\. In particular,S−nS^\{\-n\}denotes the sample with its last point removed\. The sample sizennis always clear from context\.

### 3\.2Probability Estimation

In probability estimation, one aims to estimate the mass placed by an*unknown*distributionD∈Δ​𝒳D\\in\\Delta\\mathcal\{X\}on a*known*, potentially sample\-dependent, region using i\.i\.d\. samples fromDD\. Throughout the paper, we use𝒢:𝒳⋆→\{0,1\}𝒳\\mathcal\{G\}:\\mathcal\{X\}^\{\\star\}\\rightarrow\\\{0,1\\\}^\{\\mathcal\{X\}\}to denote a known mapping that assigns to each sampleSSan indicator function on𝒳\\mathcal\{X\}\. We writef:=𝒢⁡\(S\)f:=\\mathcal\{G\}\(S\)for the resulting query andf⁡\(x\)f\(x\)for its value at a pointx∈𝒳x\\in\\mathcal\{X\}\. We identify the indicatorffwith the event \(subset\)\{x∈𝒳:f⁡\(x\)=1\}\\\{x\\in\\mathcal\{X\}:f\(x\)=1\\\}it defines, and freely use set operations on the outputs of𝒢\\mathcal\{G\}whenever convenient\. Both𝒳\\mathcal\{X\}and𝒢\\mathcal\{G\}are assumed known, and the target of estimation is the induced mass

D⁡\(𝒢⁡\(S\)\)=D⁡\(f\)=𝔼x∼D\[f⁡\(x\)\],D\(\\mathcal\{G\}\(S\)\)=D\(f\)=\\mathop\{\\mathbb\{E\}\}\_\{x\\sim D\}\\left\[f\(x\)\\right\],which for an event equalsℙx∼D\[x∈𝒢\(S\)\]\\mathop\{\\mathbb\{P\}\}\_\{x\\sim D\}\\left\[x\\in\\mathcal\{G\}\(S\)\\right\]\. More generally, we also allow𝒢\\mathcal\{G\}to output a functionf=𝒢⁡\(S\)f=\\mathcal\{G\}\(S\)from𝒳\\mathcal\{X\}to\[0,1\]\[0,1\], i\.e\. a*statistical query*or a \(bounded\) loss function\.

We first define a probability estimator for the simpler case of deterministic mappings𝒢\\mathcal\{G\}\. A probability estimatorp^\\hat\{p\}, defined formally in Definition[3\.1](https://arxiv.org/html/2610.41244#S3.Thmdefinition1), maps a sample to a value in\[0,1\]\.\[0,1\]\.In this paper, we will always assumep^\\hat\{p\}is deterministic, though all our definitions of estimatability can be naturally extended to randomized estimators\. Note that replacing a randomizedp^\\hat\{p\}by its expectation over its internal randomness can only decrease the mean squared error\.

###### Definition 3\.1\(Probability Estimator\)\.

A probability estimatorp^:𝒳⋆→\[0,1\]\\hat\{p\}:\\mathcal\{X\}^\{\\star\}\\rightarrow\[0,1\]is a function that maps a finite training sampleS∈𝒳⋆S\\in\\mathcal\{X\}^\{\\star\}to a number in\[0,1\]\[0,1\]\.

Given knowledge of𝒢\\mathcal\{G\}\(but notDD\), our goal is to find an estimatorp^\\hat\{p\}such thatp^​\(S\)\\hat\{p\}\(S\)andD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)are close whenS∼DnS\\sim D^\{n\}is an i\.i\.d\. draw\. We will focus on the mean\-squared error \(MSE\) of the estimator both for concreteness and because it is the most common notion of error in the literature\.

###### Definition 3\.2\(Estimatability\)\.

For an integernnandα∈\[0,1\]\\alpha\\in\[0,1\], a mapping𝒢:𝒳⋆→\{0,1\}𝒳\\mathcal\{G\}:\\mathcal\{X\}^\{\\star\}\\rightarrow\\\{0,1\\\}^\{\\mathcal\{X\}\}isα\\alpha\-*estimatable withnnsamples*if there exists an estimatorp^\\hat\{p\}such that

supD∈Δ​𝒳𝔼S∼Dn\[\(p^​\(S\)−D⁡\(𝒢⁡\(S\)\)\)2\]≤α\.\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\left\[\(\\hat\{p\}\(S\)\-D\(\\mathcal\{G\}\(S\)\)\)^\{2\}\\right\]\\leq\\alpha\\ \.

When the sample size is clear from the context we simply say that𝒢\\mathcal\{G\}isα\\alpha\-estimatable, and we write that𝒢\\mathcal\{G\}isα⁡\(n\)\\alpha\(n\)\-estimatable for a functionα⁡\(⋅\)\\alpha\(\\cdot\)if it isα⁡\(n\)\\alpha\(n\)\-estimatable withnnsamples for everynn\. We also allow the problem itself to be parameterized bynn, that is𝒢=\{𝒢n\}n=1∞\\mathcal\{G\}=\\\{\\mathcal\{G\}\_\{n\}\\\}\_\{n=1\}^\{\\infty\}where𝒢n:𝒳n⋆→\{0,1\}𝒳n\\mathcal\{G\}\_\{n\}:\\mathcal\{X\}\_\{n\}^\{\\star\}\\rightarrow\\\{0,1\\\}^\{\\mathcal\{X\}\_\{n\}\}is defined over a domain𝒳n\\mathcal\{X\}\_\{n\}that may depend onnn\. We say that𝒢\\mathcal\{G\}is*estimatable*if𝒢n\\mathcal\{G\}\_\{n\}isαn\\alpha\_\{n\}\-estimatable withnnsamples for some sequenceαn→0\\alpha\_\{n\}\\to 0asn→∞n\\to\\infty, and*non\-estimatable*otherwise\. This definition can be easily extended to other notions of error, such as mean absolute deviation \(MAD\) or a high\-probability tail bound\.

In many specific learning problems one is only interested in the performance of the estimator over a restricted class of input distributions𝒟\\mathcal\{D\}\(as opposed to all distributions over the domain\)\. The definition of estimation error and estimatability of mappings naturally extends to this class\-specific setting by taking the supremum overD∈𝒟D\\in\\mathcal\{D\}\. In addition, in many practical applications the event or query is generated by a randomized algorithm \(such as a randomly initialized learning algorithm\)\. In this case, we can extend the definition of estimatability to randomized mappings𝒢\\mathcal\{G\}by allowing the estimator to depend on the randomness of𝒢\\mathcal\{G\}as well\. We incorporate these generalizations into the definition below\.

###### Definition 3\.3\(General Estimatability for Randomized Mappings\)\.

Let𝒟=\(𝒟n\)n∈ℕ\\mathcal\{D\}=\(\\mathcal\{D\}\_\{n\}\)\_\{n\\in\\mathbb\{N\}\}be a family of classes of distributions over𝒳\\mathcal\{X\}, one for each sample size\. A randomized mapping is defined by a function𝒢:𝒳⋆×Ω→\[0,1\]𝒳\\mathcal\{G\}:\\mathcal\{X\}^\{\\star\}\\times\\Omega\\rightarrow\[0,1\]^\{\\mathcal\{X\}\}, whereΩ\\Omegais the space of random seeds together with a distributionRRoverΩ\\Omega\. For an integernnandα∈\[0,1\]\\alpha\\in\[0,1\], the mapping𝒢\\mathcal\{G\}is then said to beα\\alpha\-estimatable over𝒟\\mathcal\{D\}withnnsamples if there exists an estimatorp^:𝒳⋆×Ω→\[0,1\]\\hat\{p\}:\\mathcal\{X\}^\{\\star\}\\times\\Omega\\rightarrow\[0,1\]such that

supD∈𝒟n𝔼S∼Dn,r∼R\[\(p^​\(S,r\)−D⁡\(𝒢⁡\(S,r\)\)\)2\]≤α\.\\sup\_\{D\\in\\mathcal\{D\}\_\{n\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\},r\\sim R\}\\left\[\(\\hat\{p\}\(S,r\)\-D\(\\mathcal\{G\}\(S,r\)\)\)^\{2\}\\right\]\\leq\\alpha\\ \.

In this paper, we are interested in understanding general conditions under which functions𝒢:𝒳⋆→\{0,1\}𝒳\\mathcal\{G\}:\\mathcal\{X\}^\{\\star\}\\rightarrow\\\{0,1\\\}^\{\\mathcal\{X\}\}are estimatable\. We now discuss several known choices of𝒢\\mathcal\{G\}arising in specific problems and their estimatability properties\.

### 3\.3Relationship to Known Estimation Problems

##### Prediction\-error and loss estimation\.

Estimating the error of a data\-trained predictor is a prototypical instance of our question\. If a learning algorithm maps a labeled sampleSSto a classifierhSh\_\{S\}, then𝒢⁡\(S\)=\{\(x,y\):hS​\(x\)≠y\}\\mathcal\{G\}\(S\)=\\\{\(x,y\):h\_\{S\}\(x\)\\neq y\\\}is the \(data\-dependent\) error region andD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)is its test error; for a bounded loss, taking𝒢⁡\(S\)\\mathcal\{G\}\(S\)to be the corresponding loss function makesD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)the risk\. Classical generalization theory estimates this quantity by the training error whenever the induced class of error regions has low complexity, e\.g\. bounded VC dimension\([Vapnik and Chervonenkis, 1971](https://arxiv.org/html/2610.41244#bib.bib80)\)or bounded Rademacher complexity\([Boucheron et al\., 2013](https://arxiv.org/html/2610.41244#bib.bib14)\)\. In some regimes where the empirical estimator fails, cross\-validation, leave\-one\-out, and bootstrap methods have been shown to estimate risk\([Stone, 1974](https://arxiv.org/html/2610.41244#bib.bib74);[Devroye and Wagner, 1979](https://arxiv.org/html/2610.41244#bib.bib20);[Kearns and Ron, 1999](https://arxiv.org/html/2610.41244#bib.bib48);[Efron, 1983](https://arxiv.org/html/2610.41244#bib.bib25)\)\.

##### Estimability of learning algorithms\.

The question of when the test error of the classifier produced by a known learning algorithm can be estimated from the training sample alone was posed by[Gastpar et al\. \(2024a\)](https://arxiv.org/html/2610.41244#bib.bib36)and studied further by[Gastpar et al\. \(2024b\)](https://arxiv.org/html/2610.41244#bib.bib37)\. In their terminology, a learning algorithm𝒜\\mathcal\{A\}is\(ε,δ,n\)\(\\varepsilon,\\delta,n\)\-estimable with respect to a class of distributions if there is an estimatorEE\(which may depend on𝒜\\mathcal\{A\}\) such that\|E⁡\(S\)−D⁡\(𝒢⁡\(S\)\)\|≤ε\|E\(S\)\-D\(\\mathcal\{G\}\(S\)\)\|\\leq\\varepsilonwith probability at least1−δ1\-\\deltaoverS∼DnS\\sim D^\{n\}for every distributionDDin the class, where𝒢⁡\(S\)\\mathcal\{G\}\(S\)is the error region of𝒜⁡\(S\)\\mathcal\{A\}\(S\)\(or, for a bounded loss, its loss function\)\.[Gastpar et al\. \(2024b\)](https://arxiv.org/html/2610.41244#bib.bib37)also consider the version of this guarantee that holds on average over a uniformly random distribution from a finite collection, and its mean\-squared\-error analogue\. Since𝒜\\mathcal\{A\}is known, estimability with respect to all distributions is estimatability of the mapping𝒢\\mathcal\{G\}in the sense of Definition[3\.2](https://arxiv.org/html/2610.41244#S3.Thmdefinition2), up to the choice of the error criterion\. Conversely, for any mapping𝒢\\mathcal\{G\}over𝒳\\mathcal\{X\}, consider the labeled domain𝒳×\{0,1\}\\mathcal\{X\}\\times\\\{0,1\\\}with distributions supported on the label00, and the learning algorithm that on a sampleSSoutputs the classifierx↦𝒢​\(S\)​\(x\)x\\mapsto\\mathcal\{G\}\(S\)\(x\); its error region is𝒢⁡\(S\)×\{0\}\\mathcal\{G\}\(S\)\\times\\\{0\\\}, so estimating its error is the same problem as estimatingD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)\(for a\[0,1\]\[0,1\]\-valued query the same identification goes through the lossℓ⁡\(q,x\)=q⁡\(x\)\\ell\(q,x\)=q\(x\)of Section[4](https://arxiv.org/html/2610.41244#S4)\)\. Thus the two frameworks describe the same class of problems, and we keep the term*estimatability*for Definition[3\.2](https://arxiv.org/html/2610.41244#S3.Thmdefinition2), which applies to mappings and uses the mean squared error\. The formulation in terms of events makes it natural to consider missing mass and its structured variants alongside prediction error, and to combine the estimators for them, which is the focus of this work\.

##### Missing mass estimation\.

The most classical special case is*missing mass*: taking𝒢⁡\(S\)=Sc\\mathcal\{G\}\(S\)=S^\{c\}, the targetD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)is the probability that a fresh sample is not present inSS\. Here the empirical estimator is identically zero, yet the Good–Turing estimator and its refinements estimate the missing mass at mean\-squared\-error rateΘ⁡\(1/n\)\\Theta\(1/n\): the Good–Turing bias isO⁡\(1/n\)O\(1/n\)\([Good, 1953](https://arxiv.org/html/2610.41244#bib.bib38)\), with high\-probability guarantees given by[McAllester and Schapire \(2000\)](https://arxiv.org/html/2610.41244#bib.bib57), and the minimax mean\-squared error isΘ⁡\(1/n\)\\Theta\(1/n\)\([Rajaraman et al\., 2017](https://arxiv.org/html/2610.41244#bib.bib65);[Acharya et al\., 2018](https://arxiv.org/html/2610.41244#bib.bib1)\)\. More generally, the mass of thekk\-occurrence \(heavy\-hitter\) set𝒢\(S\)=\{x∈𝒳:∑i=1n𝟏\{xi=x\}=k\}\\mathcal\{G\}\(S\)=\\\{x\\in\\mathcal\{X\}:\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{x\_\{i\}=x\\\}=k\\\}isO⁡\(k/n\)O\(k/n\)\-estimatable\([McAllester and Schapire, 2000](https://arxiv.org/html/2610.41244#bib.bib57)\)\. The leave\-one\-out estimator of Section[5](https://arxiv.org/html/2610.41244#S5)is based on these results and extends them to several additional structures\.

##### Adaptive data analysis\.

In adaptive data analysis \(ADA\), a curator holding a sampleS∼DnS\\sim D^\{n\}answers a sequence of statistical queriesh:𝒳→\[0,1\]h:\\mathcal\{X\}\\to\[0,1\]posed adaptively by an analyst, returning estimates of each valueD⁡\(h\)=𝔼x∼D\[h⁡\(x\)\]D\(h\)=\\mathop\{\\mathbb\{E\}\}\_\{x\\sim D\}\[h\(x\)\]\([Dwork et al\., 2014](https://arxiv.org/html/2610.41244#bib.bib21);[Dwork et al\., 2015a](https://arxiv.org/html/2610.41244#bib.bib22);[Dwork et al\., 2015b](https://arxiv.org/html/2610.41244#bib.bib23);[Bassily et al\., 2016](https://arxiv.org/html/2610.41244#bib.bib7);[Russo and Zou, 2016](https://arxiv.org/html/2610.41244#bib.bib69);[Feldman and Steinke, 2018](https://arxiv.org/html/2610.41244#bib.bib30)\)\. Our targetD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)is the value of a single such query,h=𝒢⁡\(S\)h=\\mathcal\{G\}\(S\)\. In the positive direction, the machinery developed for ADA transfers to our setting directly\. That machinery controls the*generalization gap*𝔼S\|1n​∑i=1n𝒢⁡\(S\)​\(xi\)−D⁡\(𝒢⁡\(S\)\)\|\\mathop\{\\mathbb\{E\}\}\_\{S\}\\bigl\|\\tfrac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathcal\{G\}\(S\)\(x\_\{i\}\)\-D\(\\mathcal\{G\}\(S\)\)\\bigr\|between the empirical answer and its true value by limiting how strongly the query𝒢⁡\(S\)\\mathcal\{G\}\(S\)depends on the sampleSS\. The main techniques are:

- •Differential privacy\.If𝒢⁡\(⋅\)\\mathcal\{G\}\(\\cdot\)is\(ε,δ\)\(\\varepsilon,\\delta\)\-differentially private as a function ofSS, its output is insensitive to any single sample point, and the generalization gap is controlled byε\\varepsilonandδ\\delta\([Dwork et al\., 2014](https://arxiv.org/html/2610.41244#bib.bib21)\); tight and variance\-adaptive versions of this transfer theorem were given by[Bassily et al\. \(2016\)](https://arxiv.org/html/2610.41244#bib.bib7);[Feldman and Steinke \(2018\)](https://arxiv.org/html/2610.41244#bib.bib30)\.
- •Max\-information\.More generally, a bound on the \(approximate\) max\-informationI∞βI\_\{\\infty\}^\{\\beta\}between the sampleSSand the query𝒢⁡\(S\)\\mathcal\{G\}\(S\)controls the gap\([Dwork et al\., 2015a](https://arxiv.org/html/2610.41244#bib.bib22);[Rogers et al\., 2016](https://arxiv.org/html/2610.41244#bib.bib67)\)\.
- •Mutual information\.A bound on the mutual informationI⁡\(S,𝒢⁡\(S\)\)I\(S;\\mathcal\{G\}\(S\)\)between the sample and the query likewise controls the gap: the expected*signed*gap is at mostI⁡\(S,𝒢⁡\(S\)\)/\(2​n\)\\sqrt\{I\(S;\\mathcal\{G\}\(S\)\)/\(2n\)\}\([Russo and Zou, 2016](https://arxiv.org/html/2610.41244#bib.bib69);[Xu and Raginsky, 2017](https://arxiv.org/html/2610.41244#bib.bib84);[Feldman and Steinke, 2018](https://arxiv.org/html/2610.41244#bib.bib30)\)\.

Each of these is a sufficient condition for the empirical estimator to accurately estimateD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)\.

At the same time the requirements in ADA are incomparable to those of our setting\. Adaptive data analysis requires a guarantee that holds for*every*distributionDDand*every*analyst; equivalently, the analyst may be assumed to knowDDbut not the realized sampleSS, so the query it produces is independent ofSS\(it can depend onSSonly indirectly, through the curator’s earlier answers\)\. However in estimatability, the mapping𝒢\\mathcal\{G\}is fixed and known and its output𝒢⁡\(S\)\\mathcal\{G\}\(S\)depends onSS*directly*, and the estimator is given both𝒢\\mathcal\{G\}andSS\. Thus the basic ADA setting does not itself fall under our notion of estimatability\. In particular, while positive results transfer,*hardness does not*: a lower bound for adaptive data analysis\([Hardt and Ullman, 2014](https://arxiv.org/html/2610.41244#bib.bib40);[Steinke and Ullman, 2015](https://arxiv.org/html/2610.41244#bib.bib72)\)does not imply a lower bound for estimatability, which is why the impossibility results of Section[7](https://arxiv.org/html/2610.41244#S7)require constructions of their own rather than being inherited from ADA\.

##### Bayesian adaptive data analysis\.

[Elder \(2016a\)](https://arxiv.org/html/2610.41244#bib.bib26)proposed a Bayesian version of ADA in which the analyst and the curator both receive a prior over distributions on𝒳\\mathcal\{X\}, and the data distributionDDis drawn from this prior \(and is unknown to both\)\. The curator wins if, with probability at least1−δ1\-\\delta, all of its answers are withinε\\varepsilonof the values of the queries, where the probability is also over the draw ofDD\([Elder, 2016a](https://arxiv.org/html/2610.41244#bib.bib26), Section 2\)\.[Nissim et al\. \(2023\)](https://arxiv.org/html/2610.41244#bib.bib61)study a balanced model in which the distribution is chosen by a sampler that passes no information to the analyst\. They note that when the sampler is publicly known, the two models are equivalent from an information\-theoretic point of view\. By a standard minimax argument, a curator that wins against every analyst exists for every prior if and only if for every analyst there is a curator that wins against it for every distributionDD\(the curator may depend on the strategy of the analyst but not on its random bits\)\. Indeed, for a fixed prior the minimax theorem allows the curator to be chosen after the analyst, and for a fixed analyst it equates the worst case over priors with the worst case over distributions \(for a finite domain and finitely many possible queries and answers\)\. We are not aware of this equivalence being stated in the literature\. For a known analyst and fixed answering rules of the curator for the firstj−1j\-1queries, thejj\-th query is a known randomized function of the sample whose value the curator needs to estimate for every distribution\.111Strictly speaking, Definition[3\.3](https://arxiv.org/html/2610.41244#S3.Thmdefinition3)gives the estimator the random bits of the analyst, which the curator does not see\. This does not change the minimax error since, for every prior, the conditional expectation of the value of the query given the sample and the random bits depends only on the sample and the query\.Thus our framework \(Definition[3\.3](https://arxiv.org/html/2610.41244#S3.Thmdefinition3)\) captures this setting, one query at a time\. For Dirichlet priors,[Elder \(2016b\)](https://arxiv.org/html/2610.41244#bib.bib27)shows that the curator that answers with the posterior mean matches the statistical guarantees of the static case\. Beyond such specific priors, we are not aware of positive results for this setting that are stronger than those for general ADA\. The negative results are either purely computational\([Nissim et al\., 2023](https://arxiv.org/html/2610.41244#bib.bib61)\)or apply only to restricted families of curators, such as those that answer each query with a function of its prior and posterior means\([Elder, 2016a](https://arxiv.org/html/2610.41244#bib.bib26)\)\.

##### Post\-selection and selective inference\.

In post\-selection \(selective\) inference, a model, variable, or hypothesis is chosen after examining the data, for example the support recovered by the Lasso, or the most significant among many candidates, and one seeks inference for a target*defined by*that selection\([Berk et al\., 2013](https://arxiv.org/html/2610.41244#bib.bib11);[Taylor and Tibshirani, 2015](https://arxiv.org/html/2610.41244#bib.bib77);[Lee et al\., 2016](https://arxiv.org/html/2610.41244#bib.bib51);[Fithian et al\., 2014](https://arxiv.org/html/2610.41244#bib.bib34)\)\. This setting differs from ordinary generalization in two ways\. First, the selection is typically from a rich family \(all sub\-models, all subsets of variables\), so uniform convergence over the family is unavailable and the naive in\-sample value of the selected target is systematically biased\. Second, the standard remedy is not a complexity bound but*conditioning on the selection event*and performing inference under the resulting conditional law\([Lee et al\., 2016](https://arxiv.org/html/2610.41244#bib.bib51);[Fithian et al\., 2014](https://arxiv.org/html/2610.41244#bib.bib34)\)\. In our notation the selected object is𝒢⁡\(S\)\\mathcal\{G\}\(S\)and the selected parameter is its massD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)\. We differ in two ways: we seek distribution\-free*point estimation*ofD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)rather than conditional tests or intervals, and we ask when this is possible*at all*– for a sufficiently rich selection family no estimator can succeed, as our impossibility results show \(e\.g\. Theorem[7\.1](https://arxiv.org/html/2610.41244#S7.Thmtheorem1), which selects the coordinate of maximal empirical mean among exponentially many candidates\)\.

##### Conformal prediction and distribution\-free uncertainty quantification\.

Given a training or calibration sampleSS, a conformal method outputs a prediction setCS​\(x\)C\_\{S\}\(x\)for the label of a new pointxx; its error event𝒢⁡\(S\)=\{\(x,y\):y∉CS​\(x\)\}\\mathcal\{G\}\(S\)=\\\{\(x,y\):y\\notin C\_\{S\}\(x\)\\\}is data\-dependent, andD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)is the realized miscoverage of the particular set produced fromSS\([Vovk et al\., 2005](https://arxiv.org/html/2610.41244#bib.bib82);[Lei et al\., 2013](https://arxiv.org/html/2610.41244#bib.bib52);[Angelopoulos and Bates, 2021](https://arxiv.org/html/2610.41244#bib.bib2)\)\. Conformal methods are designed to control this probability marginally over the joint draw ofSSand the test point, under exchangeability\. Our question is complementary: once a particularCSC\_\{S\}has been produced, can its realized miscoverageD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)be estimated from the same sampleSS?[Noorani et al\. \(2025\)](https://arxiv.org/html/2610.41244#bib.bib62)use ideas from missing mass estimation to address this question for generative models\.

##### Classical estimation\.

Finally, our task differs from classical parameter estimation in that the estimand is itself*random*:D⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)is a function of the realized sample, whereas in classical problems, mean estimation, or empirical risk minimization overUU\-statistics\([Clémençon et al\., 2008](https://arxiv.org/html/2610.41244#bib.bib19)\), the target is a fixed functional ofDD\. This randomness of the estimand drives several of the phenomena we study and means that standard lower\-bound techniques for classical estimation, such as Le Cam’s two\-point method, do not directly apply: Appendix[E](https://arxiv.org/html/2610.41244#A5)exhibits a mapping that is estimatable with zero error in the sense of Definition[3\.2](https://arxiv.org/html/2610.41244#S3.Thmdefinition2)while the corresponding deterministic functional𝔼S∼Dn\[D⁡\(𝒢⁡\(S\)\)\]\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\[D\(\\mathcal\{G\}\(S\)\)\]cannot be estimated to within a constant\.

In Sections[4](https://arxiv.org/html/2610.41244#S4)and[5](https://arxiv.org/html/2610.41244#S5), we focus on two natural estimatorsp^\\hat\{p\}: the empirical\-distribution\-based estimator and the leave\-one\-out estimator\. We show that these two estimators are sufficient for estimating a large class of functions𝒢\\mathcal\{G\}\. In Section[6](https://arxiv.org/html/2610.41244#S6)we combine the two estimators to solve adaptive missing mass estimation, and in Section[7](https://arxiv.org/html/2610.41244#S7)we complement our upper bounds with lower bounds\.

## 4Empirical Estimator

The simplest and most well\-studied estimatorp^\\hat\{p\}constructs the empirical distributionD^\\hat\{D\}over its samplesx1,…,xnx\_\{1\},\\dots,x\_\{n\}and returns the empirical massD^​\(𝒢​\(S\)\)\\hat\{D\}\(\\mathcal\{G\}\(S\)\)of the queryf=𝒢⁡\(S\)f=\\mathcal\{G\}\(S\)\(for an event,ℙx^∼D^\[x^∈𝒢\(S\)\]\\mathop\{\\mathbb\{P\}\}\_\{\\hat\{x\}\\sim\\hat\{D\}\}\\left\[\\hat\{x\}\\in\\mathcal\{G\}\(S\)\\right\]\), or equivalently,

p^𝒢emp​\(S\):=1n​∑i=1nf⁡\(xi\)\.\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\text\{emp\}\}\(S\):=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}f\(x\_\{i\}\)\.We can view the output𝒢⁡\(S\)\\mathcal\{G\}\(S\)directly as a \(data\-dependent\) loss function on a data point, in which case the error of the empirical estimator becomes the gap between the empirical and population loss\. More formally, define𝒬=\[0,1\]𝒳\\mathcal\{Q\}=\[0,1\]^\{\\mathcal\{X\}\}\(which contains\{0,1\}𝒳\\\{0,1\\\}^\{\\mathcal\{X\}\}\) and an algorithm𝒜:𝒳⋆→𝒬\\mathcal\{A\}:\\mathcal\{X\}^\{\\star\}\\rightarrow\\mathcal\{Q\}such that on inputS∈𝒳nS\\in\\mathcal\{X\}^\{n\}, we have𝒜⁡\(S\)=𝒢⁡\(S\)\.\\mathcal\{A\}\(S\)=\\mathcal\{G\}\(S\)\.Define the loss functionℓ:𝒬×𝒳→\[0,1\]\\ell:\\mathcal\{Q\}\\times\\mathcal\{X\}\\rightarrow\[0,1\]byℓ⁡\(q,x\):=q⁡\(x\)\\ell\(q,x\):=q\(x\)\(for an eventqq, this is𝟏\{x∈q\}\\mathbf\{1\}\\\{x\\in q\\\}\)\. Then the minimax MSE of the empirical\-distribution\-based estimator can be written as

supD∈Δ​𝒳𝔼S∼Dn\[\(p^𝒢emp​\(S\)−D⁡\(𝒢⁡\(S\)\)\)2\]\\displaystyle\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\left\[\\left\(\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\text\{emp\}\}\(S\)\-D\(\\mathcal\{G\}\(S\)\)\\right\)^\{2\}\\right\]=supD∈Δ​𝒳𝔼S∼Dn\[\(1n​∑i=1nℓ⁡\(𝒜⁡\(S\),xi\)−𝔼x∼D\[ℓ⁡\(𝒜⁡\(S\),x\)\]\)2\]\\displaystyle=\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\left\[\\left\(\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\ell\(\\mathcal\{A\}\(S\),x\_\{i\}\)\-\\mathop\{\\mathbb\{E\}\}\_\{x\\sim D\}\\left\[\\ell\(\\mathcal\{A\}\(S\),x\)\\right\]\\right\)^\{2\}\\right\]where the last line is exactly the generalization error for algorithm𝒜\\mathcal\{A\}with respect to the loss functionℓ\\ell\. This relationship implies that standard bounds for the empirical estimation of losses imply bounds for the corresponding events\.

For a sample sizen∈ℕn\\in\\mathbb\{N\}, defineℋn:=\{𝒢⁡\(S\)∣S∈𝒳n\}\\mathcal\{H\}\_\{n\}:=\\\{\\mathcal\{G\}\(S\)\\mid S\\in\\mathcal\{X\}^\{n\}\\\}as the hypothesis class induced by the image space of𝒢\\mathcal\{G\}on𝒳n\.\\mathcal\{X\}^\{n\}\.Classical VC theory then yields the following bound, proved in Appendix[A](https://arxiv.org/html/2610.41244#A1); in particular, any𝒢\\mathcal\{G\}withVC⁡\(ℋn\)=o⁡\(n\)\\operatorname\{VC\}\(\\mathcal\{H\}\_\{n\}\)=o\(n\)is estimatable via the empirical estimator\.

###### Corollary 4\.1\(VC\-based upper bound for the empirical estimator\)\.

Let𝒢:𝒳⋆→\{0,1\}𝒳\\mathcal\{G\}:\\mathcal\{X\}^\{\\star\}\\rightarrow\\\{0,1\\\}^\{\\mathcal\{X\}\}be any function such thatVC⁡\(ℋn\)<∞\\operatorname\{VC\}\(\\mathcal\{H\}\_\{n\}\)<\\inftyfor alln∈ℕn\\in\\mathbb\{N\}\. Then

supD∈Δ​𝒳𝔼S∼Dn\[\(p^𝒢emp​\(S\)−D⁡\(𝒢⁡\(S\)\)\)2\]=O⁡\(VC⁡\(ℋn\)\+1n\)\.\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\left\[\\left\(\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\emph\{\\text\{emp\}\}\}\(S\)\-D\(\\mathcal\{G\}\(S\)\)\\right\)^\{2\}\\right\]=O\\left\(\\frac\{\\operatorname\{VC\}\(\\mathcal\{H\}\_\{n\}\)\+1\}\{n\}\\right\)\.

A second, incomparable, sufficient condition is that the output of𝒢\\mathcal\{G\}be small on average\. Writing

τ𝒢​\(n\):=supD∈Δ​𝒳𝔼S∼Dn\|𝒢⁡\(S\)\|\\tau\_\{\\mathcal\{G\}\}\(n\):=\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathop\{\\mathbb\{E\}\}\}\_\{S\\sim D^\{n\}\}\|\\mathcal\{G\}\(S\)\|\(1\)for the worst\-case expected cardinality of the output of𝒢\\mathcal\{G\}, we show in Appendix[A](https://arxiv.org/html/2610.41244#A1)that the mean\-squared error of the empirical estimator isO⁡\(\(τ𝒢​\(n\)/n\)​log⁡\(e​n/τ𝒢​\(n\)\)\)O\\big\(\(\\tau\_\{\\mathcal\{G\}\}\(n\)/n\)\\log\(en/\\tau\_\{\\mathcal\{G\}\}\(n\)\)\\big\), so that estimation is possible wheneverτ𝒢​\(n\)=o​\(n\)\\tau\_\{\\mathcal\{G\}\}\(n\)=o\(n\)\.

###### Theorem 4\.2\(Cardinality\-based upper bound for the empirical estimator\)\.

Let𝒢:𝒳⋆→\{0,1\}𝒳\\mathcal\{G\}:\\mathcal\{X\}^\{\\star\}\\rightarrow\\\{0,1\\\}^\{\\mathcal\{X\}\}andn≥1n\\geq 1be such that0<τ𝒢​\(n\)≤n0<\\tau\_\{\\mathcal\{G\}\}\(n\)\\leq n\. Then

supD∈Δ​𝒳𝔼S∼Dn\[\(p^𝒢emp​\(S\)−D⁡\(𝒢⁡\(S\)\)\)2\]≤τ𝒢​\(n\)n​\(2​ln⁡nτ𝒢​\(n\)\+3\)\.\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\left\[\\Bigl\(\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\emph\{\\text\{emp\}\}\}\(S\)\-D\(\\mathcal\{G\}\(S\)\)\\Bigr\)^\{2\}\\right\]\\leq\\frac\{\\tau\_\{\\mathcal\{G\}\}\(n\)\}\{n\}\\left\(2\\ln\\frac\{n\}\{\\tau\_\{\\mathcal\{G\}\}\(n\)\}\+3\\right\)\.If moreover\|𝒢⁡\(S\)\|≤τ0\|\\mathcal\{G\}\(S\)\|\\leq\\tau\_\{0\}for everyS∈𝒳nS\\in\\mathcal\{X\}^\{n\}, then the left\-hand side is at mostτ0/n\\tau\_\{0\}/n\.

The two complexity measuresVC⁡\(ℋn\)\\operatorname\{VC\}\(\\mathcal\{H\}\_\{n\}\)andτ𝒢​\(n\)\\tau\_\{\\mathcal\{G\}\}\(n\)are incomparable: Appendix[A](https://arxiv.org/html/2610.41244#A1)exhibits mappings for which each of the two bounds is vacuous while the other is not\.

Another class of approaches for understanding the properties of the empirical estimator is based on various notions of stability of the output\([Bousquet and Elisseeff, 2002](https://arxiv.org/html/2610.41244#bib.bib15);[Shalev\-Shwartz et al\., 2010](https://arxiv.org/html/2610.41244#bib.bib71);[Feldman and Vondrak, 2018](https://arxiv.org/html/2610.41244#bib.bib31);[Feldman and Vondrak, 2019](https://arxiv.org/html/2610.41244#bib.bib32)\), all of which become properties of𝒢\\mathcal\{G\}since𝒜⁡\(S\)=𝒢⁡\(S\)\\mathcal\{A\}\(S\)=\\mathcal\{G\}\(S\)\. Information\-theoretic generalization bounds, controlling the gap through the mutual or conditional mutual information between the sample and the output\([Xu and Raginsky, 2017](https://arxiv.org/html/2610.41244#bib.bib84);[Steinke and Zakynthinou, 2020](https://arxiv.org/html/2610.41244#bib.bib73);[Hellström et al\., 2025](https://arxiv.org/html/2610.41244#bib.bib43)\), apply in the same way\. Since these arguments mostly require only plugging in existing upper bounds on generalization error, we omit them here\.

Finally, the adaptive\-data\-analysis techniques discussed in Section[3\.3](https://arxiv.org/html/2610.41244#S3.SS3), namely differential privacy, max\-information, and mutual information, each yield a further sufficient condition for the empirical estimator: whenever𝒢⁡\(S\)\\mathcal\{G\}\(S\)has a small value of the corresponding quantity, the generalization gap above is controlled\([Dwork et al\., 2014](https://arxiv.org/html/2610.41244#bib.bib21);[Dwork et al\., 2015a](https://arxiv.org/html/2610.41244#bib.bib22);[Bassily et al\., 2016](https://arxiv.org/html/2610.41244#bib.bib7);[Russo and Zou, 2016](https://arxiv.org/html/2610.41244#bib.bib69);[Feldman and Steinke, 2018](https://arxiv.org/html/2610.41244#bib.bib30);[Rogers et al\., 2016](https://arxiv.org/html/2610.41244#bib.bib67)\)\.

All of the above guarantees extend directly to*randomized*mappings \(Definition[3\.3](https://arxiv.org/html/2610.41244#S3.Thmdefinition3)\): given the seedrr, the empirical estimator uses the realized query𝒢⁡\(S,r\)\\mathcal\{G\}\(S,r\), and identifying the algorithm𝒜⁡\(S,r\)=𝒢⁡\(S,r\)\\mathcal\{A\}\(S,r\)=\\mathcal\{G\}\(S,r\)absorbs the internal randomness of𝒢\\mathcal\{G\}into that of𝒜\\mathcal\{A\}\. Since the VC\-, stability\-, privacy\-, and information\-based bounds above all apply to randomized algorithms, they carry over without change\.

## 5Estimation via the Leave\-One\-Out Estimator

In Section[4](https://arxiv.org/html/2610.41244#S4), we identified generic conditions on𝒢\\mathcal\{G\}for which the empirical\-distribution\-based estimator enjoys vanishing estimation error\. One might wonder if this empirical distribution\-based estimator can work for all𝒢\\mathcal\{G\}\. Unfortunately, this is not the case even for the well\-studied missing mass estimation problem𝒢⁡\(S\)=Sc\\mathcal\{G\}\(S\)=S^\{c\}\. In this setting, the empirical plug\-in estimator is identically zero, while the true probability mass of unseen elements is typically nonzero, leading to a large bias\. Motivated by this example, we study the leave\-one\-out estimatorp^𝒢loo\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\text\{loo\}\}, which, writingfi:=𝒢⁡\(S−i\)f\_\{i\}:=\\mathcal\{G\}\(S^\{\-i\}\)for the query produced on the sample with theiith point removed, computes

p^𝒢loo​\(S\)=1n​∑i=1nfi​\(xi\)\.\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\text\{loo\}\}\(S\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}f\_\{i\}\(x\_\{i\}\)\.It turns out that while the missing mass𝒢\\mathcal\{G\}is not estimatable via the empirical\-distribution\-based estimator, it is estimatable using the leave\-one\-out estimator\. In fact, we show that the leave\-one\-out estimator is valid for*any*sufficiently stable function𝒢\\mathcal\{G\}\. Our notion of stability involves the following quantity:

γ𝒢​\(n\):=supD∈Δ​𝒳γ𝒢D​\(n\),whereγ𝒢D​\(n\):=𝔼S∼Dn\[D⁡\(\|f−f′\|\)\],\\gamma\_\{\\mathcal\{G\}\}\(n\):=\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\gamma\_\{\\mathcal\{G\}\}^\{D\}\(n\),\\qquad\\text\{where\}\\qquad\\gamma\_\{\\mathcal\{G\}\}^\{D\}\(n\):=\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\left\[D\\big\(\|f\-f^\{\\prime\}\|\\big\)\\right\],\(2\)wheref=𝒢⁡\(S\)f=\\mathcal\{G\}\(S\),f′=𝒢⁡\(S−n\)f^\{\\prime\}=\\mathcal\{G\}\(S^\{\-n\}\), andD⁡\(\|f−f′\|\)=𝔼x∼D\|f⁡\(x\)−f′​\(x\)\|D\\big\(\|f\-f^\{\\prime\}\|\\big\)=\\mathop\{\\mathbb\{E\}\}\_\{x\\sim D\}\\,\|f\(x\)\-f^\{\\prime\}\(x\)\|is the expected change in the query when the last sample point is dropped; for an event \(indicator\-valued𝒢\\mathcal\{G\}\) this equals the symmetric\-difference massD⁡\(𝒢⁡\(S\)​Δ​𝒢​\(S−n\)\)D\(\\mathcal\{G\}\(S\)\\,\\Delta\\,\\mathcal\{G\}\(S^\{\-n\}\)\)\. We callγ𝒢​\(n\)\\gamma\_\{\\mathcal\{G\}\}\(n\)the*deletion stability*of𝒢\\mathcal\{G\}at sample sizenn, and say that𝒢\\mathcal\{G\}is*stable*ifγ𝒢​\(n\)=o​\(1\)\\gamma\_\{\\mathcal\{G\}\}\(n\)=o\(1\)\. This quantity is the*hypothesis stability*of[Devroye and Wagner \(1979\)](https://arxiv.org/html/2610.41244#bib.bib20), named by[Kearns and Ron \(1999\)](https://arxiv.org/html/2610.41244#bib.bib48)and used in the form of[Bousquet and Elisseeff \(2002, Definition 3\)](https://arxiv.org/html/2610.41244#bib.bib15), for the “algorithm”S↦𝒢⁡\(S\)S\\mapsto\\mathcal\{G\}\(S\)and the lossℓ⁡\(𝒢⁡\(S\),x\)=𝒢⁡\(S\)​\(x\)\\ell\(\\mathcal\{G\}\(S\),x\)=\\mathcal\{G\}\(S\)\(x\)\. Theorem[5\.1](https://arxiv.org/html/2610.41244#S5.Thmtheorem1)below is the classical bound on the deleted estimate for hypothesis\-stable algorithms \([Kearns and Ron, 1999](https://arxiv.org/html/2610.41244#bib.bib48), Theorem 3\.1;[Bousquet and Elisseeff, 2002](https://arxiv.org/html/2610.41244#bib.bib15), Lemma 9\), restated in this setting: the quantity those results bound, the difference between the true error of the hypothesis trained on the full sample and its leave\-one\-out estimate, is exactly the estimation error ofp^𝒢loo\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\text\{loo\}\}forD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)\. What is new is the object to which the bound is applied\. A data\-dependent event is the output of a learning algorithm in this sense, with no labels and no hypothesis class, and the content of this section lies in computingγ𝒢\\gamma\_\{\\mathcal\{G\}\}for the mappings considered below and in identifying the resulting estimators with the Good–Turing estimator \(Remark[5\.1](https://arxiv.org/html/2610.41244#S5.Thmremark1)\)\.

Theorem[5\.1](https://arxiv.org/html/2610.41244#S5.Thmtheorem1)bounds the error of the leave\-one\-out estimator byγ𝒢​\(n\)\\gamma\_\{\\mathcal\{G\}\}\(n\)up to an additiveO⁡\(1/n\)O\(1/n\); in particular, every stable mapping is estimatable via the leave\-one\-out estimator\. Missing proofs for this section are in Appendix[B](https://arxiv.org/html/2610.41244#A2)\.

###### Theorem 5\.1\(Estimation via the Leave\-One\-Out Estimator\)\.

Let𝒢:𝒳⋆→\[0,1\]𝒳\\mathcal\{G\}:\\mathcal\{X\}^\{\\star\}\\rightarrow\[0,1\]^\{\\mathcal\{X\}\}be any*symmetric*mapping\. Then, for everyn≥1n\\geq 1and everyD∈Δ​𝒳D\\in\\Delta\\mathcal\{X\},

𝔼S∼Dn\[\(p^𝒢loo​\(S\)−D⁡\(𝒢⁡\(S\)\)\)2\]≤12​n\+3​γ𝒢D​\(n\),\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\left\[\\left\(\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\emph\{\\text\{loo\}\}\}\(S\)\-D\(\\mathcal\{G\}\(S\)\)\\right\)^\{2\}\\right\]\\leq\\frac\{1\}\{2n\}\+3\\gamma\_\{\\mathcal\{G\}\}^\{D\}\(n\),and consequently

supD∈Δ​𝒳𝔼S∼Dn\[\(p^𝒢loo​\(S\)−D⁡\(𝒢⁡\(S\)\)\)2\]≤12​n\+3​γ𝒢​\(n\)\.\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\left\[\\left\(\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\emph\{\\text\{loo\}\}\}\(S\)\-D\(\\mathcal\{G\}\(S\)\)\\right\)^\{2\}\\right\]\\leq\\frac\{1\}\{2n\}\+3\\gamma\_\{\\mathcal\{G\}\}\(n\)\.In particular, ifγ𝒢​\(n\)=o​\(1\)\\gamma\_\{\\mathcal\{G\}\}\(n\)=o\(1\)then𝒢\\mathcal\{G\}is estimatable\.

While missing mass estimation gives a task for which leave\-one\-out succeeds and the empirical estimator fails, the following proposition gives the reverse direction\. Together, these examples show that the two estimators are incomparable\.

###### Proposition 5\.2\(Empirical succeeds while leave\-one\-out fails\)\.

For any non\-empty domain𝒳\\mathcal\{X\}, define𝒢⁡\(S\)=𝒳\\mathcal\{G\}\(S\)=\\mathcal\{X\}if the length of the*sequence*SSis even, and𝒢⁡\(S\)=∅\\mathcal\{G\}\(S\)=\\emptysetif the length is odd\. Thenp^𝒢emp​\(S\)=D⁡\(𝒢⁡\(S\)\)\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\emph\{\\text\{emp\}\}\}\(S\)=D\(\\mathcal\{G\}\(S\)\)whilep^𝒢loo​\(S\)=1−D⁡\(𝒢⁡\(S\)\)\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\emph\{\\text\{loo\}\}\}\(S\)=1\-D\(\\mathcal\{G\}\(S\)\), for everySSandDD\.

###### Proof\.

Ifnnis even then𝒢⁡\(S\)=𝒳\\mathcal\{G\}\(S\)=\\mathcal\{X\}, soD⁡\(𝒢⁡\(S\)\)=1=p^𝒢emp​\(S\)D\(\\mathcal\{G\}\(S\)\)=1=\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\text\{emp\}\}\(S\), while every foldS−iS^\{\-i\}has odd length, so𝒢⁡\(S−i\)=∅\\mathcal\{G\}\(S^\{\-i\}\)=\\emptysetandp^𝒢loo​\(S\)=0\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\text\{loo\}\}\(S\)=0\. Ifnnis odd the roles are reversed:D⁡\(𝒢⁡\(S\)\)=0=p^𝒢emp​\(S\)D\(\\mathcal\{G\}\(S\)\)=0=\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\text\{emp\}\}\(S\)andp^𝒢loo​\(S\)=1\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\text\{loo\}\}\(S\)=1\. ∎

Appendix[C\.2](https://arxiv.org/html/2610.41244#A3.SS2)shows a simple problem that combines the failure modes of both the empirical and the leave\-one\-out estimators \(but is solved by the proposed hybrid estimator\)\.

As with the empirical estimator, the leave\-one\-out estimator extends directly to*randomized*mappings \(Definition[3\.3](https://arxiv.org/html/2610.41244#S3.Thmdefinition3)\): it reuses a single seedrracross all folds, computing𝒢⁡\(S−i,r\)\\mathcal\{G\}\(S^\{\-i\},r\), so that conditioning onrrreduces to the deterministic guarantee of Theorem[5\.1](https://arxiv.org/html/2610.41244#S5.Thmtheorem1)\. Averaging overr∼Rr\\sim Rthen preserves the bound, withγ𝒢​\(n\)\\gamma\_\{\\mathcal\{G\}\}\(n\)now also averaged overrr\. We omit the formal details\.

### 5\.1Applications

In this section, we upper boundγ𝒢​\(n\)\\gamma\_\{\\mathcal\{G\}\}\(n\)for several natural choices of𝒢\\mathcal\{G\}\. Our results recover well\-known facts, such as missing mass beingO⁡\(1/n\)O\(1/n\)\-estimatable, while also showing that estimation is possible for new choices of𝒢\\mathcal\{G\}\.

##### Estimating Mass of Neighbors\.

In this section, we study the estimatability of natural𝒢\\mathcal\{G\}functions whose output size can be much larger thannn\. These functions𝒢\\mathcal\{G\}are best described by a directed graph on the vertex set𝒳\\mathcal\{X\}whose edges are given by a functionN:𝒳→2𝒳N:\\mathcal\{X\}\\rightarrow 2^\{\\mathcal\{X\}\}: for each vertexx∈𝒳x\\in\\mathcal\{X\},N⁡\(x\)N\(x\)is the set of outgoing neighbors ofxx\. We writeN−1​\(x\):=\{y∈𝒳:x∈N⁡\(y\)\}N^\{\-1\}\(x\):=\\\{y\\in\\mathcal\{X\}:x\\in N\(y\)\\\}for the set of in\-neighbors ofxx\. Given such a functionNN, we consider functions𝒢\\mathcal\{G\}of the form

𝒢⁡\(S\)=⋃i∈\[n\]N⁡\(xi\)\.\\mathcal\{G\}\(S\)=\\bigcup\_\{i\\in\[n\]\}N\(x\_\{i\}\)\.On a sampleS∼DnS\\sim D^\{n\},𝒢\\mathcal\{G\}returns the set of all outgoing neighbors across the examples inSS, and thusD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)measures the mass placed byDDon all the neighbors of the sample\. The following theorem shows that for*any*neighboring functionNN, its corresponding𝒢\\mathcal\{G\}function is estimatable\.

###### Theorem 5\.3\(Unions of Neighborhoods\)\.

LetN:𝒳→2𝒳N:\\mathcal\{X\}\\rightarrow 2^\{\\mathcal\{X\}\}be any function and consider the function𝒢⁡\(S\)=⋃i∈\[n\]N⁡\(xi\)\.\\mathcal\{G\}\(S\)=\\bigcup\_\{i\\in\[n\]\}N\(x\_\{i\}\)\.Then𝒢\\mathcal\{G\}isO⁡\(1/n\)O\(1/n\)\-estimatable via the leave\-one\-out estimator\.

Complements require no separate argument\. For every mapping𝒢\\mathcal\{G\}, the leave\-one\-out estimate of the complement𝒢c​\(S\):=𝒳∖𝒢⁡\(S\)\\mathcal\{G\}^\{c\}\(S\):=\\mathcal\{X\}\\setminus\\mathcal\{G\}\(S\)is1−p^𝒢loo​\(S\)1\-\\hat\{p\}^\{\\mathrm\{loo\}\}\_\{\\mathcal\{G\}\}\(S\), andγ𝒢c=γ𝒢\\gamma\_\{\\mathcal\{G\}^\{c\}\}=\\gamma\_\{\\mathcal\{G\}\}becauseAc​Δ​Bc=A​Δ​BA^\{c\}\\,\\Delta\\,B^\{c\}=A\\,\\Delta\\,B\. Hence𝒢c\\mathcal\{G\}^\{c\}is estimatable via the leave\-one\-out estimator at the same rate as𝒢\\mathcal\{G\}, and we obtain the following corollary\.

###### Corollary 5\.4\.

LetN:𝒳→2𝒳N:\\mathcal\{X\}\\rightarrow 2^\{\\mathcal\{X\}\}be any function and consider the function𝒢⁡\(S\)=⋂i∈\[n\]N⁡\(xi\)\.\\mathcal\{G\}\(S\)=\\bigcap\_\{i\\in\[n\]\}N\(x\_\{i\}\)\.Then𝒢\\mathcal\{G\}isO⁡\(1/n\)O\(1/n\)\-estimatable via the leave\-one\-out estimator\.

Indeed,𝒢​\(S\)c=⋃i∈\[n\]N′​\(xi\)\\mathcal\{G\}\(S\)^\{c\}=\\bigcup\_\{i\\in\[n\]\}N^\{\\prime\}\(x\_\{i\}\)withN′​\(x\):=𝒳∖N⁡\(x\)N^\{\\prime\}\(x\):=\\mathcal\{X\}\\setminus N\(x\), so this follows from Theorem[5\.3](https://arxiv.org/html/2610.41244#S5.Thmtheorem3)and the observation above\. Note that a special case of Corollary[5\.4](https://arxiv.org/html/2610.41244#S5.Thmtheorem4)is the classical missing mass problem𝒢⁡\(S\)=Sc\.\\mathcal\{G\}\(S\)=S^\{c\}\.Hence, these results provide, to the best of our knowledge, an alternative proof of the fact that missing mass isO⁡\(1/n\)O\(1/n\)\-estimatable\.

##### Estimating Mass of Pierced Sets\.

In many applications, one is interested in estimating the mass of in\-sample examples that satisfy certain properties\. For example, in ecology, one might be interested in estimating the mass of species with a*predetermined*anomaly\([Good, 1953](https://arxiv.org/html/2610.41244#bib.bib38);[Chao and Lee, 1992](https://arxiv.org/html/2610.41244#bib.bib17);[Bunge et al\., 2014](https://arxiv.org/html/2610.41244#bib.bib16)\)\. Motivated by these applications, we consider functions𝒢\\mathcal\{G\}of the form

𝒢⁡\(S\)=S∩V\\mathcal\{G\}\(S\)=S\\cap VwhereV⊆𝒳V\\subseteq\\mathcal\{X\}is a prespecified “piercing” set that is*fixed*, i\.e\. does not depend on the realized samplesSS\. SinceS∩VS\\cap Vis the union of the neighborhoodsN⁡\(x\)=\{x\}∩VN\(x\)=\\\{x\\\}\\cap V, Theorem[5\.3](https://arxiv.org/html/2610.41244#S5.Thmtheorem3)shows that estimation is then possible at a rate ofO⁡\(1/n\)O\(1/n\)\. The setVVmay itself be chosen as a function of the sample size, sayV=VnV=V\_\{n\}\. The proof is unchanged, but the estimator must then be the*level\-nn*leave\-one\-out estimator1n∑i=1n𝟏\{xi∈S−i∩Vn\}\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{x\_\{i\}\\in S^\{\-i\}\\cap V\_\{n\}\\\}, which holdsVnV\_\{n\}fixed across the folds\.

The same bound holds for the unseen partSc∩VS^\{c\}\\cap Vof a fixed region, which is the mass of the*missing*examples with the property, and for the unionsS∪VS\\cup VandSc∪VS^\{c\}\\cup V\.

###### Corollary 5\.5\(Pierced Sets\)\.

LetV⊆𝒳V\\subseteq\\mathcal\{X\}be any fixed set\. Each of the mappingsS↦S∩VS\\mapsto S\\cap V,S↦Sc∩VS\\mapsto S^\{c\}\\cap V,S↦S∪VS\\mapsto S\\cup VandS↦Sc∪VS\\mapsto S^\{c\}\\cup Vhasγ𝒢​\(n\)≤1/n\\gamma\_\{\\mathcal\{G\}\}\(n\)\\leq 1/nfor everyn≥1n\\geq 1, and is thereforeO⁡\(1/n\)O\(1/n\)\-estimatable via the leave\-one\-out estimator\.

###### Proof\.

For each of the four mappings,𝒢⁡\(S\)​Δ​𝒢​\(S−n\)⊆\{xn\}∖T⁡\(S−n\)\\mathcal\{G\}\(S\)\\,\\Delta\\,\\mathcal\{G\}\(S^\{\-n\}\)\\subseteq\\\{x\_\{n\}\\\}\\setminus T\(S^\{\-n\}\), since addingxnx\_\{n\}toS−nS^\{\-n\}changes the set of sample points only by addingxnx\_\{n\}, and only ifxn∉T⁡\(S−n\)x\_\{n\}\\notin T\(S^\{\-n\}\)\. Hence

γ𝒢D\(n\)≤𝔼\[D\(xn\)1\{xn∉T\(S−n\)\}\]=∑x∈𝒳D\(x\)2\(1−D\(x\)\)n−1≤maxx∈𝒳D\(x\)\(1−D\(x\)\)n−1≤1n,\\gamma^\{D\}\_\{\\mathcal\{G\}\}\(n\)\\leq\\mathop\{\\mathbb\{E\}\}\\left\[D\(x\_\{n\}\)\\,\\mathbf\{1\}\\\{x\_\{n\}\\notin T\(S^\{\-n\}\)\\\}\\right\]=\\sum\_\{x\\in\\mathcal\{X\}\}D\(x\)^\{2\}\\,\(1\-D\(x\)\)^\{n\-1\}\\leq\\max\_\{x\\in\\mathcal\{X\}\}D\(x\)\(1\-D\(x\)\)^\{n\-1\}\\leq\\frac\{1\}\{n\},and Theorem[5\.1](https://arxiv.org/html/2610.41244#S5.Thmtheorem1)applies\. ∎

WithV=∅V=\\emptyset, the mappingS↦Sc∪VS\\mapsto S^\{c\}\\cup Vis the missing mass\.

##### Estimating Mass of Functions of Heavy Hitters\.

One important generalization of missing mass estimation is estimating the mass of heavy hitters\. Given a sampleSSand an integerk≥0k\\geq 0, defineck​\(S\)c\_\{k\}\(S\)to be the set of examplesx∈𝒳x\\in\\mathcal\{X\}that occur exactlykktimes inSS\(i\.e\. thekk\-heavy hitters\); fork≥1k\\geq 1we haveck​\(S\)⊆Sc\_\{k\}\(S\)\\subseteq S, whilec0​\(S\)=Scc\_\{0\}\(S\)=S^\{c\}\. When𝒢​\(S\)=ck​\(S\)\\mathcal\{G\}\(S\)=c\_\{k\}\(S\), our estimation task reduces exactly to that of estimating thekk\-heavy hitters, which is known to beO⁡\(k/n\)O\(k/n\)\-estimatable\([McAllester and Schapire, 2000](https://arxiv.org/html/2610.41244#bib.bib57)\)\. Lemma[5\.6](https://arxiv.org/html/2610.41244#S5.Thmtheorem6)shows thatγ𝒢​\(n\)≤2​k\+1n\\gamma\_\{\\mathcal\{G\}\}\(n\)\\leq\\frac\{2k\+1\}\{n\}when𝒢​\(S\)=ck​\(S\)\.\\mathcal\{G\}\(S\)=c\_\{k\}\(S\)\.Hence, by Theorem[5\.1](https://arxiv.org/html/2610.41244#S5.Thmtheorem1), we recover this known result\.

###### Lemma 5\.6\.

Fixk≥1k\\geq 1and let𝒢​\(S\)=ck​\(S\)\\mathcal\{G\}\(S\)=c\_\{k\}\(S\)\. Then,γ𝒢​\(n\)≤2​k\+1n\.\\gamma\_\{\\mathcal\{G\}\}\(n\)\\leq\\frac\{2k\+1\}\{n\}\.

Next, we consider estimating the mass of the neighbors of thekk\-heavy hitters\. Unlike Lemma[5\.6](https://arxiv.org/html/2610.41244#S5.Thmtheorem6), this result has an additionallog⁡n\\log nterm, and we leave whether the rateO⁡\(k/n\)O\(k/n\)holds for every neighborhood function as an open question\.

###### Theorem 5\.7\(Unions of Heavy\-Hitter Neighborhoods\)\.

LetN:𝒳→2𝒳N:\\mathcal\{X\}\\rightarrow 2^\{\\mathcal\{X\}\}be any function\. Fork≥1k\\geq 1, consider the function𝒢⁡\(S\)=⋃x∈ck​\(S\)N⁡\(x\)\.\\mathcal\{G\}\(S\)=\\bigcup\_\{x\\in c\_\{k\}\(S\)\}N\(x\)\.Thenγ𝒢​\(n\)≤3​k\+2​ln⁡n\+2n\\gamma\_\{\\mathcal\{G\}\}\(n\)\\leq\\frac\{3k\+2\\ln n\+2\}\{n\}for everyn≥2n\\geq 2, and𝒢\\mathcal\{G\}isO⁡\(k\+log⁡nn\)O\\big\(\\frac\{k\+\\log n\}\{n\}\\big\)\-estimatable via the leave\-one\-out estimator\.

Finally, we also extend these results to estimating the mass of arbitrary piercings of thekk\-heavy hitters\.

###### Theorem 5\.8\(Piercings of Heavy Hitters\)\.

LetV⊆𝒳V\\subseteq\\mathcal\{X\}be any fixed set\. Fork≥1k\\geq 1, consider the function𝒢⁡\(S\)=V∩ck​\(S\)\.\\mathcal\{G\}\(S\)=V\\cap c\_\{k\}\(S\)\.Then𝒢\\mathcal\{G\}isO⁡\(k/n\)O\(k/n\)\-estimatable via the leave\-one\-out estimator\.

## 6Estimating the Error of a Memorizing Classifier via Adaptive Missing Mass Estimation

Estimating the true error of a trained classifier is the basic instance of our problem\. Most theoretical approaches to it rely on the empirical estimate together with an upper bound on the generalization gap, obtained by one of the methods discussed in Section[4](https://arxiv.org/html/2610.41244#S4)\. Yet in practice the empirical error is close to00while the generalization gap is large, often over 20%\([Zhang et al\., 2017](https://arxiv.org/html/2610.41244#bib.bib88)\)\. An estimate obtained in this way cannot be more accurate than the gap it bounds, and so these approaches cannot give a useful estimate of the true error\.

In this section we show that by combining the two types of estimators one can estimate the error of a natural class of*exception\-memorizing*predictors\. These predictors combine a structured base classifier with data\-dependent corrections, such as the memorization of individual, atypical training examples\. Such classifiers are used both in theory \(e\.g\.,[Board and Pitt, 1990](https://arxiv.org/html/2610.41244#bib.bib13);[Angluin et al\., 1997](https://arxiv.org/html/2610.41244#bib.bib3);[Manoj and Srebro, 2023](https://arxiv.org/html/2610.41244#bib.bib54)\), most notably in the classical proof that PAC learning implies an Occam \(or consistent and compressing\) classifier\([Blumer et al\., 1987](https://arxiv.org/html/2610.41244#bib.bib12);[Board and Pitt, 1990](https://arxiv.org/html/2610.41244#bib.bib13)\), and in many practical systems\. For example, Batchwise Patching retains an immutable black\-box classifier and invokes local patch classifiers selected by an error\-region detector for concept drift and transfer learning\([Kauschke and Fürnkranz, 2018](https://arxiv.org/html/2610.41244#bib.bib47)\), andResMemaugments an existing prediction model \(e\.g\., a neural network\) by fitting the model’s residuals with a nearest\-neighbor based regressor\([Yang et al\., 2023](https://arxiv.org/html/2610.41244#bib.bib85)\)\. Other correction modules populated by specific errors, edits, or user feedback include feedback\-memory graph repair, memory\-assisted prompt correction, discrete edit codebooks, per\-edit experts, and routed side memories\([Tandon et al\., 2022](https://arxiv.org/html/2610.41244#bib.bib76);[Mitchell et al\., 2022](https://arxiv.org/html/2610.41244#bib.bib58);[Madaan et al\., 2022](https://arxiv.org/html/2610.41244#bib.bib53);[Hartvigsen et al\., 2023](https://arxiv.org/html/2610.41244#bib.bib41);[Yao et al\., 2024](https://arxiv.org/html/2610.41244#bib.bib86);[Wang et al\., 2024](https://arxiv.org/html/2610.41244#bib.bib83)\)\. It is also known that standard training methods memorize such atypical examples\([Feldman, 2020](https://arxiv.org/html/2610.41244#bib.bib29);[Feldman and Zhang, 2020](https://arxiv.org/html/2610.41244#bib.bib33)\), although in this case there is typically no explicit separation between the base classifier and the exceptions\.

We first describe this class of learners formally, starting with the simplest one, which memorizes every exception in the training set\.

### 6\.1Exception\-Memorizing Learners

Let inputs come from a space𝒲\\mathcal\{W\}with labels given by a fixed labeling functiony:𝒲→𝒴y:\\mathcal\{W\}\\to\\mathcal\{Y\}, and identify the example space with the set of correctly labeled pairs,𝒳=\{\(w,y⁡\(w\)\):w∈𝒲\}\\mathcal\{X\}=\\\{\(w,y\(w\)\):w\\in\\mathcal\{W\}\\\}; we suppress the label and writewwfor the example\(w,y⁡\(w\)\)\(w,y\(w\)\)\. A*base learner*𝒜\\mathcal\{A\}is an algorithm that maps a sampleSSto a classifierhS:𝒲→𝒴h\_\{S\}:\\mathcal\{W\}\\to\\mathcal\{Y\}\. We write

E⁡\(S\):=\{\(w,y⁡\(w\)\)∈𝒳:hS​\(w\)≠y⁡\(w\)\}E\(S\):=\\\{\(w,y\(w\)\)\\in\\mathcal\{X\}:h\_\{S\}\(w\)\\neq y\(w\)\\\}for the error region ofhSh\_\{S\}\. \(The base learner may be randomized; for simplicity we suppress the dependence on its random seed and treat it as deterministic\.\)

The simplest exception\-memorizing learner runs𝒜\\mathcal\{A\}and then memorizes the training set: on an example that occurs inSSit predicts the label recorded inSS, and elsewhere it predicts ashSh\_\{S\}\. Its memorized answers are correct, so its error region is

𝒢⁡\(S\)=E⁡\(S\)∖T⁡\(S\),\\mathcal\{G\}\(S\)=E\(S\)\\setminus T\(S\),\(3\)whereT⁡\(S\)=\{x1,…,xn\}T\(S\)=\\\{x\_\{1\},\\dots,x\_\{n\}\\\}is the set of sample points, as in Section[3](https://arxiv.org/html/2610.41244#S3)\.

In practice, a memorized exception is used to correct the predictions on other, sufficiently similar inputs as well\. To model this we use a neighborhood functionN:𝒳→2𝒳N:\\mathcal\{X\}\\to 2^\{\\mathcal\{X\}\}as in Section[5\.1](https://arxiv.org/html/2610.41244#S5.SS1.SSS0.Px1), which assigns to each examplexxa setN⁡\(x\)N\(x\)of neighbors; we assume throughout thatx∈N⁡\(x\)x\\in N\(x\)\. Memorizing an exceptionxxthen corrects the base classifier on all ofN⁡\(x\)N\(x\)\.

###### Definition 6\.1\(Neighborhood\-correcting learner𝒜N\\mathcal\{A\}\_\{N\}\)\.

Let𝒜\\mathcal\{A\}be a base learner andNNa neighborhood function\. For a regionV⊆𝒳V\\subseteq\\mathcal\{X\}and a sampleUU, the*correction set*

CV​\(U\):=V∩⋃x∈V∩T⁡\(U\)N⁡\(x\)C\_\{V\}\(U\):=V\\cap\\bigcup\_\{x\\in V\\cap T\(U\)\}N\(x\)\(4\)is the part ofVVthat is corrected by memorizing the exceptions inUU, that is, the points ofUUthat lie inVV\. The learner𝒜N\\mathcal\{A\}\_\{N\}runs𝒜\\mathcal\{A\}onSSto obtainhSh\_\{S\}and then correctshSh\_\{S\}on every neighbor of every exception inSS\. Its error region is

𝒢⁡\(S\):=E⁡\(S\)∖CE⁡\(S\)​\(S\)\.\\mathcal\{G\}\(S\):=E\(S\)\\setminus C\_\{E\(S\)\}\(S\)\.\(5\)

Here we model the correction as exact: on every neighbor of a memorized exception the corrected classifier is right\. SinceCV​\(U\)⊆VC\_\{V\}\(U\)\\subseteq V, a correction never introduces an error; it only removes errors ofhSh\_\{S\}\. WhenN⁡\(x\)=\{x\}N\(x\)=\\\{x\\\}we haveCV​\(U\)=V∩T⁡\(U\)C\_\{V\}\(U\)=V\\cap T\(U\), and𝒜N\\mathcal\{A\}\_\{N\}is the exception\-memorizing learner of \([3](https://arxiv.org/html/2610.41244#S6.E3)\), which we denote by𝒜mem\\mathcal\{A\}\_\{\\mathrm\{mem\}\}\.

Neither of the two standard estimators is adequate for estimating the error of the exception\-memorizing classifier\. The empirical estimator is identically zero, since𝒢⁡\(S\)\\mathcal\{G\}\(S\)excludes every sampled point\. The leave\-one\-out estimator retrains𝒜\\mathcal\{A\}on each of thennfolds, which is expensive, and it is not covered by the guarantee of Theorem[5\.1](https://arxiv.org/html/2610.41244#S5.Thmtheorem1)when𝒜\\mathcal\{A\}is unstable, for example because its training objective is non\-convex; Appendix[C\.2](https://arxiv.org/html/2610.41244#A3.SS2)gives a simple example in which it fails\.

### 6\.2Adaptive Missing Mass Estimation

The true error of the exception\-memorizing classifier,D⁡\(𝒢⁡\(S\)\)=D⁡\(E⁡\(S\)∖T⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)=D\(E\(S\)\\setminus T\(S\)\), is exactly the*missing mass of the error region*\. For a region fixed in advance this is the mass of the out\-of\-sample pierced set we defined in Section[5\.1](https://arxiv.org/html/2610.41244#S5.SS1.SSS0.Px2), which isO⁡\(1/n\)O\(1/n\)\-estimatable by Corollary[5\.5](https://arxiv.org/html/2610.41244#S5.Thmtheorem5)\. In our problem the regionE⁡\(S\)E\(S\)is selected using the same sample whose missing mass is then estimated\. This gives rise to a general question ofadaptive missing mass estimationthat we formulate below\.

###### Definition 6\.2\(Adaptive missing mass estimation\)\.

A*region selection rule*is a map𝒱:𝒳n→2𝒳\\mathcal\{V\}:\\mathcal\{X\}^\{n\}\\to 2^\{\\mathcal\{X\}\}, possibly randomized using an internal seedr∼Rr\\sim R, as in Definition[3\.3](https://arxiv.org/html/2610.41244#S3.Thmdefinition3)\. For a regionV⊆𝒳V\\subseteq\\mathcal\{X\}and a sampleSS, let

MV​\(S\):=D⁡\(V∖T⁡\(S\)\)M\_\{V\}\(S\):=D\\big\(V\\setminus T\(S\)\\big\)\(6\)be the missing mass ofVV\. Adaptive missing mass estimation for a selection rule𝒱\\mathcal\{V\}is the problem of estimatingM𝒱⁡\(S\)​\(S\)M\_\{\\mathcal\{V\}\(S\)\}\(S\), the missing mass of the selected region\.

### 6\.3The Hybrid Estimator

The missing mass of the selected region is the difference of two masses,

M𝒱⁡\(S\)​\(S\)=D⁡\(𝒱⁡\(S\)\)−D⁡\(𝒱⁡\(S\)∩T⁡\(S\)\),M\_\{\\mathcal\{V\}\(S\)\}\(S\)=D\(\\mathcal\{V\}\(S\)\)\-D\\big\(\\mathcal\{V\}\(S\)\\cap T\(S\)\\big\),\(7\)and we estimate the two terms using two different estimators\. The mass of the selected region is estimated empirically, by the fractionD^​\(𝒱​\(S\)\)\\hat\{D\}\(\\mathcal\{V\}\(S\)\)of the sample that it contains, which for the error region of a base classifier is its training error\. The mass of the seen part is estimated by leave\-one\-out with the region held fixed: for a fixed regionVV, the leave\-one\-out estimator of the in\-sample piercingU↦V∩T⁡\(U\)U\\mapsto V\\cap T\(U\)of Section[5\.1](https://arxiv.org/html/2610.41244#S5.SS1.SSS0.Px2)is

p^V∩Tloo\(S\):=1n∑i=1n𝟏\{xi∈V∩T\(S−i\)\},\\hat\{p\}^\{\\mathrm\{loo\}\}\_\{V\\cap T\}\(S\):=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\big\\\{x\_\{i\}\\in V\\cap T\(S^\{\-i\}\)\\big\\\},\(8\)and the hybrid evaluates it atV=𝒱⁡\(S\)V=\\mathcal\{V\}\(S\), the region output on the full sample\. Writing\#x\(S\):=∑i=1n𝟏\{xi=x\}\\\#\_\{x\}\(S\):=\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{x\_\{i\}=x\\\}for the number of occurrences ofxxinSS, a pointxix\_\{i\}lies inT⁡\(S−i\)T\(S^\{\-i\}\)exactly when\#xi​\(S\)≥2\\\#\_\{x\_\{i\}\}\(S\)\\geq 2, so the difference of the two estimates is a count of singletons\.

###### Definition 6\.3\(Hybrid estimator\)\.

For a region selection rule𝒱\\mathcal\{V\}, the*hybrid estimator*of the missing massM𝒱⁡\(S\)​\(S\)M\_\{\\mathcal\{V\}\(S\)\}\(S\)is

p^𝒱hyb​\(S\)\\displaystyle\\hat\{p\}\_\{\\mathcal\{V\}\}^\{\\mathrm\{hyb\}\}\(S\):=1n∑i=1n𝟏\{xi∈𝒱\(S\)\}−1n∑i=1n𝟏\{xi∈𝒱\(S\)∩T\(S−i\)\}\\displaystyle:=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{x\_\{i\}\\in\\mathcal\{V\}\(S\)\\\}\-\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\big\\\{x\_\{i\}\\in\\mathcal\{V\}\(S\)\\cap T\(S^\{\-i\}\)\\big\\\}\(9\)=1n​∑i=1n𝟏​\{xi∈𝒱⁡\(S\),\#xi​\(S\)=1\}\.\\displaystyle=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{x\_\{i\}\\in\\mathcal\{V\}\(S\),\\ \\\#\_\{x\_\{i\}\}\(S\)=1\\\}\.\(10\)For the exception\-memorizing classifier,𝒢⁡\(S\)=E⁡\(S\)∖T⁡\(S\)\\mathcal\{G\}\(S\)=E\(S\)\\setminus T\(S\), we writep^𝒢hyb:=p^Ehyb\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\mathrm\{hyb\}\}:=\\hat\{p\}\_\{E\}^\{\\mathrm\{hyb\}\}\.

The right\-hand side of \([10](https://arxiv.org/html/2610.41244#S6.E10)\) is the Good–Turing estimator of the missing mass restricted to the selected region\. For a regionVVfixed in advance we writeM^V​\(S\):=1n​∑i=1n𝟏​\{xi∈V,\#xi​\(S\)=1\}\\widehat\{M\}\_\{V\}\(S\):=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{x\_\{i\}\\in V,\\ \\\#\_\{x\_\{i\}\}\(S\)=1\\\}for this*restricted Good–Turing estimator*, so thatp^𝒱hyb​\(S\)=M^𝒱⁡\(S\)​\(S\)\\hat\{p\}\_\{\\mathcal\{V\}\}^\{\\mathrm\{hyb\}\}\(S\)=\\widehat\{M\}\_\{\\mathcal\{V\}\(S\)\}\(S\)\. Sincexi∈V∖T⁡\(S−i\)x\_\{i\}\\in V\\setminus T\(S^\{\-i\}\)exactly whenxi∈Vx\_\{i\}\\in Vis a singleton,M^V\\widehat\{M\}\_\{V\}is the leave\-one\-out estimator of the out\-of\-sample piercingU↦V∖T⁡\(U\)U\\mapsto V\\setminus T\(U\), and Corollary[5\.5](https://arxiv.org/html/2610.41244#S5.Thmtheorem5)givessupD𝔼\[\(M^V​\(S\)−MV​\(S\)\)2\]=O⁡\(1/n\)\\sup\_\{D\}\\mathop\{\\mathbb\{E\}\}\[\(\\widehat\{M\}\_\{V\}\(S\)\-M\_\{V\}\(S\)\)^\{2\}\]=O\(1/n\)\. We note that for the error region of a base classifier, computing the hybrid requires running the base learner once rather thannntimes\.

The two components of the hybrid have errors of different kinds; the following lemma, immediate from \([7](https://arxiv.org/html/2610.41244#S6.E7)\) and \([9](https://arxiv.org/html/2610.41244#S6.E9)\), fixes the notation for them\.

###### Lemma 6\.1\(Error decomposition\)\.

For every region selection rule𝒱\\mathcal\{V\}and every sampleSS,

p^𝒱hyb​\(S\)−M𝒱⁡\(S\)​\(S\)=\(D^​\(𝒱⁡\(S\)\)−D⁡\(𝒱⁡\(S\)\)\)−\(p^𝒱⁡\(S\)∩Tloo​\(S\)−D⁡\(𝒱⁡\(S\)∩T⁡\(S\)\)\)\.\\hat\{p\}\_\{\\mathcal\{V\}\}^\{\\mathrm\{hyb\}\}\(S\)\-M\_\{\\mathcal\{V\}\(S\)\}\(S\)=\\Big\(\\hat\{D\}\(\\mathcal\{V\}\(S\)\)\-D\(\\mathcal\{V\}\(S\)\)\\Big\)\-\\Big\(\\hat\{p\}^\{\\mathrm\{loo\}\}\_\{\\mathcal\{V\}\(S\)\\cap T\}\(S\)\-D\\big\(\\mathcal\{V\}\(S\)\\cap T\(S\)\\big\)\\Big\)\.\(11\)Consequently, writing

ε𝒱emp​\(n\)\\displaystyle\\varepsilon^\{\\mathrm\{emp\}\}\_\{\\mathcal\{V\}\}\(n\):=supD∈Δ​𝒳𝔼S∼Dn\[\(D^​\(𝒱⁡\(S\)\)−D⁡\(𝒱⁡\(S\)\)\)2\],\\displaystyle:=\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\Big\[\\big\(\\hat\{D\}\(\\mathcal\{V\}\(S\)\)\-D\(\\mathcal\{V\}\(S\)\)\\big\)^\{2\}\\Big\],\(12\)ε𝒱loo​\(n\)\\displaystyle\\varepsilon^\{\\mathrm\{loo\}\}\_\{\\mathcal\{V\}\}\(n\):=supD∈Δ​𝒳𝔼S∼Dn\[\(p^𝒱⁡\(S\)∩Tloo​\(S\)−D⁡\(𝒱⁡\(S\)∩T⁡\(S\)\)\)2\],\\displaystyle:=\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\Big\[\\big\(\\hat\{p\}^\{\\mathrm\{loo\}\}\_\{\\mathcal\{V\}\(S\)\\cap T\}\(S\)\-D\\big\(\\mathcal\{V\}\(S\)\\cap T\(S\)\\big\)\\big\)^\{2\}\\Big\],\(13\)ε𝒱amm​\(n\)\\displaystyle\\varepsilon^\{\\mathrm\{amm\}\}\_\{\\mathcal\{V\}\}\(n\):=supD∈Δ​𝒳𝔼S∼Dn\[\(p^𝒱hyb​\(S\)−M𝒱⁡\(S\)​\(S\)\)2\]\\displaystyle:=\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\Big\[\\big\(\\hat\{p\}\_\{\\mathcal\{V\}\}^\{\\mathrm\{hyb\}\}\(S\)\-M\_\{\\mathcal\{V\}\(S\)\}\(S\)\\big\)^\{2\}\\Big\]\(14\)for the worst\-case mean\-squared errors of the empirical estimate of the selected region, of the leave\-one\-out estimate of its seen part, and of the hybrid, we have

ε𝒱amm​\(n\)≤2​ε𝒱emp​\(n\)\+2​ε𝒱loo​\(n\)\.\\varepsilon^\{\\mathrm\{amm\}\}\_\{\\mathcal\{V\}\}\(n\)\\leq 2\\,\\varepsilon^\{\\mathrm\{emp\}\}\_\{\\mathcal\{V\}\}\(n\)\+2\\,\\varepsilon^\{\\mathrm\{loo\}\}\_\{\\mathcal\{V\}\}\(n\)\.\(15\)

The first term is controlled by any of the conditions of Section[4](https://arxiv.org/html/2610.41244#S4), and the second would beO⁡\(1/n\)O\(1/n\)if the region were fixed in advance\. The key problem is the adaptivity: the estimate is evaluated at the region𝒱⁡\(S\)\\mathcal\{V\}\(S\)chosen by the same sampleSS, and this dependence invalidates the standard analysis\. One might hope that the generalization of the selection rule is sufficient to control the error: ifD^​\(𝒱​\(S\)\)\\hat\{D\}\(\\mathcal\{V\}\(S\)\)is an accurate estimate ofD⁡\(𝒱⁡\(S\)\)D\(\\mathcal\{V\}\(S\)\), perhapsM^𝒱⁡\(S\)​\(S\)\\widehat\{M\}\_\{\\mathcal\{V\}\(S\)\}\(S\)is an accurate estimate ofM𝒱⁡\(S\)​\(S\)M\_\{\\mathcal\{V\}\(S\)\}\(S\)as well\. The following proposition, proved in Appendix[C](https://arxiv.org/html/2610.41244#A3), shows that it is not\.

###### Proposition 6\.2\(Generalization of the base learner does not suffice for the hybrid estimator\)\.

There is a base learner𝒜\\mathcal\{A\}, with a symmetric error\-region ruleS↦E⁡\(S\)S\\mapsto E\(S\), such thatεEemp​\(n\)=O⁡\(1/n\)\\varepsilon^\{\\mathrm\{emp\}\}\_\{E\}\(n\)=O\(1/n\), while for the exception\-memorizing learner built from itD⁡\(𝒢⁡\(S\)\)=0D\(\\mathcal\{G\}\(S\)\)=0for every sample and

supD∈Δ​𝒳𝔼S∼Dn\[\(p^𝒢hyb​\(S\)−D⁡\(𝒢⁡\(S\)\)\)2\]=εEamm​\(n\)≥cfor every​n,\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\Big\[\\big\(\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\mathrm\{hyb\}\}\(S\)\-D\(\\mathcal\{G\}\(S\)\)\\big\)^\{2\}\\Big\]=\\varepsilon^\{\\mathrm\{amm\}\}\_\{E\}\(n\)\\geq c\\qquad\\text\{for every \}n,for an absolute constantc\>0c\>0\.

In the construction,E⁡\(S\)E\(S\)is the set of points that occur exactly once inSS, provided that the sample passes a consistency check, and it is empty otherwise\. The check compares the fraction of the sample made up of such points with the Good–Turing estimate of their mass\. Passing this check guarantees that the training error ofhSh\_\{S\}is an accurate estimate of the population errorD⁡\(E⁡\(S\)\)D\(E\(S\)\), under every distribution\. We show that the check holds with constant probability under the uniform distribution onnnpoints\. YetE⁡\(S\)E\(S\)contains no unseen point, so the memorizing classifier is perfect, whereas the hybrid counts every singleton ofE⁡\(S\)E\(S\)and reports an error of about1/e1/e\.

The proposition shows that the two ingredients of the hybrid cannot be analyzed separately: no bound of the formε𝒱amm​\(n\)≤C​ε𝒱emp​\(n\)\+O⁡\(1/n\)\\varepsilon^\{\\mathrm\{amm\}\}\_\{\\mathcal\{V\}\}\(n\)\\leq C\\,\\varepsilon^\{\\mathrm\{emp\}\}\_\{\\mathcal\{V\}\}\(n\)\+O\(1/n\)holds for all selection rules\. We note that in this construction the error of the memorizing classifier is identically zero and is therefore trivially estimatable, so the proposition is a statement about the hybrid estimator and not about estimatability\. We next give two natural conditions on the selection rule under which the error can be controlled\. The first bounds the error by the amount of information that the selected region carries about the sample\. The second bounds it by the complexity of the class of regions that the rule can output, with no restriction on how the region is chosen from the class\.

###### Theorem 6\.3\(Adaptive missing mass estimation\)\.

Let𝒱\\mathcal\{V\}be a region selection rule and letℋn\\mathcal\{H\}\_\{n\}be the class of all regions that𝒱\\mathcal\{V\}can output on samples of sizenn\. The constants in the following bounds are absolute\.

1. \(i\)For everyD∈Δ​𝒳D\\in\\Delta\\mathcal\{X\}, writingID​\(S,𝒱\)I\_\{D\}\(S;\\mathcal\{V\}\)for the mutual information \(in nats\) between the sampleS∼DnS\\sim D^\{n\}and the selected region, 𝔼S∼Dn\[\(M^𝒱⁡\(S\)​\(S\)−M𝒱⁡\(S\)​\(S\)\)2\]=O⁡\(ID​\(S,𝒱\)\+1n\)\.\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\Big\[\\big\(\\widehat\{M\}\_\{\\mathcal\{V\}\(S\)\}\(S\)\-M\_\{\\mathcal\{V\}\(S\)\}\(S\)\\big\)^\{2\}\\Big\]=O\\Big\(\\frac\{I\_\{D\}\(S;\\mathcal\{V\}\)\+1\}\{n\}\\Big\)\.In particular, if𝒱\\mathcal\{V\}takes at mostLLvalues thenε𝒱amm​\(n\)=O⁡\(\(log⁡L\+1\)/n\)\\varepsilon^\{\\mathrm\{amm\}\}\_\{\\mathcal\{V\}\}\(n\)=O\\big\(\(\\log L\+1\)/n\\big\)\.
2. \(ii\)Ifdn:=VC⁡\(ℋn\)d\_\{n\}:=\\operatorname\{VC\}\(\\mathcal\{H\}\_\{n\}\)satisfies1≤dn≤n1\\leq d\_\{n\}\\leq n, then ε𝒱amm​\(n\)=O⁡\(dn​log⁡\(e​n/dn\)n\)\.\\varepsilon^\{\\mathrm\{amm\}\}\_\{\\mathcal\{V\}\}\(n\)=O\\Big\(\\frac\{d\_\{n\}\\log\(en/d\_\{n\}\)\}\{n\}\\Big\)\.

In particular,ε𝒱amm​\(n\)→0\\varepsilon^\{\\mathrm\{amm\}\}\_\{\\mathcal\{V\}\}\(n\)\\to 0wheneversupDID​\(S,𝒱\)=o⁡\(n\)\\sup\_\{D\}I\_\{D\}\(S;\\mathcal\{V\}\)=o\(n\)ordn=o⁡\(n\)d\_\{n\}=o\(n\)\.

The proof of part[\(i\)](https://arxiv.org/html/2610.41244#S6.I1.i1), given in Appendix[C\.3](https://arxiv.org/html/2610.41244#A3.SS3), uses known concentration results for the missing mass\([McAllester and Ortiz, 2003](https://arxiv.org/html/2610.41244#bib.bib56)\)to show that for every region fixed in advance, the error of the restricted Good–Turing estimator is sub\-Gaussian at scale1/n1/\\sqrt\{n\}\. It then uses the Donsker–Varadhan variational inequality to decouple the selected region from the sample at a price ofID​\(S,𝒱\)I\_\{D\}\(S;\\mathcal\{V\}\)\. This approach is common in information\-theoretic generalization bounds mentioned in Section[3\.3](https://arxiv.org/html/2610.41244#S3.SS3)\. The information\-theoretic argument immediately implies a cardinality\-based bound which can also be derived via the union bound from the concentration results of[McAllester and Ortiz \(2003\)](https://arxiv.org/html/2610.41244#bib.bib56)\. To derive part[\(ii\)](https://arxiv.org/html/2610.41244#S6.I1.i2), proved in Appendix[C\.4](https://arxiv.org/html/2610.41244#A3.SS4), we rely on the cardinality\-based bound together with standard covering arguments based on the VC dimension\. The two conditions are incomparable\. The class of all singletons has VC dimension11, yet the rule𝒱⁡\(S\)=\{min⁡T⁡\(S\)\}\\mathcal\{V\}\(S\)=\\\{\\min T\(S\)\\\}on𝒳=ℕ\\mathcal\{X\}=\\mathbb\{N\}, which is symmetric, can reveal arbitrarily many nats about the sample, so[\(ii\)](https://arxiv.org/html/2610.41244#S6.I1.i2)is not a consequence of[\(i\)](https://arxiv.org/html/2610.41244#S6.I1.i1); conversely, a rule whose output carries little information about the sample may range over a class of large VC dimension\.

##### Implications for the error of a memorizing classifier\.

Theorem[6\.3](https://arxiv.org/html/2610.41244#S6.Thmtheorem3)can be directly translated into analogous bounds on the error of the hybrid estimator for the exception\-memorizing classifier, with the VC dimension of the error\-region classℰn:=\{E⁡\(S\):S∈𝒳n\}\\mathcal\{E\}\_\{n\}:=\\\{E\(S\):S\\in\\mathcal\{X\}^\{n\}\\\}replacing that ofℋn\\mathcal\{H\}\_\{n\}, and\|ℰn\|\|\\mathcal\{E\}\_\{n\}\|replacingLL\. The conditionVC⁡\(ℰn\)=o⁡\(n\)\\operatorname\{VC\}\(\\mathcal\{E\}\_\{n\}\)=o\(n\)is the same one that makes the error of the base learner itself estimatable by the empirical estimator \(Corollary[4\.1](https://arxiv.org/html/2610.41244#S4.Thmtheorem1)\)\. The theorem shows that it also makes the error of the memorizing learner built on top of it estimatable, via the hybrid, even though for this learner the empirical estimator is identically zero\.

Finally, we observe that the VC dimension of the error\-region class is bounded for every base learner whose output is constrained to a hypothesis class of bounded VC dimension, for every possible labeling of the data\. To state this uniformly over labelings, let the base learner𝒜\\mathcal\{A\}be defined on all labeled samples in\(𝒲×𝒴\)n\(\\mathcal\{W\}\\times\\mathcal\{Y\}\)^\{n\}, so that it applies to every labelingy:𝒲→𝒴y:\\mathcal\{W\}\\to\\mathcal\{Y\}, and write𝒳y:=\{\(w,y⁡\(w\)\):w∈𝒲\}\\mathcal\{X\}\_\{y\}:=\\\{\(w,y\(w\)\):w\\in\\mathcal\{W\}\\\},Ey​\(S\):=\{\(w,y⁡\(w\)\)∈𝒳y:hS​\(w\)≠y⁡\(w\)\}E^\{y\}\(S\):=\\\{\(w,y\(w\)\)\\in\\mathcal\{X\}\_\{y\}:h\_\{S\}\(w\)\\neq y\(w\)\\\},ℰny:=\{Ey​\(S\):S∈𝒳yn\}\\mathcal\{E\}\_\{n\}^\{y\}:=\\\{E^\{y\}\(S\):S\\in\\mathcal\{X\}\_\{y\}^\{n\}\\\}, and𝒢y​\(S\):=Ey​\(S\)∖T⁡\(S\)\\mathcal\{G\}\_\{y\}\(S\):=E^\{y\}\(S\)\\setminus T\(S\)for the example space, the error regions of𝒜\\mathcal\{A\}, and the error region of the exception\-memorizing learner under the labelingyy\.

###### Corollary 6\.4\(Base learners with a hypothesis class of bounded VC dimension\)\.

Let𝒴=\{0,1\}\\mathcal\{Y\}=\\\{0,1\\\}, letℋ⊆\{0,1\}𝒲\\mathcal\{H\}\\subseteq\\\{0,1\\\}^\{\\mathcal\{W\}\}be a class withVC⁡\(ℋ\)=d\\operatorname\{VC\}\(\\mathcal\{H\}\)=d, and let𝒜\\mathcal\{A\}be a base learner whose output lies inℋ\\mathcal\{H\}on every labeled sample\. ThenVC⁡\(ℰny\)≤d\\operatorname\{VC\}\(\\mathcal\{E\}\_\{n\}^\{y\}\)\\leq dfor every labelingyyand everynn\. Consequently, if1≤d≤n1\\leq d\\leq n, then for every labelingyythe hybrid estimator for the error of the exception\-memorizing learner built from𝒜\\mathcal\{A\}satisfies

supD∈Δ​𝒳y𝔼S∼Dn\[\(p^𝒢yhyb​\(S\)−D⁡\(𝒢y​\(S\)\)\)2\]=O⁡\(d​log⁡\(e​n/d\)n\),\\sup\_\{D\\in\\Delta\\mathcal\{X\}\_\{y\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\Big\[\\big\(\\hat\{p\}\_\{\\mathcal\{G\}\_\{y\}\}^\{\\mathrm\{hyb\}\}\(S\)\-D\(\\mathcal\{G\}\_\{y\}\(S\)\)\\big\)^\{2\}\\Big\]=O\\Big\(\\frac\{d\\log\(en/d\)\}\{n\}\\Big\),with an absolute constant that does not depend onyy\.

The proof \(in Appendix[C\.5](https://arxiv.org/html/2610.41244#A3.SS5)\) follows directly from the definition of VC dimension\. The indicator of the error region ofhhrelative toyyisw↦h⁡\(w\)⊕y⁡\(w\)w\\mapsto h\(w\)\\oplus y\(w\), with⊕\\oplusaddition modulo22, and addingyypointwise is a bijection on the labelings of any finite set, so a set is shattered by the error regions ofℋ\\mathcal\{H\}if and only if it is shattered byℋ\\mathcal\{H\}\. Note that the labeling need not belong toℋ\\mathcal\{H\}, and the estimator is the same for every labeling, since \([10](https://arxiv.org/html/2610.41244#S6.E10)\) is computed from the labeled sample andhSh\_\{S\}alone\. The corollary extends to an arbitrary label set, withVC⁡\(ℋ\)\\operatorname\{VC\}\(\\mathcal\{H\}\)replaced by the graph dimension ofℋ\\mathcal\{H\}; see Corollary[C\.7](https://arxiv.org/html/2610.41244#A3.Thmtheorem7)in Appendix[C\.5](https://arxiv.org/html/2610.41244#A3.SS5)\.

For the neighborhood\-correcting learner𝒜N\\mathcal\{A\}\_\{N\}, bounding the error of the hybrid estimator beyond the memorization case is an open problem, discussed in Section[8](https://arxiv.org/html/2610.41244#S8)\.

## 7The Limits of Estimatability

Our framework leads to a natural question: when is a data\-dependent function𝒢\\mathcal\{G\}estimatable by*some*procedure? We first observe that standard lower bounds on learnability of function classes or distributions do not directly imply the existence of non\-estimatable mappings, nor do classical estimation lower bounds \(Appendix[E](https://arxiv.org/html/2610.41244#A5)\)\. In these lower bounds, one usually proves that the error of the learning process is high with high probability\. Such a lower bound typically defines an event \(or set corresponding to the loss\) whose probability is high and, importantly, known\. We demonstrate that there exist ways to define functions𝒢\\mathcal\{G\}in the transition between the learnable regime and the hard regime so that the defined event is not estimatable\.

We give three constructions of non\-estimatable events, of decreasing domain size, which we include for completeness: the first and simplest uses a domain of size22n\+12^\{2^\{n\}\+1\}, the second2n\+22^\{n\+2\}, and the third onlyO⁡\(n2\)O\(n^\{2\}\)\. The first construction is a simple instance of post\-selection which shows that even a simple event that selects the coordinate with the largest empirical mean cannot be estimated when the number of coordinates is exponentially large innn\. The second construction corresponds to learning parity functions and is close to the constructions of[Gastpar et al\. \(2024a\)](https://arxiv.org/html/2610.41244#bib.bib36), and the third is a random code, as is the construction underlying Theorem 2\.1 of[Gastpar et al\. \(2024b\)](https://arxiv.org/html/2610.41244#bib.bib37)\. Since both are stated directly in terms of events, their proofs are self\-contained and, we believe, somewhat simpler\. The mechanism in all three constructions is the same\. With constant probability the sample is consistent with a small number of candidate distributions that are equally likely given the sample, and the selected event has different masses under them, so that no estimator can do better than the posterior variance of the target\.

###### Theorem 7\.1\.

For everyn≥1n\\geq 1, letd=2n\+1d=2^\{n\}\+1and𝒳n=\{0,1\}d\\mathcal\{X\}\_\{n\}=\\\{0,1\\\}^\{d\}\. ForS∈𝒳nnS\\in\\mathcal\{X\}\_\{n\}^\{n\}, leti⁡\(S\)i\(S\)be the smallest coordinatej∈\[d\]j\\in\[d\]maximizingμ^j​\(S\)=1n​∑t=1nxt,j\\widehat\{\\mu\}\_\{j\}\(S\)=\\frac\{1\}\{n\}\\sum\_\{t=1\}^\{n\}x\_\{t,j\}, and define

𝒢max​\(S\)=\{x∈𝒳n:xi⁡\(S\)=1\}\.\\mathcal\{G\}\_\{\\max\}\(S\)=\\\{x\\in\\mathcal\{X\}\_\{n\}:x\_\{i\(S\)\}=1\\\}\.Then no estimator achieves mean\-squared error below1/641/64for𝒢max\\mathcal\{G\}\_\{\\max\}\.

###### Proof\.

For eachj∈\[d\]j\\in\[d\], letDjD\_\{j\}be the product distribution on𝒳n\\mathcal\{X\}\_\{n\}in which coordinatejjis deterministically11and every coordinatek≠jk\\neq jis an independentBern⁡\(1/2\)\\mathrm\{Bern\}\(1/2\)random variable\. For these product laws,Dj​\(𝒢max​\(S\)\)D\_\{j\}\(\\mathcal\{G\}\_\{\\max\}\(S\)\)is exactly the mean of the coordinate selected by the maximum empirical mean rule\.

Fix any estimatorp^:𝒳nn→\[0,1\]\\hat\{p\}:\\mathcal\{X\}\_\{n\}^\{n\}\\to\[0,1\]\. It suffices to lower\-bound the Bayes risk whenJJis uniform on\[d\]\[d\]and, conditional onJJ,S∼DJnS\\sim D\_\{J\}^\{n\}\. Given the sample, let

A⁡\(S\)=\{k∈\[d\]:xt,k=1​for all​t∈\[n\]\}A\(S\)=\\\{k\\in\[d\]:x\_\{t,k\}=1\\ \\text\{for all \}t\\in\[n\]\\\}be the set of all\-one coordinates\. Sinceμ^j​\(S\)=1\\widehat\{\\mu\}\_\{j\}\(S\)=1exactly whenj∈A⁡\(S\)j\\in A\(S\), andA⁡\(S\)≠∅A\(S\)\\neq\\emptysetbecauseJ∈A⁡\(S\)J\\in A\(S\), the maximum empirical mean equals11and its argmax set isA⁡\(S\)A\(S\); hencei⁡\(S\)=min⁡A⁡\(S\)i\(S\)=\\min A\(S\)\. Moreover, eachk≠Jk\\neq Jlies inA⁡\(S\)A\(S\)independently with probability2−n2^\{\-n\}\. LetEEbe the event\|A⁡\(S\)\|=2\|A\(S\)\|=2\. Then

ℙ\[E\]=\(d−1\)​2−n​\(1−2−n\)d−2=\(1−2−n\)2n−1≥14,\\mathop\{\\mathbb\{P\}\}\[E\]=\(d\-1\)2^\{\-n\}\(1\-2^\{\-n\}\)^\{d\-2\}=\(1\-2^\{\-n\}\)^\{2^\{n\}\-1\}\\geq\\frac\{1\}\{4\},where the last inequality holds because\(1−2−n\)2n−1\(1\-2^\{\-n\}\)^\{2^\{n\}\-1\}is decreasing innnwith limite−1\>1/4e^\{\-1\}\>1/4\.

Now fix a realizationSSfor whichEEholds and writeA⁡\(S\)=\{a,b\}A\(S\)=\\\{a,b\\\}witha<ba<b\. By symmetry,

ℙ\[J=a∣S\]=ℙ\[J=b∣S\]=12\.\\mathop\{\\mathbb\{P\}\}\[J=a\\mid S\]=\\mathop\{\\mathbb\{P\}\}\[J=b\\mid S\]=\\frac\{1\}\{2\}\.On this realization,i⁡\(S\)=ai\(S\)=a\. Therefore

DJ​\(𝒢max​\(S\)\)=\{1,if​J=a,1/2,if​J=b\.D\_\{J\}\(\\mathcal\{G\}\_\{\\max\}\(S\)\)=\\begin\{cases\}1,&\\mbox\{if \}J=a,\\\\ 1/2,&\\mbox\{if \}J=b\.\\end\{cases\}Conditioned onSSandEE, the target is thus uniform on\{1,1/2\}\\\{1,1/2\\\}, so every estimate has conditional squared loss at least its variance, namely1/161/16\. Averaging,

𝔼J,S\[\(p^​\(S\)−DJ​\(𝒢max​\(S\)\)\)2\]≥ℙ\[E\]⋅116≥164\.\\mathop\{\\mathbb\{E\}\}\_\{J,S\}\\left\[\\left\(\\hat\{p\}\(S\)\-D\_\{J\}\(\\mathcal\{G\}\_\{\\max\}\(S\)\)\\right\)^\{2\}\\right\]\\geq\\mathop\{\\mathbb\{P\}\}\[E\]\\cdot\\frac\{1\}\{16\}\\geq\\frac\{1\}\{64\}\.Since the supremum overD∈Δ​𝒳nD\\in\\Delta\\mathcal\{X\}\_\{n\}is at least this average overD1,…,DdD\_\{1\},\\ldots,D\_\{d\}, the claim follows\. ∎

A limitation of the lower bound in Theorem[7\.1](https://arxiv.org/html/2610.41244#S7.Thmtheorem1)is that it requires an input space of size22Ω⁡\(n\)2^\{2^\{\\Omega\(n\)\}\}\. Next, we give another example of a hard\-to\-estimate event that directly corresponds to learning parity functions in dimensionn\+2n\+2\. This example is still relatively easy to analyze and the input space size is exponentially smaller:2n\+22^\{n\+2\}\.

###### Theorem 7\.2\.

For everyn∈ℕn\\in\\mathbb\{N\}, let𝒳=𝔽2n\+2\\mathcal\{X\}=\\mathbb\{F\}\_\{2\}^\{n\+2\}\. For a sampleS∈𝒳nS\\in\\mathcal\{X\}^\{n\}, let

VS=\{w∈𝔽2n\+2:⟨xi,w⟩=0​for all​i∈\[n\]\},V\_\{S\}=\\\{w\\in\\mathbb\{F\}\_\{2\}^\{n\+2\}:\\langle x\_\{i\},w\\rangle=0\\ \\text\{for all \}i\\in\[n\]\\\},letzSz\_\{S\}be the lexicographically first non\-zero vector inVSV\_\{S\}ifVS≠\{0\}V\_\{S\}\\neq\\\{0\\\}, andzS=0z\_\{S\}=0otherwise, and define𝒢⁡\(S\)=\{x∈𝒳:⟨x,zS⟩=0\}\\mathcal\{G\}\(S\)=\\\{x\\in\\mathcal\{X\}:\\langle x,z\_\{S\}\\rangle=0\\\}\. Then no estimator achieves mean\-squared error below1/361/36for𝒢\\mathcal\{G\}\.

###### Proof of Theorem[7\.2](https://arxiv.org/html/2610.41244#S7.Thmtheorem2)\.

Fixn∈ℕn\\in\\mathbb\{N\}and let𝒳=𝔽2n\+2\\mathcal\{X\}=\\mathbb\{F\}\_\{2\}^\{n\+2\}\. For any vectorw∈𝔽2n\+2w\\in\\mathbb\{F\}\_\{2\}^\{n\+2\}, definew⟂:=\{u∈𝔽2n\+2∣⟨u,w⟩=0\}w^\{\\perp\}:=\\\{u\\in\\mathbb\{F\}\_\{2\}^\{n\+2\}\\mid\\langle u,w\\rangle=0\\\}, i\.e\., the subspace orthogonal toww, which has dimensionn\+1n\+1\(wheneverw≠0w\\neq 0\)\. The function𝒢\\mathcal\{G\}is defined in the theorem statement\. Note that both𝒳\\mathcal\{X\}and𝒢\\mathcal\{G\}depend onnn\. This still yields a single non\-estimatable mapping on a fixed countable domain\. Concretely, one may take𝒳=\{0,1\}⋆\\mathcal\{X\}=\\\{0,1\\\}^\{\\star\}, the \(countable\) set of all finite binary strings, and apply the construction to the projection of each sample point onto its firstn\+2n\+2coordinates, padding with zeros as needed\.

Next, consider the following distribution over input distributions \(which may depend onnn\)\. Choose a non\-zero vectorz∈𝔽2n\+2z\\in\\mathbb\{F\}\_\{2\}^\{n\+2\}uniformly at random, and letDzD\_\{z\}be the uniform distribution onz⟂\.z^\{\\perp\}\.Now, letp^:𝒳n→\[0,1\]\\hat\{p\}:\\mathcal\{X\}^\{n\}\\to\[0,1\]be any purported estimator\. We will show that

𝔼z,S\[\(p^​\(S\)−Dz​\(𝒢⁡\(S\)\)\)2\]≥c:=136,\\mathop\{\\mathbb\{E\}\}\_\{z,S\}\[\(\\hat\{p\}\(S\)\-D\_\{z\}\(\\mathcal\{G\}\(S\)\)\)^\{2\}\]\\geq c:=\\tfrac\{1\}\{36\},which implies thatp^\\hat\{p\}is not a constant\-error estimator for𝒢\\mathcal\{G\}\.

To prove this, first note that underDzD\_\{z\}, eachxix\_\{i\}is uniform on the\(n\+1\)\(n\+1\)\-dimensional spacez⟂z^\{\\perp\}, so the probability thatSSis linearly independent is

p:=\(1−12n\+1\)\(1−22n\+1\)⋯\(1−2n−12n\+1\)≥1−12n\+1−⋯−2n−12n\+1=1−2n−12n\+1≥12\.p:=\\left\(1\-\\frac\{1\}\{2^\{n\+1\}\}\\right\)\\left\(1\-\\frac\{2\}\{2^\{n\+1\}\}\\right\)\\cdots\\left\(1\-\\frac\{2^\{n\-1\}\}\{2^\{n\+1\}\}\\right\)\\;\\geq\\;1\-\\frac\{1\}\{2^\{n\+1\}\}\-\\cdots\-\\frac\{2^\{n\-1\}\}\{2^\{n\+1\}\}=1\-\\frac\{2^\{n\}\-1\}\{2^\{n\+1\}\}\\;\\geq\\;\\frac\{1\}\{2\}\.Next, given a linearly independent sample setSS, there are exactly 3 non\-zero vectors orthogonal to all elements ofSS, one of which iszSz\_\{S\}\. If the other two non\-zero vectors orthogonal toSSareuuandvv, then by symmetry,ℙ\[z=zS∣S\]=ℙ\[z=u∣S\]=ℙ\[z=v∣S\]=13\\mathop\{\\mathbb\{P\}\}\[z=z\_\{S\}\\mid S\]=\\mathop\{\\mathbb\{P\}\}\[z=u\\mid S\]=\\mathop\{\\mathbb\{P\}\}\[z=v\\mid S\]=\\frac\{1\}\{3\}\. Furthermore, ifz=zSz=z\_\{S\}, then𝒢⁡\(S\)\\mathcal\{G\}\(S\)contains all ofzS⟂z\_\{S\}^\{\\perp\}, soDz​\(𝒢​\(S\)\)=1D\_\{z\}\(\\mathcal\{G\}\(S\)\)=1\. Ifz≠zSz\\neq z\_\{S\}\(i\.e\.,z∈\{u,v\}z\\in\\\{u,v\\\}\), thenz⟂∩zS⟂z^\{\\perp\}\\cap z\_\{S\}^\{\\perp\}has dimensionnn, so withinz⟂z^\{\\perp\}we haveDz​\(𝒢⁡\(S\)\)=2n2n\+1=12D\_\{z\}\(\\mathcal\{G\}\(S\)\)=\\frac\{2^\{n\}\}\{2^\{n\+1\}\}=\\frac\{1\}\{2\}\.

Thus conditioned on the linear independence ofSS, the variance of the target value is easily computed to be1/181/18\. Since independence holds with probability at least1/21/2, we conclude that𝔼z,S\[\(p^​\(S\)−Dz​\(𝒢⁡\(S\)\)\)2\]≥136\\mathop\{\\mathbb\{E\}\}\_\{z,S\}\[\(\\hat\{p\}\(S\)\-D\_\{z\}\(\\mathcal\{G\}\(S\)\)\)^\{2\}\]\\geq\\frac\{1\}\{36\}\. ∎

### 7\.1Hardness on a Domain of Quadratic Size

Both constructions above require a domain that is exponential innn\. We now show that non\-estimatability already arises on a domain whose size is only*quadratic*innn\.

###### Theorem 7\.3\.

For everyn≥2n\\geq 2there is a domain𝒳n\\mathcal\{X\}\_\{n\}with\|𝒳n\|=2​n2\|\\mathcal\{X\}\_\{n\}\|=2n^\{2\}and a function𝒢n:𝒳nn→\{0,1\}𝒳n\\mathcal\{G\}\_\{n\}:\\mathcal\{X\}\_\{n\}^\{n\}\\to\\\{0,1\\\}^\{\\mathcal\{X\}\_\{n\}\}such that

infp^:𝒳nn→\[0,1\]supD∈Δ⁡\(𝒳n\)𝔼S∼Dn\[\(p^\(S\)−D\(𝒢n\(S\)\)\)2\]≥1576\.\\inf\_\{\\hat\{p\}:\\mathcal\{X\}\_\{n\}^\{n\}\\to\[0,1\]\}\\sup\_\{D\\in\\Delta\(\\mathcal\{X\}\_\{n\}\)\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\left\[\\left\(\\hat\{p\}\(S\)\-D\(\\mathcal\{G\}\_\{n\}\(S\)\)\\right\)^\{2\}\\right\]\\geq\\frac\{1\}\{576\}\.

##### Proof outline\.

The full proof is in Appendix[D](https://arxiv.org/html/2610.41244#A4); we sketch the idea\. Fixw=n2w=n^\{2\},m=2​wm=2wand𝒳n=\[m\]\\mathcal\{X\}\_\{n\}=\[m\]\. We select a random “code” ofMMsetsV1,…,VMV\_\{1\},\\ldots,V\_\{M\}, each an independent uniformly randomww\-subset of\[m\]\[m\], withM=⌊1/pn⌋\+1M=\\lfloor 1/p\_\{n\}\\rfloor\+1, wherepn=ℙ\[T⊆Vj\]p\_\{n\}=\\mathop\{\\mathbb\{P\}\}\[T\\subseteq V\_\{j\}\]for a fixednn\-element setTT\(sopn≤2−np\_\{n\}\\leq 2^\{\-n\}andM≈2nM\\approx 2^\{n\}\)\. LetDiD\_\{i\}be uniform onViV\_\{i\}, and let𝒢𝒞​\(S\)\\mathcal\{G\}\_\{\\mathcal\{C\}\}\(S\)output the first setViV\_\{i\}that contains the sampled setT⁡\(S\)=\{x1,…,xn\}T\(S\)=\\\{x\_\{1\},\\dots,x\_\{n\}\\\}\. Consider the Bayesian experiment withIIuniform on\[M\]\[M\]andS∼DInS\\sim D\_\{I\}^\{n\}\. With constant probability the sample has no repetitions, and then the number of*other*VjV\_\{j\}’s containingT⁡\(S\)T\(S\)isBinomial⁡\(M−1,pn\)\\mathrm\{Binomial\}\(M\-1,p\_\{n\}\), which takes the value11with constant probability\. In that case there are exactly two candidate supportsVaV\_\{a\}andVbV\_\{b\}, the posterior distribution ofIIis uniform on\{a,b\}\\\{a,b\\\}, and the estimand is11for one of them andρ=\|Va∩Vb\|/w\\rho=\|V\_\{a\}\\cap V\_\{b\}\|/wfor the other\. The other candidate is a uniformly randomww\-set containingT⁡\(S\)T\(S\), so𝔼\[1−ρ\]=\(n−1\)/\(2​n−1\)≥1/3\\mathop\{\\mathbb\{E\}\}\[1\-\\rho\]=\(n\-1\)/\(2n\-1\)\\geq 1/3, and by Jensen’s inequality the posterior variance\(1−ρ\)2/4\(1\-\\rho\)^\{2\}/4is at least1/361/36on average\. Averaging over the code and applying the probabilistic method fixes a single code\.

We remark that in this case the image classℋn=\{𝒢𝒞​\(S\):S∈𝒳nn\}\\mathcal\{H\}\_\{n\}=\\\{\\mathcal\{G\}\_\{\\mathcal\{C\}\}\(S\):S\\in\\mathcal\{X\}\_\{n\}^\{n\}\\\}has sizeM\+1≤2n\+1M\+1\\leq 2^\{n\+1\}, so its VC dimension is at mostn\+1n\+1\.

## 8Discussion and Open Problems

In this work we studied data\-dependent probability estimation via a unified framework that incorporates a variety of existing problems and methods, and used it to estimate the error of exception\-memorizing predictors via adaptive missing mass estimation\. We also described several limitations on estimatability\. Our results suggest that estimatability can arise from fundamentally different structural properties\. Empirical estimators exploit generalization control, for example through low complexity of the induced image class, algorithmic stability, differential privacy, or information\-theoretic bounds, while leave\-one\-out estimators rely on stability under small perturbations of the sample\. Understanding how these principles interact, and whether they admit a unified characterization, remains an intriguing direction for future work\. We list a few directions below\.

##### Characterizing estimatability\.

The most fundamental open problem is to characterize which functions𝒢:𝒳⋆→\{0,1\}𝒳\\mathcal\{G\}:\\mathcal\{X\}^\{\\star\}\\to\\\{0,1\\\}^\{\\mathcal\{X\}\}are estimatable\. Our results provide several sufficient conditions and impossibility results, but a complete characterization remains open\. In particular, it is unclear whether there exists a single structural notion that captures estimatability, or whether fundamentally different mechanisms are unavoidable\.

##### Domain size of hard instances\.

Theorem[7\.3](https://arxiv.org/html/2610.41244#S7.Thmtheorem3)gives a non\-estimatable mapping on a domain of sizeO⁡\(n2\)O\(n^\{2\}\)\. On the other hand, if\|𝒳n\|=o⁡\(n\)\|\\mathcal\{X\}\_\{n\}\|=o\(n\), then for*every*𝒢\\mathcal\{G\}the image classℋn=\{𝒢⁡\(S\):S∈𝒳nn\}\\mathcal\{H\}\_\{n\}=\\\{\\mathcal\{G\}\(S\):S\\in\\mathcal\{X\}\_\{n\}^\{n\}\\\}has VC dimension at most\|𝒳n\|=o⁡\(n\)\|\\mathcal\{X\}\_\{n\}\|=o\(n\), so the empirical estimator is already consistent by Corollary[4\.1](https://arxiv.org/html/2610.41244#S4.Thmtheorem1)\. Closing the gap between this linear lower bound and the quadratic construction is a natural and interesting open problem\.

##### Neighborhood\-correcting learners\.

Our results for the exception\-memorizing learner concern a classifier that overrides the base classifier only at the training points themselves\. In practice a memorized exception is also used to correct the predictions on nearby inputs, and the natural model is a learner that correctshSh\_\{S\}on the neighborhoodN⁡\(x\)N\(x\)of every exceptionxxin the sample, for a neighborhood functionNNas in Section[5\.1](https://arxiv.org/html/2610.41244#S5.SS1.SSS0.Px1)\(Definition[6\.1](https://arxiv.org/html/2610.41244#S6.Thmdefinition1)\)\. Its error region isE⁡\(S\)E\(S\)with the part covered by the neighborhoods of the sample points inE⁡\(S\)E\(S\)removed, and the hybrid estimator extends naturally: the mass ofE⁡\(S\)E\(S\)is estimated by the training error, and the corrected mass by leave\-one\-out with the region held fixed\. For a region fixed in advance the corrected part is a union of neighborhoods, so the second estimate isO⁡\(1/n\)O\(1/n\)\-accurate by Theorem[5\.3](https://arxiv.org/html/2610.41244#S5.Thmtheorem3)\. What is missing is the adaptive step\. The proof of Theorem[6\.3](https://arxiv.org/html/2610.41244#S6.Thmtheorem3)rests on exponential concentration of the error of the restricted Good–Turing estimator for a fixed region, which comes from the concentration of the missing mass\([McAllester and Ortiz, 2003](https://arxiv.org/html/2610.41244#bib.bib56)\)together with a bounded\-differences argument for the count of singletons\. Neither ingredient is available once neighborhoods are involved: in general a single sample point can cover or uncover many others, so the leave\-one\-out estimate of the corrected mass does not have bounded differences, and the indicators of the uncovered points need not be negatively associated, so the argument for the missing mass does not apply\. For the uncovered mass itself, concentration is known only under additional conditions in metric spaces\([Maurer, 2022](https://arxiv.org/html/2610.41244#bib.bib55)\)\. Establishing such concentration, or bounding the error of the hybrid for neighborhood\-correcting learners by other means, in terms of the complexity of the error\-region class or the information it carries about the sample, is an open problem\.

##### Optimal rates and complexity measures\.

Our analysis primarily focuses on establishing consistency under broad conditions\. A natural next step is to determine optimal rates of convergence for different families of functions𝒢\\mathcal\{G\}\.

##### Beyond the current estimators\.

The examples in this work suggest that empirical and leave\-one\-out estimators are complementary rather than competing approaches and can be combined to obtain new estimators\. This raises the possibility of developing new estimators that adaptively combine multiple structural properties of𝒢\\mathcal\{G\}\. Understanding the space of such estimators, and identifying natural problems that require genuinely new techniques, is an interesting direction for future work\.

#### AI Use Disclosure

The authors formulated the framework, initiated the research on all questions and wrote a preliminary draft of this work\. All parts of this version were created via an interactive process in which AI \(Claude Opus/Fable;ChatGPT Sol/Astra\) generated drafts, details of proofs, and improved authors’ proofs based on author\-provided structure and instructions\. The resulting text was also extensively edited and proofread by the authors\. The authors take full responsibility for the content of this paper\.

## Appendix AResults for the Empirical Estimator

###### Definition A\.1\(VC dimension\([Vapnik and Chervonenkis, 1971](https://arxiv.org/html/2610.41244#bib.bib80)\)\)\.

Letℋ⊆\{0,1\}𝒳\\mathcal\{H\}\\subseteq\\\{0,1\\\}^\{\\mathcal\{X\}\}\. A set\{x1,…,xd\}⊆𝒳\\\{x\_\{1\},\\ldots,x\_\{d\}\\\}\\subseteq\\mathcal\{X\}is shattered byℋ\\mathcal\{H\}if, for everyy1,…,yd∈\{0,1\}y\_\{1\},\\ldots,y\_\{d\}\\in\\\{0,1\\\}, there existsh∈ℋh\\in\\mathcal\{H\}such thath⁡\(xi\)=yih\(x\_\{i\}\)=y\_\{i\}for alli∈\[d\]i\\in\[d\]\. The VC dimension ofℋ\\mathcal\{H\}, denotedVC⁡\(ℋ\)\\operatorname\{VC\}\(\\mathcal\{H\}\), is the largest integerd≥0d\\geq 0for which there exists a set\{x1,…,xd\}⊆𝒳\\\{x\_\{1\},\\ldots,x\_\{d\}\\\}\\subseteq\\mathcal\{X\}that is shattered byℋ\\mathcal\{H\}\.

This section proves Corollary[4\.1](https://arxiv.org/html/2610.41244#S4.Thmtheorem1)and Theorem[4\.2](https://arxiv.org/html/2610.41244#S4.Thmtheorem2)of Section[4](https://arxiv.org/html/2610.41244#S4)and shows that the two complexity measures they involve are incomparable\.

For a classℱ\\mathcal\{F\}of subsets of𝒳\\mathcal\{X\}we write

‖D^−D‖ℱ:=supF∈ℱ\|D^​\(F\)−D⁡\(F\)\|\\\|\\hat\{D\}\-D\\\|\_\{\\mathcal\{F\}\}:=\\sup\_\{F\\in\\mathcal\{F\}\}\\big\|\\hat\{D\}\(F\)\-D\(F\)\\big\|for the uniform deviation of the empirical measure overℱ\\mathcal\{F\}\. Both Corollary[4\.1](https://arxiv.org/html/2610.41244#S4.Thmtheorem1)and the VC bound for adaptive missing mass \(Appendix[C\.4](https://arxiv.org/html/2610.41244#A3.SS4)\) rest on the following bound\.

###### Lemma A\.1\(Uniform deviation\)\.

IfVC⁡\(ℱ\)=v<∞\\operatorname\{VC\}\(\\mathcal\{F\}\)=v<\\inftythensupD∈Δ​𝒳𝔼S∼Dn\[‖D^−D‖ℱ2\]=O⁡\(\(v\+1\)/n\)\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\big\[\\\|\\hat\{D\}\-D\\\|\_\{\\mathcal\{F\}\}^\{2\}\\big\]=O\\big\(\(v\+1\)/n\\big\)\.

###### Proof\.

The classical chaining bound on the Rademacher complexity of a VC class gives𝔼‖D^−D‖ℱ=O⁡\(\(v\+1\)/n\)\\mathop\{\\mathbb\{E\}\}\\\|\\hat\{D\}\-D\\\|\_\{\\mathcal\{F\}\}=O\\big\(\\sqrt\{\(v\+1\)/n\}\\big\)\([Talagrand, 1994](https://arxiv.org/html/2610.41244#bib.bib75);[Boucheron et al\., 2013](https://arxiv.org/html/2610.41244#bib.bib14);[Vershynin, 2018](https://arxiv.org/html/2610.41244#bib.bib81)\), and‖D^−D‖ℱ\\\|\\hat\{D\}\-D\\\|\_\{\\mathcal\{F\}\}changes by at most1/n1/nwhen one sample point is replaced, so the bounded\-differences form of the Efron–Stein inequality\([Boucheron et al\., 2013](https://arxiv.org/html/2610.41244#bib.bib14)\)givesVar⁡\(‖D^−D‖ℱ\)≤1/\(4​n\)\\operatorname\{Var\}\(\\\|\\hat\{D\}\-D\\\|\_\{\\mathcal\{F\}\}\)\\leq 1/\(4n\)\. Hence𝔼‖D^−D‖ℱ2=\(𝔼‖D^−D‖ℱ\)2\+Var⁡\(‖D^−D‖ℱ\)=O⁡\(\(v\+1\)/n\)\\mathop\{\\mathbb\{E\}\}\\\|\\hat\{D\}\-D\\\|\_\{\\mathcal\{F\}\}^\{2\}=\(\\mathop\{\\mathbb\{E\}\}\\\|\\hat\{D\}\-D\\\|\_\{\\mathcal\{F\}\}\)^\{2\}\+\\operatorname\{Var\}\(\\\|\\hat\{D\}\-D\\\|\_\{\\mathcal\{F\}\}\)=O\\big\(\(v\+1\)/n\\big\), uniformly inDD\. ∎

###### Proof of Corollary[4\.1](https://arxiv.org/html/2610.41244#S4.Thmtheorem1)\.

Since𝒢⁡\(S\)∈ℋn\\mathcal\{G\}\(S\)\\in\\mathcal\{H\}\_\{n\}, the estimation error satisfies\|p^𝒢emp​\(S\)−D⁡\(𝒢⁡\(S\)\)\|=\|D^​\(𝒢⁡\(S\)\)−D⁡\(𝒢⁡\(S\)\)\|≤‖D^−D‖ℋn\|\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\text\{emp\}\}\(S\)\-D\(\\mathcal\{G\}\(S\)\)\|=\|\\hat\{D\}\(\\mathcal\{G\}\(S\)\)\-D\(\\mathcal\{G\}\(S\)\)\|\\leq\\\|\\hat\{D\}\-D\\\|\_\{\\mathcal\{H\}\_\{n\}\}, so Lemma[A\.1](https://arxiv.org/html/2610.41244#A1.Thmtheorem1)withℱ=ℋn\\mathcal\{F\}=\\mathcal\{H\}\_\{n\}gives the claim\. ∎

We record the cardinality\-based complexity measure of \([1](https://arxiv.org/html/2610.41244#S4.E1)\) for reference:

τ𝒢​\(n\):=supD∈Δ​𝒳𝔼S∼Dn\|𝒢⁡\(S\)\|\.\\tau\_\{\\mathcal\{G\}\}\(n\):=\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathop\{\\mathbb\{E\}\}\}\_\{S\\sim D^\{n\}\}\|\\mathcal\{G\}\(S\)\|\.
###### Proof of Theorem[4\.2](https://arxiv.org/html/2610.41244#S4.Thmtheorem2)\.

FixD∈Δ​𝒳D\\in\\Delta\\mathcal\{X\}and writeA=𝒢⁡\(S\)A=\\mathcal\{G\}\(S\),px=D⁡\(x\)p\_\{x\}=D\(x\),p^x=D^​\(x\)\\hat\{p\}\_\{x\}=\\hat\{D\}\(x\)andY:=∑x∈𝒳\(p^x−px\)2Y:=\\sum\_\{x\\in\\mathcal\{X\}\}\(\\hat\{p\}\_\{x\}\-p\_\{x\}\)^\{2\}\. Since𝔼\|A\|≤τ𝒢​\(n\)<∞\\mathop\{\\mathbb\{E\}\}\|A\|\\leq\\tau\_\{\\mathcal\{G\}\}\(n\)<\\infty, the setAAis finite almost surely, and Cauchy–Schwarz overAAgives

\(p^𝒢emp​\(S\)−D⁡\(A\)\)2=\(∑x∈A\(p^x−px\)\)2≤\|A\|​Y\.\\left\(\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\mathrm\{emp\}\}\(S\)\-D\(A\)\\right\)^\{2\}=\\Bigl\(\\sum\_\{x\\in A\}\(\\hat\{p\}\_\{x\}\-p\_\{x\}\)\\Bigr\)^\{2\}\\leq\|A\|\\,Y\.If\|A\|≤τ0\|A\|\\leq\\tau\_\{0\}for every sample, taking expectations and using𝔼Y=1n​∑xpx​\(1−px\)≤1n\\mathop\{\\mathbb\{E\}\}Y=\\frac\{1\}\{n\}\\sum\_\{x\}p\_\{x\}\(1\-p\_\{x\}\)\\leq\\frac\{1\}\{n\}gives the second claim\. In general, since the error is at most11in absolute value, for everyy\>0y\>0

𝔼\[\(p^𝒢emp\(S\)−D\(A\)\)2\]≤𝔼\[\|A\|Y1\{Y≤y\}\]\+ℙ\[Y\>y\]≤yτ𝒢\(n\)\+ℙ\[Y\>y\]\.\\mathop\{\\mathbb\{E\}\}\\left\[\\left\(\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\mathrm\{emp\}\}\(S\)\-D\(A\)\\right\)^\{2\}\\right\]\\leq\\mathop\{\\mathbb\{E\}\}\\left\[\|A\|\\,Y\\,\\mathbf\{1\}\\\{Y\\leq y\\\}\\right\]\+\\mathop\{\\mathbb\{P\}\}\[Y\>y\]\\leq y\\,\\tau\_\{\\mathcal\{G\}\}\(n\)\+\\mathop\{\\mathbb\{P\}\}\\left\[\\sqrt\{Y\}\>\\sqrt\{y\}\\right\]\.The functionf⁡\(S\):=Y=‖p^−p‖2f\(S\):=\\sqrt\{Y\}=\\\|\\hat\{p\}\-p\\\|\_\{2\}satisfies𝔼f≤𝔼Y≤1/n\\mathop\{\\mathbb\{E\}\}f\\leq\\sqrt\{\\mathop\{\\mathbb\{E\}\}Y\}\\leq 1/\\sqrt\{n\}, and replacing one sample point changesp^\\hat\{p\}by a vector ofℓ2\\ell\_\{2\}norm at most2/n\\sqrt\{2\}/n, so McDiarmid’s inequality givesℙ\[f\>1/n\+t\]≤e−n​t2\\mathop\{\\mathbb\{P\}\}\[f\>1/\\sqrt\{n\}\+t\]\\leq e^\{\-nt^\{2\}\}for everyt\>0t\>0\. We taket=ln⁡\(n/τ𝒢​\(n\)\)/nt=\\sqrt\{\\ln\(n/\\tau\_\{\\mathcal\{G\}\}\(n\)\)/n\}andy=1/n\+t\\sqrt\{y\}=1/\\sqrt\{n\}\+t, so thaty≤2/n\+2​t2y\\leq 2/n\+2t^\{2\}andℙ\[Y\>y\]≤τ𝒢\(n\)/n\\mathop\{\\mathbb\{P\}\}\[\\sqrt\{Y\}\>\\sqrt\{y\}\]\\leq\\tau\_\{\\mathcal\{G\}\}\(n\)/n\. This gives

𝔼\[\(p^𝒢emp​\(S\)−D⁡\(A\)\)2\]≤τ𝒢​\(n\)n​\(2​ln⁡nτ𝒢​\(n\)\+2\)\+τ𝒢​\(n\)n,\\mathop\{\\mathbb\{E\}\}\\left\[\\left\(\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\mathrm\{emp\}\}\(S\)\-D\(A\)\\right\)^\{2\}\\right\]\\leq\\frac\{\\tau\_\{\\mathcal\{G\}\}\(n\)\}\{n\}\\left\(2\\ln\\frac\{n\}\{\\tau\_\{\\mathcal\{G\}\}\(n\)\}\+2\\right\)\+\\frac\{\\tau\_\{\\mathcal\{G\}\}\(n\)\}\{n\},and taking the supremum overDDproves the first claim\. ∎

We end this section by showing that the upper bounds of Corollary[4\.1](https://arxiv.org/html/2610.41244#S4.Thmtheorem1)and Theorem[4\.2](https://arxiv.org/html/2610.41244#S4.Thmtheorem2)are incomparable: writingℋ𝒢,n:=\{𝒢⁡\(S\):S∈𝒳n\}\\mathcal\{H\}\_\{\\mathcal\{G\},n\}:=\\\{\\mathcal\{G\}\(S\):S\\in\\mathcal\{X\}^\{n\}\\\}for the image class of a mapping𝒢\\mathcal\{G\}, there exist𝒢1,𝒢2\\mathcal\{G\}\_\{1\},\\mathcal\{G\}\_\{2\}such that \(1\)τ𝒢1​\(n\)=Ω​\(n\)\\tau\_\{\\mathcal\{G\}\_\{1\}\}\(n\)=\\Omega\(n\)butVC⁡\(ℋ𝒢1,n\)=0\\operatorname\{VC\}\(\\mathcal\{H\}\_\{\\mathcal\{G\}\_\{1\},n\}\)=0, and \(2\)τ𝒢2​\(n\)=o​\(n\)\\tau\_\{\\mathcal\{G\}\_\{2\}\}\(n\)=o\(n\)butVC⁡\(ℋ𝒢2,n\)=Ω⁡\(n\)\\operatorname\{VC\}\(\\mathcal\{H\}\_\{\\mathcal\{G\}\_\{2\},n\}\)=\\Omega\(n\)\. For \(1\), take𝒳=ℕ\\mathcal\{X\}=\\mathbb\{N\}and consider𝒢1​\(S\)=\{1,…,n\}\\mathcal\{G\}\_\{1\}\(S\)=\\\{1,\\dots,n\\\}, so thatτ𝒢1​\(n\)=n\\tau\_\{\\mathcal\{G\}\_\{1\}\}\(n\)=nwhileℋ𝒢1,n\\mathcal\{H\}\_\{\\mathcal\{G\}\_\{1\},n\}is a singleton\. For \(2\), take𝒳=ℕ×𝒫fin​\(ℕ\)\\mathcal\{X\}=\\mathbb\{N\}\\times\\mathcal\{P\}\_\{\\text\{fin\}\}\(\\mathbb\{N\}\), where𝒫fin​\(ℕ\)\\mathcal\{P\}\_\{\\text\{fin\}\}\(\\mathbb\{N\}\)denotes the collection of finite subsets ofℕ\\mathbb\{N\}, and consider

𝒢2\(S\)=\{\{\(i,∅\):i∈A\},if for someA⊆\[n\], the sample is\{\(1,A\),…,\(n,A\)\}∅,otherwise\.\\mathcal\{G\}\_\{2\}\(S\)=\\begin\{cases\}\\\{\(i,\\emptyset\):i\\in A\\\},&\\text\{if for some $A\\subseteq\[n\]$, the sample is $\\\{\(1,A\),\\dots,\(n,A\)\\\}$\}\\\\ \\emptyset,&\\text\{otherwise\}\\end\{cases\}\.
Note thatVC⁡\(ℋ𝒢2,n\)=n\\operatorname\{VC\}\(\\mathcal\{H\}\_\{\\mathcal\{G\}\_\{2\},n\}\)=nsince we can always consider samples\{\(1,A\),…,\(n,A\)\}\\\{\(1,A\),\\dots,\(n,A\)\\\}for allA⊆\[n\]\.A\\subseteq\[n\]\.On the other hand,𝒢2​\(S\)\\mathcal\{G\}\_\{2\}\(S\)is nonempty only when thennpoints ofSSare distinct and exhaust\{\(1,A\),…,\(n,A\)\}\\\{\(1,A\),\\dots,\(n,A\)\\\}for a singleAA\. WritingmA:=∑i∈\[n\]D⁡\(\(i,A\)\)m\_\{A\}:=\\sum\_\{i\\in\[n\]\}D\(\(i,A\)\), the probability of that event for a givenAAisn\!​∏i∈\[n\]D⁡\(\(i,A\)\)≤n\!nn​mAnn\!\\prod\_\{i\\in\[n\]\}D\(\(i,A\)\)\\leq\\frac\{n\!\}\{n^\{n\}\}m\_\{A\}^\{n\}by the AM–GM inequality; the events for distinctAAare disjoint and∑AmAn≤\(∑AmA\)n≤1\\sum\_\{A\}m\_\{A\}^\{n\}\\leq\(\\sum\_\{A\}m\_\{A\}\)^\{n\}\\leq 1\. Since\|𝒢2​\(S\)\|≤n\|\\mathcal\{G\}\_\{2\}\(S\)\|\\leq nalways,τ𝒢2​\(n\)≤n⋅n\!nn=Θ⁡\(n3/2​e−n\)=o⁡\(n\)\\tau\_\{\\mathcal\{G\}\_\{2\}\}\(n\)\\leq\\frac\{n\\cdot n\!\}\{n^\{n\}\}=\\Theta\\big\(n^\{3/2\}e^\{\-n\}\\big\)=o\(n\)by Stirling’s approximation\.

## Appendix BMissing Proofs for Section[5](https://arxiv.org/html/2610.41244#S5)

###### Proof of Theorem[5\.1](https://arxiv.org/html/2610.41244#S5.Thmtheorem1)\.

At a fixedDD, this is the bound of[Devroye and Wagner \(1979\)](https://arxiv.org/html/2610.41244#bib.bib20)on the deleted estimate in the form of[Bousquet and Elisseeff \(2002, Lemma 9\)](https://arxiv.org/html/2610.41244#bib.bib15), applied to the lossℓ⁡\(𝒢⁡\(S\),x\)=𝒢⁡\(S\)​\(x\)\\ell\(\\mathcal\{G\}\(S\),x\)=\\mathcal\{G\}\(S\)\(x\), whose hypothesis stability\([Bousquet and Elisseeff, 2002](https://arxiv.org/html/2610.41244#bib.bib15), Definition 3\)isγ𝒢D​\(n\)\\gamma^\{D\}\_\{\\mathcal\{G\}\}\(n\)\(see the discussion after \([2](https://arxiv.org/html/2610.41244#S5.E2)\)\); taking the supremum overDDgives the uniform form\.

∎

###### Proof of Theorem[5\.3](https://arxiv.org/html/2610.41244#S5.Thmtheorem3)\.

By Theorem[5\.1](https://arxiv.org/html/2610.41244#S5.Thmtheorem1), it suffices to boundγ𝒢​\(n\)\.\\gamma\_\{\\mathcal\{G\}\}\(n\)\.FixDDand writeqx:=D⁡\(N−1​\(x\)\)q\_\{x\}:=D\(N^\{\-1\}\(x\)\)for the mass of the in\-neighbors ofxx\. Deletingxnx\_\{n\}fromSSremoves from𝒢⁡\(S\)\\mathcal\{G\}\(S\)exactly the points ofN⁡\(xn\)N\(x\_\{n\}\)that lie in no other neighborhood, so forx∼Dx\\sim Dindependent ofSS,

𝔼S∼Dn\[D\(𝒢\(S\)Δ𝒢\(S−n\)\)\]=ℙ\[x∈N\(xn\),x∉N\(xi\)for alli<n\]=𝔼x∼D\[qx\(1−qx\)n−1\]≤1n,\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\left\[D\(\\mathcal\{G\}\(S\)\\Delta\\mathcal\{G\}\(S^\{\-n\}\)\)\\right\]=\\mathop\{\\mathbb\{P\}\}\\left\[x\\in N\(x\_\{n\}\),\\ x\\notin N\(x\_\{i\}\)\\text\{ for all \}i<n\\right\]=\\mathop\{\\mathbb\{E\}\}\_\{x\\sim D\}\\left\[q\_\{x\}\(1\-q\_\{x\}\)^\{n\-1\}\\right\]\\leq\\frac\{1\}\{n\},sincex∈N⁡\(xi\)x\\in N\(x\_\{i\}\)if and only ifxi∈N−1​\(x\)x\_\{i\}\\in N^\{\-1\}\(x\), thesennevents are independent with probabilityqxq\_\{x\}givenxx, andp​\(1−p\)n−1≤1/np\(1\-p\)^\{n\-1\}\\leq 1/nfor allp∈\[0,1\]p\\in\[0,1\]\. Thus,γ𝒢​\(n\)≤1n\\gamma\_\{\\mathcal\{G\}\}\(n\)\\leq\\frac\{1\}\{n\}, and hence𝒢\\mathcal\{G\}is estimatable with MSE that decays at a rate ofO⁡\(1/n\)O\(1/n\)\. ∎

Corollary[5\.5](https://arxiv.org/html/2610.41244#S5.Thmtheorem5)is proved in the main text\. Lemma[5\.6](https://arxiv.org/html/2610.41244#S5.Thmtheorem6)and Theorem[5\.8](https://arxiv.org/html/2610.41244#S5.Thmtheorem8)rest on one identity: forp∈\[0,1\]p\\in\[0,1\]and0≤j≤n−10\\leq j\\leq n\-1,

p​\(n−1j\)​pj​\(1−p\)n−1−j=j\+1n​\(nj\+1\)​pj\+1​\(1−p\)n−1−j≤j\+1n,p\\binom\{n\-1\}\{j\}p^\{j\}\(1\-p\)^\{n\-1\-j\}=\\frac\{j\+1\}\{n\}\\binom\{n\}\{j\+1\}p^\{j\+1\}\(1\-p\)^\{n\-1\-j\}\\leq\\frac\{j\+1\}\{n\},\(16\)which uses\(n−1j\)=j\+1n​\(nj\+1\)\\binom\{n\-1\}\{j\}=\\frac\{j\+1\}\{n\}\\binom\{n\}\{j\+1\}and\(nj\+1\)pj\+1\(1−p\)n−\(j\+1\)=ℙ\[Bin\(n,p\)=j\+1\]≤1\\binom\{n\}\{j\+1\}p^\{j\+1\}\(1\-p\)^\{n\-\(j\+1\)\}=\\mathop\{\\mathbb\{P\}\}\[\\operatorname\{Bin\}\(n,p\)=j\+1\]\\leq 1\. In words, the probability that a point of massppis drawn and occurs exactlyjjtimes amongn−1n\-1further draws is at most\(j\+1\)/n\(j\+1\)/n\.

###### Proof of Lemma[5\.6](https://arxiv.org/html/2610.41244#S5.Thmtheorem6)and Theorem[5\.8](https://arxiv.org/html/2610.41244#S5.Thmtheorem8)\.

Both mappings have the form𝒢⁡\(S\)=⋃x∈ck​\(S\)N⁡\(x\)\\mathcal\{G\}\(S\)=\\bigcup\_\{x\\in c\_\{k\}\(S\)\}N\(x\)for a neighborhood functionNN, and we first boundγ𝒢​\(n\)\\gamma\_\{\\mathcal\{G\}\}\(n\)for an arbitraryNN\. Fixk≥1k\\geq 1and a distributionD∈Δ​𝒳D\\in\\Delta\\mathcal\{X\}\. Addingxnx\_\{n\}toS−nS^\{\-n\}increases the multiplicity ofxnx\_\{n\}by one and leaves every other point unchanged\. Hencexnx\_\{n\}*enters*ckc\_\{k\}exactly when its multiplicity inS−nS^\{\-n\}isk−1k\-1and*leaves*ckc\_\{k\}exactly when its multiplicity iskk, and no other point changes status; in either case the union of neighborhoods changes only withinN⁡\(xn\)N\(x\_\{n\}\)\. Therefore, for anyS∈𝒳nS\\in\\mathcal\{X\}^\{n\},

D\(𝒢\(S\)Δ𝒢\(S−n\)\)≤𝟏\{xn∈ck−1\(S−n\)∪ck\(S−n\)\}D\(N\(xn\)\)\.D\(\\mathcal\{G\}\(S\)\\Delta\\mathcal\{G\}\(S^\{\-n\}\)\)\\leq\\mathbf\{1\}\\\{x\_\{n\}\\in c\_\{k\-1\}\(S^\{\-n\}\)\\cup c\_\{k\}\(S^\{\-n\}\)\\\}D\(N\(x\_\{n\}\)\)\.Conditioning onxn=xx\_\{n\}=x, the multiplicity ofxxinS−nS^\{\-n\}is distributed asBin⁡\(n−1,D⁡\(x\)\)\\operatorname\{Bin\}\(n\-1,D\(x\)\), so by \([16](https://arxiv.org/html/2610.41244#A2.E16)\) withj=k−1j=k\-1andj=kj=k,

𝔼S∼Dn\[D\(𝒢\(S\)Δ𝒢\(S−n\)\)\]≤∑x∈𝒳D\(N\(x\)\)D\(x\)ℙ\[Bin\(n−1,D\(x\)\)∈\{k−1,k\}\]≤2​k\+1n∑x∈𝒳D\(N\(x\)\)\.\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\left\[D\(\\mathcal\{G\}\(S\)\\Delta\\mathcal\{G\}\(S^\{\-n\}\)\)\\right\]\\leq\\sum\_\{x\\in\\mathcal\{X\}\}D\(N\(x\)\)\\,D\(x\)\\mathop\{\\mathbb\{P\}\}\\left\[\\operatorname\{Bin\}\(n\-1,D\(x\)\)\\in\\\{k\-1,k\\\}\\right\]\\leq\\frac\{2k\+1\}\{n\}\\sum\_\{x\\in\\mathcal\{X\}\}D\(N\(x\)\)\.For𝒢​\(S\)=ck​\(S\)\\mathcal\{G\}\(S\)=c\_\{k\}\(S\)takeN⁡\(x\)=\{x\}N\(x\)=\\\{x\\\}: then∑xD⁡\(N⁡\(x\)\)=1\\sum\_\{x\}D\(N\(x\)\)=1, and the displayed bound readsγ𝒢​\(n\)≤2​k\+1n\\gamma\_\{\\mathcal\{G\}\}\(n\)\\leq\\frac\{2k\+1\}\{n\}, which is Lemma[5\.6](https://arxiv.org/html/2610.41244#S5.Thmtheorem6)\. For𝒢⁡\(S\)=V∩ck​\(S\)\\mathcal\{G\}\(S\)=V\\cap c\_\{k\}\(S\)takeN⁡\(x\)=\{x\}∩VN\(x\)=\\\{x\\\}\\cap V: then∑xD⁡\(N⁡\(x\)\)=D⁡\(V\)≤1\\sum\_\{x\}D\(N\(x\)\)=D\(V\)\\leq 1, so againγ𝒢​\(n\)≤2​k\+1n\\gamma\_\{\\mathcal\{G\}\}\(n\)\\leq\\frac\{2k\+1\}\{n\}, and Theorem[5\.1](https://arxiv.org/html/2610.41244#S5.Thmtheorem1)gives estimation errorO⁡\(kn\)O\(\\frac\{k\}\{n\}\)\. ∎

###### Proof of Theorem[5\.7](https://arxiv.org/html/2610.41244#S5.Thmtheorem7)\.

Fixn≥2n\\geq 2,D∈Δ​𝒳D\\in\\Delta\\mathcal\{X\}and a pointz∈𝒳z\\in\\mathcal\{X\}, letU:=N−1​\(z\)U:=N^\{\-1\}\(z\), and writepu:=D⁡\(u\)p\_\{u\}:=D\(u\)\. Thenz∈𝒢⁡\(S\)z\\in\\mathcal\{G\}\(S\)if and only ifck​\(S\)∩U≠∅c\_\{k\}\(S\)\\cap U\\neq\\emptyset\. Passing fromS−nS^\{\-n\}toSSraises the multiplicity ofxnx\_\{n\}by one and changes no other multiplicity, sock​\(S\)c\_\{k\}\(S\)andck​\(S−n\)c\_\{k\}\(S^\{\-n\}\)differ at most inxnx\_\{n\}\. Hencez∈𝒢⁡\(S\)∖𝒢⁡\(S−n\)z\\in\\mathcal\{G\}\(S\)\\setminus\\mathcal\{G\}\(S^\{\-n\}\)exactly whenck​\(S\)∩U=\{xn\}c\_\{k\}\(S\)\\cap U=\\\{x\_\{n\}\\\}, andz∈𝒢⁡\(S−n\)∖𝒢⁡\(S\)z\\in\\mathcal\{G\}\(S^\{\-n\}\)\\setminus\\mathcal\{G\}\(S\)exactly whenck​\(S−n\)∩U=\{xn\}c\_\{k\}\(S^\{\-n\}\)\\cap U=\\\{x\_\{n\}\\\}\.

By symmetry ofckc\_\{k\},ℙ\[ck\(S\)∩U=\{xn\}\]=1n𝔼∑i=1n𝟏\{ck\(S\)∩U=\{xi\}\}\\mathop\{\\mathbb\{P\}\}\[c\_\{k\}\(S\)\\cap U=\\\{x\_\{n\}\\\}\]=\\frac\{1\}\{n\}\\mathop\{\\mathbb\{E\}\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{c\_\{k\}\(S\)\\cap U=\\\{x\_\{i\}\\\}\\\}\. Whenck​\(S\)∩Uc\_\{k\}\(S\)\\cap Uis a single point, exactlykkindicesiihavexix\_\{i\}equal to it, and otherwise the sum is00\. So this probability isknℙ\[\|ck\(S\)∩U\|=1\]≤kn\\frac\{k\}\{n\}\\mathop\{\\mathbb\{P\}\}\[\|c\_\{k\}\(S\)\\cap U\|=1\]\\leq\\frac\{k\}\{n\}\.

For the second event,xnx\_\{n\}is independent ofS−nS^\{\-n\}, so withEu:=\{ck\(S−n\)∩U=\{u\}\}E\_\{u\}:=\\\{c\_\{k\}\(S^\{\-n\}\)\\cap U=\\\{u\\\}\\\}its probability is∑u∈Upu​ℙ\[Eu\]\\sum\_\{u\\in U\}p\_\{u\}\\mathop\{\\mathbb\{P\}\}\[E\_\{u\}\]\. The eventsEuE\_\{u\}are disjoint, so∑uℙ\[Eu\]≤1\\sum\_\{u\}\\mathop\{\\mathbb\{P\}\}\[E\_\{u\}\]\\leq 1, andEuE\_\{u\}requires the multiplicity ofuuinS−nS^\{\-n\}, which has distributionBin⁡\(n−1,pu\)\\operatorname\{Bin\}\(n\-1,p\_\{u\}\), to equalkk\. LetT:=\(2​k\+2​ln⁡n\)/\(n−1\)T:=\(2k\+2\\ln n\)/\(n\-1\)\. The terms withpu≤Tp\_\{u\}\\leq Tcontribute at mostTT\. Forpu\>Tp\_\{u\}\>Tthe meanμ:=\(n−1\)​pu\\mu:=\(n\-1\)p\_\{u\}exceedsμ0:=2​k\+2​ln⁡n\>k\\mu\_\{0\}:=2k\+2\\ln n\>k, and the Chernoff boundℙ\[Bin\(n−1,pu\)≤k\]≤infs\>0es​k𝔼e−s​Bin⁡\(n−1,pu\)≤e−μ\(eμ/k\)k\\mathop\{\\mathbb\{P\}\}\[\\operatorname\{Bin\}\(n\-1,p\_\{u\}\)\\leq k\]\\leq\\inf\_\{s\>0\}e^\{sk\}\\,\\mathop\{\\mathbb\{E\}\}e^\{\-s\\operatorname\{Bin\}\(n\-1,p\_\{u\}\)\}\\leq e^\{\-\\mu\}\(e\\mu/k\)^\{k\}\(takee−s=k/μe^\{\-s\}=k/\\mu\) has a right\-hand side that is decreasing inμ\>k\\mu\>k\. Atμ=μ0\\mu=\\mu\_\{0\}, writinga:=ln⁡n/ka:=\\ln n/k, it equalsexp⁡\(k⁡\(ln⁡\(2\+2​a\)−1−2​a\)\)≤e−a​k=1/n\\exp\\bigl\(k\(\\ln\(2\+2a\)\-1\-2a\)\\bigr\)\\leq e^\{\-ak\}=1/n, sinceln⁡\(2\+2​a\)≤ln⁡2\+a<1\+a\\ln\(2\+2a\)\\leq\\ln 2\+a<1\+a\. So these terms contribute at most1n​∑upu≤1n\\frac\{1\}\{n\}\\sum\_\{u\}p\_\{u\}\\leq\\frac\{1\}\{n\}\.

Thereforeℙ\[z∈𝒢\(S\)Δ𝒢\(S−n\)\]≤kn\+T\+1n\\mathop\{\\mathbb\{P\}\}\[z\\in\\mathcal\{G\}\(S\)\\,\\Delta\\,\\mathcal\{G\}\(S^\{\-n\}\)\]\\leq\\frac\{k\}\{n\}\+T\+\\frac\{1\}\{n\}for everyzz, and averaging overz∼Dz\\sim Dgivesγ𝒢D​\(n\)≤k\+1n\+2​k\+2​ln⁡nn−1\\gamma^\{D\}\_\{\\mathcal\{G\}\}\(n\)\\leq\\frac\{k\+1\}\{n\}\+\\frac\{2k\+2\\ln n\}\{n\-1\}\. If2​k\+2​ln⁡n≤n−12k\+2\\ln n\\leq n\-1, this is at most\(3​k\+2​ln⁡n\+2\)/n\(3k\+2\\ln n\+2\)/n; otherwise\(3​k\+2​ln⁡n\+2\)/n\>1≥γ𝒢D​\(n\)\(3k\+2\\ln n\+2\)/n\>1\\geq\\gamma^\{D\}\_\{\\mathcal\{G\}\}\(n\)\. Taking the supremum overDDand applying Theorem[5\.1](https://arxiv.org/html/2610.41244#S5.Thmtheorem1)completes the proof\. ∎

## Appendix CProofs for Section[6](https://arxiv.org/html/2610.41244#S6)

### C\.1Proof of Proposition[6\.2](https://arxiv.org/html/2610.41244#S6.Thmtheorem2)

Recall from Section[5\.1](https://arxiv.org/html/2610.41244#S5.SS1.SSS0.Px3)thatck​\(S\)c\_\{k\}\(S\)is the set of points that occur exactlykktimes inSS, and from Remark[5\.1](https://arxiv.org/html/2610.41244#S5.Thmremark1)thatFk​\(S\):=\|ck​\(S\)\|F\_\{k\}\(S\):=\|c\_\{k\}\(S\)\|\. For a sample of sizennlet

Bn:=\{S:\|F1​\(S\)−2​F2​\(S\)\|≤6​n\}B\_\{n\}:=\\big\\\{S:\\ \|F\_\{1\}\(S\)\-2F\_\{2\}\(S\)\|\\leq 6\\sqrt\{n\}\\big\\\}and define the region selection rule

E⁡\(S\):=\{c1​\(S\),S∈Bn,∅,otherwise\.E\(S\):=\\begin\{cases\}c\_\{1\}\(S\),&S\\in B\_\{n\},\\\\ \\emptyset,&\\text\{otherwise\.\}\\end\{cases\}The rule depends onSSonly through its multiset of points, so it is symmetric, and it is the error region of a base learner: given the labelingyy, lethSh\_\{S\}predicty⁡\(x\)y\(x\)forx∉E⁡\(S\)x\\notin E\(S\)and a label different fromy⁡\(x\)y\(x\)forx∈E⁡\(S\)x\\in E\(S\)\. Throughout,𝒢⁡\(S\)=E⁡\(S\)∖T⁡\(S\)\\mathcal\{G\}\(S\)=E\(S\)\\setminus T\(S\)is the error region of the exception\-memorizing learner built from this base learner\.

*The base learner generalizes\.*Every point ofc1​\(S\)c\_\{1\}\(S\)occurs once inSS, soD^​\(c1​\(S\)\)=F1​\(S\)/n\\hat\{D\}\(c\_\{1\}\(S\)\)=F\_\{1\}\(S\)/n\. By Remark[5\.1](https://arxiv.org/html/2610.41244#S5.Thmremark1), the leave\-one\-out estimator of the mappingS↦c1​\(S\)S\\mapsto c\_\{1\}\(S\)is2​F2​\(S\)/n2F\_\{2\}\(S\)/n, and Lemma[5\.6](https://arxiv.org/html/2610.41244#S5.Thmtheorem6)together with Theorem[5\.1](https://arxiv.org/html/2610.41244#S5.Thmtheorem1)gives

supD∈Δ​𝒳𝔼S∼Dn\[\(2​F2​\(S\)n−D⁡\(c1​\(S\)\)\)2\]≤12​n\+9n≤10n\.\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\left\[\\left\(\\frac\{2F\_\{2\}\(S\)\}\{n\}\-D\(c\_\{1\}\(S\)\)\\right\)^\{2\}\\right\]\\leq\\frac\{1\}\{2n\}\+\\frac\{9\}\{n\}\\leq\\frac\{10\}\{n\}\.OnBnB\_\{n\}we haveD^​\(E⁡\(S\)\)=F1​\(S\)/n\\hat\{D\}\(E\(S\)\)=F\_\{1\}\(S\)/nandD⁡\(E⁡\(S\)\)=D⁡\(c1​\(S\)\)D\(E\(S\)\)=D\(c\_\{1\}\(S\)\), so

\|D^​\(E⁡\(S\)\)−D⁡\(E⁡\(S\)\)\|≤\|F1​\(S\)−2​F2​\(S\)\|n\+\|2​F2​\(S\)n−D⁡\(c1​\(S\)\)\|≤6n\+\|2​F2​\(S\)n−D⁡\(c1​\(S\)\)\|,\\big\|\\hat\{D\}\(E\(S\)\)\-D\(E\(S\)\)\\big\|\\leq\\frac\{\|F\_\{1\}\(S\)\-2F\_\{2\}\(S\)\|\}\{n\}\+\\left\|\\frac\{2F\_\{2\}\(S\)\}\{n\}\-D\(c\_\{1\}\(S\)\)\\right\|\\leq\\frac\{6\}\{\\sqrt\{n\}\}\+\\left\|\\frac\{2F\_\{2\}\(S\)\}\{n\}\-D\(c\_\{1\}\(S\)\)\\right\|,while outsideBnB\_\{n\}bothD^​\(E​\(S\)\)\\hat\{D\}\(E\(S\)\)andD⁡\(E⁡\(S\)\)D\(E\(S\)\)are 0\. Squaring with\(u\+v\)2≤2​u2\+2​v2\(u\+v\)^\{2\}\\leq 2u^\{2\}\+2v^\{2\}and taking expectations,

εEemp​\(n\)=supD∈Δ​𝒳𝔼S∼Dn\[\(D^​\(E⁡\(S\)\)−D⁡\(E⁡\(S\)\)\)2\]≤72n\+20n=92n\.\\varepsilon^\{\\mathrm\{emp\}\}\_\{E\}\(n\)=\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\left\[\\left\(\\hat\{D\}\(E\(S\)\)\-D\(E\(S\)\)\\right\)^\{2\}\\right\]\\leq\\frac\{72\}\{n\}\+\\frac\{20\}\{n\}=\\frac\{92\}\{n\}\.
*The hybrid fails\.*SinceE⁡\(S\)⊆c1​\(S\)⊆T⁡\(S\)E\(S\)\\subseteq c\_\{1\}\(S\)\\subseteq T\(S\), we have𝒢⁡\(S\)=∅\\mathcal\{G\}\(S\)=\\emptysetandD⁡\(𝒢⁡\(S\)\)=ME⁡\(S\)​\(S\)=0D\(\\mathcal\{G\}\(S\)\)=M\_\{E\(S\)\}\(S\)=0for every sample\. On the other hand every point ofE⁡\(S\)E\(S\)is a singleton ofSS, so by the definition \([10](https://arxiv.org/html/2610.41244#S6.E10)\) of the hybrid estimator

p^𝒢hyb\(S\)=M^E⁡\(S\)\(S\)=F1​\(S\)n1\{S∈Bn\}\.\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\mathrm\{hyb\}\}\(S\)=\\widehat\{M\}\_\{E\(S\)\}\(S\)=\\frac\{F\_\{1\}\(S\)\}\{n\}\\,\\mathbf\{1\}\\\{S\\in B\_\{n\}\\\}\.LetDnD\_\{n\}be the uniform distribution on\[n\]\[n\]and letS∼DnnS\\sim D\_\{n\}^\{n\}\. Then

𝔼\[F1​\(S\)\]=n​\(1−1n\)n−1≥neand𝔼\[F2​\(S\)\]=\(n2\)​1n​\(1−1n\)n−2=n−12​\(1−1n\)n−2,\\mathop\{\\mathbb\{E\}\}\\left\[F\_\{1\}\(S\)\\right\]=n\\left\(1\-\\frac\{1\}\{n\}\\right\)^\{n\-1\}\\geq\\frac\{n\}\{e\}\\qquad\\text\{and\}\\qquad\\mathop\{\\mathbb\{E\}\}\\left\[F\_\{2\}\(S\)\\right\]=\\binom\{n\}\{2\}\\frac\{1\}\{n\}\\left\(1\-\\frac\{1\}\{n\}\\right\)^\{n\-2\}=\\frac\{n\-1\}\{2\}\\left\(1\-\\frac\{1\}\{n\}\\right\)^\{n\-2\},so that𝔼\[F1​\(S\)−2​F2​\(S\)\]=0\\mathop\{\\mathbb\{E\}\}\[F\_\{1\}\(S\)\-2F\_\{2\}\(S\)\]=0\. Replacing one sample point changes each ofF1F\_\{1\}andF2F\_\{2\}by at most22, henceF1−2​F2F\_\{1\}\-2F\_\{2\}by at most66, and McDiarmid’s inequality givesℙ\[S∉Bn\]≤2e−2\\mathop\{\\mathbb\{P\}\}\[S\\notin B\_\{n\}\]\\leq 2e^\{\-2\}\. SinceF1​\(S\)/n≤1F\_\{1\}\(S\)/n\\leq 1,

𝔼\[F1​\(S\)n𝟏\{S∈Bn\}\]≥𝔼\[F1​\(S\)n\]−ℙ\[S∉Bn\]≥1e−2e2,\\mathop\{\\mathbb\{E\}\}\\left\[\\frac\{F\_\{1\}\(S\)\}\{n\}\\mathbf\{1\}\\\{S\\in B\_\{n\}\\\}\\right\]\\geq\\mathop\{\\mathbb\{E\}\}\\left\[\\frac\{F\_\{1\}\(S\)\}\{n\}\\right\]\-\\mathop\{\\mathbb\{P\}\}\[S\\notin B\_\{n\}\]\\geq\\frac\{1\}\{e\}\-\\frac\{2\}\{e^\{2\}\},and by the Cauchy–Schwarz inequality,𝔼\[X𝟏\{S∈Bn\}\]2≤𝔼\[X2𝟏\{S∈Bn\}\]\\mathop\{\\mathbb\{E\}\}\[X\\mathbf\{1\}\\\{S\\in B\_\{n\}\\\}\]^\{2\}\\leq\\mathop\{\\mathbb\{E\}\}\[X^\{2\}\\mathbf\{1\}\\\{S\\in B\_\{n\}\\\}\]forX=F1​\(S\)/nX=F\_\{1\}\(S\)/n, we conclude that

𝔼S∼Dnn\[\(p^𝒢hyb\(S\)−Dn\(𝒢\(S\)\)\)2\]=𝔼\[F1​\(S\)2n2𝟏\{S∈Bn\}\]≥\(1e−2e2\)2\>0\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D\_\{n\}^\{n\}\}\\left\[\\left\(\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\mathrm\{hyb\}\}\(S\)\-D\_\{n\}\(\\mathcal\{G\}\(S\)\)\\right\)^\{2\}\\right\]=\\mathop\{\\mathbb\{E\}\}\\left\[\\frac\{F\_\{1\}\(S\)^\{2\}\}\{n^\{2\}\}\\mathbf\{1\}\\\{S\\in B\_\{n\}\\\}\\right\]\\geq\\left\(\\frac\{1\}\{e\}\-\\frac\{2\}\{e^\{2\}\}\\right\)^\{2\}\>0for everynn\. This proves the proposition withc=\(1/e−2/e2\)2c=\(1/e\-2/e^\{2\}\)^\{2\}\.

### C\.2A Learner for Which the Hybrid Beats Both Standard Estimators

The following example shows that holding the base classifier fixed across the folds can be essential\. It gives an exception\-memorizing learner whose error the hybrid estimates at rateO⁡\(1/n\)O\(1/n\)uniformly over all distributions, while both the empirical and the leave\-one\-out estimator have error bounded away from zero\.

Let𝒳=\{w\}∪ℛ\\mathcal\{X\}=\\\{w\\\}\\cup\\mathcal\{R\}, whereℛ:=\{r1,r2,…\}\\mathcal\{R\}:=\\\{r\_\{1\},r\_\{2\},\\ldots\\\}is a set of rare inputs\. The base learner is unstable in the simplest possible way: it returns a perfect classifier when the sample size is odd and a classifier that errs exactly onℛ\\mathcal\{R\}when the sample size is even, so thatE⁡\(S\)=∅E\(S\)=\\emptysetfor oddnnandE⁡\(S\)=ℛE\(S\)=\\mathcal\{R\}for evennn\. \(A symmetric rule that depends on the sample rather than onnn, such as the parity of the number of distinct sample points, has the same effect\.\) Concretely, labely⁡\(w\)=0y\(w\)=0andy⁡\(rj\)=1y\(r\_\{j\}\)=1for everyjj; the learner returns the true labeling at odd sample sizes and the constant classifier00at even ones\. The exception\-memorizing learner built from it has error region𝒢⁡\(S\)=E⁡\(S\)∖T⁡\(S\)\\mathcal\{G\}\(S\)=E\(S\)\\setminus T\(S\)\.

###### Proposition C\.1\(The hybrid succeeds where both standard estimators fail\)\.

For the learner above,

supD∈Δ​𝒳𝔼S∼Dn\[\(p^𝒢hyb​\(S\)−D⁡\(𝒢⁡\(S\)\)\)2\]=O⁡\(1n\)for every​n,\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\Big\[\\big\(\\hat\{p\}\_\{\\mathcal\{G\}\}^\{\\mathrm\{hyb\}\}\(S\)\-D\(\\mathcal\{G\}\(S\)\)\\big\)^\{2\}\\Big\]=O\\Big\(\\frac\{1\}\{n\}\\Big\)\\qquad\\text\{for every \}n,whereas for every evennnthere is a distributionDnD\_\{n\}at which both the empirical and the leave\-one\-out estimator have mean\-squared error at least1/161/16\.

###### Proof\.

SinceE⁡\(S\)E\(S\)depends only onnn, the selection ruleS↦E⁡\(S\)S\\mapsto E\(S\)takes a single value, so the first claim follows from Definition[6\.3](https://arxiv.org/html/2610.41244#S6.Thmdefinition3)and part[\(i\)](https://arxiv.org/html/2610.41244#S6.I1.i1)of Theorem[6\.3](https://arxiv.org/html/2610.41244#S6.Thmtheorem3)withL=1L=1\. For the lower bounds, letnnbe even and letDnD\_\{n\}put mass1/21/2onwwand mass1/\(2​n2\)1/\(2n^\{2\}\)on each ofr1,…,rn2r\_\{1\},\\ldots,r\_\{n^\{2\}\}\. ThenDn​\(𝒢⁡\(S\)\)=12−Dn​\(ℛ∩T⁡\(S\)\)D\_\{n\}\(\\mathcal\{G\}\(S\)\)=\\tfrac\{1\}\{2\}\-D\_\{n\}\(\\mathcal\{R\}\\cap T\(S\)\), and since eachrjr\_\{j\}occurs inSSwith probability at mostn⋅12​n2=12​nn\\cdot\\frac\{1\}\{2n^\{2\}\}=\\frac\{1\}\{2n\},

𝔼\[Dn\(ℛ∩T\(S\)\)\]=∑j=1n212​n2ℙ\[rj∈T\(S\)\]≤14​n,so that𝔼\[Dn\(𝒢\(S\)\)\]≥12−14​n≥14\.\\mathop\{\\mathbb\{E\}\}\\big\[D\_\{n\}\(\\mathcal\{R\}\\cap T\(S\)\)\\big\]=\\sum\_\{j=1\}^\{n^\{2\}\}\\frac\{1\}\{2n^\{2\}\}\\mathop\{\\mathbb\{P\}\}\[r\_\{j\}\\in T\(S\)\]\\leq\\frac\{1\}\{4n\},\\qquad\\text\{so that\}\\qquad\\mathop\{\\mathbb\{E\}\}\\big\[D\_\{n\}\(\\mathcal\{G\}\(S\)\)\\big\]\\geq\\frac\{1\}\{2\}\-\\frac\{1\}\{4n\}\\geq\\frac\{1\}\{4\}\.The empirical estimator is identically zero because𝒢⁡\(S\)\\mathcal\{G\}\(S\)contains no sample point\. Every leave\-one\-out foldS−iS^\{\-i\}has odd size, so𝒢⁡\(S−i\)=∅\\mathcal\{G\}\(S^\{\-i\}\)=\\emptysetand the leave\-one\-out estimator is identically zero as well\. For either estimator, Jensen’s inequality gives

𝔼\[\(0−Dn​\(𝒢⁡\(S\)\)\)2\]≥\(𝔼\[Dn​\(𝒢⁡\(S\)\)\]\)2≥116\.∎\\mathop\{\\mathbb\{E\}\}\\Big\[\\big\(0\-D\_\{n\}\(\\mathcal\{G\}\(S\)\)\\big\)^\{2\}\\Big\]\\geq\\big\(\\mathop\{\\mathbb\{E\}\}\[D\_\{n\}\(\\mathcal\{G\}\(S\)\)\]\\big\)^\{2\}\\geq\\frac\{1\}\{16\}\.\\qed

### C\.3An Information Bound for Adaptive Missing Mass

This section and the next \(Appendix[C\.4](https://arxiv.org/html/2610.41244#A3.SS4)\) prove Theorem[6\.3](https://arxiv.org/html/2610.41244#S6.Thmtheorem3)\. We use the notation of Section[6\.2](https://arxiv.org/html/2610.41244#S6.SS2): for a regionV⊆𝒳V\\subseteq\\mathcal\{X\}and a sampleSS,

MV​\(S\)=D⁡\(V∖T⁡\(S\)\),M^V​\(S\)=1n​∑i=1n𝟏​\{xi∈V,\#xi​\(S\)=1\},ZV​\(S\):=M^V​\(S\)−MV​\(S\)M\_\{V\}\(S\)=D\\big\(V\\setminus T\(S\)\\big\),\\qquad\\widehat\{M\}\_\{V\}\(S\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{x\_\{i\}\\in V,\\ \\\#\_\{x\_\{i\}\}\(S\)=1\\\},\\qquad Z\_\{V\}\(S\):=\\widehat\{M\}\_\{V\}\(S\)\-M\_\{V\}\(S\)are the missing mass ofVV, its restricted Good–Turing estimator, and the error of that estimator\. A region selection rule is a map𝒱=𝒱⁡\(S,r\)\\mathcal\{V\}=\\mathcal\{V\}\(S,r\), wherer∼Rr\\sim Ris an internal seed independent ofSS\(Definition[3\.3](https://arxiv.org/html/2610.41244#S3.Thmdefinition3)\); a deterministic rule ignoresrr\. For a selection rule we writeZ𝒱​\(S\)Z\_\{\\mathcal\{V\}\}\(S\)forZ𝒱⁡\(S,r\)​\(S\)Z\_\{\\mathcal\{V\}\(S,r\)\}\(S\), andID​\(S,𝒱\)I\_\{D\}\(S;\\mathcal\{V\}\)for the mutual information, in nats, betweenSSand𝒱⁡\(S,r\)\\mathcal\{V\}\(S,r\)whenS∼DnS\\sim D^\{n\}\.

###### Theorem C\.2\(Information bound for adaptive missing mass\)\.

There is an absolute constantccsuch that for everynn, everyD∈Δ​𝒳D\\in\\Delta\\mathcal\{X\}, and every region selection rule𝒱\\mathcal\{V\},

𝔼\[Z𝒱​\(S\)2\]≤c​ID​\(S,𝒱\)\+1n,\\mathop\{\\mathbb\{E\}\}\\big\[Z\_\{\\mathcal\{V\}\}\(S\)^\{2\}\\big\]\\leq c\\,\\frac\{I\_\{D\}\(S;\\mathcal\{V\}\)\+1\}\{n\},\(17\)where the expectation is overS∼DnS\\sim D^\{n\}and the seedr∼Rr\\sim R\. In particular, if𝒱\\mathcal\{V\}takes at mostLLvalues then𝔼\[Z𝒱​\(S\)2\]≤c⁡\(log⁡L\+1\)/n\\mathop\{\\mathbb\{E\}\}\[Z\_\{\\mathcal\{V\}\}\(S\)^\{2\}\]\\leq c\\,\(\\log L\+1\)/n\.

The proof has two steps\. First, for a region fixed in advance, the errorZV​\(S\)Z\_\{V\}\(S\)is sub\-Gaussian at scale1/n1/\\sqrt\{n\}, so thatexp⁡\(c′​n​ZV​\(S\)2\)\\exp\(c^\{\\prime\}nZ\_\{V\}\(S\)^\{2\}\)has bounded expectation for a small absolute constantc′c^\{\\prime\}\. Second, a change of measure from the joint law of\(S,𝒱\)\(S,\\mathcal\{V\}\)to the product of its marginals, at a price ofID​\(S,𝒱\)I\_\{D\}\(S;\\mathcal\{V\}\), transfers this bound to the selected region\.

###### Proof\.

*Step 1: a fixed region\.*FixDDand a regionV⊆𝒳V\\subseteq\\mathcal\{X\}, and writepx:=D⁡\(x\)p\_\{x\}:=D\(x\)\. Sincexix\_\{i\}is a singleton ofSSexactly when it does not occur inS−iS^\{\-i\},

𝔼M^V​\(S\)=ℙ\[x1∈V,x1∉T⁡\(S−1\)\]=∑x∈Vpx​\(1−px\)n−1,𝔼MV​\(S\)=∑x∈Vpx​\(1−px\)n,\\mathop\{\\mathbb\{E\}\}\\,\\widehat\{M\}\_\{V\}\(S\)=\\mathop\{\\mathbb\{P\}\}\\big\[x\_\{1\}\\in V,\\ x\_\{1\}\\notin T\(S^\{\-1\}\)\\big\]=\\sum\_\{x\\in V\}p\_\{x\}\(1\-p\_\{x\}\)^\{n\-1\},\\qquad\\mathop\{\\mathbb\{E\}\}\\,M\_\{V\}\(S\)=\\sum\_\{x\\in V\}p\_\{x\}\(1\-p\_\{x\}\)^\{n\},so the bias of the estimator is

0≤𝔼ZV​\(S\)=∑x∈Vpx2​\(1−px\)n−1≤1n​∑x∈Vpx≤1n,0\\leq\\mathop\{\\mathbb\{E\}\}\\,Z\_\{V\}\(S\)=\\sum\_\{x\\in V\}p\_\{x\}^\{2\}\(1\-p\_\{x\}\)^\{n\-1\}\\leq\\frac\{1\}\{n\}\\sum\_\{x\\in V\}p\_\{x\}\\leq\\frac\{1\}\{n\},\(18\)usingp​\(1−p\)n−1≤1/np\(1\-p\)^\{n\-1\}\\leq 1/nforp∈\[0,1\]p\\in\[0,1\]\.

Both terms ofZVZ\_\{V\}concentrate\. The estimatorM^V​\(S\)=1n​\|\{x∈V:\#x​\(S\)=1\}\|\\widehat\{M\}\_\{V\}\(S\)=\\frac\{1\}\{n\}\\,\|\\\{x\\in V:\\\#\_\{x\}\(S\)=1\\\}\|changes by at most2/n2/nwhen one sample point is replaced, since only the singleton status of the old and of the new value can change, so McDiarmid’s inequality gives

ℙ\[\|M^V\(S\)−𝔼M^V\(S\)\|≥t\]≤2e−nt2/2\.\\mathop\{\\mathbb\{P\}\}\\big\[\|\\widehat\{M\}\_\{V\}\(S\)\-\\mathop\{\\mathbb\{E\}\}\\widehat\{M\}\_\{V\}\(S\)\|\\geq t\\big\]\\leq 2e^\{\-nt^\{2\}/2\}\.\(19\)The missing massMV\(S\)=∑x∈Vpx𝟏\{\#x\(S\)=0\}M\_\{V\}\(S\)=\\sum\_\{x\\in V\}p\_\{x\}\\mathbf\{1\}\\\{\\\#\_\{x\}\(S\)=0\\\}does not have bounded differences, but it concentrates at the same scale\. The proofs of[McAllester and Ortiz \(2003, Theorems 10 and 16\)](https://arxiv.org/html/2610.41244#bib.bib56)for the unrestricted missing mass \(V=𝒳V=\\mathcal\{X\}\) use only the negative association of the indicators𝟏\{\#x\(S\)=0\}\\mathbf\{1\}\\\{\\\#\_\{x\}\(S\)=0\\\}, which is inherited by every subcollection, together with bounds on∑xpx2​\(1−px\)n\\sum\_\{x\}p\_\{x\}^\{2\}\(1\-p\_\{x\}\)^\{n\}and on∑xpx2/log⁡\(\(1−px\)−n\)\\sum\_\{x\}p\_\{x\}^\{2\}/\\log\\big\(\(1\-p\_\{x\}\)^\{\-n\}\\big\), which can only decrease when the sums are restricted tox∈Vx\\in V\. Hence there is an absolute constantc1\>0c\_\{1\}\>0such that

ℙ\[\|MV\(S\)−𝔼MV\(S\)\|≥t\]≤2e−c1​n​t2\.\\mathop\{\\mathbb\{P\}\}\\big\[\|M\_\{V\}\(S\)\-\\mathop\{\\mathbb\{E\}\}M\_\{V\}\(S\)\|\\geq t\\big\]\\leq 2e^\{\-c\_\{1\}nt^\{2\}\}\.\(20\)LetXV:=ZV​\(S\)−𝔼ZV​\(S\)X\_\{V\}:=Z\_\{V\}\(S\)\-\\mathop\{\\mathbb\{E\}\}Z\_\{V\}\(S\)\. Since\|XV\|≥t\|X\_\{V\}\|\\geq trequires one of the two centered terms to deviate by at leastt/2t/2, \([19](https://arxiv.org/html/2610.41244#A3.E19)\) and \([20](https://arxiv.org/html/2610.41244#A3.E20)\) giveℙ\[\|XV\|≥t\]≤4e−c2​n​t2\\mathop\{\\mathbb\{P\}\}\[\|X\_\{V\}\|\\geq t\]\\leq 4e^\{\-c\_\{2\}nt^\{2\}\}withc2:=min⁡\{1/8,c1/4\}c\_\{2\}:=\\min\\\{1/8,\\,c\_\{1\}/4\\\}\. Integrating this tail withλ:=c2​n/2\\lambda:=c\_\{2\}n/2,

𝔼eλ​XV2=1\+∫0∞λeλ​uℙ\[XV2\>u\]du≤1\+4λ∫0∞e−\(c2​n−λ\)​udu=5\.\\mathop\{\\mathbb\{E\}\}\\,e^\{\\lambda X\_\{V\}^\{2\}\}=1\+\\int\_\{0\}^\{\\infty\}\\lambda e^\{\\lambda u\}\\mathop\{\\mathbb\{P\}\}\\big\[X\_\{V\}^\{2\}\>u\\big\]\\,du\\leq 1\+4\\lambda\\int\_\{0\}^\{\\infty\}e^\{\-\(c\_\{2\}n\-\\lambda\)u\}\\,du=5\.FinallyZV2≤2​XV2\+2​\(𝔼ZV\)2≤2​XV2\+2/n2Z\_\{V\}^\{2\}\\leq 2X\_\{V\}^\{2\}\+2\(\\mathop\{\\mathbb\{E\}\}Z\_\{V\}\)^\{2\}\\leq 2X\_\{V\}^\{2\}\+2/n^\{2\}by \([18](https://arxiv.org/html/2610.41244#A3.E18)\), so withc3:=c2/4c\_\{3\}:=c\_\{2\}/4we obtain, for every regionVV, everyDDand everyn≥1n\\geq 1\(sincec2≤1/8c\_\{2\}\\leq 1/8, so that5​ec2/\(2​n\)≤5​e1/16<65e^\{c\_\{2\}/\(2n\)\}\\leq 5e^\{1/16\}<6\),

𝔼S∼Dnexp⁡\(c3​n​ZV​\(S\)2\)≤5​ec2/\(2​n\)≤6\.\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\exp\\big\(c\_\{3\}nZ\_\{V\}\(S\)^\{2\}\\big\)\\leq 5e^\{c\_\{2\}/\(2n\)\}\\leq 6\.\(21\)
*Step 2: decoupling\.*LetPPbe the joint law of\(S,𝒱\)\(S,\\mathcal\{V\}\)withS∼DnS\\sim D^\{n\}and𝒱=𝒱⁡\(S,r\)\\mathcal\{V\}=\\mathcal\{V\}\(S,r\), and letQ:=PS⊗P𝒱Q:=P\_\{S\}\\otimes P\_\{\\mathcal\{V\}\}be the product of its marginals, so thatDKL\(P∥Q\)=ID\(S;𝒱\)D\_\{\\mathrm\{KL\}\}\(P\\,\\\|\\,Q\)=I\_\{D\}\(S;\\mathcal\{V\}\)\. IfID​\(S,𝒱\)=∞I\_\{D\}\(S;\\mathcal\{V\}\)=\\inftythere is nothing to prove\. Otherwise the Donsker–Varadhan variational inequality,𝔼P\[f\]≤DKL\(P∥Q\)\+log𝔼Q\[ef\]\\mathop\{\\mathbb\{E\}\}\_\{P\}\[f\]\\leq D\_\{\\mathrm\{KL\}\}\(P\\,\\\|\\,Q\)\+\\log\\mathop\{\\mathbb\{E\}\}\_\{Q\}\[e^\{f\}\], applied tof⁡\(S,𝒱\):=c3​n​Z𝒱​\(S\)2f\(S,\\mathcal\{V\}\):=c\_\{3\}nZ\_\{\\mathcal\{V\}\}\(S\)^\{2\}gives

c3n𝔼P\[Z𝒱\(S\)2\]≤ID\(S;𝒱\)\+log𝔼Qexp\(c3nZ𝒱\(S\)2\)≤ID\(S;𝒱\)\+log6\.c\_\{3\}n\\,\\mathop\{\\mathbb\{E\}\}\_\{P\}\\big\[Z\_\{\\mathcal\{V\}\}\(S\)^\{2\}\\big\]\\leq I\_\{D\}\(S;\\mathcal\{V\}\)\+\\log\\mathop\{\\mathbb\{E\}\}\_\{Q\}\\exp\\big\(c\_\{3\}nZ\_\{\\mathcal\{V\}\}\(S\)^\{2\}\\big\)\\leq I\_\{D\}\(S;\\mathcal\{V\}\)\+\\log 6\.The last step uses that underQQthe region𝒱\\mathcal\{V\}is independent ofSS, so \([21](https://arxiv.org/html/2610.41244#A3.E21)\) applies conditionally on𝒱\\mathcal\{V\}and hence after averaging over its law\. Rearranging proves \([17](https://arxiv.org/html/2610.41244#A3.E17)\) withc:=\(log⁡6\)/c3c:=\(\\log 6\)/c\_\{3\}\. If𝒱\\mathcal\{V\}takes at mostLLvalues thenID​\(S,𝒱\)≤H⁡\(𝒱\)≤log⁡LI\_\{D\}\(S;\\mathcal\{V\}\)\\leq H\(\\mathcal\{V\}\)\\leq\\log L\. ∎

### C\.4VC Bounds for Adaptive Missing Mass

Theorem[C\.2](https://arxiv.org/html/2610.41244#A3.Thmtheorem2)gives the rate\(log⁡L\+1\)/n\(\\log L\+1\)/nfor a selection rule with at mostLLpossible outputs\. We now replacelog⁡L\\log Lby the VC dimension of the class of possible outputs, with no restriction on how the region is chosen from that class\. Throughout,𝒱=𝒱⁡\(S,r\)\\mathcal\{V\}=\\mathcal\{V\}\(S,r\)is a region selection rule with values in a classℋ⊆2𝒳\\mathcal\{H\}\\subseteq 2^\{\\mathcal\{X\}\},Z𝒱​\(S\)=M^𝒱⁡\(S\)​\(S\)−M𝒱⁡\(S\)​\(S\)Z\_\{\\mathcal\{V\}\}\(S\)=\\widehat\{M\}\_\{\\mathcal\{V\}\(S\)\}\(S\)\-M\_\{\\mathcal\{V\}\(S\)\}\(S\)is its error as in Appendix[C\.3](https://arxiv.org/html/2610.41244#A3.SS3), andD^\\hat\{D\}is the empirical distribution ofSS\(Section[4](https://arxiv.org/html/2610.41244#S4)\)\. As in Appendix[A](https://arxiv.org/html/2610.41244#A1),‖D^−D‖ℱ\\\|\\hat\{D\}\-D\\\|\_\{\\mathcal\{F\}\}denotes the uniform deviation of the empirical measure over a classℱ\\mathcal\{F\}, and we writeℋΔℋ:=\{VΔV′:V,V′∈ℋ\}\\mathcal\{H\}\\,\\Delta\\,\\mathcal\{H\}:=\\\{V\\,\\Delta\\,V^\{\\prime\}:V,V^\{\\prime\}\\in\\mathcal\{H\}\\\}for the class of symmetric differences of pairs of regions inℋ\\mathcal\{H\}\.

The argument is a covering reduction, applied to one distributionDDat a time \(the cover is used only in the analysis, so it may depend onDD\)\. ForV,V′⊆𝒳V,V^\{\\prime\}\\subseteq\\mathcal\{X\}letρD​\(V,V′\):=D⁡\(V​Δ​V′\)\\rho\_\{D\}\(V,V^\{\\prime\}\):=D\(V\\,\\Delta\\,V^\{\\prime\}\)\. An*internalη\\eta\-cover*ofℋ\\mathcal\{H\}is a finiteℬ⊆ℋ\\mathcal\{B\}\\subseteq\\mathcal\{H\}such that everyV∈ℋV\\in\\mathcal\{H\}has someB∈ℬB\\in\\mathcal\{B\}withρD​\(V,B\)≤η\\rho\_\{D\}\(V,B\)\\leq\\eta; let𝒩D​\(η,ℋ\)\\mathcal\{N\}\_\{D\}\(\\eta,\\mathcal\{H\}\)denote the smallest size of such a cover\. We replace the selected region by a nearby element of a cover, apply Theorem[C\.2](https://arxiv.org/html/2610.41244#A3.Thmtheorem2)to the resulting finite\-valued rule, and control the effect of the replacement by uniform convergence overℋ​Δ​ℋ\\mathcal\{H\}\\,\\Delta\\,\\mathcal\{H\}\. Requiring the cover to lie insideℋ\\mathcal\{H\}restricts the replacement errors to this class\. The two lemmas below and Lemma[A\.1](https://arxiv.org/html/2610.41244#A1.Thmtheorem1)supply the ingredients\.

###### Lemma C\.3\(Replacing the region\)\.

For all regionsV,V′⊆𝒳V,V^\{\\prime\}\\subseteq\\mathcal\{X\}and every sampleSS,

\|ZV​\(S\)−ZV′​\(S\)\|≤D^​\(V​Δ​V′\)\+D⁡\(V​Δ​V′\)\.\|Z\_\{V\}\(S\)\-Z\_\{V^\{\\prime\}\}\(S\)\|\\leq\\hat\{D\}\(V\\,\\Delta\\,V^\{\\prime\}\)\+D\(V\\,\\Delta\\,V^\{\\prime\}\)\.

###### Proof\.

A sample point contributes to exactly one ofM^V​\(S\)\\widehat\{M\}\_\{V\}\(S\)andM^V′​\(S\)\\widehat\{M\}\_\{V^\{\\prime\}\}\(S\)only if it lies inV​Δ​V′V\\,\\Delta\\,V^\{\\prime\}, so\|M^V\(S\)−M^V′\(S\)\|≤1n∑i=1n𝟏\{xi∈VΔV′\}=D^\(VΔV′\)\|\\widehat\{M\}\_\{V\}\(S\)\-\\widehat\{M\}\_\{V^\{\\prime\}\}\(S\)\|\\leq\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{x\_\{i\}\\in V\\,\\Delta\\,V^\{\\prime\}\\\}=\\hat\{D\}\(V\\,\\Delta\\,V^\{\\prime\}\)\. Also\|MV​\(S\)−MV′​\(S\)\|=\|D⁡\(V∖T⁡\(S\)\)−D⁡\(V′∖T⁡\(S\)\)\|≤D⁡\(V​Δ​V′\)\|M\_\{V\}\(S\)\-M\_\{V^\{\\prime\}\}\(S\)\|=\|D\(V\\setminus T\(S\)\)\-D\(V^\{\\prime\}\\setminus T\(S\)\)\|\\leq D\(V\\,\\Delta\\,V^\{\\prime\}\)\. ∎

###### Lemma C\.4\(Symmetric differences\)\.

IfVC⁡\(ℋ\)=d\\operatorname\{VC\}\(\\mathcal\{H\}\)=dthenVC⁡\(ℋ​Δ​ℋ\)≤10​d\\operatorname\{VC\}\(\\mathcal\{H\}\\,\\Delta\\,\\mathcal\{H\}\)\\leq 10d\.

###### Proof\.

Ifd=0d=0thenℋ\\mathcal\{H\}has at most one member andℋ​Δ​ℋ⊆\{∅\}\\mathcal\{H\}\\,\\Delta\\,\\mathcal\{H\}\\subseteq\\\{\\emptyset\\\}\. Letd≥1d\\geq 1and letΠℋ​\(m\)\\Pi\_\{\\mathcal\{H\}\}\(m\)be the growth function ofℋ\\mathcal\{H\}, the largest number of distinct traces ofℋ\\mathcal\{H\}onmmpoints\. Every trace ofℋ​Δ​ℋ\\mathcal\{H\}\\,\\Delta\\,\\mathcal\{H\}on a set ofmmpoints is the symmetric difference of two traces ofℋ\\mathcal\{H\}, soΠℋ​Δ​ℋ​\(m\)≤Πℋ​\(m\)2\\Pi\_\{\\mathcal\{H\}\\Delta\\mathcal\{H\}\}\(m\)\\leq\\Pi\_\{\\mathcal\{H\}\}\(m\)^\{2\}\. Ifℋ​Δ​ℋ\\mathcal\{H\}\\,\\Delta\\,\\mathcal\{H\}shatteredm=10​dm=10dpoints, Sauer’s lemma would give210​d≤Πℋ​\(10​d\)2≤\(10​e\)2​d2^\{10d\}\\leq\\Pi\_\{\\mathcal\{H\}\}\(10d\)^\{2\}\\leq\(10e\)^\{2d\}, which is false since\(10​e\)2<740<1024=210\(10e\)^\{2\}<740<1024=2^\{10\}\. ∎

###### Theorem C\.5\(Covering bound for adaptive missing mass\)\.

LetVC⁡\(ℋ\)=d<∞\\operatorname\{VC\}\(\\mathcal\{H\}\)=d<\\inftyand let𝒱\\mathcal\{V\}be a selection rule with values inℋ\\mathcal\{H\}\. There is an absolute constantccsuch that for everyD∈Δ​𝒳D\\in\\Delta\\mathcal\{X\}and every0<η≤10<\\eta\\leq 1,

𝔼\[Z𝒱​\(S\)2\]≤c⁡\(η2\+log⁡𝒩D​\(η,ℋ\)\+1n\+d\+1n\)\.\\mathop\{\\mathbb\{E\}\}\\big\[Z\_\{\\mathcal\{V\}\}\(S\)^\{2\}\\big\]\\leq c\\left\(\\eta^\{2\}\+\\frac\{\\log\\mathcal\{N\}\_\{D\}\(\\eta,\\mathcal\{H\}\)\+1\}\{n\}\+\\frac\{d\+1\}\{n\}\\right\)\.\(22\)

###### Proof\.

FixDDandη\\eta; if𝒩D​\(η,ℋ\)=∞\\mathcal\{N\}\_\{D\}\(\\eta,\\mathcal\{H\}\)=\\inftythere is nothing to prove\. Fix an internalη\\eta\-coverℬ=\{B1,…,BL\}⊆ℋ\\mathcal\{B\}=\\\{B\_\{1\},\\ldots,B\_\{L\}\\\}\\subseteq\\mathcal\{H\}of sizeL=𝒩D​\(η,ℋ\)L=\\mathcal\{N\}\_\{D\}\(\\eta,\\mathcal\{H\}\), and letπ:ℋ→ℬ\\pi:\\mathcal\{H\}\\to\\mathcal\{B\}map each region to the first cover element withinρD\\rho\_\{D\}\-distanceη\\etaof it\. ThenB:=π⁡\(𝒱\)B:=\\pi\(\\mathcal\{V\}\)is a selection rule with at mostLLvalues, so Theorem[C\.2](https://arxiv.org/html/2610.41244#A3.Thmtheorem2)gives𝔼\[ZB​\(S\)2\]≤c0​\(log⁡L\+1\)/n\\mathop\{\\mathbb\{E\}\}\[Z\_\{B\}\(S\)^\{2\}\]\\leq c\_\{0\}\(\\log L\+1\)/nfor an absolute constantc0c\_\{0\}\. Since𝒱⁡\(S\)​Δ​B​\(S\)∈ℋ​Δ​ℋ\\mathcal\{V\}\(S\)\\,\\Delta\\,B\(S\)\\in\\mathcal\{H\}\\,\\Delta\\,\\mathcal\{H\}andD⁡\(𝒱⁡\(S\)​Δ​B​\(S\)\)≤ηD\(\\mathcal\{V\}\(S\)\\,\\Delta\\,B\(S\)\)\\leq\\eta, Lemma[C\.3](https://arxiv.org/html/2610.41244#A3.Thmtheorem3)gives

\|Z𝒱​\(S\)−ZB​\(S\)\|≤D^​\(𝒱⁡\(S\)​Δ​B​\(S\)\)\+η≤2​η\+‖D^−D‖ℋ​Δ​ℋ\.\|Z\_\{\\mathcal\{V\}\}\(S\)\-Z\_\{B\}\(S\)\|\\leq\\hat\{D\}\(\\mathcal\{V\}\(S\)\\,\\Delta\\,B\(S\)\)\+\\eta\\leq 2\\eta\+\\\|\\hat\{D\}\-D\\\|\_\{\\mathcal\{H\}\\Delta\\mathcal\{H\}\}\.Therefore

𝔼\[Z𝒱​\(S\)2\]≤2​𝔼\[ZB​\(S\)2\]\+2​𝔼\[\(Z𝒱​\(S\)−ZB​\(S\)\)2\]≤2​c0​\(log⁡L\+1\)n\+16​η2\+4​𝔼\[‖D^−D‖ℋ​Δ​ℋ2\],\\mathop\{\\mathbb\{E\}\}\\big\[Z\_\{\\mathcal\{V\}\}\(S\)^\{2\}\\big\]\\leq 2\\mathop\{\\mathbb\{E\}\}\\big\[Z\_\{B\}\(S\)^\{2\}\\big\]\+2\\mathop\{\\mathbb\{E\}\}\\big\[\(Z\_\{\\mathcal\{V\}\}\(S\)\-Z\_\{B\}\(S\)\)^\{2\}\\big\]\\leq\\frac\{2c\_\{0\}\(\\log L\+1\)\}\{n\}\+16\\eta^\{2\}\+4\\mathop\{\\mathbb\{E\}\}\\big\[\\\|\\hat\{D\}\-D\\\|\_\{\\mathcal\{H\}\\Delta\\mathcal\{H\}\}^\{2\}\\big\],and by Lemmas[C\.4](https://arxiv.org/html/2610.41244#A3.Thmtheorem4)and[A\.1](https://arxiv.org/html/2610.41244#A1.Thmtheorem1)the last expectation isO⁡\(\(d\+1\)/n\)O\(\(d\+1\)/n\)\. ∎

Haussler’s packing bound\([Haussler, 1995](https://arxiv.org/html/2610.41244#bib.bib42)\)controls the covering numbers uniformly inDD: for every class of VC dimensiond≥1d\\geq 1and every0<η≤10<\\eta\\leq 1,

log⁡𝒩D​\(η,ℋ\)≤c1​d​log⁡c2η\\log\\mathcal\{N\}\_\{D\}\(\\eta,\\mathcal\{H\}\)\\leq c\_\{1\}\\,d\\log\\frac\{c\_\{2\}\}\{\\eta\}\(23\)for absolute constantsc1,c2≥ec\_\{1\},c\_\{2\}\\geq e\. Choosingη\\etato balance the terms of \([22](https://arxiv.org/html/2610.41244#A3.E22)\) gives part[\(ii\)](https://arxiv.org/html/2610.41244#S6.I1.i2)of Theorem[6\.3](https://arxiv.org/html/2610.41244#S6.Thmtheorem3)\.

###### Corollary C\.6\(VC bound for adaptive missing mass\)\.

Let𝒱\\mathcal\{V\}be a selection rule with values in a classℋ\\mathcal\{H\}withVC⁡\(ℋ\)=d\\operatorname\{VC\}\(\\mathcal\{H\}\)=d\. If1≤d≤n1\\leq d\\leq nthen

supD∈Δ​𝒳𝔼\[Z𝒱​\(S\)2\]=O⁡\(d​log⁡\(e​n/d\)n\)\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\\big\[Z\_\{\\mathcal\{V\}\}\(S\)^\{2\}\\big\]=O\\Big\(\\frac\{d\\log\(en/d\)\}\{n\}\\Big\)\(24\)with an absolute constant, and ifd=0d=0the left\-hand side isO⁡\(1/n\)O\(1/n\)\. In particular, ifdn:=VC⁡\(ℋn\)=o⁡\(n\)d\_\{n\}:=\\operatorname\{VC\}\(\\mathcal\{H\}\_\{n\}\)=o\(n\)then the left\-hand side tends to00\.

###### Proof\.

For1≤d≤n1\\leq d\\leq napply Theorem[C\.5](https://arxiv.org/html/2610.41244#A3.Thmtheorem5)withη=d/n≤1\\eta=\\sqrt\{d/n\}\\leq 1and use \([23](https://arxiv.org/html/2610.41244#A3.E23)\): sincelog⁡\(e​n/d\)≥1\\log\(en/d\)\\geq 1, each of the three terms in \([22](https://arxiv.org/html/2610.41244#A3.E22)\) isO⁡\(d​log⁡\(e​n/d\)/n\)O\(d\\log\(en/d\)/n\)\. Ifd=0d=0thenℋ\\mathcal\{H\}has a single member, and Theorem[C\.2](https://arxiv.org/html/2610.41244#A3.Thmtheorem2)withL=1L=1givesO⁡\(1/n\)O\(1/n\)\. For the last claim,x​log⁡\(e/x\)→0x\\log\(e/x\)\\to 0asx=dn/n→0x=d\_\{n\}/n\\to 0\. ∎

### C\.5Proof of Corollary[6\.4](https://arxiv.org/html/2610.41244#S6.Thmtheorem4)and the Multiclass Extension

Throughout,𝒳y\\mathcal\{X\}\_\{y\},ℰny\\mathcal\{E\}\_\{n\}^\{y\}, and𝒢y\\mathcal\{G\}\_\{y\}are defined as in Section[6](https://arxiv.org/html/2610.41244#S6)for a labelingy:𝒲→𝒴y:\\mathcal\{W\}\\to\\mathcal\{Y\}\.

###### Proof of Corollary[6\.4](https://arxiv.org/html/2610.41244#S6.Thmtheorem4)\.

*Error regions\.*Fix a labelingyyand, forh∈ℋh\\in\\mathcal\{H\}, letEh:=\{w∈𝒲:h⁡\(w\)≠y⁡\(w\)\}E\_\{h\}:=\\\{w\\in\\mathcal\{W\}:h\(w\)\\neq y\(w\)\\\}be its error region relative toyy, whose indicator ish⊕yh\\oplus y\. For a finiteT⊆𝒲T\\subseteq\\mathcal\{W\}, the mapb↦b⊕y\|Tb\\mapsto b\\oplus y\|\_\{T\}is a bijection of\{0,1\}T\\\{0,1\\\}^\{T\}, and it maps the set of restrictions toTTof the members ofℋ\\mathcal\{H\}onto the set of restrictions toTTof the members of\{Eh:h∈ℋ\}\\\{E\_\{h\}:h\\in\\mathcal\{H\}\\\}\. HenceTTis shattered by\{Eh:h∈ℋ\}\\\{E\_\{h\}:h\\in\\mathcal\{H\}\\\}if and only if it is shattered byℋ\\mathcal\{H\}, andVC⁡\(\{Eh:h∈ℋ\}\)=d\\operatorname\{VC\}\(\\\{E\_\{h\}:h\\in\\mathcal\{H\}\\\}\)=d\. Since the output of𝒜\\mathcal\{A\}lies inℋ\\mathcal\{H\}, every member ofℰny\\mathcal\{E\}\_\{n\}^\{y\}is the image of someEhE\_\{h\}under the bijectionw↦\(w,y⁡\(w\)\)w\\mapsto\(w,y\(w\)\)from𝒲\\mathcal\{W\}to𝒳y\\mathcal\{X\}\_\{y\}, which preserves the VC dimension, and soVC⁡\(ℰny\)≤d\\operatorname\{VC\}\(\\mathcal\{E\}\_\{n\}^\{y\}\)\\leq d\.

*The estimate\.*Fixyy\. By Definition[6\.3](https://arxiv.org/html/2610.41244#S6.Thmdefinition3), the error of the hybrid estimator for𝒢y\\mathcal\{G\}\_\{y\}isεEyamm​\(n\)\\varepsilon^\{\\mathrm\{amm\}\}\_\{E^\{y\}\}\(n\)for the selection ruleS↦Ey​\(S\)S\\mapsto E^\{y\}\(S\)on the example space𝒳y\\mathcal\{X\}\_\{y\}, whose image class isℰny\\mathcal\{E\}\_\{n\}^\{y\}\. Apply Theorem[6\.3](https://arxiv.org/html/2610.41244#S6.Thmtheorem3)withdn:=VC⁡\(ℰny\)≤d≤nd\_\{n\}:=\\operatorname\{VC\}\(\\mathcal\{E\}\_\{n\}^\{y\}\)\\leq d\\leq n\. Ifdn≥1d\_\{n\}\\geq 1, part[\(ii\)](https://arxiv.org/html/2610.41244#S6.I1.i2)givesO⁡\(dn​log⁡\(e​n/dn\)/n\)O\(d\_\{n\}\\log\(en/d\_\{n\}\)/n\), which isO⁡\(d​log⁡\(e​n/d\)/n\)O\(d\\log\(en/d\)/n\)becausex↦x​log⁡\(e​n/x\)x\\mapsto x\\log\(en/x\)is nondecreasing on\(0,n\]\(0,n\]\. Ifdn=0d\_\{n\}=0thenℰny\\mathcal\{E\}\_\{n\}^\{y\}consists of a single region, and part[\(i\)](https://arxiv.org/html/2610.41244#S6.I1.i1)withL=1L=1givesO⁡\(1/n\)O\(1/n\), which is againO⁡\(d​log⁡\(e​n/d\)/n\)O\(d\\log\(en/d\)/n\)asd≥1d\\geq 1\. The constants in Theorem[6\.3](https://arxiv.org/html/2610.41244#S6.Thmtheorem3)are absolute and do not depend on the example space, so the bound holds with one constant for everyyy\. ∎

For a general label set the role of the VC dimension is played by the graph dimension\. For a classℋ⊆𝒴𝒲\\mathcal\{H\}\\subseteq\\mathcal\{Y\}^\{\\mathcal\{W\}\}, writeℋgr:=\{\(w,y′\)↦𝟏\{h\(w\)=y′\}:h∈ℋ\}\\mathcal\{H\}^\{\\mathrm\{gr\}\}:=\\\{\(w,y^\{\\prime\}\)\\mapsto\\mathbf\{1\}\\\{h\(w\)=y^\{\\prime\}\\\}:h\\in\\mathcal\{H\}\\\}for the class of graphs of its members, viewed as subsets of𝒲×𝒴\\mathcal\{W\}\\times\\mathcal\{Y\}; the*graph dimension*ofℋ\\mathcal\{H\}isVC⁡\(ℋgr\)\\operatorname\{VC\}\(\\mathcal\{H\}^\{\\mathrm\{gr\}\}\)\([Natarajan, 1989](https://arxiv.org/html/2610.41244#bib.bib60);[Ben\-David et al\., 1995](https://arxiv.org/html/2610.41244#bib.bib8)\)\. When𝒴=\{0,1\}\\mathcal\{Y\}=\\\{0,1\\\}it coincides withVC⁡\(ℋ\)\\operatorname\{VC\}\(\\mathcal\{H\}\)\. Indeed, ifT⊆𝒲T\\subseteq\\mathcal\{W\}is shattered byℋ\\mathcal\{H\}then\{\(w,1\):w∈T\}\\\{\(w,1\):w\\in T\\\}is shattered byℋgr\\mathcal\{H\}^\{\\mathrm\{gr\}\}, since𝟏\{h\(w\)=1\}=h\(w\)\\mathbf\{1\}\\\{h\(w\)=1\\\}=h\(w\)\. Conversely, letU⊆𝒲×\{0,1\}U\\subseteq\\mathcal\{W\}\\times\\\{0,1\\\}be shattered byℋgr\\mathcal\{H\}^\{\\mathrm\{gr\}\}\. Nohhsatisfiesh⁡\(w\)=0h\(w\)=0andh⁡\(w\)=1h\(w\)=1at once, soUUcontains at most one pair with each first coordinate, andU=\{\(w,yw′\):w∈T\}U=\\\{\(w,y^\{\\prime\}\_\{w\}\):w\\in T\\\}for someT⊆𝒲T\\subseteq\\mathcal\{W\}with\|T\|=\|U\|\|T\|=\|U\|\. For everyb∈\{0,1\}Tb\\in\\\{0,1\\\}^\{T\}there ish∈ℋh\\in\\mathcal\{H\}withh⁡\(w\)=yw′h\(w\)=y^\{\\prime\}\_\{w\}whenb⁡\(w\)=1b\(w\)=1andh⁡\(w\)=1−yw′h\(w\)=1\-y^\{\\prime\}\_\{w\}whenb⁡\(w\)=0b\(w\)=0, and asbbranges over\{0,1\}T\\\{0,1\\\}^\{T\}so does this labeling ofTT; thusTTis shattered byℋ\\mathcal\{H\}\. Corollary[6\.4](https://arxiv.org/html/2610.41244#S6.Thmtheorem4)is therefore the case𝒴=\{0,1\}\\mathcal\{Y\}=\\\{0,1\\\}of the following statement\.

###### Corollary C\.7\(Multiclass version of Corollary[6\.4](https://arxiv.org/html/2610.41244#S6.Thmtheorem4)\)\.

Let𝒴\\mathcal\{Y\}be any label set, letℋ⊆𝒴𝒲\\mathcal\{H\}\\subseteq\\mathcal\{Y\}^\{\\mathcal\{W\}\}be a class with graph dimensiondd, and let𝒜\\mathcal\{A\}be a base learner whose output lies inℋ\\mathcal\{H\}on every labeled sample\. ThenVC⁡\(ℰny\)≤d\\operatorname\{VC\}\(\\mathcal\{E\}\_\{n\}^\{y\}\)\\leq dfor every labelingy:𝒲→𝒴y:\\mathcal\{W\}\\to\\mathcal\{Y\}and everynn, and if1≤d≤n1\\leq d\\leq nthen

supD∈Δ​𝒳y𝔼S∼Dn\[\(p^𝒢yhyb​\(S\)−D⁡\(𝒢y​\(S\)\)\)2\]=O⁡\(d​log⁡\(e​n/d\)n\)\\sup\_\{D\\in\\Delta\\mathcal\{X\}\_\{y\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\Big\[\\big\(\\hat\{p\}\_\{\\mathcal\{G\}\_\{y\}\}^\{\\mathrm\{hyb\}\}\(S\)\-D\(\\mathcal\{G\}\_\{y\}\(S\)\)\\big\)^\{2\}\\Big\]=O\\Big\(\\frac\{d\\log\(en/d\)\}\{n\}\\Big\)for every labelingyy, with an absolute constant\.

###### Proof\.

Fix a labelingyyand, forh∈ℋh\\in\\mathcal\{H\}, letEh:=\{w∈𝒲:h⁡\(w\)≠y⁡\(w\)\}E\_\{h\}:=\\\{w\\in\\mathcal\{W\}:h\(w\)\\neq y\(w\)\\\}\. Suppose thatT⊆𝒲T\\subseteq\\mathcal\{W\}is shattered by\{Eh:h∈ℋ\}\\\{E\_\{h\}:h\\in\\mathcal\{H\}\\\}and letU:=\{\(w,y⁡\(w\)\):w∈T\}U:=\\\{\(w,y\(w\)\):w\\in T\\\}, so that\|U\|=\|T\|\|U\|=\|T\|\. For everyb∈\{0,1\}Tb\\in\\\{0,1\\\}^\{T\}there ish∈ℋh\\in\\mathcal\{H\}with𝟏\{h\(w\)≠y\(w\)\}=b\(w\)\\mathbf\{1\}\\\{h\(w\)\\neq y\(w\)\\\}=b\(w\)for allw∈Tw\\in T, that is,𝟏\{h\(w\)=y\(w\)\}=1−b\(w\)\\mathbf\{1\}\\\{h\(w\)=y\(w\)\\\}=1\-b\(w\); henceUUis shattered byℋgr\\mathcal\{H\}^\{\\mathrm\{gr\}\}and\|T\|≤d\|T\|\\leq d\. Since every member ofℰny\\mathcal\{E\}\_\{n\}^\{y\}is the image of someEhE\_\{h\}under the bijectionw↦\(w,y⁡\(w\)\)w\\mapsto\(w,y\(w\)\), we getVC⁡\(ℰny\)≤d\\operatorname\{VC\}\(\\mathcal\{E\}\_\{n\}^\{y\}\)\\leq d\. The remaining step of the proof of Corollary[6\.4](https://arxiv.org/html/2610.41244#S6.Thmtheorem4)applies verbatim, with𝒴\\mathcal\{Y\}in place of\{0,1\}\\\{0,1\\\}\. ∎

## Appendix DProof of the Quadratic\-Domain Construction

We assumen≥2n\\geq 2throughout\.

###### Proof of Theorem[7\.3](https://arxiv.org/html/2610.41244#S7.Thmtheorem3)\.

*The construction\.*Letw=n2w=n^\{2\},m=2​w=2​n2m=2w=2n^\{2\}and𝒳n=\[m\]\\mathcal\{X\}\_\{n\}=\[m\]\. For a setT⊆\[m\]T\\subseteq\[m\]with\|T\|=n\|T\|=nandVVuniform on\(\[m\]w\)\\binom\{\[m\]\}\{w\}, let

pn:=ℙ\[T⊆V\]=\(m−nw−n\)\(mw\)=∏ℓ=0n−1w−ℓm−ℓ,p\_\{n\}:=\\mathop\{\\mathbb\{P\}\}\[T\\subseteq V\]=\\frac\{\\binom\{m\-n\}\{w\-n\}\}\{\\binom\{m\}\{w\}\}=\\prod\_\{\\ell=0\}^\{n\-1\}\\frac\{w\-\\ell\}\{m\-\\ell\},which does not depend onTT, and setM:=⌊1/pn⌋\+1M:=\\lfloor 1/p\_\{n\}\\rfloor\+1\. Since each factor\(w−ℓ\)/\(m−ℓ\)\(w\-\\ell\)/\(m\-\\ell\)is at most1/21/2, we havepn≤2−np\_\{n\}\\leq 2^\{\-n\}\. DrawV1,…,VMV\_\{1\},\\ldots,V\_\{M\}independently and uniformly from\(\[m\]w\)\\binom\{\[m\]\}\{w\}, write𝒞=\(V1,…,VM\)\\mathcal\{C\}=\(V\_\{1\},\\ldots,V\_\{M\}\), and letDiD\_\{i\}be the uniform distribution onViV\_\{i\}\. For a sampleS=\(x1,…,xn\)∈\[m\]nS=\(x\_\{1\},\\ldots,x\_\{n\}\)\\in\[m\]^\{n\}letT⁡\(S\)=\{x1,…,xn\}T\(S\)=\\\{x\_\{1\},\\ldots,x\_\{n\}\\\}, letI𝒞​\(S\)=\{i∈\[M\]:T⁡\(S\)⊆Vi\}I\_\{\\mathcal\{C\}\}\(S\)=\\\{i\\in\[M\]:T\(S\)\\subseteq V\_\{i\}\\\}be the set of codewords consistent withSS, and define𝒢𝒞​\(S\)=Vmin⁡I𝒞​\(S\)\\mathcal\{G\}\_\{\\mathcal\{C\}\}\(S\)=V\_\{\\min I\_\{\\mathcal\{C\}\}\(S\)\}ifI𝒞​\(S\)≠∅I\_\{\\mathcal\{C\}\}\(S\)\\neq\\emptysetand𝒢𝒞​\(S\)=∅\\mathcal\{G\}\_\{\\mathcal\{C\}\}\(S\)=\\emptysetotherwise\.

*Reduction to a Bayesian experiment\.*Fix a code𝒞\\mathcal\{C\}and an estimatorp^:𝒳nn→\[0,1\]\\hat\{p\}:\\mathcal\{X\}\_\{n\}^\{n\}\\to\[0,1\]\. LetIIbe uniform on\[M\]\[M\]and, givenII, letS∼DInS\\sim D\_\{I\}^\{n\}\. Since the supremum overD∈Δ⁡\(𝒳n\)D\\in\\Delta\(\\mathcal\{X\}\_\{n\}\)dominates the average overD1,…,DMD\_\{1\},\\ldots,D\_\{M\},

supD∈Δ⁡\(𝒳n\)𝔼S∼Dn\[\(p^​\(S\)−D⁡\(𝒢𝒞​\(S\)\)\)2\]≥𝔼\[\(p^​\(S\)−DI​\(𝒢𝒞​\(S\)\)\)2\|𝒞\]\.\\sup\_\{D\\in\\Delta\(\\mathcal\{X\}\_\{n\}\)\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\left\[\\left\(\\hat\{p\}\(S\)\-D\(\\mathcal\{G\}\_\{\\mathcal\{C\}\}\(S\)\)\\right\)^\{2\}\\right\]\\geq\\mathop\{\\mathbb\{E\}\}\\left\[\\left\(\\hat\{p\}\(S\)\-D\_\{I\}\(\\mathcal\{G\}\_\{\\mathcal\{C\}\}\(S\)\)\\right\)^\{2\}\\;\\middle\|\\;\\mathcal\{C\}\\right\]\.\(25\)EachDinD\_\{i\}^\{n\}assigns probabilityw−nw^\{\-n\}to every ordered sampleSSwithT⁡\(S\)⊆ViT\(S\)\\subseteq V\_\{i\}and probability00to every other sample\. Hence, given𝒞\\mathcal\{C\}andSS, the posterior distribution ofIIis uniform onI𝒞​\(S\)I\_\{\\mathcal\{C\}\}\(S\), which containsII\. On the eventG:=\{\|T⁡\(S\)\|=n,\|I𝒞​\(S\)\|=2\}G:=\\\{\|T\(S\)\|=n,\\ \|I\_\{\\mathcal\{C\}\}\(S\)\|=2\\\}, writeI𝒞​\(S\)=\{a,b\}I\_\{\\mathcal\{C\}\}\(S\)=\\\{a,b\\\}, letJ=min⁡\{a,b\}J=\\min\\\{a,b\\\}, so that𝒢𝒞​\(S\)=VJ\\mathcal\{G\}\_\{\\mathcal\{C\}\}\(S\)=V\_\{J\}, and letρ:=\|Va∩Vb\|/w\\rho:=\|V\_\{a\}\\cap V\_\{b\}\|/w\. The targetDI​\(VJ\)D\_\{I\}\(V\_\{J\}\)equals11ifI=JI=Jandρ\\rhootherwise, each with posterior probability1/21/2\. Sincep^​\(S\)\\hat\{p\}\(S\)is determined bySS, its conditional mean\-squared error given\(𝒞,S\)\(\\mathcal\{C\},S\)is at least the conditional variance\(1−ρ\)2/4\(1\-\\rho\)^\{2\}/4of the target\. So for every estimator the right\-hand side of \([25](https://arxiv.org/html/2610.41244#A4.E25)\) is at leastB⁡\(𝒞\):=14​𝔼\[\(1−ρ\)2​𝟏G\|𝒞\]B\(\\mathcal\{C\}\):=\\frac\{1\}\{4\}\\mathop\{\\mathbb\{E\}\}\\left\[\(1\-\\rho\)^\{2\}\\mathbf\{1\}\_\{G\}\\;\\middle\|\\;\\mathcal\{C\}\\right\], and it suffices to show that𝔼𝒞B⁡\(𝒞\)≥1/576\\mathop\{\\mathbb\{E\}\}\_\{\\mathcal\{C\}\}B\(\\mathcal\{C\}\)\\geq 1/576: some code𝒞∗\\mathcal\{C\}^\{\*\}then hasB⁡\(𝒞∗\)≥1/576B\(\\mathcal\{C\}^\{\*\}\)\\geq 1/576, and𝒢n:=𝒢𝒞∗\\mathcal\{G\}\_\{n\}:=\\mathcal\{G\}\_\{\\mathcal\{C\}^\{\*\}\}has the claimed property\.

*Lower bound on𝔼𝒞B⁡\(𝒞\)\\mathop\{\\mathbb\{E\}\}\_\{\\mathcal\{C\}\}B\(\\mathcal\{C\}\)\.*Condition onI=iI=i, onViV\_\{i\}, and on the sampleSS\. Under this conditioning the other codewordsVjV\_\{j\},j≠ij\\neq i, are still independent and uniform on\(\[m\]w\)\\binom\{\[m\]\}\{w\}\. LetE0E\_\{0\}be the event thatx1,…,xnx\_\{1\},\\ldots,x\_\{n\}are distinct\. Since the sample is drawn uniformly from a set of sizew=n2w=n^\{2\},

ℙ\[E0∣I,VI\]=∏t=0n−1\(1−tw\)≥1−n⁡\(n−1\)2​w≥12\.\\mathop\{\\mathbb\{P\}\}\[E\_\{0\}\\mid I,V\_\{I\}\]=\\prod\_\{t=0\}^\{n\-1\}\\Big\(1\-\\frac\{t\}\{w\}\\Big\)\\geq 1\-\\frac\{n\(n\-1\)\}\{2w\}\\geq\\frac\{1\}\{2\}\.Assume thatE0E\_\{0\}holds, so thatT:=T⁡\(S\)T:=T\(S\)has exactlynnelements\. ThenW:=\|I𝒞\(S\)\|−1=∑j≠i𝟏\{T⊆Vj\}W:=\|I\_\{\\mathcal\{C\}\}\(S\)\|\-1=\\sum\_\{j\\neq i\}\\mathbf\{1\}\\\{T\\subseteq V\_\{j\}\\\}isBinomial⁡\(M−1,pn\)\\operatorname\{Binomial\}\(M\-1,p\_\{n\}\)with meanλ:=\(M−1\)​pn=⌊1/pn⌋​pn∈\[1−pn,1\]\\lambda:=\(M\-1\)p\_\{n\}=\\lfloor 1/p\_\{n\}\\rfloor p\_\{n\}\\in\[1\-p\_\{n\},1\], and

ℙ\[W=1∣I,VI,S\]=λ\(1−pn\)M−2≥12⋅14=18,\\mathop\{\\mathbb\{P\}\}\[W=1\\mid I,V\_\{I\},S\]=\\lambda\(1\-p\_\{n\}\)^\{M\-2\}\\geq\\frac\{1\}\{2\}\\cdot\\frac\{1\}\{4\}=\\frac\{1\}\{8\},usingλ≥1−pn≥1/2\\lambda\\geq 1\-p\_\{n\}\\geq 1/2,M−2≤1/pnM\-2\\leq 1/p\_\{n\}, and\(1−p\)1/p≥1/4\(1\-p\)^\{1/p\}\\geq 1/4for0<p≤1/20<p\\leq 1/2\. Given in addition thatW=1W=1and thatbbis the index of the other consistent codeword, the codewordVbV\_\{b\}is uniform among theww\-subsets of\[m\]\[m\]that containTT, independently ofViV\_\{i\}: the event depends onVbV\_\{b\}only throughT⊆VbT\\subseteq V\_\{b\}, and on the other codewords only through their not containingTT\. SoVb∖TV\_\{b\}\\setminus Tis a uniform\(w−n\)\(w\-n\)\-subset of\[m\]∖T\[m\]\\setminus T, and\|Vi∩Vb\|=n\+H\|V\_\{i\}\\cap V\_\{b\}\|=n\+HwithH∼Hypergeometric⁡\(m−n,w−n,w−n\)H\\sim\\operatorname\{Hypergeometric\}\(m\-n,\\,w\-n,\\,w\-n\)\(a population ofm−nm\-nelements, of which thew−nw\-nelements ofVi∖TV\_\{i\}\\setminus Tare marked, andw−nw\-ndraws\)\. Sincem=2​wm=2wandw=n2w=n^\{2\},

𝔼\[1−ρ\|I,VI,S,W=1,b\]=1−nw−\(w−n\)2w⁡\(m−n\)=w−n2​w−n=n−12​n−1≥13,\\mathop\{\\mathbb\{E\}\}\\left\[1\-\\rho\\;\\middle\|\\;I,V\_\{I\},S,W=1,b\\right\]=1\-\\frac\{n\}\{w\}\-\\frac\{\(w\-n\)^\{2\}\}\{w\(m\-n\)\}=\\frac\{w\-n\}\{2w\-n\}=\\frac\{n\-1\}\{2n\-1\}\\geq\\frac\{1\}\{3\},and by Jensen’s inequality𝔼\[\(1−ρ\)2\|I,VI,S,W=1,b\]≥1/9\\mathop\{\\mathbb\{E\}\}\\left\[\(1\-\\rho\)^\{2\}\\;\\middle\|\\;I,V\_\{I\},S,W=1,b\\right\]\\geq 1/9\. Averaging overbb,SS,VIV\_\{I\}andII, and using thatG⊇E0∩\{W=1\}G\\supseteq E\_\{0\}\\cap\\\{W=1\\\},

𝔼𝒞B⁡\(𝒞\)≥14⋅ℙ\[E0\]⋅18⋅19≥14⋅12⋅18⋅19=1576\.∎\\mathop\{\\mathbb\{E\}\}\_\{\\mathcal\{C\}\}B\(\\mathcal\{C\}\)\\geq\\frac\{1\}\{4\}\\cdot\\mathop\{\\mathbb\{P\}\}\[E\_\{0\}\]\\cdot\\frac\{1\}\{8\}\\cdot\\frac\{1\}\{9\}\\geq\\frac\{1\}\{4\}\\cdot\\frac\{1\}\{2\}\\cdot\\frac\{1\}\{8\}\\cdot\\frac\{1\}\{9\}=\\frac\{1\}\{576\}\.\\qed

## Appendix EEstimation of Data\-dependent Mass versus Its Expectation

The valueD⁡\(𝒢⁡\(S\)\)D\(\\mathcal\{G\}\(S\)\)in Definition[3\.2](https://arxiv.org/html/2610.41244#S3.Thmdefinition2)is a random quantity, determined by the realized sample\. One could instead ask to estimate its expectation,

θ𝒢​\(D\):=𝔼S∼Dn\[D⁡\(𝒢⁡\(S\)\)\],\\theta\_\{\\mathcal\{G\}\}\(D\):=\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\big\[D\(\\mathcal\{G\}\(S\)\)\\big\],\(26\)a deterministic functional ofDD\. This is the form of problem to which the classical lower\-bound techniques for functional estimation, the two\-point method of Le Cam and the method of Fano\([Le Cam, 1973](https://arxiv.org/html/2610.41244#bib.bib50);[Fano, 1966](https://arxiv.org/html/2610.41244#bib.bib28);[Yu, 1997](https://arxiv.org/html/2610.41244#bib.bib87)\), apply, and one might hope to obtain lower bounds on estimatability from them\. The following example shows that the two targets are different: the random mass can be observed exactly while its expectation cannot be estimated to within a constant\. A lower bound on estimating \([26](https://arxiv.org/html/2610.41244#A5.E26)\) therefore carries no implication for estimatability in the sense of Definition[3\.2](https://arxiv.org/html/2610.41244#S3.Thmdefinition2), which is why the impossibility results of Section[7](https://arxiv.org/html/2610.41244#S7)argue directly about the conditional distribution of the random target given the sample\.

###### Proposition E\.1\.

Let𝒳=ℕ∪\{0\}\\mathcal\{X\}=\\mathbb\{N\}\\cup\\\{0\\\}and let𝒢⁡\(S\)=𝒳\\mathcal\{G\}\(S\)=\\mathcal\{X\}if0∈S0\\in Sand𝒢⁡\(S\)=∅\\mathcal\{G\}\(S\)=\\emptysetotherwise\. Then the estimatorp^\(S\)=𝟏\{0∈S\}\\hat\{p\}\(S\)=\\mathbf\{1\}\\\{0\\in S\\\}satisfiesp^​\(S\)=D​\(𝒢​\(S\)\)\\hat\{p\}\(S\)=D\(\\mathcal\{G\}\(S\)\)for every sample and everyDD, so𝒢\\mathcal\{G\}is estimatable with zero error, whereas for everyn≥1n\\geq 1

infp^supD∈Δ​𝒳𝔼S∼Dn\[\(p^​\(S\)−θ𝒢​\(D\)\)2\]≥\(1−e−1/2\)216\.\\inf\_\{\\hat\{p\}\}\\sup\_\{D\\in\\Delta\\mathcal\{X\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D^\{n\}\}\\Big\[\\big\(\\hat\{p\}\(S\)\-\\theta\_\{\\mathcal\{G\}\}\(D\)\\big\)^\{2\}\\Big\]\\geq\\frac\{\(1\-e^\{\-1/2\}\)^\{2\}\}\{16\}\.

###### Proof\.

The first claim holds becauseD\(𝒢\(S\)\)=𝟏\{0∈S\}D\(\\mathcal\{G\}\(S\)\)=\\mathbf\{1\}\\\{0\\in S\\\}is a function of the sample\.

For the second claim, note thatθ𝒢​\(D\)\\theta\_\{\\mathcal\{G\}\}\(D\)is the probability that the point00appears in the sample,

θ𝒢\(D\)=ℙS∼Dn\[0∈S\]=1−\(1−D\(0\)\)n\.\\theta\_\{\\mathcal\{G\}\}\(D\)=\\mathop\{\\mathbb\{P\}\}\_\{S\\sim D^\{n\}\}\[0\\in S\]=1\-\(1\-D\(0\)\)^\{n\}\.We compare two distributions that differ only in the mass of the point00\. Letδ:=1/\(2​n\)\\delta:=1/\(2n\), letD0D\_\{0\}put all of its mass on the point11, and letD1D\_\{1\}put massδ\\deltaon00and mass1−δ1\-\\deltaon11\. UnderD0D\_\{0\}the point00never appears, soθ𝒢​\(D0\)=0\\theta\_\{\\mathcal\{G\}\}\(D\_\{0\}\)=0, whereas

θ𝒢\(D1\)=1−\(1−δ\)n≥1−e−n​δ=1−e−1/2\.\\theta\_\{\\mathcal\{G\}\}\(D\_\{1\}\)=1\-\(1\-\\delta\)^\{n\}\\geq 1\-e^\{\-n\\delta\}=1\-e^\{\-1/2\}\.LetΔ:=θ𝒢​\(D1\)−θ𝒢​\(D0\)\\Delta:=\\theta\_\{\\mathcal\{G\}\}\(D\_\{1\}\)\-\\theta\_\{\\mathcal\{G\}\}\(D\_\{0\}\)denote the gap between the two values, soΔ≥1−e−1/2\\Delta\\geq 1\-e^\{\-1/2\}\. The two sample laws, on the other hand, are close:D0D\_\{0\}andD1D\_\{1\}differ byδ\\deltain total variation, so

TV⁡\(D0n,D1n\)≤n​TV⁡\(D0,D1\)=n​δ=12\.\\operatorname\{TV\}\(D\_\{0\}^\{n\},D\_\{1\}^\{n\}\)\\leq n\\,\\operatorname\{TV\}\(D\_\{0\},D\_\{1\}\)=n\\delta=\\frac\{1\}\{2\}\.By the two\-point method of Le Cam\([Le Cam, 1973](https://arxiv.org/html/2610.41244#bib.bib50);[Yu, 1997](https://arxiv.org/html/2610.41244#bib.bib87)\), every estimatorp^\\hat\{p\}therefore satisfies

max⁡𝔼S∼Djnj∈\{0,1\}⁡\[\(p^​\(S\)−θ𝒢​\(Dj\)\)2\]≥Δ28​\(1−TV⁡\(D0n,D1n\)\)≥\(1−e−1/2\)216\.\\max\_\{j\\in\\\{0,1\\\}\}\\mathop\{\\mathbb\{E\}\}\_\{S\\sim D\_\{j\}^\{n\}\}\\Big\[\\big\(\\hat\{p\}\(S\)\-\\theta\_\{\\mathcal\{G\}\}\(D\_\{j\}\)\\big\)^\{2\}\\Big\]\\geq\\frac\{\\Delta^\{2\}\}\{8\}\\big\(1\-\\operatorname\{TV\}\(D\_\{0\}^\{n\},D\_\{1\}^\{n\}\)\\big\)\\geq\\frac\{\(1\-e^\{\-1/2\}\)^\{2\}\}\{16\}\.∎

## References

- Acharya et al\. \[2018\]Jayadev Acharya, Yelun Bao, Yuheng Kang, and Ziteng Sun\.Improved bounds for minimax risk of estimating missing mass\.In*IEEE International Symposium on Information Theory \(ISIT\)*, 2018\.
- Angelopoulos and Bates \[2021\]Anastasios N Angelopoulos and Stephen Bates\.A gentle introduction to conformal prediction and distribution\-free uncertainty quantification\.arXiv:[2107\.07511](https://arxiv.org/abs/2107.07511), 2021\.
- Angluin et al\. \[1997\]Dana Angluin, Mārtiņš Kriķis, Robert H\. Sloan, and György Turán\.Malicious omissions and errors in answers to membership queries\.*Machine Learning*, 1997\.
- Anthony and Bartlett \[2009\]Martin Anthony and Peter L\. Bartlett\.*Neural Network Learning: Theoretical Foundations*\.Cambridge University Press, 2009\.
- Awasthi et al\. \[2020\]Pranjal Awasthi, Satyen Kale, Stefani Karp, and Mehryar Mohri\.Pac\-bayes learning bounds for sample\-dependent priors\.In*NeurIPS*, 2020\.
- Balocchi et al\. \[2026\]Cecilia Balocchi, Stefano Favaro, and Zacharie Naulet\.Bayesian nonparametric inference for “species\-sampling” problems\.*Statistical Science*, 2026\.
- Bassily et al\. \[2016\]Raef Bassily, Kobbi Nissim, Adam D\. Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman\.Algorithmic stability for adaptive data analysis\.In*ACM Symposium on Theory of Computing \(STOC\)*, 2016\.
- Ben\-David et al\. \[1995\]Shai Ben\-David, Nicolò Cesa\-Bianchi, David Haussler, and Philip M\. Long\.Characterizations of learnability for classes of\{0,…,n\}\\\{0,\\ldots,n\\\}\-valued functions\.*Journal of Computer and System Sciences*, 1995\.
- Berend and Kontorovich \[2012\]Daniel Berend and Aryeh Kontorovich\.The missing mass problem\.*Statistics & Probability Letters*, 2012\.
- Berend and Kontorovich \[2013\]Daniel Berend and Aryeh Kontorovich\.On the concentration of the missing mass\.*Electronic Communications in Probability*, 2013\.
- Berk et al\. \[2013\]Richard Berk, Lawrence Brown, Andreas Buja, Kai Zhang, and Linda Zhao\.Valid post\-selection inference\.*The Annals of Statistics*, 2013\.
- Blumer et al\. \[1987\]Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K\. Warmuth\.Occam’s razor\.*Information Processing Letters*, 1987\.
- Board and Pitt \[1990\]Raymond Board and Leonard Pitt\.On the necessity of Occam algorithms\.In*ACM Symposium on Theory of Computing \(STOC\)*, 1990\.
- Boucheron et al\. \[2013\]Stéphane Boucheron, Gábor Lugosi, and Pascal Massart\.*Concentration Inequalities: A Nonasymptotic Theory of Independence*\.Oxford University Press, 2013\.
- Bousquet and Elisseeff \[2002\]Olivier Bousquet and André Elisseeff\.Stability and generalization\.*Journal of Machine Learning Research*, 2002\.
- Bunge et al\. \[2014\]John Bunge, Amy Willis, and Fiona Walsh\.Estimating the number of species in microbial diversity studies\.*Annual Review of Statistics and Its Application*, 2014\.
- Chao and Lee \[1992\]Anne Chao and Shen\-Ming Lee\.Estimating the number of classes via sample coverage\.*Journal of the American Statistical Association*, 1992\.
- Charikar et al\. \[2000\]Moses Charikar, Surajit Chaudhuri, Rajeev Motwani, and Vivek Narasayya\.Towards estimation error guarantees for distinct values\.In*ACM Symposium on Principles of Database Systems \(PODS\)*, 2000\.
- Clémençon et al\. \[2008\]Stéphan Clémençon, Gábor Lugosi, and Nicolas Vayatis\.Ranking and empirical minimization of U\-statistics\.*The Annals of Statistics*, 2008\.
- Devroye and Wagner \[1979\]Luc Devroye and Terry Wagner\.Distribution\-free performance bounds for potential function rules\.*IEEE Transactions on Information Theory*, 1979\.
- Dwork et al\. \[2014\]Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth\.Preserving statistical validity in adaptive data analysis\.arXiv:[1411\.2664](https://arxiv.org/abs/1411.2664), 2014\.Extended abstract in STOC 2015\.
- Dwork et al\. \[2015a\]Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth\.Generalization in adaptive data analysis and holdout reuse\.arXiv:[1506\.02629](https://arxiv.org/abs/1506.02629), 2015a\.Extended abstract in NeurIPS 2015\.
- Dwork et al\. \[2015b\]Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth\.The reusable holdout: Preserving validity in adaptive data analysis\.*Science*, 2015b\.
- Dziugaite and Roy \[2018\]Gintare Karolina Dziugaite and Daniel M Roy\.Data\-dependent pac\-bayes priors via differential privacy\.In*NeurIPS*, 2018\.
- Efron \[1983\]Bradley Efron\.Estimating the error rate of a prediction rule: improvement on cross\-validation\.*Journal of the American Statistical Association*, 1983\.
- Elder \[2016a\]Sam Elder\.Challenges in Bayesian adaptive data analysis\.arXiv:[1604\.02492](https://arxiv.org/abs/1604.02492), 2016a\.
- Elder \[2016b\]Sam Elder\.Bayesian adaptive data analysis guarantees from subgaussianity\.arXiv:[1611\.00065](https://arxiv.org/abs/1611.00065), 2016b\.
- Fano \[1966\]Robert Mario Fano\.*Transmission of Information: A statistical theory of communications*\.MIT Press, 1966\.
- Feldman \[2020\]Vitaly Feldman\.Does learning require memorization? A short tale about a long tail\.In*ACM Symposium on Theory of Computing \(STOC\)*, 2020\.
- Feldman and Steinke \[2018\]Vitaly Feldman and Thomas Steinke\.Calibrating noise to variance in adaptive data analysis\.In*Conference on Learning Theory \(COLT\)*, 2018\.
- Feldman and Vondrak \[2018\]Vitaly Feldman and Jan Vondrak\.Generalization bounds for uniformly stable algorithms\.In*NeurIPS*, 2018\.
- Feldman and Vondrak \[2019\]Vitaly Feldman and Jan Vondrak\.High probability generalization bounds for uniformly stable algorithms with nearly optimal rate\.In*Conference on Learning Theory \(COLT\)*, 2019\.
- Feldman and Zhang \[2020\]Vitaly Feldman and Chiyuan Zhang\.What neural networks memorize and why: Discovering the long tail via influence estimation\.In*NeurIPS*, 2020\.
- Fithian et al\. \[2014\]William Fithian, Dennis Sun, and Jonathan Taylor\.Optimal inference after model selection\.arXiv:[1410\.2597](https://arxiv.org/abs/1410.2597), 2014\.
- Foster et al\. \[2019\]Dylan J Foster, Spencer Greenberg, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan\.Hypothesis set stability and generalization\.In*NeurIPS*, 2019\.
- Gastpar et al\. \[2024a\]Michael Gastpar, Ido Nachum, Jonathan Shafer, and Thomas Weinberger\.Fantastic generalization measures are nowhere to be found\.In*International Conference on Learning Representations \(ICLR\)*, 2024a\.
- Gastpar et al\. \[2024b\]Michael Gastpar, Ido Nachum, Jonathan Shafer, and Thomas Weinberger\.Which algorithms have tight generalization bounds?arXiv:[2410\.01969](https://arxiv.org/abs/2410.01969), 2024b\.
- Good \[1953\]Irving J Good\.The population frequencies of species and the estimation of population parameters\.*Biometrika*, 1953\.
- Haas et al\. \[1995\]Peter J Haas, Jeffrey F Naughton, S Seshadri, and Lynne Stokes\.Sampling\-based estimation of the number of distinct values of an attribute\.In*International Conference on Very Large Data Bases \(VLDB\)*, 1995\.
- Hardt and Ullman \[2014\]Moritz Hardt and Jonathan Ullman\.Preventing false discovery in interactive data analysis is hard\.In*IEEE Symposium on Foundations of Computer Science \(FOCS\)*, 2014\.
- Hartvigsen et al\. \[2023\]Tom Hartvigsen, Swami Sankaranarayanan, Hamid Palangi, Yoon Kim, and Marzyeh Ghassemi\.Aging with GRACE: Lifelong model editing with discrete key\-value adaptors\.In*NeurIPS*, 2023\.
- Haussler \[1995\]David Haussler\.Sphere packing numbers for subsets of the booleannn\-cube with bounded Vapnik–Chervonenkis dimension\.*Journal of Combinatorial Theory, Series A*, 1995\.
- Hellström et al\. \[2025\]Fredrik Hellström, Giuseppe Durisi, Benjamin Guedj, and Maxim Raginsky\.Generalization bounds: Perspectives from information theory and PAC\-Bayes\.*Foundations and Trends in Machine Learning*, 2025\.
- Jiang et al\. \[2020\]Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio\.Fantastic generalization measures and where to find them\.In*International Conference on Learning Representations \(ICLR\)*, 2020\.
- Kalai and Vempala \[2024\]Adam Tauman Kalai and Santosh S Vempala\.Calibrated language models must hallucinate\.In*ACM Symposium on Theory of Computing \(STOC\)*, 2024\.
- Kale et al\. \[2011\]Satyen Kale, Ravi Kumar, and Sergei Vassilvitskii\.Cross\-validation and mean\-square stability\.In*Innovations in Computer Science \(ICS\)*, 2011\.
- Kauschke and Fürnkranz \[2018\]Sebastian Kauschke and Johannes Fürnkranz\.Batchwise patching of classifiers\.In*AAAI Conference on Artificial Intelligence \(AAAI\)*, 2018\.
- Kearns and Ron \[1999\]Michael Kearns and Dana Ron\.Algorithmic stability and sanity\-check bounds for leave\-one\-out cross\-validation\.*Neural Computation*, 1999\.
- Kumar et al\. \[2013\]Ravi Kumar, Daniel Lokshtanov, Sergei Vassilvitskii, and Andrea Vattani\.Near\-optimal bounds for cross\-validation via loss stability\.In*ICML*, 2013\.
- Le Cam \[1973\]Lucien Le Cam\.Convergence of estimates under dimensionality restrictions\.*The Annals of Statistics*, 1973\.
- Lee et al\. \[2016\]Jason D Lee, Dennis L Sun, Yuekai Sun, and Jonathan E Taylor\.Exact post\-selection inference, with application to the lasso\.*The Annals of Statistics*, 2016\.
- Lei et al\. \[2013\]Jing Lei, James Robins, and Larry Wasserman\.Distribution\-free prediction sets\.*Journal of the American Statistical Association*, 2013\.
- Madaan et al\. \[2022\]Aman Madaan, Niket Tandon, Peter Clark, and Yiming Yang\.Memory\-assisted prompt editing to improve GPT\-3 after deployment\.In*Conference on Empirical Methods in Natural Language Processing \(EMNLP\)*, 2022\.
- Manoj and Srebro \[2023\]Naren Sarayu Manoj and Nathan Srebro\.Shortest program interpolation learning\.In*Conference on Learning Theory \(COLT\)*, 2023\.
- Maurer \[2022\]Andreas Maurer\.Concentration of the missing mass in metric spaces\.arXiv:[2206\.02012](https://arxiv.org/abs/2206.02012), 2022\.
- McAllester and Ortiz \[2003\]David McAllester and Luis Ortiz\.Concentration inequalities for the missing mass and for histogram rule error\.*Journal of Machine Learning Research*, 2003\.
- McAllester and Schapire \[2000\]David A McAllester and Robert E Schapire\.On the convergence rate of Good\-Turing estimators\.In*Conference on Learning Theory \(COLT\)*, 2000\.
- Mitchell et al\. \[2022\]Eric Mitchell, Charles Lin, Antoine Bosselut, Christopher D\. Manning, and Chelsea Finn\.Memory\-based model editing at scale\.In*ICML*, 2022\.
- Mohri et al\. \[2012\]Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar\.*Foundations of Machine Learning*\.The MIT Press, 2012\.
- Natarajan \[1989\]Balas K\. Natarajan\.On learning sets and functions\.*Machine Learning*, 1989\.
- Nissim et al\. \[2023\]Kobbi Nissim, Uri Stemmer, and Eliad Tsfadia\.Adaptive data analysis in a balanced adversarial model\.In*NeurIPS*, 2023\.
- Noorani et al\. \[2025\]Sima Noorani, Shayan Kiyani, George Pappas, and Hamed Hassani\.Conformal prediction beyond the seen: A missing mass perspective for uncertainty quantification in generative models\.arXiv:[2506\.05497](https://arxiv.org/abs/2506.05497), 2025\.
- Orlitsky et al\. \[2016\]Alon Orlitsky, Ananda Theertha Suresh, and Yihong Wu\.Optimal prediction of the number of unseen species\.*Proceedings of the National Academy of Sciences*, 2016\.
- Paninski \[2003\]Liam Paninski\.Estimation of entropy and mutual information\.*Neural Computation*, 2003\.
- Rajaraman et al\. \[2017\]Nikhilesh Rajaraman, Andrew Thangaraj, and Ananda Theertha Suresh\.Minimax risk for missing mass estimation\.In*IEEE International Symposium on Information Theory \(ISIT\)*, 2017\.
- Rivasplata et al\. \[2018\]Omar Rivasplata, Emilio Parrado\-Hernández, John S Shawe\-Taylor, Shiliang Sun, and Csaba Szepesvári\.Pac\-bayes bounds for stable algorithms with instance\-dependent priors\.In*NeurIPS*, 2018\.
- Rogers et al\. \[2016\]Ryan Rogers, Aaron Roth, Adam Smith, and Om Thakkar\.Max\-information, differential privacy, and post\-selection hypothesis testing\.In*IEEE Symposium on Foundations of Computer Science \(FOCS\)*, 2016\.
- Rogers and Wagner \[1978\]William H Rogers and Terry J Wagner\.A finite sample distribution\-free performance bound for local discrimination rules\.*The Annals of Statistics*, 1978\.
- Russo and Zou \[2016\]Daniel Russo and James Zou\.Controlling bias in adaptive data analysis using information theory\.In*International Conference on Artificial Intelligence and Statistics \(AISTATS\)*, 2016\.
- Shalev\-Shwartz and Ben\-David \[2014\]Shai Shalev\-Shwartz and Shai Ben\-David\.*Understanding machine learning: From theory to algorithms*\.Cambridge University Press, 2014\.
- Shalev\-Shwartz et al\. \[2010\]Shai Shalev\-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan\.Learnability, stability and uniform convergence\.*Journal of Machine Learning Research*, 2010\.
- Steinke and Ullman \[2015\]Thomas Steinke and Jonathan Ullman\.Interactive fingerprinting codes and the hardness of preventing false discovery\.In*Conference on Learning Theory \(COLT\)*, 2015\.
- Steinke and Zakynthinou \[2020\]Thomas Steinke and Lydia Zakynthinou\.Reasoning about generalization via conditional mutual information\.In*Conference on Learning Theory \(COLT\)*, 2020\.
- Stone \[1974\]Mervyn Stone\.Cross\-validatory choice and assessment of statistical predictions\.*Journal of the Royal Statistical Society: Series B \(Methodological\)*, 1974\.
- Talagrand \[1994\]Michel Talagrand\.Sharper bounds for Gaussian and empirical processes\.*The Annals of Probability*, 1994\.
- Tandon et al\. \[2022\]Niket Tandon, Aman Madaan, Peter Clark, and Yiming Yang\.Learning to repair: Repairing model output errors after deployment using a dynamic memory of feedback\.In*Findings of the Association for Computational Linguistics: NAACL*, 2022\.
- Taylor and Tibshirani \[2015\]Jonathan Taylor and Robert J Tibshirani\.Statistical learning and selective inference\.*Proceedings of the National Academy of Sciences*, 2015\.
- Valiant and Valiant \[2011\]Gregory Valiant and Paul Valiant\.Estimating the unseen: an n/log \(n\)\-sample estimator for entropy and support size, shown optimal via new clts\.In*ACM Symposium on Theory of Computing \(STOC\)*, 2011\.
- Valiant and Valiant \[2017\]Gregory Valiant and Paul Valiant\.Estimating the unseen: improved estimators for entropy and other properties\.*Journal of the ACM*, 2017\.
- Vapnik and Chervonenkis \[1971\]VN Vapnik and A Ya Chervonenkis\.On the uniform convergence of relative frequencies of events to their probabilities\.*Theory of Probability and Its Applications*, 1971\.
- Vershynin \[2018\]Roman Vershynin\.*High\-dimensional probability: An introduction with applications in data science*\.Cambridge University Press, 2018\.
- Vovk et al\. \[2005\]Vladimir Vovk, Alexander Gammerman, and Glenn Shafer\.*Algorithmic Learning in a Random World*\.Springer, 2005\.
- Wang et al\. \[2024\]Peng Wang, Zexi Li, Ningyu Zhang, Ziwen Xu, Yunzhi Yao, Yong Jiang, Pengjun Xie, Fei Huang, and Huajun Chen\.WISE: Rethinking the knowledge memory for lifelong model editing of large language models\.In*NeurIPS*, 2024\.
- Xu and Raginsky \[2017\]Aolin Xu and Maxim Raginsky\.Information\-theoretic analysis of generalization capability of learning algorithms\.In*NeurIPS*, 2017\.
- Yang et al\. \[2023\]Zitong Yang, Michal Lukasik, Vaishnavh Nagarajan, Zonglin Li, Ankit Singh Rawat, Manzil Zaheer, Aditya Krishna Menon, and Sanjiv Kumar\.ResMem: Learn what you can and memorize the rest\.In*NeurIPS*, 2023\.
- Yao et al\. \[2024\]Zihan Yao, Yu He, Tianyu Qi, and Ming Li\.Scalable model editing via customized expert networks\.In*Conference on Language Modeling \(COLM\)*, 2024\.
- Yu \[1997\]Bin Yu\.Assouad, Fano, and Le Cam\.In*Festschrift for Lucien Le Cam: research papers in probability and statistics*\. Springer, 1997\.
- Zhang et al\. \[2017\]Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals\.Understanding deep learning requires rethinking generalization\.In*International Conference on Learning Representations \(ICLR\)*, 2017\.