度量空间回归与分类的准确性及稳定性确定性界限

# Deterministic Bounds on Accuracy and Stability of Metric-Space Regression and Classification
Source: [https://arxiv.org/html/2610.22564](https://arxiv.org/html/2610.22564)
Nina M\. Gottschling††thanks:Computing and Computational Sciences, Oak Ridge National Laboratory, Oak Ridge, Tennessee\.Jakob Gawlikowski††thanks:German Aerospace Center \(DLR\), Remote Sensing Technology Institute, Wessling, Germany\.Michele Caprio††thanks:Department of Computer Science, University of Warwick, Coventry, United Kingdom\.

###### Abstract

Data\-driven approaches often face ambiguity in datasets due to sensor or target noise, insufficient information, and noise in the input data\. While best\-fit machine learning methods can accommodate such noise through uncertainty estimates, they are prone to overfitting and it is challenging to quantify ambiguity of the relation between inputs and targets\. We introduce a geometric framework that quantifies this ambiguity through the average kernel size, computed with data\-dependent, i\.e\. model\-independent, feasible sets derived from worst\-case input and target noise\. The framework provides computable, deterministic, non\-asymptotic bounds on the best achievable empirical error and accuracy for a finite, constructed dataset, independent of the predictive model class, and applies to regression and classification with pseudo\-metric input spaces and metric target spaces\. The ambiguity of the input\-target relation implies three consequences: an empirical error floor, an accuracy–stability trade\-off, and, under standard probabilistic assumptions, a strictly positive distribution–training error gap when training below the accuracy bounds\. Under standard Borel assumptions for Euclidean norms, the distributional analogue of the average kernel size is related to Bayes risk as it reduces to the optimal distribution root\-mean\-squared error times2\\sqrt\{2\}\. Experiments spanning tabular regression, image regression and classification datasets yield nontrivial bounds on the best achievable empirical error and accuracy on a constructed dataset, alongside descriptive comparisons with model performance on the original datasets\. The bounds provide a computable, model\-independent reference scale on the constructed dataset and comparisons with model performance on the original dataset are descriptive\.

##### Keywords

accuracy bounds, data centric, aleatoric uncertainty, regression, classification, deep learning

## 1Introduction

![Refer to caption](https://arxiv.org/html/2610.22564v1/feassetex.drawio.png)Figure 1:Accuracy bounds: from data ambiguity to a reference scale on the constructed dataset\.For an inputxx, the thresholds define a feasible setFxF\_\{x\}\(Definition[1\.1](https://arxiv.org/html/2610.22564#S1.Thmtheorem1)\) of target values lying within the worst\-case noise distance\. The target values within this set may differ\. The average kernel size,KK, provides a reference scale for the best achievable empirical error on a finite constructed dataset; the term “average kernel size” is motivated by its namesake in inverse problems[Gottschling et al\. \(2026\)](https://arxiv.org/html/2610.22564#bib.bib81), but here we define it directly from the constructed dataset without requiring a forward model\. In this schematic, the optimal error on the constructed dataset lies betweenK/2K/2andKK\. Model errors reported on the original dataset are shown for descriptive comparison\. Both the finite feasible sets and the value ofKKdepend on the chosen pseudo\-metric, metric, and thresholds\. For models evaluated only on the original dataset, such comparisons are heuristic unless additional assumptions, such as those in Proposition[2\.13](https://arxiv.org/html/2610.22564#S2.Thmtheorem13), are invoked\.We express regression and classification problems using the following general framework:

predict​y∈ℳ1⊂𝒴​given​x∈ℳ2⊂𝒳,\\displaystyle\\text\{predict \}y\\in\\mathcal\{M\}\_\{1\}\\subset\\mathcal\{Y\}\\text\{ given \}x\\in\\mathcal\{M\}\_\{2\}\\subset\\mathcal\{X\},\(1\.1\)where the available input\-target pairs\(y,x\)∈ℳ1×ℳ2\(y,x\)\\in\\mathcal\{M\}\_\{1\}\\times\\mathcal\{M\}\_\{2\}are given by a finite dataset of tuples𝒟M=\{\(ym,xm\)\}m=1M⊂ℳ1×ℳ2\\mathcal\{D\}\_\{M\}=\\\{\(y\_\{m\},x\_\{m\}\)\\\}\_\{m=1\}^\{M\}\\subset\\mathcal\{M\}\_\{1\}\\times\\mathcal\{M\}\_\{2\}for someM∈ℕM\\in\\mathbb\{N\}\. Here,yyrepresents the data of interest, whilexxdenotes the available data from which we wish to predictyy\. The setsℳ1⊂𝒴\\mathcal\{M\}\_\{1\}\\subset\\mathcal\{Y\}andℳ2⊂𝒳\\mathcal\{M\}\_\{2\}\\subset\\mathcal\{X\}describe the sets of target and input signals of interest\. The dataset𝒟M\\mathcal\{D\}\_\{M\}is deliberately defined in this general way to encompass many known cases and settings\. For example, the ambient input set𝒳\\mathcal\{X\}may consist of tensors for image\-based regression and classification problems or of a structure supporting tabular data, and the setℳ2⊂𝒳\\mathcal\{M\}\_\{2\}\\subset\\mathcal\{X\}may consist of all admissible images\. For classification, the ambient target set𝒴\\mathcal\{Y\}consists of one\-hot encoded vectors or more generally𝒴=\{y∈\[0,1\]C:∑c=1Cyc=1\}\\mathcal\{Y\}=\\\{y\\in\[0,1\]^\{C\}:\\sum\_\{c=1\}^\{C\}y\_\{c\}=1\\\}forC∈ℕC\\in\\mathbb\{N\}classes\.

In applications, an input may correspond to multiple admissible targets, even if the observed dataset𝒟M\\mathcal\{D\}\_\{M\}contains a unique target for that input\. To characterize such ambiguity, we introduce a multiset of admissible input\-target pairsℛ\\mathcal\{R\}satisfying𝒟M⊂ℛ\\mathcal\{D\}\_\{M\}\\subset\\mathcal\{R\}\. For a fixed inputxx, we define its feasible set in the following Definition[1\.1](https://arxiv.org/html/2610.22564#S1.Thmtheorem1)\. If, for a fixed inputxx, the targets are ambiguous, then the feasible set can be a non\-singleton\. As the disjoint union preserves multiplicities, it can be a multiset, which is an unordered collection of elements where each element can appear more than once\.

###### Definition 1\.1\(Feasible sets\)\.

Letℛ\\mathcal\{R\}be an underlying admissible input\-target multiset\. For an inputxxobtained from a sample\(y,x\)∈ℛ\(y,x\)\\in\\mathcal\{R\}let the*feasible set*FxF\_\{x\}be defined as

Fx:=⋃⋅\(y,x\)∈ℛ⁡\{y\}⊂ℳ1\.\\displaystyle F\_\{x\}:=\\mathop\{\\vphantom\{\\bigcup\}\\mathchoice\{\\text\{\\vtop\{\\halign\{\#\\cr$\\displaystyle\\bigcup$\\cr$\\displaystyle\\cdot$\\cr\}\}\}\}\{\\text\{\\vtop\{\\halign\{\#\\cr$\\textstyle\\bigcup$\\cr$\\textstyle\\cdot$\\cr\}\}\}\}\{\\text\{\\vtop\{\\halign\{\#\\cr$\\scriptstyle\\bigcup$\\cr$\\scriptstyle\\cdot$\\cr\}\}\}\}\{\\text\{\\vtop\{\\halign\{\#\\cr$\\scriptscriptstyle\\bigcup$\\cr$\\scriptscriptstyle\\cdot$\\cr\}\}\}\}\}\\displaylimits\_\{\(y,x\)\\in\\mathcal\{R\}\}\\\{y\\\}\\subset\\mathcal\{M\}\_\{1\}\.As⋅Γ∪\\mathbin\{\\mathaccent 0\{\\cdot\}\\cup\}is the disjoint union, the*feasible set*FxF\_\{x\}is a multiset\.

A non\-singleton feasible set indicates that multiple targets are admissibly associated with the same input\. Ify,y′∈Fxy,y^\{\\prime\}\\in F\_\{x\}withy≠y′y\\neq y^\{\\prime\}, then\(y,x\),\(y′,x\)∈ℛ\(y,x\),\(y^\{\\prime\},x\)\\in\\mathcal\{R\}although these pairs need not both be contained in the observed finite dataset𝒟M\\mathcal\{D\}\_\{M\}\. Such ambiguity may arise, for example, from noisy observations, where it is generally impossible for a given sample to determine whether the input, target, or both have been corrupted, or to identify the underlying noise mechanism\. Consequently, for an individual input\-target sample we generally cannot determine whether the sample has been corrupted by noise\. To account for this ambiguity, we consider an admissible enlargement𝒟M′\\mathcal\{D\}\_\{M^\{\\prime\}\}of the observed dataset and impose the following assumption\.

###### Assumption 1\.2\(Existence of an admissible enlargement\)\.

We assume that there exists a multiset of admissible input\-target pairsℛ\\mathcal\{R\}with𝒟M⊂ℛ\\mathcal\{D\}\_\{M\}\\subset\\mathcal\{R\}\. Relative to this admissible multiset, we assume that there exists a multiset

𝒟M′=\{\(ym,xm\)\}m=1M′⊂ℛ\\displaystyle\\mathcal\{D\}\_\{M^\{\\prime\}\}=\\\{\(y\_\{m\},x\_\{m\}\)\\\}\_\{m=1\}^\{M^\{\\prime\}\}\\subset\\mathcal\{R\}\(1\.10\)such that𝒟M⊂𝒟M′\\mathcal\{D\}\_\{M\}\\subset\\mathcal\{D\}\_\{M^\{\\prime\}\}and, for somex∈ℳ2x\\in\\mathcal\{M\}\_\{2\}, there exist distincty,y′∈ℳ1y,y^\{\\prime\}\\in\\mathcal\{M\}\_\{1\}withy,y′∈Fxy,y^\{\\prime\}\\in F\_\{x\}\.

Here,𝒟M′\\mathcal\{D\}\_\{M^\{\\prime\}\}is not meant to be uniquely determined or algorithmically recovered from𝒟M\\mathcal\{D\}\_\{M\}; it is an admissible enlargement of the observed sample used to represent latent ambiguity in the input\-target relation\. The condition that someFxF\_\{x\}contains two distinct valuesy≠y′y\\neq y^\{\\prime\}excludes trivial cases and ensures a genuinely ambiguous regime\.

The goal of solving regression and classification problems of the form \([1\.1](https://arxiv.org/html/2610.22564#S1.E1)\) is to produce an approximation or set of approximationsy^⊂𝒴\\hat\{y\}\\subset\\mathcal\{Y\}to the true targetyyfrom an inputxx\. Any algorithm or method that produces a potentiallyset\-valued regressor or classifiermapping data pointsxxinℳ2\\mathcal\{M\}\_\{2\}to approximations of the true targetyyis denoted by

ϕ:ℳ2⇉𝒴,\\displaystyle\\phi:\\mathcal\{M\}\_\{2\}\\rightrightarrows\\mathcal\{Y\},withϕ⁡\(x\)=y^⊂𝒴\\phi\(x\)=\\hat\{y\}\\subset\\mathcal\{Y\}\. Examples include optimization\-based methods, such as random forests,[Segal \(2004\)](https://arxiv.org/html/2610.22564#bib.bib24);[Shwartz\-Ziv and Armon \(2022\)](https://arxiv.org/html/2610.22564#bib.bib25);[McElfresh et al\. \(2023\)](https://arxiv.org/html/2610.22564#bib.bib26)which in some cases outperform deep neural networks on tabular data, and supervised or unsupervised deep learning methods[Lathuilière et al\. \(2019\)](https://arxiv.org/html/2610.22564#bib.bib28), such as transformer\-based architectures[Han et al\. \(2022\)](https://arxiv.org/html/2610.22564#bib.bib27)\.

Theempirical error of a \(set\-valued\) regressorϕ:ℳ2⇉𝒴\\phi:\\mathcal\{M\}\_\{2\}\\rightrightarrows\\mathcal\{Y\}for approximately solving \([1\.1](https://arxiv.org/html/2610.22564#S1.E1)\) is often quantified by the empirical root\-ppmean of the residuals between the predictions and targets over theM∈ℕM\\in\\mathbb\{N\}samples𝒟M=\{\(ym,xm\)\}m=1M\\mathcal\{D\}\_\{M\}=\\\{\(y\_\{m\},x\_\{m\}\)\\\}\_\{m=1\}^\{M\}, and can be denoted by

ℒ⁡\(𝒟M,ϕ,p\)=\(1M​∑m=1Md𝒴H​\(\{ym\},ϕ⁡\(xm\)\)p\)1/p,\\displaystyle\\mathcal\{L\}\(\\mathcal\{D\}\_\{M\},\\phi,p\)=\\left\(\\frac\{1\}\{M\}\\sum\_\{m=1\}^\{M\}d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{m\}\\\},\\phi\(x\_\{m\}\)\)^\{p\}\\right\)^\{1/p\},\(1\.11\)for somep∈\[1,∞\)p\\in\[1,\\infty\)and a metricd𝒴d\_\{\\mathcal\{Y\}\}onℳ1\\mathcal\{M\}\_\{1\}, where the Hausdorff distance is defined byd𝒴H​\(\{y\},ϕ⁡\(x\)\):=supz∈ϕ⁡\(x\)d𝒴​\(y,z\)d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\\\},\\phi\(x\)\):=\\sup\_\{z\\in\\phi\(x\)\}d\_\{\\mathcal\{Y\}\}\(y,z\)\. Forp=1p=1, this is the mean absolute error \(MAE\), and forp=2p=2, it corresponds to the root\-mean\-squared error \(RMSE\); its square is the empirical risk or also mean squared loss\. The MAE and RMSE are commonly used to evaluate the error of regressors, see, e\.g\.,\([Bickel and Doksum, 2015](https://arxiv.org/html/2610.22564#bib.bib20), Chapter 1\)and\([Murphy, 2022](https://arxiv.org/html/2610.22564#bib.bib21), Chapter 1\)\.

For classification, theempirical accuracy of a \(set\-valued\) classifierϕ:ℳ2⇉𝒴\\phi:\\mathcal\{M\}\_\{2\}\\rightrightarrows\\mathcal\{Y\}can be measured by the Hausdorff distance induced by the normalized Hamming metricdHd\_\{H\}, so that

Acc⁡\(𝒟M,ϕ\)=1−1M​∑m=1MdHH​\(\{ym\},ϕ⁡\(xm\)\)\.\\displaystyle\\operatorname\{Acc\}\(\\mathcal\{D\}\_\{M\},\\phi\)=1\-\\frac\{1\}\{M\}\\sum\_\{m=1\}^\{M\}d\_\{H\}^\{H\}\\\!\\bigl\(\\\{y\_\{m\}\\\},\\phi\(x\_\{m\}\)\\bigr\)\.\(1\.12\)The normalization of the Hamming metric is introduced in detail in Section[2\.1](https://arxiv.org/html/2610.22564#S2.SS1)\.

A common objective in regression problems across various applications is to find a regressor that minimizes the loss \([1\.11](https://arxiv.org/html/2610.22564#S1.E11)\) in a given class of functions, such as finding the optimal architecture and parameter values for deep neural networks or, for example, in least squares regression[Arlot and Massart \(2009\)](https://arxiv.org/html/2610.22564#bib.bib29)\. In classification problems, this changes to maximizing the accuracy in \([1\.12](https://arxiv.org/html/2610.22564#S1.E12)\)\. This is commonly referred to as*empirical risk minimization*, where the”\[…\] true goal is to minimize the expected loss on future data that we have not yet seen\. That is, we want to generalize, rather than just do well on the training set\.”,\([Murphy, 2022](https://arxiv.org/html/2610.22564#bib.bib21), Chapter 1\)\. Under additional assumptions, the hope is that this procedure solves regression and classification problems of the form \([1\.1](https://arxiv.org/html/2610.22564#S1.E1)\) and that the resulting regressors and classifiers produce, for any inputxx, an approximation or set of approximationsy^\\hat\{y\}to the true targetyy\.

### 1\.1Challenges

Before summarizing the related work, we highlight three challenges that motivate the framework developed here\.

\(i\) Non\-uniqueness of the target given the observed input\.In many regression and classification problems, the available input does not determine a unique target, satisfying Assumption[1\.2](https://arxiv.org/html/2610.22564#S1.Thmtheorem2)\. This may occur because of measurement noise, omitted variables, or annotation uncertainty and is commonly referred to as*aleatoric uncertainty*in the field of machine learning, see[Murphy \(2022\)](https://arxiv.org/html/2610.22564#bib.bib21);[Der Kiureghian and Ditlevsen \(2009\)](https://arxiv.org/html/2610.22564#bib.bib2);[Gawlikowski et al\. \(2023\)](https://arxiv.org/html/2610.22564#bib.bib1)\. In such settings, even an ideal regressor or classifier cannot recover a single deterministic response from the observed input alone\. Consequently, part of the prediction error is intrinsic to the data\-generating relation and cannot be removed by choosing a more expressive model class or a better optimization method\.

\(ii\) The need for computable, model\-independent bounds on finite datasets\.In computationally demanding settings, it is useful to estimate achievable empirical error and accuracy before extensive model selection and training\. This motivates finite\-sample bounds that are computable from the dataset itself and independent of a specific model class\. To the best of our knowledge, related work does not provide such bounds in this form; see Table[1](https://arxiv.org/html/2610.22564#S1.T1)and Section[1\.3](https://arxiv.org/html/2610.22564#S1.SS3)\.

\(iii\) Expressive regressors and classifiers do not evade intrinsic accuracy limits\.A third challenge is that expressive regressors and classifiers can fit the training dataset without resolving ambiguity inherent in the input\-target relation\. For example, for a finite dataset𝒟M\\mathcal\{D\}\_\{M\}with no ambiguous targets that have the same input, interpolation by a large enough model is possible, but may come at the cost of poor generalization or overfitting,\([Murphy, 2022](https://arxiv.org/html/2610.22564#bib.bib21), Chapter 1\)and[Zhang et al\. \(2016\)](https://arxiv.org/html/2610.22564#bib.bib37);[Zhang et al\. \(2021\)](https://arxiv.org/html/2610.22564#bib.bib38), and potentially a large Lipschitz constant\. Hence, approximation power alone does not determine the best achievable test error and accuracy\.

Table 1:The average kernel size and its distributional analogue play different roles and are distinguished explicitly\.
### 1\.2Contributions

We develop a framework for computing deterministic bounds on achievable regression and classification accuracy from finite datasets\. Here, we introduce a metric\-space framework that encodes input\-target ambiguity through data\-dependent feasible sets, with pseudo\-metrics on inputs and metrics on targets\. The main contributions are as follows\.

We establish an*accuracy\-stability trade\-off*, Proposition[2\.5](https://arxiv.org/html/2610.22564#S2.Thmtheorem5)\. We show that a too small pointwise error on separated, ambiguous targets at nearby, but distinct, inputs forces a large \(local\) Lipschitz constant and that ambiguous targets produce a pointwise error floor\.

We derive computable, deterministic, non\-asymptotic*lower and upper bounds on the best achievable empirical error*and accuracy on datasets defined in Assumption[1\.2](https://arxiv.org/html/2610.22564#S1.Thmtheorem2)\. The lower bounds in Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)and Corollary[2\.11](https://arxiv.org/html/2610.22564#S2.Thmtheorem11)hold for all regressors and classifiers, while for distinct inputs the upper bound holds and the optimum is attained by an upper hemicontinuous compact\-valued regressor or classifier\.

Using a graph\-based argument, we show that for Lipschitz continuous regressors and classifiers, the*difference between empirical error, respectively accuracy, on the constructed and original datasets is bounded*in terms of the Lipschitz constant and input\-target ambiguity for finite feasible sets of equal cardinality \(Proposition[2\.13](https://arxiv.org/html/2610.22564#S2.Thmtheorem13)\)\.

Under standard Borel assumptions, we show that regressors and classifiers*achieving errors below the conditional ambiguity scale, necessarily incur a strictly positive generalization gap*\(Proposition[2\.18](https://arxiv.org/html/2610.22564#S2.Thmtheorem18)\)\. Under Euclidean squared loss, the Bayes squared risk equals one half the squared distributional analogue average kernel size\.

Under an ideal two\-stage design with inputs sampled from the input law and conditionally independent repeated targets, we prove a*finite\-sample concentration bound for the empirical average kernel size estimator*\(Proposition[2\.19](https://arxiv.org/html/2610.22564#S2.Thmtheorem19)\)\. This differs from the average kernel size computed by Algorithm[1](https://arxiv.org/html/2610.22564#alg1), which is a data\-dependent geometric quantity unless additional sampling assumptions are imposed\.

We*provide open\-source code for reproducibility and experiments illustrating the computation of the deterministic bounds across regression and classification tasks*, their dependence on the chosen pseudo\-metric, thresholds, and feasible set sizes, and their comparison with benchmark models and locally trained models\. The experiments examine whether the bounds are nontrivial, how selected model performances compare numerically with the resulting intervals, and how sensitive the intervals are to the finite feasible sets \(Section[3](https://arxiv.org/html/2610.22564#S3)\)\. Figures[3](https://arxiv.org/html/2610.22564#S1.F3)and[3](https://arxiv.org/html/2610.22564#S1.F3)provide descriptive visual comparisons with selected model errors and accuracies; detailed qualifications are deferred to Section[3](https://arxiv.org/html/2610.22564#S3)\.

10−210^\{\-2\}10−110^\{\-1\}10010^\{0\}10110^\{1\}10210^\{2\}Critical Heat FluxConcrete StrengthEnergy EfficiencyY2Y\_\{2\}Energy EfficiencyY1Y\_\{1\}Tropical CycloneSyntheticRMSE \[units of target\]train intervaltest intervalϕ1​s​t\\phi\_\{1st\}ϕ2​n​d\\phi\_\{2nd\}ϕ3​r​d\\phi\_\{3rd\}Figure 2:Deterministic regression accuracy intervals and regressor errors\.The theoretical interval from Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)is\[1/2​Kersize⁡\(𝒟M′,p\)K,Kersize⁡\(𝒟M′,p\)K\]\\left\[1/2\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\},\\,\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\}\\right\]\. All scores are RMSE values in the units of the target variables of three regressors on the test datasets𝒟Mtest\\mathcal\{D\}\_\{M\_\{\\mathrm\{test\}\}\}\. Theoretical intervals apply to the admissible enlarged dataset𝒟M′\\mathcal\{D\}\_\{M^\{\\prime\}\}constructed from the observed dataset𝒟M\\mathcal\{D\}\_\{M\}; plotted RMSE values are on𝒟Mtest\\mathcal\{D\}\_\{M\_\{\\mathrm\{test\}\}\}\. Numerical values and details are provided in Table[3](https://arxiv.org/html/2610.22564#S3.T3)in Section[3](https://arxiv.org/html/2610.22564#S3)\.767678788080828284848686888890909292949496969898100100MNISTEUROSATRESISC45∗CIFAR\-10Classification Accuracy \[%\]train intervaltest intervalϕ1​s​t\\phi\_\{1st\}ϕ2​n​d\\phi\_\{2nd\}ϕ3​r​d\\phi\_\{3rd\}Figure 3:Deterministic classification accuracy intervals and classifier accuracies\.Theoretical intervals from Corollary[2\.11](https://arxiv.org/html/2610.22564#S2.Thmtheorem11)are reported as percentages; explicitly, the interval is100×\[1−Kersize⁡\(𝒟M′,1\)K,1−1/2​Kersize⁡\(𝒟M′,1\)K\]\.100\\times\\left\[1\-\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},1\)\_\{K\},\\,1\-1/2\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},1\)\_\{K\}\\right\]\.Accuracies are reported on the\[0,100\]\[0,100\]scale and from classifiers on the test datasets𝒟Mtest\\mathcal\{D\}\_\{M\_\{\\mathrm\{test\}\}\}\. Intervals are for𝒟M′\\mathcal\{D\}\_\{M^\{\\prime\}\}; plotted benchmark accuracies are on𝒟M\\mathcal\{D\}\_\{M\}and may use different splits/protocols, so they are descriptive only\. For CIFAR\-10 the order of classifier names is changed relative to the numerical values provided in Table[5](https://arxiv.org/html/2610.22564#S3.T5)in Section[3](https://arxiv.org/html/2610.22564#S3)\.
Scope of the bounds\.The proposed bounds are not intrinsic properties of the dataset alone, but depend on the chosen pseudo\-metric on the input space, the evaluation metric on the target space, and the finite\-sample feasible set construction based on the thresholds from input and target noise\. In the experimental section, whenever prior information on input \(and/or target\) measurement uncertainty was available, the thresholdsτ𝒳\\tau\_\{\\mathcal\{X\}\}andτ𝒴\\tau\_\{\\mathcal\{Y\}\}were set to conservative worst\-case values implied by the corresponding noise models\. In this setting the framework isolates a model\-independent component of prediction difficulty, but does not directly account for optimization difficulty, finite model capacity, or model misspecification\.

### 1\.3Relation to previous work

The proposed framework to tackle the three challenges in Section[1\.1](https://arxiv.org/html/2610.22564#S1.SS1)is related to several existing lines of work, including optimal recovery, approximation theory, statistical learning theory, and modern deep learning\.

Optimal recovery and worst\-case approximation\.Classical approximation\-theoretic frameworks quantify best achievable worst\-case error in settings related to \([1\.1](https://arxiv.org/html/2610.22564#S1.E1)\)\. For noiseless linear problems, examples include Gelfand widths[Pinkus \(2012\)](https://arxiv.org/html/2610.22564#bib.bib4)and bestkk\-term approximation[Cohen et al\. \(2009\)](https://arxiv.org/html/2610.22564#bib.bib6)\. Worst\-case bounds for set\-valued recovery maps were established on Banach spaces in[Arestov \(1986\)](https://arxiv.org/html/2610.22564#bib.bib12)and extended to metric spaces in[Magaril\-Il’yaev and Osipenko \(1991\)](https://arxiv.org/html/2610.22564#bib.bib13)\. For noisy problems,[Binev et al\. \(2024\)](https://arxiv.org/html/2610.22564#bib.bib11)introduced optimal learning and upper bounds based on the Chebyshev radius, while[Cohen et al\. \(2022\)](https://arxiv.org/html/2610.22564#bib.bib10)studied the optimal accuracy of nonlinear approximation methods; see also the radius of information in[Traub et al\. \(1983\)](https://arxiv.org/html/2610.22564#bib.bib68)and the survey[Micchelli and Rivlin \(1977\)](https://arxiv.org/html/2610.22564#bib.bib3)\. These works show that non\-uniqueness can impose unavoidable error\. Our approach differs in using metric and Hausdorff distances on feasible sets and optimal \(set\-valued\) regressors and classifiers, without requiring a nested family of approximate prediction sets, and in providing a computable finite\-dataset perspective relevant to modern machine learning\.

Statistical learning theory and model\-dependent bounds\.Another line of work studies regressor and classifier error through sampling assumptions, hypothesis\-class complexity, or specific model classes, including neural\-network architectural restrictions\. For example,[Zhang \(2009\)](https://arxiv.org/html/2610.22564#bib.bib30)derives sharp bounds for parameter estimation in linear regression under specific assumptions, and[Qi et al\. \(2020\)](https://arxiv.org/html/2610.22564#bib.bib31)gives upper bounds for the mean absolute error of neural\-network regressors under architectural assumptions\. Vapnik\-Chervonenkis \(VC\) theory, see[Vapnik \(2006\)](https://arxiv.org/html/2610.22564#bib.bib33);[Vapnik \(1999\)](https://arxiv.org/html/2610.22564#bib.bib34), and related measures such as Rademacher complexity, see[Bartlett and Mendelson \(2002\)](https://arxiv.org/html/2610.22564#bib.bib36), provide generalization bounds for restricted model classes, while[Cherkassky et al\. \(1999\)](https://arxiv.org/html/2610.22564#bib.bib32)show the usefulness of VC\-type bounds for model selection in small i\.i\.d\. datasets and linear regression\. However, such bounds are typically not directly computable for arbitrary finite datasets and broad model classes, and they often rely on assumptions, such as i\.i\.d\. sampling, that may fail in practice or be difficult to verify[Arnold \(1979\)](https://arxiv.org/html/2610.22564#bib.bib69)\.

Modern deep learning and the limits of classical explanations\.Neural networks are universal approximators, see[Hornik et al\. \(1989\)](https://arxiv.org/html/2610.22564#bib.bib22);[Maiorov and Pinkus \(1999\)](https://arxiv.org/html/2610.22564#bib.bib23);[Bach \(2017\)](https://arxiv.org/html/2610.22564#bib.bib16);[Beck et al\. \(2022\)](https://arxiv.org/html/2610.22564#bib.bib17);[Petersen and Voigtlaender \(2018\)](https://arxiv.org/html/2610.22564#bib.bib18);[Yarotsky \(2017\)](https://arxiv.org/html/2610.22564#bib.bib19), but, as emphasized in[Adcock and Dexter \(2021\)](https://arxiv.org/html/2610.22564#bib.bib15), approximation\-theoretic expressivity does not by itself provide guarantees on trainability or practical error and accuracy\.[Zhang et al\. \(2016\)](https://arxiv.org/html/2610.22564#bib.bib37);[Zhang et al\. \(2021\)](https://arxiv.org/html/2610.22564#bib.bib38)show that deep networks can fit datasets with random labels, and argue that classical notions such as VC dimension, Rademacher complexity, and uniform stability do not explain the generalization behavior of state\-of\-the\-art neural networks\. Separately,[Northcutt et al\. \(2021\)](https://arxiv.org/html/2610.22564#bib.bib75)identified substantial label errors in widely used datasets, such as CIFAR\-10, highlighting that both label uncertainty and annotation errors can limit measurable test accuracy\. In some applications, deep learning is not even the best empirical choice: for instance, tree\-based methods can outperform deep neural networks on tabular data[Grinsztajn et al\. \(2022\)](https://arxiv.org/html/2610.22564#bib.bib35)\. These observations motivate the search for accuracy limits that depend on the task and dataset rather than on the expressive power of a specific model family\. The perspective of this paper is closest to geometric and recovery\-based approaches that quantify ambiguity in the input\-target relation\. It is complementary to information\-theoretic minimax lower bounds, such as Fano and Le Cam methods[Tsybakov \(2003\)](https://arxiv.org/html/2610.22564#bib.bib43);[Le Cam \(2012\)](https://arxiv.org/html/2610.22564#bib.bib44);[Fano and Hawkins \(1961\)](https://arxiv.org/html/2610.22564#bib.bib45), and to bias\-variance decompositions of prediction risk[Geman et al\. \(1992\)](https://arxiv.org/html/2610.22564#bib.bib40)\.

Bayes risk, irreducible error, and Bayes\-error estimation\.In statistical decision theory, the model\-independent benchmark under distributionμ\\mufor a lossℓ\\ellis the Bayes riskinfϕ𝔼μ​\[ℓ⁡\(Y,ϕ⁡\(X\)\)\]\\inf\_\{\\phi\}\\mathbb\{E\}\_\{\\mu\}\[\\ell\(Y,\\phi\(X\)\)\], where the infimum is over measurable decision rulesϕ\\phi, see[Berger \(1985\)](https://arxiv.org/html/2610.22564#bib.bib64)and[Murphy \(2022\)](https://arxiv.org/html/2610.22564#bib.bib21), which could be either regressors or classifiers\. Under Euclidean squared loss, the Bayes rule is the conditional mean and the irreducible term is the expected conditional variance\.[Cover and Hart \(1967\)](https://arxiv.org/html/2610.22564#bib.bib70)showed that the asymptotic error of a nearest\-neighbor classifier is bounded above by twice the Bayes error; in their conditional sampling formulation, this error is characterized by pairwise disagreement between conditionally independent labels, which is the distributional analogue average kernel size in our settin\. The problem of estimating this irreducible squared\-loss term, often called the residual variance, has also been studied in nonparametric regression under i\.i\.d\. sampling assumptions; see, for example,[Devroye et al\. \(2018\)](https://arxiv.org/html/2610.22564#bib.bib82), who analyze a nearest\-neighbor estimator together with asymptotic normality and concentration results\. Our distributional analogue average kernel size gives an equivalent pairwise representation, as its square is exactly twice the Bayes squared risk\. Recent work develops statistical estimators of Bayes error and optimal classification error and accuracy, including multiclass and computationally efficient approaches, see[Chen et al\. \(2023\)](https://arxiv.org/html/2610.22564#bib.bib71);[Jeong et al\. \(2023\)](https://arxiv.org/html/2610.22564#bib.bib72);[Chen et al\. \(2025\)](https://arxiv.org/html/2610.22564#bib.bib73);[Ushio et al\. \(2026\)](https://arxiv.org/html/2610.22564#bib.bib74)\. These methods estimate distribution\-level limits under probabilistic sampling assumptions, such as i\.i\.d\. sampling\. Related empirical studies refine the classical bias\-variance picture in overparameterized regimes; see, for example,[Neal et al\. \(2018\)](https://arxiv.org/html/2610.22564#bib.bib41);[Yang et al\. \(2020\)](https://arxiv.org/html/2610.22564#bib.bib42)\. In contrast, our bounds are deterministic and finite\-sample, apply to the realized empirical loss on the constructed dataset from Assumption[1\.2](https://arxiv.org/html/2610.22564#S1.Thmtheorem2), extend to metric or pseudo\-metric target spaces, and do not require i\.i\.d\. sampling\.

Nonparametric estimation of conditional structure\.Estimating conditional means, conditional variances, and Bayes risk from finite data is a central problem in nonparametric statistics, see[Stone \(1977\)](https://arxiv.org/html/2610.22564#bib.bib65);[Györfi et al\. \(2002\)](https://arxiv.org/html/2610.22564#bib.bib66)\. Such estimators typically rely on i\.i\.d\. sampling together with smoothness assumptions\. Here the bounds are computed from deterministic and geometric finite feasible sets with a chosen pseudo\-metric and threshold rule\. It should be distinguished from an estimator based on genuine conditionally i\.i\.d\. replicates\. The convergence theorem connects the deterministic bounds to such an ideal sampling design\.

Stability and generalization\.Classical algorithmic\-stability results control expected generalization error by studying how a learning rule changes when observations in the training sample are replaced[Bousquet and Elisseeff \(2002\)](https://arxiv.org/html/2610.22564#bib.bib67)\. The accuracy\-stability result concerns a different notion: the metric regularity of the fitted regressors and classifiers as a function of their input, which is a deterministic geometric obstruction\. If nearby inputs are paired with well\-separated targets, a regressor or classifier that fits both targets accurately must have a large local Lipschitz constant, independently of how the regressor or classifier was trained\.

Dimensionality reduction and geometric preservation\.Results such as the Johnson\-Lindenstrauss lemma[Johnson and Lindenstrauss \(1984\)](https://arxiv.org/html/2610.22564#bib.bib8)show that low\-dimensional embeddings can approximately preserve pairwise geometry, but this does not by itself quantify achievable prediction accuracy or ambiguity in the input\-target relation\.

Positioning of the present work\.We use a feasible\-set geometry to derive computable, deterministic, non\-asymptotic lower and upper bounds on the best achievable empirical error on a realized, finite, constructed dataset\. The bounds are model\-class independent and apply to upper hemicontinuous compact\-valued regressors and classifiers, a class containing single\-valued, continuous regressors and classifiers\. The input space has a pseudo\-metric and the target space a metric, so the construction is not restricted to Euclidean regression\. The provided distribution dependent results show that, they relate conditional target ambiguity to Bayes risk and to generalization gaps under probabilistic assumptions\.

### 1\.4Outlook and impact

An important practical feature of the proposed framework is that the bounds on empirical error on the constructed dataset𝒟M′\\mathcal\{D\}\_\{M^\{\\prime\}\}from Assumption[1\.2](https://arxiv.org/html/2610.22564#S1.Thmtheorem2)are computable before model optimization and training\. As the bounds depend on the dataset, the chosen metric structure, and the finite samples used in the analysis, they provide task\-dependent information prior to model selection and optimization\. The framework can therefore help answer questions such as:Is the available data sufficiently informative for the task under the chosen evaluation metric?andHow much improvement remains possible before the observed empirical error reaches the model\-independent floor induced by the chosen input space pseudo\-metric and finite feasible sets?The bounds quantify this remaining room for improvement in empirical error, but they do not imply that additional tuning, a different architecture, or a particular optimization method will attain it\. Although the proof of Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)is constructive and provides an explicit variational formula for the regressor obtaining the best achievable empirical error, this regressor is computationally expensive as it requires solving an optimization problem for each input\. The analogous formula and conclusion apply to classification\.

This makes the bounds potentially useful for dataset assessment, model selection, and training diagnostics\. More broadly, they provide a principled way to distinguish limitations imposed by the data from limitations imposed by a specific learning method\.

### 1\.5Outline

The remainder of the paper is organized into three logically distinct parts\. First, we develop deterministic finite\-sample bounds on empirical loss and accuracy for a constructed dataset derived from feasible\-set geometry\. Second, under additional probabilistic assumptions, we relate the distributional analogue of the average kernel size to Bayes risk and generalization gaps\. Here Section[2](https://arxiv.org/html/2610.22564#S2)develops the framework and assumptions and presents the main theoretical results, including the algorithm used to compute the accuracy bounds\. Third, we provide experiments illustrating the behavior of the deterministic construction across several datasets and choices of evaluation metric\. Here Section[3](https://arxiv.org/html/2610.22564#S3)presents the experimental results\. Proofs are deferred to the end of the manuscript, while additional material for reproducibility, including implementation details and descriptions of the datasets considered, is provided in the Appendix\. Our code is publicly available at this[GitHub repository](https://github.com/nm19000/AccuracyBoundsRegression)\.

## 2Main results

In the following subsections, we first define a minimal framework for regression and classification problems that is required to present the corresponding main theoretical results\. Then, we present the main deterministic and finite\-sample results, hereafter we introduce additional probabilistic assumptions required to present the distribution level results\.

### 2\.1Problem formulation

We model a regression or classification problem by a dataset of tuples

𝒟M⊂ℳ1×ℳ2⊂𝒴×𝒳,\\mathcal\{D\}\_\{M\}\\subset\\mathcal\{M\}\_\{1\}\\times\\mathcal\{M\}\_\{2\}\\subset\\mathcal\{Y\}\\times\\mathcal\{X\},for someM∈ℕM\\in\\mathbb\{N\}, together with the prediction task \([1\.1](https://arxiv.org/html/2610.22564#S1.E1)\)\. The ambient input space𝒳\\mathcal\{X\}is equipped with a pseudo\-metricd𝒳d\_\{\\mathcal\{X\}\}, and the ambient target space𝒴\\mathcal\{Y\}is equipped with a metricd𝒴d\_\{\\mathcal\{Y\}\}\. For image\-based regression and classification tasks in Section[3](https://arxiv.org/html/2610.22564#S3)we chose a metric based on wavelet transforms concatenated with theℓ2\\ell\_\{2\}norm\. We endow𝒳\\mathcal\{X\}and𝒴\\mathcal\{Y\}with the corresponding topologies generated by the open balls

Bd𝒳​\(x,r\)=\{z∈𝒳:d𝒳​\(x,z\)<r\},Bd𝒴​\(y,r\)=\{z∈𝒴:d𝒴​\(y,z\)<r\},B\_\{d\_\{\\mathcal\{X\}\}\}\(x,r\)=\\\{z\\in\\mathcal\{X\}:d\_\{\\mathcal\{X\}\}\(x,z\)<r\\\},\\qquad B\_\{d\_\{\\mathcal\{Y\}\}\}\(y,r\)=\\\{z\\in\\mathcal\{Y\}:d\_\{\\mathcal\{Y\}\}\(y,z\)<r\\\},forr\>0r\>0\. We equipℳ2\\mathcal\{M\}\_\{2\}with the induced subspace topology\. In addition, we assume the following\.

###### Assumption 2\.1\(Heine\-Borel property\)\.

The metric space\(𝒴,d𝒴\)\(\\mathcal\{Y\},d\_\{\\mathcal\{Y\}\}\)satisfies the Heine\-Borel property, that is, every closed and bounded subset of𝒴\\mathcal\{Y\}is compact\.

Throughout the paper, we denote byπ1:ℳ1×ℳ2→ℳ1\\pi\_\{1\}:\\mathcal\{M\}\_\{1\}\\times\\mathcal\{M\}\_\{2\}\\to\\mathcal\{M\}\_\{1\}the projection\(y,x\)↦y\(y,x\)\\mapsto yand byπ2:ℳ1×ℳ2→ℳ2\\pi\_\{2\}:\\mathcal\{M\}\_\{1\}\\times\\mathcal\{M\}\_\{2\}\\to\\mathcal\{M\}\_\{2\}the projection\(y,x\)↦x\(y,x\)\\mapsto x\. The disjoint union of setsA,B⊂𝒳A,B\\subset\\mathcal\{X\}is denoted byA⋅Γ∪BA\\mathbin\{\\mathaccent 0\{\\cdot\}\\cup\}B\. A regressor or classifier is modeled by a set\-valued map

ϕ:ℳ2⇉𝒴,x↦ϕ⁡\(x\)=y^\.\\displaystyle\\phi:\\mathcal\{M\}\_\{2\}\\rightrightarrows\\mathcal\{Y\},\\qquad x\\mapsto\\phi\(x\)=\\hat\{y\}\.\(2\.1\)ForS⊂ℳ2S\\subset\\mathcal\{M\}\_\{2\}, we define the image ofSSunderϕ\\phiby

ϕ⁡\(S\)=⋃x∈Sϕ⁡\(x\)\.\\phi\(S\)=\\bigcup\_\{x\\in S\}\\phi\(x\)\.To accommodate set\-valued regressors and classifiers, we extend the metricd𝒴d\_\{\\mathcal\{Y\}\}by the Hausdorff distance\. For bounded setsS1,S2⊂𝒴S\_\{1\},S\_\{2\}\\subset\\mathcal\{Y\}, define

d𝒴H​\(S1,S2\)=max⁡\{supz∈S1infy∈S2d𝒴​\(z,y\),supz∈S2infy∈S1d𝒴​\(z,y\)\},d\_\{\\mathcal\{Y\}\}^\{H\}\(S\_\{1\},S\_\{2\}\)=\\max\\Bigl\\\{\\sup\_\{z\\in S\_\{1\}\}\\inf\_\{y\\in S\_\{2\}\}d\_\{\\mathcal\{Y\}\}\(z,y\),\\;\\sup\_\{z\\in S\_\{2\}\}\\inf\_\{y\\in S\_\{1\}\}d\_\{\\mathcal\{Y\}\}\(z,y\)\\Bigr\\\},which is well\-defined for nonempty compact sets\. Considering set\-valued regressors and classifiers allows us to include stochastic models, such as diffusion\-based generative models\. For example, a finite collection of predictions\{yℓ\}ℓ=1L\\\{y\_\{\\ell\}\\\}\_\{\\ell=1\}^\{L\}produced for a given inputxx, yields a prediction setϕ⁡\(x\)=\{yℓ\}ℓ=1L\\phi\(x\)=\\\{y\_\{\\ell\}\\\}\_\{\\ell=1\}^\{L\}\. For a dataset𝒟M=\{\(ym,xm\)\}m=1M\\mathcal\{D\}\_\{M\}=\\\{\(y\_\{m\},x\_\{m\}\)\\\}\_\{m=1\}^\{M\}andp∈\[1,∞\)p\\in\[1,\\infty\), the empirical regression error ofϕ\\phiis defined by \([1\.11](https://arxiv.org/html/2610.22564#S1.E11)\), which depends only on the sampled pairs in𝒟M\\mathcal\{D\}\_\{M\}\.

For classification problems withC∈ℕC\\in\\mathbb\{N\}classes, we use the normalized Hamming distance and restrict the target ambient space𝒴\\mathcal\{Y\}as follows\.

###### Assumption 2\.2\(Classification decisions and loss\)\.

For classification, the target and decision space is𝒴C=\{e1,…,eC\}\\mathcal\{Y\}\_\{C\}=\\\{e\_\{1\},\\ldots,e\_\{C\}\\\}, equipped with its power\-set sigma\-algebra and the normalized Hamming metric

dH\(ec,ec′\)=𝟏\{c≠c′\}\.d\_\{H\}\(e\_\{c\},e\_\{c^\{\\prime\}\}\)=\\mathbf\{1\}\_\{\\\{c\\neq c^\{\\prime\}\\\}\}\.If a model outputs a score or probability vector inΔC−1\\Delta^\{C\-1\}, it is converted to a one\-hot decision by a fixed Borel\-measurable tie\-breakingarg⁡max\\arg\\maxrule\.

Given a classifierϕ:ℳ2⇉𝒴\\phi:\\mathcal\{M\}\_\{2\}\\rightrightarrows\\mathcal\{Y\}, the empirical accuracy is defined by \([1\.12](https://arxiv.org/html/2610.22564#S1.E12)\) withd𝒴=dHd\_\{\\mathcal\{Y\}\}=d\_\{H\}\.

We quantify the stability of a regressor or classifierϕ:ℳ2⇉𝒴\\phi:\\mathcal\{M\}\_\{2\}\\rightrightarrows\\mathcal\{Y\}by local and global Lipschitz constants\. Forϵ\>0\\epsilon\>0andx∈ℳ2x\\in\\mathcal\{M\}\_\{2\}, the localϵ\\epsilon\-Lipschitz constant is defined by

Lϵ​\(ϕ,x\)=supz∈ℳ20<d𝒳​\(z,x\)≤ϵd𝒴H​\(ϕ⁡\(x\),ϕ⁡\(z\)\)d𝒳​\(x,z\),L^\{\\epsilon\}\(\\phi,x\)=\\sup\_\{\\begin\{subarray\}\{c\}z\\in\\mathcal\{M\}\_\{2\}\\\\ 0<d\_\{\\mathcal\{X\}\}\(z,x\)\\leq\\epsilon\\end\{subarray\}\}\\frac\{d\_\{\\mathcal\{Y\}\}^\{H\}\(\\phi\(x\),\\phi\(z\)\)\}\{d\_\{\\mathcal\{X\}\}\(x,z\)\},where in the classification settingd𝒴=dHd\_\{\\mathcal\{Y\}\}=d\_\{H\}\. The global Lipschitz constant is defined by

L⁡\(ϕ\)=supx,z∈ℳ20<d𝒳​\(x,z\)d𝒴H​\(ϕ⁡\(x\),ϕ⁡\(z\)\)d𝒳​\(x,z\)\.L\(\\phi\)=\\sup\_\{\\begin\{subarray\}\{c\}x,z\\in\\mathcal\{M\}\_\{2\}\\\\ 0<d\_\{\\mathcal\{X\}\}\(x,z\)\\end\{subarray\}\}\\frac\{d\_\{\\mathcal\{Y\}\}^\{H\}\(\\phi\(x\),\\phi\(z\)\)\}\{d\_\{\\mathcal\{X\}\}\(x,z\)\}\.Related notions of Lipschitz continuity for set\-valued maps may be found in[Li \(1994\)](https://arxiv.org/html/2610.22564#bib.bib46);[Aubin \(1990\)](https://arxiv.org/html/2610.22564#bib.bib39)\.

Following\([Aliprantis and Border, 2006](https://arxiv.org/html/2610.22564#bib.bib9), Definition 17\.2\)we define upper hemicontinuity of a set\-valued regressor or classifierϕ:ℳ2⇉𝒴\\phi:\\mathcal\{M\}\_\{2\}\\rightrightarrows\\mathcal\{Y\}\. For this we define theupper inverseϕu\\phi^\{u\}of a subsetA⊂𝒴A\\subset\\mathcal\{Y\}by

ϕu​\(A\)=\{x∈ℳ2:ϕ⁡\(x\)⊂A\}\.\\phi^\{u\}\(A\)=\\\{x\\in\\mathcal\{M\}\_\{2\}:\\phi\(x\)\\subset A\\\}\.Then,ϕ:ℳ2⇉𝒴\\phi:\\mathcal\{M\}\_\{2\}\\rightrightarrows\\mathcal\{Y\}is*upper hemicontinuous*atxxif for every neighborhoodUUofϕ⁡\(x\)\\phi\(x\), there is a neighborhoodVVofxxsuch thatz∈Vz\\in Vimpliesϕ⁡\(z\)⊂U\\phi\(z\)\\subset Uor, equivalently, ifϕu​\(U\)\\phi^\{u\}\(U\)is a neighborhood ofxxin𝒳\\mathcal\{X\}\. As with functions, we sayϕ\\phiis upper hemicontinuous onℳ2\\mathcal\{M\}\_\{2\}, if it is upper hemicontinuous at every point ofℳ2\\mathcal\{M\}\_\{2\}\. For more context, see Section[8](https://arxiv.org/html/2610.22564#S8)\.

### 2\.2Dataset\-level stability and accuracy bounds

Motivated by the accuracy\-stability trade\-off for single\-valued decoders solving inverse problems in[Gottschling et al\. \(2025\)](https://arxiv.org/html/2610.22564#bib.bib7), we begin with an accuracy\-stability trade\-off showing that, when distinct targets correspond to nearby or identical inputs, a highly accurate regressor or classifier must become locally unstable\. This observation motivates the lower bounds developed below\.

###### Proposition 2\.5\(Accuracy–stability trade\-off\)\.

Letη,τ𝒳\>0\\eta,\\tau\_\{\\mathcal\{X\}\}\>0, letM∈ℕM\\in\\mathbb\{N\}, let𝒟M⊂ℳ1×ℳ2\\mathcal\{D\}\_\{M\}\\subset\\mathcal\{M\}\_\{1\}\\times\\mathcal\{M\}\_\{2\}be a dataset, and letϕ:ℳ2⇉𝒴\\phi:\\mathcal\{M\}\_\{2\}\\rightrightarrows\\mathcal\{Y\}be an upper hemicontinuous regressor or classifier with nonempty compact values and letd𝒳d\_\{\\mathcal\{X\}\}be a metric\. Suppose there exist\(y,x\),\(y′,x′\),\(y′′,x′′\)∈𝒟M\(y,x\),\(y^\{\\prime\},x^\{\\prime\}\),\(y^\{\\prime\\prime\},x^\{\\prime\\prime\}\)\\in\\mathcal\{D\}\_\{M\}such that

d𝒴H​\(ϕ⁡\(x\),\{y\}\)<η,d𝒴H​\(ϕ⁡\(x′\),\{y′′\}\)<η,0<d𝒳​\(x,x′\)<τ𝒳\.\\displaystyle d\_\{\\mathcal\{Y\}\}^\{H\}\(\\phi\(x\),\\\{y\\\}\)<\\eta,\\qquad d\_\{\\mathcal\{Y\}\}^\{H\}\(\\phi\(x^\{\\prime\}\),\\\{y^\{\\prime\\prime\}\\\}\)<\\eta,\\qquad 0<d\_\{\\mathcal\{X\}\}\(x,x^\{\\prime\}\)<\\tau\_\{\\mathcal\{X\}\}\.\(2\.2\)Then, there exists an open ballℬ⊂ℳ2\\mathcal\{B\}\\subset\\mathcal\{M\}\_\{2\}centered atxxsuch that, for everyϵ\>0\\epsilon\>0withτ𝒳≤ϵ\\tau\_\{\\mathcal\{X\}\}\\leq\\epsilon, the localϵ\\epsilon\-Lipschitz constant satisfies

Lϵ​\(ϕ,x~\)≥1τ𝒳​\(d𝒴​\(y,y′′\)−2​η\)for all​x~∈ℬ\.L^\{\\epsilon\}\(\\phi,\\tilde\{x\}\)\\geq\\frac\{1\}\{\\tau\_\{\\mathcal\{X\}\}\}\\bigl\(d\_\{\\mathcal\{Y\}\}\(y,y^\{\\prime\\prime\}\)\-2\\eta\\bigr\)\\qquad\\text\{for all \}\\tilde\{x\}\\in\\mathcal\{B\}\.

While the proposition is, in essence, a geometric statement about an upper hemicontinuousϕ\\phi, we formulate it using dataset points to situate it in the data\-dependent framework used throughout the paper\. The use of three dataset pairs in \([2\.2](https://arxiv.org/html/2610.22564#S2.E2)\) is deliberate\. The dataset contains\(y,x\),\(y′,x′\)∈𝒟M\(y,x\),\(y^\{\\prime\},x^\{\\prime\}\)\\in\\mathcal\{D\}\_\{M\}and,\(y′′,x′′\)∈𝒟M\(y^\{\\prime\\prime\},x^\{\\prime\\prime\}\)\\in\\mathcal\{D\}\_\{M\}, but the second accuracy condition evaluates the prediction atx′x^\{\\prime\}against the targety′′y^\{\\prime\\prime\}, rather than against the targety′y^\{\\prime\}paired withx′x^\{\\prime\}\. Thus, the proposition does not requireϕ⁡\(x′\)\\phi\(x^\{\\prime\}\)to predict the target observed atx′x^\{\\prime\}\. It only requires that the prediction at the nearby inputx′x^\{\\prime\}be close to some targety′′y^\{\\prime\\prime\}that occurs in the dataset, possibly paired with a different inputx′′x^\{\\prime\\prime\}\. The more restrictive paired\-target assumption is recovered by imposingy′′=y′y^\{\\prime\\prime\}=y^\{\\prime\}\. Since the proposition allowsy′′≠y′y^\{\\prime\\prime\}\\neq y^\{\\prime\}, it applies under a strictly weaker assumption and is therefore more general\.

Under the assumptions of Proposition[2\.5](https://arxiv.org/html/2610.22564#S2.Thmtheorem5), the global Lipschitz constant satisfies

L⁡\(ϕ\)≥supx~∈ℳ2Lϵ​\(ϕ,x~\)≥1τ𝒳​\(d𝒴​\(y,y′′\)−2​η\)\.L\(\\phi\)\\geq\\sup\_\{\\tilde\{x\}\\in\\mathcal\{M\}\_\{2\}\}L^\{\\epsilon\}\(\\phi,\\tilde\{x\}\)\\geq\\frac\{1\}\{\\tau\_\{\\mathcal\{X\}\}\}\\bigl\(d\_\{\\mathcal\{Y\}\}\(y,y^\{\\prime\\prime\}\)\-2\\eta\\bigr\)\.Hence, ifd𝒴​\(y,y′′\)−2​η≥C\>0d\_\{\\mathcal\{Y\}\}\(y,y^\{\\prime\\prime\}\)\-2\\eta\\geq C\>0, then lettingτ𝒳→0\+\\tau\_\{\\mathcal\{X\}\}\\to 0^\{\+\}forcesL⁡\(ϕ\)→∞L\(\\phi\)\\to\\infty\. If two distinct targets are feasible for inputs with a very small distance, then uniformly small pointwise error is incompatible with global stability\.

If two targetsy,y~∈Fxy,\\tilde\{y\}\\in F\_\{x\}share exactly the same input and both are predicted with a pointwise error at mostη\\eta, then asd𝒴​\(y,y~\)≤d𝒴H​\(\{y\},ϕ⁡\(x\)\)\+d𝒴H​\(\{y~\},ϕ⁡\(x\)\)≤2​η,d\_\{\\mathcal\{Y\}\}\(y,\\tilde\{y\}\)\\leq d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\\\},\\phi\(x\)\)\+d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{\\tilde\{y\}\\\},\\phi\(x\)\)\\leq 2\\eta,necessarilyη≥12​d𝒴​\(y,y~\)\\eta\\geq\\frac\{1\}\{2\}d\_\{\\mathcal\{Y\}\}\(y,\\tilde\{y\}\)\. In worst\-case form, this gives

η≥12​diam⁡\(Fx\),diam⁡\(Fx\):=supy,y~∈Fxd𝒴​\(y,y~\)\.\\eta\\geq\\frac\{1\}\{2\}\\operatorname\{diam\}\(F\_\{x\}\),\\qquad\\operatorname\{diam\}\(F\_\{x\}\):=\\sup\_\{y,\\tilde\{y\}\\in F\_\{x\}\}d\_\{\\mathcal\{Y\}\}\(y,\\tilde\{y\}\)\.While this yields a worst\-case obstruction, in statistical learning it is often more informative to quantify the*typical*ambiguity of the prediction task\. This leads to the average kernel size and the computable empirical bounds below\. The average kernel size is computed with the help of Algorithm[1](https://arxiv.org/html/2610.22564#alg1)which constructs finite\-sample feasible sets from Definition[1\.1](https://arxiv.org/html/2610.22564#S1.Thmtheorem1)\. It takes as input a collection of anchor points inℳ2\\mathcal\{M\}\_\{2\}, a dataset𝒟M⊂ℳ1×ℳ2\\mathcal\{D\}\_\{M\}\\subset\\mathcal\{M\}\_\{1\}\\times\\mathcal\{M\}\_\{2\}and threshold functionsτ𝒳:ℳ2→\(0,∞\)\\tau\_\{\\mathcal\{X\}\}:\\mathcal\{M\}\_\{2\}\\to\(0,\\infty\)andτ𝒴:ℳ1→\(0,∞\)\\tau\_\{\\mathcal\{Y\}\}:\\mathcal\{M\}\_\{1\}\\to\(0,\\infty\), that satisfy the following assumption\.

###### Assumption 2\.6\(Threshold compatibility with admissibility\)\.

We assume that the threshold functionsτ𝒳:ℳ2→\(0,∞\)\\tau\_\{\\mathcal\{X\}\}:\\mathcal\{M\}\_\{2\}\\to\(0,\\infty\)andτ𝒴:ℳ1→\(0,∞\)\\tau\_\{\\mathcal\{Y\}\}:\\mathcal\{M\}\_\{1\}\\to\(0,\\infty\)are such that for all candidate pairs\(yk,xk\),\(yk,n,xk,n\)∈𝒟M\(y\_\{k\},x\_\{k\}\),\(y\_\{k,n\},x\_\{k,n\}\)\\in\\mathcal\{D\}\_\{M\}whenever

d𝒴​\(yk,n,yk\)≤τ𝒴​\(yk\)ord𝒳​\(xk,n,xk\)≤τ𝒳​\(xk\),\\displaystyle d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k\}\)\\leq\\tau\_\{\\mathcal\{Y\}\}\(y\_\{k\}\)\\quad\\text\{or\}\\quad d\_\{\\mathcal\{X\}\}\(x\_\{k,n\},x\_\{k\}\)\\leq\\tau\_\{\\mathcal\{X\}\}\(x\_\{k\}\),\(2\.3\)then

\(yk,n,xk\)∈ℛ,\(y\_\{k,n\},x\_\{k\}\)\\in\\mathcal\{R\},whereℛ\\mathcal\{R\}is the underlying admissible input\-target multiset from Assumption[1\.2](https://arxiv.org/html/2610.22564#S1.Thmtheorem2)\.

Assumption[2\.6](https://arxiv.org/html/2610.22564#S2.Thmtheorem6)is a compatibility condition between the threshold\-based feasible\-set rule \([2\.3](https://arxiv.org/html/2610.22564#S2.E3)\) and the underlying admissibility: it does not assume thatℛ\\mathcal\{R\}is recovered from\(τ𝒳,τ𝒴\)\(\\tau\_\{\\mathcal\{X\}\},\\tau\_\{\\mathcal\{Y\}\}\), but that the chosen thresholds are chosen such that reassignments remain in the multisetℛ\\mathcal\{R\}\. For a given sample, we generally cannot determine whether the observed input or target has been corrupted, nor which noise mechanism is responsible\. Worst\-case magnitudes from input\-noise and target\-/measurement\-noise models motivate candidate choices forτ𝒳\\tau\_\{\\mathcal\{X\}\}andτ𝒴\\tau\_\{\\mathcal\{Y\}\}; see Section[3](https://arxiv.org/html/2610.22564#S3)for examples\. Their use in Algorithm[1](https://arxiv.org/html/2610.22564#alg1)is justified only when Assumption[2\.6](https://arxiv.org/html/2610.22564#S2.Thmtheorem6)also holds, i\.e\. when the threshold\-based reassignments are compatible with the underlying admissible multisetℛ\\mathcal\{R\}\. The assumption requires that, for observed pairs already contained in𝒟M⊂ℛ\\mathcal\{D\}\_\{M\}\\subset\\mathcal\{R\}, a distance\-based replacement of the input or target according to the corresponding threshold also yields an element ofℛ\\mathcal\{R\}\.111If the sample\-level noise corruption is known, we instead denoise sample\-wise and chooseτ𝒳\\tau\_\{\\mathcal\{X\}\}andτ𝒴\\tau\_\{\\mathcal\{Y\}\}according to any remaining worst\-case noise\.The disjunctive rule in Assumption[2\.6](https://arxiv.org/html/2610.22564#S2.Thmtheorem6)and Algorithm[1](https://arxiv.org/html/2610.22564#alg1)reflects uncertainty about the source of corruption: a candidate pair is admitted whenever it is compatible by either the input\-threshold or the target\-threshold criterion\. Thus, the “or” does not mean that proximity in input and target space is equivalent; it reflects that the source of corruption is unknown at the sample level\. Unless the noise is heteroskedastic, see[Gawlikowski et al\. \(2023\)](https://arxiv.org/html/2610.22564#bib.bib1), the threshold functionsτ𝒳\\tau\_\{\\mathcal\{X\}\}andτ𝒴\\tau\_\{\\mathcal\{Y\}\}are constant\. If no reliable prior information is available for choosingτ𝒳\\tau\_\{\\mathcal\{X\}\}, another choice is to calibrate it using Proposition[2\.5](https://arxiv.org/html/2610.22564#S2.Thmtheorem5)\.

Algorithm 1Approximation of feasible sets1:

K,Nmaxf∈ℕK,N^\{f\}\_\{\\max\}\\in\\mathbb\{N\}, dataset

𝒟M\\mathcal\{D\}\_\{M\}
2:threshold functions

τ𝒳​\(⋅\)\>0\\tau\_\{\\mathcal\{X\}\}\(\\cdot\)\>0,

τ𝒴​\(⋅\)\>0\\tau\_\{\\mathcal\{Y\}\}\(\\cdot\)\>0
3:

𝒟M′←∅\\mathcal\{D\}\_\{M^\{\\prime\}\}\\leftarrow\\emptyset
4:for

k=1,…,Kk=1,\\dots,Kdo

5:choose an anchor

\(yk,xk\)∈𝒟M\(y\_\{k\},x\_\{k\}\)\\in\\mathcal\{D\}\_\{M\}⊳\\trianglerightSample without replacement\.

6:

FxkN⁡\(k\)←∅F\_\{x\_\{k\}\}^\{N\(k\)\}\\leftarrow\\emptyset,

N⁡\(k\)←0N\(k\)\\leftarrow 0
7:while

N⁡\(k\)<NmaxfN\(k\)<N^\{f\}\_\{\\max\}do⊳\\trianglerightSample without replacement; untilN⁡\(k\)≥NmaxfN\(k\)\\geq N^\{f\}\_\{\\max\}or𝒟M\\mathcal\{D\}\_\{M\}is empty\.

8:sample

\(yk,n,xk,n\)∈𝒟M\(y\_\{k,n\},x\_\{k,n\}\)\\in\\mathcal\{D\}\_\{M\}
9:if

d𝒴​\(yk,n,yk\)≤τ𝒴​\(yk\)d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k\}\)\\leq\\tau\_\{\\mathcal\{Y\}\}\(y\_\{k\}\)or

d𝒳​\(xk,n,xk\)≤τ𝒳​\(xk\)d\_\{\\mathcal\{X\}\}\(x\_\{k,n\},x\_\{k\}\)\\leq\\tau\_\{\\mathcal\{X\}\}\(x\_\{k\}\)then

10:

FxkN⁡\(k\)←FxkN⁡\(k\)⋅Γ∪\{yk,n\}F\_\{x\_\{k\}\}^\{N\(k\)\}\\leftarrow F\_\{x\_\{k\}\}^\{N\(k\)\}\\mathbin\{\\mathaccent 0\{\\cdot\}\\cup\}\\\{y\_\{k,n\}\\\}⊳\\triangleright”⋅Γ∪\\mathbin\{\\mathaccent 0\{\\cdot\}\\cup\}” denotes the disjoint union\.

11:

𝒟M′←𝒟M′⋅Γ∪\{\(yk,n,xk\)\}\\mathcal\{D\}\_\{M^\{\\prime\}\}\\leftarrow\\mathcal\{D\}\_\{M^\{\\prime\}\}\\mathbin\{\\mathaccent 0\{\\cdot\}\\cup\}\\\{\(y\_\{k,n\},x\_\{k\}\)\\\}
12:

N⁡\(k\)←N⁡\(k\)\+1N\(k\)\\leftarrow N\(k\)\+1
13:endif

14:endwhile

15:endfor

16:return

\{FxkN⁡\(k\)\}k=1K\\\{F\_\{x\_\{k\}\}^\{N\(k\)\}\\\}\_\{k=1\}^\{K\},

\{N⁡\(k\)\}k=1K\\\{N\(k\)\\\}\_\{k=1\}^\{K\}, and

𝒟M′\\mathcal\{D\}\_\{M^\{\\prime\}\}

Algorithm[1](https://arxiv.org/html/2610.22564#alg1)returns finite multisets\{FxkN⁡\(k\)\}k=1K\\\{F\_\{x\_\{k\}\}^\{N\(k\)\}\\\}\_\{k=1\}^\{K\}, the finite feasible sets, together with their cardinalities\{N⁡\(k\)\}k=1K\\\{N\(k\)\\\}\_\{k=1\}^\{K\}and a constructed dataset

𝒟M′=\{\(yk,n,xk\):1≤k≤K,1≤n≤N\(k\)\},M′=∑k=1KN\(k\)\.\\mathcal\{D\}\_\{M^\{\\prime\}\}=\\\{\(y\_\{k,n\},x\_\{k\}\):1\\leq k\\leq K,\\ 1\\leq n\\leq N\(k\)\\\},\\qquad M^\{\\prime\}=\\sum\_\{k=1\}^\{K\}N\(k\)\.If threshold functionsτ𝒳\\tau\_\{\\mathcal\{X\}\}andτ𝒴\\tau\_\{\\mathcal\{Y\}\}satisfy Assumption[2\.6](https://arxiv.org/html/2610.22564#S2.Thmtheorem6)and additionally we chose the number of anchor samples such thatK=MK=Mand if each anchor’s own pair is in its feasible set and at least one set must be non\-degenerate, then, as the anchors are sampled without replacement, the constructed dataset𝒟M′\\mathcal\{D\}\_\{M^\{\\prime\}\}from Algorithm[1](https://arxiv.org/html/2610.22564#alg1)satisfies Assumption[1\.2](https://arxiv.org/html/2610.22564#S1.Thmtheorem2)and makes this additional assumption obsolete\. The sampling procedure in the algorithm is intentionally left open and may be implemented, for example, by brute\-force search, Monte Carlo methods, or nearest\-neighbor queries, depending on the application\. In our minimal implementation and examples in Section[3](https://arxiv.org/html/2610.22564#S3), we adopt queries based on nearest\-neighbor distance matrices\.

With the outputs from Algorithm[1](https://arxiv.org/html/2610.22564#alg1)we define the quantity that is central to the lower and upper bounds on empirical accuracy and error\.

###### Definition 2\.8\(Average kernel size\)\.

Letp∈\[1,∞\)p\\in\[1,\\infty\), let𝒟M\\mathcal\{D\}\_\{M\}be a dataset, and fixK,Nmaxf∈ℕK,N^\{f\}\_\{\\max\}\\in\\mathbb\{N\}\. Apply Algorithm[1](https://arxiv.org/html/2610.22564#alg1)to obtain finite feasible sets

\{FxkN⁡\(k\)\}k=1K=\{\{yk,n\}n=1N⁡\(k\)\}k=1K\\left\\\{F\_\{x\_\{k\}\}^\{N\(k\)\}\\right\\\}\_\{k=1\}^\{K\}=\\left\\\{\\\{y\_\{k,n\}\\\}\_\{n=1\}^\{N\(k\)\}\\right\\\}\_\{k=1\}^\{K\}and letM′=∑k=1KN⁡\(k\)M^\{\\prime\}=\\sum\_\{k=1\}^\{K\}N\(k\)\. The*average kernel size*is defined by

Kersize⁡\(𝒟M′,p\)K=\(1M′​∑k=1K21\{N\(k\)\>1\}N⁡\(k\)−1​∑1≤n<n′≤N⁡\(k\)d𝒴​\(yk,n,yk,n′\)p\)1/p\.\\displaystyle\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\}=\\left\(\\frac\{1\}\{M^\{\\prime\}\}\\sum\_\{k=1\}^\{K\}\\frac\{2\\,\\mathds\{1\}\_\{\\\{N\(k\)\>1\\\}\}\}\{N\(k\)\-1\}\\sum\_\{1\\leq n<n^\{\\prime\}\\leq N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,n^\{\\prime\}\}\)^\{p\}\\right\)^\{1/p\}\.\(2\.4\)

The diagonal termsd𝒴​\(yk,n,yk,n\)=0d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,n\}\)=0are omitted, and the normalization averages pairwise distances within each feasible set before averaging across all allocated samples\. Thus,Kersize⁡\(𝒟M′,p\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\}measures the typical spread of targets associated with locally indistinguishable inputs and is a sample\-weighted within\-group average pairwise distance\. The average kernel size provides the following finite sample, deterministic lower and upper bounds on the empirical error of regressors\.

###### Theorem 2\.9\(Deterministic accuracy bounds and upper\-hemicontinuous attainment\)\.

Letp∈\[1,∞\)p\\in\[1,\\infty\), assume Assumptions[1\.2](https://arxiv.org/html/2610.22564#S1.Thmtheorem2)and[2\.1](https://arxiv.org/html/2610.22564#S2.Thmtheorem1), and let𝒟M′=\{\(yk,n,xk\):1≤k≤K,1≤n≤N\(k\)\}\\mathcal\{D\}\_\{M^\{\\prime\}\}=\\\{\(y\_\{k,n\},x\_\{k\}\):1\\leq k\\leq K,\\ 1\\leq n\\leq N\(k\)\\\}, withM′=∑k=1KN⁡\(k\)M^\{\\prime\}=\\sum\_\{k=1\}^\{K\}N\(k\), be the constructed dataset returned by Algorithm[1](https://arxiv.org/html/2610.22564#alg1)and whereN⁡\(k\)≥1N\(k\)\\geq 1for everyk∈\{1,…,K\}k\\in\\\{1,\\ldots,K\\\}\. Then, every regressorϕ:ℳ2⇉𝒴\\phi:\\mathcal\{M\}\_\{2\}\\rightrightarrows\\mathcal\{Y\}with nonempty values satisfies

12​Kersize⁡\(𝒟M′,p\)K≤ℒ⁡\(𝒟M′,ϕ,p\)\.\\frac\{1\}\{2\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\}\\leq\\mathcal\{L\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi,p\)\.If additionallyd𝒳​\(xk,xk′\)\>0d\_\{\\mathcal\{X\}\}\(x\_\{k\},x\_\{k^\{\\prime\}\}\)\>0for allk≠k′k\\neq k^\{\\prime\}, then

12​Kersize⁡\(𝒟M′,p\)K≤infϕuhcℒ⁡\(𝒟M′,ϕuhc,p\)=infϕℒ⁡\(𝒟M′,ϕ,p\)≤Kersize⁡\(𝒟M′,p\)K,\\frac\{1\}\{2\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\}\\leq\\inf\_\{\\phi\_\{\\mathrm\{uhc\}\}\}\\mathcal\{L\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi\_\{\\mathrm\{uhc\}\},p\)=\\inf\_\{\\phi\}\\mathcal\{L\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi,p\)\\leq\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\},where the first infimum is taken over all upper hemicontinuous regressors with nonempty, compact values and the second over all maps with nonempty bounded values\. The infimum is attained by an upper hemicontinuous regressor with nonempty compact values\. The attaining regressor can be chosen singleton\-valued on a neighborhood of every anchorxkx\_\{k\}\.

Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)shows that enlarging the admissible model class to include discontinuous set\-valued regressors does not improve the optimal empirical error on the constructed dataset\. This supports the intuition that the average kernel size quantifies the residual variation in the target given a fixed pseudo\-metric on the input space\. If this quantity is nonzero, then part of the prediction error is intrinsic to the task and cannot be removed by changing the model or learning architecture alone\. Although Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)holds for all sample sizesM,K∈ℕM,K\\in\\mathbb\{N\}and all feasible set cardinalitiesN⁡\(k\)∈ℕN\(k\)\\in\\mathbb\{N\}for allk∈\{1,…,K\}k\\in\\\{1,\\ldots,K\\\}, in the numerical experiments in Section[3](https://arxiv.org/html/2610.22564#S3)to ensure the average kernel size is representative of the whole dataset with sizeM∈ℕM\\in\\mathbb\{N\}, if possible we choseK=MK=M\. The feasible set cardinalitiesN⁡\(k\)∈ℕN\(k\)\\in\\mathbb\{N\}are determined by the thresholds, which we chose to satisfy Assumption[2\.6](https://arxiv.org/html/2610.22564#S2.Thmtheorem6)\.

Under additional assumptions on the target ambient space the minimizer admits a continuous single\-valued extension via a standard bump function construction\.

###### Corollary 2\.10\(Continuous attainment under linear extension assumptions\)\.

Assume, in addition to the assumptions made in Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)including thatd𝒳​\(xk,xk′\)\>0d\_\{\\mathcal\{X\}\}\(x\_\{k\},x\_\{k^\{\\prime\}\}\)\>0for allk≠k′k\\neq k^\{\\prime\}, that𝒴\\mathcal\{Y\}is a convex subset of a normed linear space and thatd𝒴d\_\{\\mathcal\{Y\}\}is a norm\. Then, the finite assignmentxk↦zkx\_\{k\}\\mapsto z\_\{k\}admits a continuous single\-valued extensionθ:ℳ2→𝒴\\theta:\\mathcal\{M\}\_\{2\}\\to\\mathcal\{Y\}, andθ\\thetaattains the unrestricted empirical minimum onℳ2\\mathcal\{M\}\_\{2\}\.

In the scalar\-valued case, where𝒴⊂ℝ\\mathcal\{Y\}\\subset\\mathbb\{R\}, the minimizer admits a Lipschitz\-continuous single\-valued extension via the extension theorem from[McShane \(1934\)](https://arxiv.org/html/2610.22564#bib.bib83)\. For classification, we define the average kernel size by using the Hamming distance in \([2\.4](https://arxiv.org/html/2610.22564#S2.E4)\) withp=1p=1\. Since accuracy is an affine transformation of a metric rather than a metric itself, the classification statement is formulated as an upper bound on achievable accuracy and we obtain the upper bound in Corollary[2\.11](https://arxiv.org/html/2610.22564#S2.Thmtheorem11)under the additional Assumption[2\.2](https://arxiv.org/html/2610.22564#S2.Thmtheorem2), as an immediate consequence of Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)\.

###### Corollary 2\.11\(Accuracy bounds for upper hemicontinuous classifiers\)\.

Assume Assumptions[1\.2](https://arxiv.org/html/2610.22564#S1.Thmtheorem2)and[2\.1](https://arxiv.org/html/2610.22564#S2.Thmtheorem1)and[2\.2](https://arxiv.org/html/2610.22564#S2.Thmtheorem2), withp=1p=1,d𝒴=dHd\_\{\\mathcal\{Y\}\}=d\_\{H\}, and let𝒟M′=\{\(yk,n,xk\):1≤k≤K,1≤n≤N\(k\)\}\\mathcal\{D\}\_\{M^\{\\prime\}\}=\\\{\(y\_\{k,n\},x\_\{k\}\):1\\leq k\\leq K,\\ 1\\leq n\\leq N\(k\)\\\}withM′=∑k=1KN⁡\(k\)M^\{\\prime\}=\\sum\_\{k=1\}^\{K\}N\(k\)be the dataset returned by Algorithm[1](https://arxiv.org/html/2610.22564#alg1)and whereN⁡\(k\)≥1N\(k\)\\geq 1for everyk∈\{1,…,K\}k\\in\\\{1,\\ldots,K\\\}\. Then, every classifierϕ:ℳ2⇉𝒴\\phi:\\mathcal\{M\}\_\{2\}\\rightrightarrows\\mathcal\{Y\}with nonempty values satisfies

Acc⁡\(𝒟M′,ϕ\)≤1−12​Kersize⁡\(𝒟M′,1\)K\.\\operatorname\{Acc\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi\)\\leq 1\-\\frac\{1\}\{2\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},1\)\_\{K\}\.If additionallyd𝒳​\(xk,xk′\)\>0d\_\{\\mathcal\{X\}\}\(x\_\{k\},x\_\{k^\{\\prime\}\}\)\>0for allk≠k′k\\neq k^\{\\prime\}, then

1−Kersize⁡\(𝒟M′,1\)K≤supϕuhcAcc⁡\(𝒟M′,ϕuhc\)=supϕAcc⁡\(𝒟M′,ϕ\)≤1−12​Kersize​\(𝒟M′,1\)K\.1\-\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},1\)\_\{K\}\\leq\\sup\_\{\\phi\_\{\\mathrm\{uhc\}\}\}\\operatorname\{Acc\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi\_\{\\mathrm\{uhc\}\}\)=\\sup\_\{\\phi\}\\operatorname\{Acc\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi\)\\leq 1\-\\frac\{1\}\{2\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},1\)\_\{K\}\.The common supremum is attained by an upper hemicontinuous classifier with nonempty finite values\.

Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)and Corollary[2\.11](https://arxiv.org/html/2610.22564#S2.Thmtheorem11)provide lower, respectively upper, bounds to the error, or respectively accuracy, of any model evaluated on a dataset constructed with Algorithm[1](https://arxiv.org/html/2610.22564#alg1)\. A natural question is, whether the error, or accuracy, on the constructed dataset are near the error or accuracy on the original dataset\. In the following we provide a deterministic comparison bound of these two quantities where we utilize a graph\-based argument\. LetE⊂\{1,…,M\}2E\\subset\\\{1,\\ldots,M\\\}^\{2\}denote the collection of reassignment edges generated by Algorithm[1](https://arxiv.org/html/2610.22564#alg1)\. An edgee=\(k,j\)∈Ee=\(k,j\)\\in Eindicates that the targetyjy\_\{j\}is reassigned to the anchor inputxkx\_\{k\}\. Thus,M′=\|E\|M^\{\\prime\}=\|E\|, and the constructed dataset empirical loss can be written as an average overe∈Ee\\in E\. Form∈\{1,…,M\}m\\in\\\{1,\\ldots,M\\\}, define the original pointwise loss by

ℓm​\(ϕ\):=d𝒴H​\(\{ym\},ϕ⁡\(xm\)\)\.\\ell\_\{m\}\(\\phi\):=d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{m\}\\\},\\phi\(x\_\{m\}\)\)\.For each edgee=\(k,j\)∈Ee=\(k,j\)\\in E, we associate a reference indexr⁡\(e\)∈\{1,…,M\}r\(e\)\\in\\\{1,\\ldots,M\\\}and a corresponding reassignment errorγe\\gamma\_\{e\}\. Ifeeis generated by the input distance criterion, we set

r⁡\(e\)=j,γe:=d𝒴H​\(ϕ⁡\(xk\),ϕ⁡\(xj\)\)\.r\(e\)=j,\\qquad\\gamma\_\{e\}:=d\_\{\\mathcal\{Y\}\}^\{H\}\(\\phi\(x\_\{k\}\),\\phi\(x\_\{j\}\)\)\.Ifϕ\\phiisLL\-Lipschitz, thenγe≤L​d𝒳​\(xk,xj\)\\gamma\_\{e\}\\leq L\\,d\_\{\\mathcal\{X\}\}\(x\_\{k\},x\_\{j\}\)\. Ifeeis generated by the target distance criterion, we instead set

r⁡\(e\)=k,γe:=d𝒴​\(yj,yk\)\.r\(e\)=k,\\qquad\\gamma\_\{e\}:=d\_\{\\mathcal\{Y\}\}\(y\_\{j\},y\_\{k\}\)\.If both criteria apply, we choose the reference index corresponding to the smaller of the two available upper bounds\. With this choice, the reverse triangle inequality for the Hausdorff metric gives, for everye=\(k,j\)∈Ee=\(k,j\)\\in E,

\|d𝒴H​\(\{yj\},ϕ⁡\(xk\)\)−ℓr⁡\(e\)​\(ϕ\)\|≤γe\.\\displaystyle\\left\|d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{j\}\\\},\\phi\(x\_\{k\}\)\)\-\\ell\_\{r\(e\)\}\(\\phi\)\\right\|\\leq\\gamma\_\{e\}\.We define the induced reference weights by

wm:=1M′\#\{e∈E:r\(e\)=m\},m=1,…,M\.w\_\{m\}:=\\frac\{1\}\{M^\{\\prime\}\}\\\#\\\{e\\in E:r\(e\)=m\\\},\\qquad m=1,\\ldots,M\.Thuswmw\_\{m\}is the fraction of constructed tuples whose reference index ismm\.∑m=1Mwm=1\\sum\_\{m=1\}^\{M\}w\_\{m\}=1and ifN⁡\(m\)N\(m\)denotes the number of constructed tuples for whichmmis the reference index, thenwm=N⁡\(m\)M′w\_\{m\}=\\frac\{N\(m\)\}\{M^\{\\prime\}\}\. Finally, define

Γp​\(ϕ\):=\(1M′​∑e∈Eγep\)1/p,Bϕ:=max1≤m≤M⁡ℓm​\(ϕ\)\.\\Gamma\_\{p\}\(\\phi\):=\\left\(\\frac\{1\}\{M^\{\\prime\}\}\\sum\_\{e\\in E\}\\gamma\_\{e\}^\{p\}\\right\)^\{1/p\},\\qquad B\_\{\\phi\}:=\\max\_\{1\\leq m\\leq M\}\\ell\_\{m\}\(\\phi\)\.The quantityΓp​\(ϕ\)\\Gamma\_\{p\}\(\\phi\)measures the average geometric error introduced by the reassignments, while the weightswmw\_\{m\}quantify the frequency with which the original observations are represented through the reference construction\.

###### Proposition 2\.13\(Original versus constructed dataset empirical loss\)\.

Assume Assumptions[1\.2](https://arxiv.org/html/2610.22564#S1.Thmtheorem2)and[2\.1](https://arxiv.org/html/2610.22564#S2.Thmtheorem1), and let𝒟M′=\{\(yk,n,xk\):1≤k≤K,1≤n≤N\(k\)\}\\mathcal\{D\}\_\{M^\{\\prime\}\}=\\\{\(y\_\{k,n\},x\_\{k\}\):1\\leq k\\leq K,\\ 1\\leq n\\leq N\(k\)\\\}withM′=∑k=1KN⁡\(k\)M^\{\\prime\}=\\sum\_\{k=1\}^\{K\}N\(k\)be the dataset returned by Algorithm[1](https://arxiv.org/html/2610.22564#alg1)and whereN⁡\(k\)≥1N\(k\)\\geq 1for everyk∈\{1,…,K\}k\\in\\\{1,\\ldots,K\\\}\. For everyp∈\[1,∞\)p\\in\[1,\\infty\)and every regressorϕ:ℳ2⇉𝒴\\phi:\\mathcal\{M\}\_\{2\}\\rightrightarrows\\mathcal\{Y\}with nonempty values,

\|ℒ⁡\(𝒟M′,ϕ,p\)−ℒ⁡\(𝒟M,ϕ,p\)\|≤Γp​\(ϕ\)\+Bϕ​\(∑m=1M\|wm−1M\|\)1/p\.\\left\|\\mathcal\{L\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi,p\)\-\\mathcal\{L\}\(\\mathcal\{D\}\_\{M\},\\phi,p\)\\right\|\\leq\\Gamma\_\{p\}\(\\phi\)\+B\_\{\\phi\}\\left\(\\sum\_\{m=1\}^\{M\}\\left\|w\_\{m\}\-\\frac\{1\}\{M\}\\right\|\\right\)^\{1/p\}\.

### 2\.3Non\-Vanishing Generalization Gaps

Up to this point, all statements have been deterministic and require only a dataset together with a metric structure\. Extending the work on inverse problems in[Gottschling et al\. \(2026\)](https://arxiv.org/html/2610.22564#bib.bib81)to regression and classification problems, we introduce a probabilistic setting to interpret the average kernel size as a model\-independent component of irreducible prediction error\. This requires measurability assumptions and the existence of conditional laws\. For simplicity we consider single\-valued measurable maps in the following and leave extensions to set\-valued measurable regressors and classifiers to future work\.

###### Assumption 2\.15\(Standard Borel quotient setting\)\.

Letx∼x′x\\sim x^\{\\prime\}if and only ifd𝒳​\(x,x′\)=0d\_\{\\mathcal\{X\}\}\(x,x^\{\\prime\}\)=0, let

ℳ¯2:=ℳ2/∼,\\overline\{\\mathcal\{M\}\}\_\{2\}:=\\mathcal\{M\}\_\{2\}/\{\\sim\},and letq:ℳ2→ℳ¯2q:\\mathcal\{M\}\_\{2\}\\to\\overline\{\\mathcal\{M\}\}\_\{2\}be the quotient map\. We assume thatℳ¯2\\overline\{\\mathcal\{M\}\}\_\{2\}and𝒴\\mathcal\{Y\}are standard Borel spaces\. For example, it suffices that they are Polish spaces equipped with their Borel sigma\-algebras\. We also assume that\(y,y′\)↦d𝒴​\(y,y′\)p\(y,y^\{\\prime\}\)\\mapsto d\_\{\\mathcal\{Y\}\}\(y,y^\{\\prime\}\)^\{p\}is Borel measurable\.

###### Assumption 2\.16\(Data\-generating law\)\.

Let\(Ω,ℱ,ℙ\)\(\\Omega,\\mathcal\{F\},\\mathbb\{P\}\)be a probability space\. Equipℳ2\\mathcal\{M\}\_\{2\}with the Borel sigma\-algebra of its pseudo\-metric topology, and letX:Ω→ℳ2X:\\Omega\\to\\mathcal\{M\}\_\{2\}andY:Ω→𝒴Y:\\Omega\\to\\mathcal\{Y\}be measurable\. The quotient mapqqis Borel measurable, so we may define the quotient input random variable

X¯:=q⁡\(X\)\.\\overline\{X\}:=q\(X\)\.Letμ\\mudenote the joint law of\(Y,X¯\)\(Y,\\overline\{X\}\)\.

Under Assumption[2\.16](https://arxiv.org/html/2610.22564#S2.Thmtheorem16), Theorem[8\.3](https://arxiv.org/html/2610.22564#S8.Thmtheorem3)implies that there exists a regular conditional law

μx¯​\(A\):=ℙ⁡\(Y∈A∣X¯=x¯\),A∈ℬ⁡\(𝒴\),\\mu\_\{\\bar\{x\}\}\(A\):=\\mathbb\{P\}\(Y\\in A\\mid\\overline\{X\}=\\bar\{x\}\),\\qquad A\\in\\mathcal\{B\}\(\\mathcal\{Y\}\),defined forμX¯\\mu\_\{\\overline\{X\}\}\-almost everyx¯\\bar\{x\}\. Now letYYandY′Y^\{\\prime\}be conditionally independent with common conditional lawμX¯\\mu\_\{\\overline\{X\}\}givenX¯\\overline\{X\}\. Similar to the deterministic analog of the average kernel size in \([2\.4](https://arxiv.org/html/2610.22564#S2.E4)\), we define the distributional analogue average kernel size by

Kersize⁡\(𝒟μ,p\):=\(𝔼X¯​𝔼Y,Y′\|X¯​\[d𝒴​\(Y,Y′\)p\]\)1/p\.\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},p\):=\\left\(\\mathbb\{E\}\_\{\\overline\{X\}\}\\mathbb\{E\}\_\{Y,Y^\{\\prime\}\\mid\\overline\{X\}\}\\bigl\[d\_\{\\mathcal\{Y\}\}\(Y,Y^\{\\prime\}\)^\{p\}\\bigr\]\\right\)^\{1/p\}\.
For classification, we define the distributional analogue average kernel size analogously, replacingd𝒴d\_\{\\mathcal\{Y\}\}by the Hamming distancedHd\_\{H\}and takingp=1p=1\. In the Euclidean setting we can show that the distributional analogue average kernel size also quantifies the irreducible error, akin to the bias\-variance decomposition introduced in[Geman et al\. \(1992\)](https://arxiv.org/html/2610.22564#bib.bib40)\.

###### Proposition 2\.17\(Exact Euclidean squared\-loss identity\)\.

Assume Assumptions[2\.15](https://arxiv.org/html/2610.22564#S2.Thmtheorem15)and[2\.16](https://arxiv.org/html/2610.22564#S2.Thmtheorem16),𝒴=ℝd\\mathcal\{Y\}=\\mathbb\{R\}^\{d\},d𝒴​\(y,y′\)=‖y−y′‖2d\_\{\\mathcal\{Y\}\}\(y,y^\{\\prime\}\)=\\\|y\-y^\{\\prime\}\\\|\_\{2\}, and𝔼​‖Y‖22<∞\\mathbb\{E\}\\\|Y\\\|\_\{2\}^\{2\}<\\infty\. Letm⁡\(X¯\):=𝔼⁡\[Y∣X¯\]m\(\\overline\{X\}\):=\\mathbb\{E\}\[Y\\mid\\overline\{X\}\]denote the conditional mean\. Then, every measurableϕ¯:ℳ¯2→ℝd\\overline\{\\phi\}:\\overline\{\\mathcal\{M\}\}\_\{2\}\\to\\mathbb\{R\}^\{d\}with finite squared risk satisfies

𝔼​‖Y−ϕ¯​\(X¯\)‖22=12​Kersize⁡\(𝒟μ,2\)2\+𝔼​‖m⁡\(X¯\)−ϕ¯​\(X¯\)‖22\.\\mathbb\{E\}\\\|Y\-\\overline\{\\phi\}\(\\overline\{X\}\)\\\|\_\{2\}^\{2\}=\\frac\{1\}\{2\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},2\)^\{2\}\+\\mathbb\{E\}\\\|m\(\\overline\{X\}\)\-\\overline\{\\phi\}\(\\overline\{X\}\)\\\|\_\{2\}^\{2\}\.Consequently,

infϕ¯\(𝔼​‖Y−ϕ¯​\(X¯\)‖22\)1/2=12​Kersize⁡\(𝒟μ,2\),\\inf\_\{\\overline\{\\phi\}\}\\left\(\\mathbb\{E\}\\\|Y\-\\overline\{\\phi\}\(\\overline\{X\}\)\\\|\_\{2\}^\{2\}\\right\)^\{1/2\}=\\tfrac\{1\}\{\\sqrt\{2\}\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},2\),where the infimum is attained by the conditional meanmm\.

A large distributional analogue average kernel size therefore indicates that a substantial part of the prediction error is caused by aleatoric uncertainty or non\-identifiability rather than by an inadequate model class\. We define the generalized risk of a measurable regressorϕ¯:ℳ¯2→𝒴\\overline\{\\phi\}:\\overline\{\\mathcal\{M\}\}\_\{2\}\\to\\mathcal\{Y\}by

ℒ⁡\(𝒟μ,ϕ¯,p\):=\(𝔼\(Y,X¯\)∼μ​\[d𝒴​\(ϕ¯​\(X¯\),Y\)p\]\)1/p,\\mathcal\{L\}\(\\mathcal\{D\}\_\{\\mu\},\\overline\{\\phi\},p\):=\\Bigl\(\\mathbb\{E\}\_\{\(Y,\\overline\{X\}\)\\sim\\mu\}\\bigl\[d\_\{\\mathcal\{Y\}\}\(\\overline\{\\phi\}\(\\overline\{X\}\),Y\)^\{p\}\\bigr\]\\Bigr\)^\{1/p\},and, analogously, the generalized accuracy of a measurable classifier by

Acc⁡\(𝒟μ,ϕ¯\):=1−𝔼\(Y,X¯\)∼μ​\[dH​\(ϕ¯​\(X¯\),Y\)\]\.\\operatorname\{Acc\}\(\\mathcal\{D\}\_\{\\mu\},\\overline\{\\phi\}\):=1\-\\mathbb\{E\}\_\{\(Y,\\overline\{X\}\)\\sim\\mu\}\\bigl\[d\_\{H\}\(\\overline\{\\phi\}\(\\overline\{X\}\),Y\)\\bigr\]\.
This probabilistic interpretation also yields lower bounds on generalization gaps whenever the training error is substantially smaller than the ambiguity encoded by the conditional law\.

###### Proposition 2\.18\(Positive generalization gaps from conditional ambiguity\)\.

Assume Assumptions[2\.15](https://arxiv.org/html/2610.22564#S2.Thmtheorem15)and[2\.16](https://arxiv.org/html/2610.22564#S2.Thmtheorem16)and letM∈ℕM\\in\\mathbb\{N\}and𝒟M=\{\(ym,xm\)\}m=1M⊂ℳ1×ℳ2\\mathcal\{D\}\_\{M\}=\\\{\(y\_\{m\},x\_\{m\}\)\\\}\_\{m=1\}^\{M\}\\subset\\mathcal\{M\}\_\{1\}\\times\\mathcal\{M\}\_\{2\}\.

Regression\.Letp≥1p\\geq 1andϵ∈\(0,12​Kersize⁡\(𝒟μ,p\)\)\\epsilon\\in\(0,\\tfrac\{1\}\{2\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},p\)\)\. Letϕ¯:ℳ¯2→𝒴\\overline\{\\phi\}:\\overline\{\\mathcal\{M\}\}\_\{2\}\\to\\mathcal\{Y\}be measurable and letϕ=ϕ¯∘q:ℳ2→𝒴\\phi=\\overline\{\\phi\}\\circ q:\\mathcal\{M\}\_\{2\}\\to\\mathcal\{Y\}withℒ⁡\(𝒟μ,ϕ¯,p\)<∞\\mathcal\{L\}\(\\mathcal\{D\}\_\{\\mu\},\\overline\{\\phi\},p\)<\\infty\. If its empirical training loss satisfies

ℒ⁡\(𝒟M,ϕ,p\)≤ϵ,\\mathcal\{L\}\(\\mathcal\{D\}\_\{M\},\\phi,p\)\\leq\\epsilon,then

0<12​Kersize⁡\(𝒟μ,p\)−ϵ≤ℒ⁡\(𝒟μ,ϕ¯,p\)−ℒ⁡\(𝒟M,ϕ,p\)\.0<\\tfrac\{1\}\{2\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},p\)\-\\epsilon\\leq\\mathcal\{L\}\(\\mathcal\{D\}\_\{\\mu\},\\overline\{\\phi\},p\)\-\\mathcal\{L\}\(\\mathcal\{D\}\_\{M\},\\phi,p\)\.Ifp=2p=2and𝒴=ℝd\\mathcal\{Y\}=\\mathbb\{R\}^\{d\}with Euclidean loss, then the sharper exact Bayes bound holds:

0<12​Kersize⁡\(𝒟μ,2\)−ϵ≤ℒ⁡\(𝒟μ,ϕ¯,2\)−ℒ⁡\(𝒟M,ϕ,2\),0<\\tfrac\{1\}\{\\sqrt\{2\}\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},2\)\-\\epsilon\\leq\\mathcal\{L\}\(\\mathcal\{D\}\_\{\\mu\},\\overline\{\\phi\},2\)\-\\mathcal\{L\}\(\\mathcal\{D\}\_\{M\},\\phi,2\),providedKersize⁡\(𝒟μ,2\)\>2​ϵ\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},2\)\>\\sqrt\{2\}\\,\\epsilon\.

Classification\.Let the target space be the finite one\-hot set from Assumption[2\.2](https://arxiv.org/html/2610.22564#S2.Thmtheorem2)and letϵ∈\(0,12​Kersize⁡\(𝒟μ,1\)\)\\epsilon\\in\(0,\\tfrac\{1\}\{2\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},1\)\)\. If a measurable quotient classifier satisfies

Acc⁡\(𝒟M,ϕ\)≥1−ϵ,\\operatorname\{Acc\}\(\\mathcal\{D\}\_\{M\},\\phi\)\\geq 1\-\\epsilon,then

0<12​Kersize⁡\(𝒟μ,1\)−ϵ≤Acc⁡\(𝒟M,ϕ\)−Acc⁡\(𝒟μ,ϕ¯\)\.0<\\tfrac\{1\}\{2\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},1\)\-\\epsilon\\leq\\operatorname\{Acc\}\(\\mathcal\{D\}\_\{M\},\\phi\)\-\\operatorname\{Acc\}\(\\mathcal\{D\}\_\{\\mu\},\\overline\{\\phi\}\)\.

Under ideal sampling conditions the following theorem relates the distributional analogue average kernel size to a finite\-sample estimator\.

###### Proposition 2\.19\(Concentration of the ideal conditional\-sampling estimator\)\.

Assume Assumptions[2\.15](https://arxiv.org/html/2610.22564#S2.Thmtheorem15)and[2\.16](https://arxiv.org/html/2610.22564#S2.Thmtheorem16)\. Letp∈\[1,∞\)p\\in\[1,\\infty\)and assume

vmax:=supy,y′∈𝒴d𝒴​\(y,y′\)p<∞\.v\_\{\\max\}:=\\sup\_\{y,y^\{\\prime\}\\in\\mathcal\{Y\}\}d\_\{\\mathcal\{Y\}\}\(y,y^\{\\prime\}\)^\{p\}<\\infty\.Fork=1,…,Kk=1,\\ldots,K, sampleX¯k\\overline\{X\}\_\{k\}independently fromμX¯\\mu\_\{\\overline\{X\}\}\. LetNK≥2N\_\{K\}\\geq 2and conditional on all anchors\(X¯1,…,X¯K\)\(\\overline\{X\}\_\{1\},\\ldots,\\overline\{X\}\_\{K\}\), sample an arrayYk,nY\_\{k,n\}forn∈\{1,…,NK\}n\\in\\\{1,\\ldots,N\_\{K\}\\\}mutually independent fromμX¯k\\mu\_\{\\overline\{X\}\_\{k\}\}\. Assume that the arraysYkY\_\{k\}andYk′Y\_\{k^\{\\prime\}\}are independent for everyk≠k′k\\neq k^\{\\prime\}, regardless of whether the corresponding anchorsX¯k\\overline\{X\}\_\{k\}andX¯k′\\overline\{X\}\_\{k^\{\\prime\}\}coincide\. Define

κ^K,NKp:=1K​∑k=1K2NK​\(NK−1\)​∑1≤n<n′≤NKd𝒴​\(Yk,n,Yk,n′\)p\.\\widehat\{\\kappa\}\_\{K,N\_\{K\}\}^\{p\}:=\\frac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}\\frac\{2\}\{N\_\{K\}\(N\_\{K\}\-1\)\}\\sum\_\{1\\leq n<n^\{\\prime\}\\leq N\_\{K\}\}d\_\{\\mathcal\{Y\}\}\(Y\_\{k,n\},Y\_\{k,n^\{\\prime\}\}\)^\{p\}\.Then, for everyδ\>0\\delta\>0,

ℙ⁡\(\|κ^K,NKp−Kersize⁡\(𝒟μ,p\)p\|≥δ\)≤2​exp⁡\(−2​K​δ2vmax2\)\.\\mathbb\{P\}\\left\(\\left\|\\widehat\{\\kappa\}\_\{K,N\_\{K\}\}^\{p\}\-\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},p\)^\{p\}\\right\|\\geq\\delta\\right\)\\leq 2\\exp\\left\(\-\\frac\{2K\\delta^\{2\}\}\{v\_\{\\max\}^\{2\}\}\\right\)\.κ^K,NKp\\widehat\{\\kappa\}\_\{K,N\_\{K\}\}^\{p\}converges in probability toKersize⁡\(𝒟μ,p\)p\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},p\)^\{p\}asK→∞K\\to\\infty, for any choiceNK≥2N\_\{K\}\\geq 2\.

## 3Applications

In the following we provide an outline of experiments and implementation, however, comprehensive details on the implementation and considered datasets are in the Appendix in Section[9\.1](https://arxiv.org/html/2610.22564#S9.SS1)\. We applied the framework to a range of tabular and image\-regression tasks and image\-classification tasks\. For each experiment, we sampled finite feasible sets, constructed the dataset𝒟M′\\mathcal\{D\}\_\{M^\{\\prime\}\}, computed the average kernel size, and used Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)and Corollary[2\.11](https://arxiv.org/html/2610.22564#S2.Thmtheorem11)to obtain model\-independent bounds on the optimal empirical regression loss and classification error, respectively\. The experiments are intended as illustrations of the deterministic construction\. They address three empirical questions:OPENi\)i\)whether the lower bound is nontrivial across domains,OPENi​i\)ii\)how reported or measured model performance compares numerically with the resulting interval, andOPENi​i​i\)iii\)how sensitive the bound is to the threshold and parameters used for the feasible set construction\. We compared the theoretical intervals with the error and accuracy of several regressors and classifiers evaluated on both the original datasets and, where the models are available, on constructed datasets\. We used a synthetic regression example to study how the accuracy bounds interact with the accuracy\-stability trade\-off from Proposition[2\.5](https://arxiv.org/html/2610.22564#S2.Thmtheorem5)\.

Across all experiments, the threshold\-selection rule was as follows: when an input\-noise model or target/label measurement\-noise model was available, we setτ𝒳\\tau\_\{\\mathcal\{X\}\}andτ𝒴\\tau\_\{\\mathcal\{Y\}\}equal to conservative worst\-case noise magnitudes implied by that model\. If such knowledge was not available, for the input thresholdτ𝒳\\tau\_\{\\mathcal\{X\}\}we followed a practical empirical heuristic based on quantiles detailed in the Appendix in Section[9\.1\.2](https://arxiv.org/html/2610.22564#S9.SS1.SSS2)and assumed ideal, noiseless targets withτ𝒴=0\\tau\_\{\\mathcal\{Y\}\}=0\. Forτ𝒴=0\\tau\_\{\\mathcal\{Y\}\}=0the target criterion in the ”or”\-condition Algorithm[1](https://arxiv.org/html/2610.22564#alg1)was not included\. We used a wavelet\-based metric with a conversion to float3232for all image inputs described in the Appendix in Section[9\.1\.1](https://arxiv.org/html/2610.22564#S9.SS1.SSS1); for images represented in float6464, this induces a pseudo\-metric\. All details on the datasets, wavelet\-based metric and feasible set sampling are in the Appendix in Section[9\.1](https://arxiv.org/html/2610.22564#S9.SS1)\.

### 3\.1Theoretical assumptions and guarantees versus experimental procedure

In all experiments, if an input\-noise model or target/label measurement\-noise model was available, thenτ𝒳\\tau\_\{\\mathcal\{X\}\}andτ𝒴\\tau\_\{\\mathcal\{Y\}\}were set to conservative worst\-case values implied by that model; this first choice satisfies a part of Assumption[2\.6](https://arxiv.org/html/2610.22564#S2.Thmtheorem6)without taking into account the correct frequencies in the underlying admissible multiset\.

For smaller datasets, \(M≈1​kM\\approx 1k\), we computed the bounds on the full dataset and did not compute these separately on the train and test splits\. For large and high\-dimensional datasets, such as Tropical Cyclone and RESISC45, with a full dataset size in the rangeM≈100​kM\\approx 100kand/or inputs with higher dimension, we computed the bounds on random subsets of anchor samples with sizeK=1​kK=1korK=3​kK=3kfrom the train or test splits over2020different random seeds\. AsK<MK<MAssumption[2\.6](https://arxiv.org/html/2610.22564#S2.Thmtheorem6)is not satisfied\. Here we reported the mean and standard deviation of the resulting bounds\. For even larger datasetsM≫100​kM\\gg 100kwhere a sample numberK≈3​kK\\approx 3kis not representative of the dataset, the implementation of Algorithm[1](https://arxiv.org/html/2610.22564#alg1)using nearest neighbors may not be feasible\. Extending Algorithm[1](https://arxiv.org/html/2610.22564#alg1)to be applicable to this scale is beyond the scope of this work\.

Comparison to theoretical assumptions and guarantees:Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)and Corollary[2\.11](https://arxiv.org/html/2610.22564#S2.Thmtheorem11)only provide bounds on the error, respectively accuracy, on the constructed dataset𝒟M′\\mathcal\{D\}\_\{M^\{\\prime\}\}from Algorithm[1](https://arxiv.org/html/2610.22564#alg1)\. We explicitly computed the accuracy on the original and constructed dataset to validate the bounds for the synthetic regression example, MNIST, CIFAR\-10 and EUROSAT\. For the remaining datasets we did not compute the regressor errors or classifier accuracies on the constructed dataset𝒟M′\\mathcal\{D\}\_\{M^\{\\prime\}\}from Algorithm[1](https://arxiv.org/html/2610.22564#alg1)and instead report errors and accuracies from benchmark dataset challenges and published state\-of\-the\-art models on the same datasets\. In these cases, for CIFAR\-10 and RESISC45, differing evaluation protocols make published results not directly comparable to the𝒟M′\\mathcal\{D\}\_\{M^\{\\prime\}\}\-based bounds and thus not violations of them\. We did not compare the average kernel size against empirical conditional variance as a general baseline, as it is only directly estimable with additional assumptions, such as i\.i\.d\. samples, in Euclidean regression settings with repeated or conditionally repeated observations\. For the same reason, we did not compute the conditional mean, which is optimal according to Proposition[2\.17](https://arxiv.org/html/2610.22564#S2.Thmtheorem17)\.

### 3\.2Regression tasks

For all regression datasets considered, the accuracy bounds provided by Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)in conjunction with Algorithm[1](https://arxiv.org/html/2610.22564#alg1)are provided in Table[3](https://arxiv.org/html/2610.22564#S3.T3)and the parameters used for computation are provided in Table[2](https://arxiv.org/html/2610.22564#S3.T2)\. We followed the procedure summarized above and outlined in the Appendix in Section[9\.1\.2](https://arxiv.org/html/2610.22564#S9.SS1.SSS2)\. We computed the bounds on a synthetic regression dataset, the Tropical Cyclone open\-source dataset from[Huggingface](https://huggingface.co/datasets/TCBench/TCBench), the UCI Energy Efficiency open\-source datasets[Tsanas and Xifara \(2012\)](https://arxiv.org/html/2610.22564#bib.bib59)from[UCI](https://archive.ics.uci.edu/dataset/242/energy+efficiency), the UCI Concrete Compressive Strength open\-source dataset[Yeh \(1998\)](https://arxiv.org/html/2610.22564#bib.bib61)from[UCI](https://archive.ics.uci.edu/dataset/165/concrete+compressive+strength)and the KAERI Critical Heat Flux \(CHF\) open\-source dataset with uniform axial heating[Park \(2000\)](https://arxiv.org/html/2610.22564#bib.bib62)from[Kaggle](https://www.kaggle.com/datasets/kaustubhdhote/critical-heat-flux-dataset/data)\. Detailed dataset descriptions, as well as the RMSE of the optimal regressor on the constructed test dataset from the proof of Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9), are in Appendix in Section[9\.1\.3](https://arxiv.org/html/2610.22564#S9.SS1.SSS3)\.

Table 2:Parameters for the regression tasks\. Here,MMdenotes the original dataset size,M′M^\{\\prime\}the constructed dataset size generated by Algorithm[1](https://arxiv.org/html/2610.22564#alg1),KKthe number of anchors,NmaxN\_\{\\max\}the maximum number of nearest neighbors andN⁡\(k\)¯\\overline\{N\(k\)\}the mean size of the feasible sets from the test dataset\.∗: for tropical cyclone the mean±\\pmthe standard deviation ofτ𝒳\\tau\_\{\\mathcal\{X\}\}across2020subsets of size1​k1kare:\(τ𝒳¯\)train=284\.7±11\.5\(\\overline\{\\tau\_\{\\mathcal\{X\}\}\}\)\_\{\\mathrm\{train\}\}=284\.7\\pm 11\.5,\(τ𝒳¯\)test=227\.7±8\.9\(\\overline\{\\tau\_\{\\mathcal\{X\}\}\}\)\_\{\\mathrm\{test\}\}=227\.7\\pm 8\.9,N⁡\(k\)¯=169\.4±2\.7\\overline\{N\(k\)\}=169\.4\\pm 2\.7Table 3:Optimal regression accuracy intervals and regressor errors\. The theoretical interval from Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)is\[1/2​Kersize⁡\(𝒟M′,p\)K,Kersize⁡\(𝒟M′,p\)K\]\\left\[1/2\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\},\\,\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\}\\right\]\. All scores for modelsϕn\\phi\_\{n\}withn∈\{1,2,3\}n\\in\\\{1,2,3\\\}are RMSE values,ℒ⁡\(𝒟M,ϕ,2\)\\mathcal\{L\}\(\\mathcal\{D\}\_\{M\},\\phi,2\), in the units of the target variable reported in the three right columns\.\(1\): models evaluated on a different test split\.∗: for tropical cyclone the mean bounds across2020subsets of size1​k1kare reported\.#### 3\.2\.1Relation to the accuracy\-stability trade\-off

10−310^\{\-3\}10−210^\{\-2\}10−110^\{\-1\}1122334412​Kersize≤RMSE≤Kersize\\frac\{1\}\{2\}\\mathrm\{Kersize\}\\leq\\mathrm\{RMSE\}\\leq\\mathrm\{Kersize\}RMSELipschitz lower boundL^\\hat\{L\}G​PoGP^\{o\}trainG​PoGP^\{o\}testG​PGPtrainG​PGPtestS​V​RoSVR^\{o\}trainS​V​RoSVR^\{o\}testS​V​RSVRtrainS​V​RSVRtestLf=0\.9L\_\{f\}=0\.9Figure 4:Accuracy\-stability trade\-off\.The empirical Lipschitz constant compared against the RMSE of GP and SVR regressors on the train and test dataset\. The average kernel size was computed from the reference dataset𝒟Mtrain′\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{train\}\}\}\. Regression modelsϕno\\phi\_\{\\mathrm\{n\}\}^\{o\}satisfyRMSEtrain​\(ϕno,𝒟Mtrain\)<12​Kersize⁡\(𝒟Mtrain′,2\)\\mathrm\{RMSE\}\_\{\\mathrm\{train\}\}\(\\phi\_\{\\mathrm\{n\}\}^\{o\},\\mathcal\{D\}\_\{M\_\{\\mathrm\{train\}\}\}\)<\\frac\{1\}\{2\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{train\}\}\},2\), whereas modelsϕn\\phi\_\{\\mathrm\{n\}\}satisfy12​Kersize⁡\(𝒟Mtrain′,2\)≤RMSEtrain​\(ϕn,𝒟Mtrain\)≤Kersize⁡\(𝒟Mtrain′,2\)\\frac\{1\}\{2\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{train\}\}\},2\)\\leq\\mathrm\{RMSE\}\_\{\\mathrm\{train\}\}\(\\phi\_\{\\mathrm\{n\}\},\\mathcal\{D\}\_\{M\_\{\\mathrm\{train\}\}\}\)\\leq\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{train\}\}\},2\)\. The parameters for computing the average kernel size wereNmax=300N\_\{\\mathrm\{max\}\}=300,τ𝒳=0\.014\\tau\_\{\\mathcal\{X\}\}=0\.014andτ𝒴=0\.03\\tau\_\{\\mathcal\{Y\}\}=0\.03\. The exact numerical values and errors on the constructed test dataset are reported in the Appendix in Table[6](https://arxiv.org/html/2610.22564#S9.T6)\.We studied the accuracy\-stability trade\-off from Proposition[2\.5](https://arxiv.org/html/2610.22564#S2.Thmtheorem5)for the synthetic regression problemf⁡\(x1,x2\)=sin⁡\(1\+0\.9​x12\+x22\)f\(x\_\{1\},x\_\{2\}\)=\\sin\\\!\\left\(1\+0\.9\\sqrt\{x\_\{1\}^\{2\}\+x\_\{2\}^\{2\}\}\\right\)with input noiseU⁡\(\[0,0\.01\]2\)U\(\[0,0\.01\]^\{2\}\)and target noiseU⁡\(\[0,0\.03\]\)U\(\[0,0\.03\]\)\. The accuracy stability trade\-off is visualized in Figure[4](https://arxiv.org/html/2610.22564#S3.F4)\. We trained two versions of each of the two regressors to approximate the target functionfffrom samples in a train dataset𝒟Mtrain\\mathcal\{D\}\_\{M\_\{\\mathrm\{train\}\}\}to obtain errors below half of the average kernel size and above on the train dataset, the latter attaining the accuracy within the bounds from Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)\. We considered two Gaussian Process regressors, and two Support Vector Regression \(SVR\) models with a radial basis function \(RBF\) kernel and optimized the model hyperparameters with a brute\-force grid search to meet the accuracy bounds conditions\. We report the RMSE of each model on both the original train and test datasets and the constructed test dataset generated by Algorithm[1](https://arxiv.org/html/2610.22564#alg1)and a lower bound to the Lipschitz constant of all models on the test dataset in the Appendix in Table[6](https://arxiv.org/html/2610.22564#S9.T6)\. For noiseless inputsffis0\.90\.9\-Lipschitz with respect to the Euclidean metric, sincer⁡\(x\)=‖x‖2r\(x\)=\\\|x\\\|\_\{2\}is11\-Lipschitz andg⁡\(r\)=sin⁡\(1\+0\.9​r\)g\(r\)=\\sin\(1\+0\.9r\)is0\.90\.9\-Lipschitz, and hence, by composition,f=g∘rf=g\\circ ris0\.90\.9\-Lipschitz\. Inspired by Proposition[2\.5](https://arxiv.org/html/2610.22564#S2.Thmtheorem5), we compute1/τ𝒳​\(τ𝒴−2​RMSEtrain​\(ϕno,𝒟Mtrain\)\)1/\\tau\_\{\\mathcal\{X\}\}\(\\tau\_\{\\mathcal\{Y\}\}\-2\\mathrm\{RMSE\}\_\{\\mathrm\{train\}\}\(\\phi\_\{\\mathrm\{n\}\}^\{o\},\\mathcal\{D\}\_\{M\_\{\\mathrm\{train\}\}\}\)\)and compare it to the empirical Lipschitz constant of the unstable regressors, see Table[7](https://arxiv.org/html/2610.22564#S9.T7)in the Appendix\.

#### 3\.2\.2Sensitivity of the average kernel size to noise

In Figures[5](https://arxiv.org/html/2610.22564#S3.F5)and[6](https://arxiv.org/html/2610.22564#S3.F6)we illustrate the effect of increasing input and target noise of the synthetic regression problem on the average kernel size\. For this we chose a larger dataset size ofM=2\.5​kM=2\.5kand increase the thresholds for feasible set sampling according to the increasing noise level on inputs or outputs\. In Section[9\.1\.3](https://arxiv.org/html/2610.22564#S9.SS1.SSS3)in the Appendix, we report the average kernel size for a noiseless control setting, evaluated the effect of misspecified thresholdsτ𝒳\\tau\_\{\\mathcal\{X\}\}andτ𝒴\\tau\_\{\\mathcal\{Y\}\}and compare the empirical average kernel size with the Bayes RMSE under an additional independence assumption, as well as evaluate Assumption[2\.6](https://arxiv.org/html/2610.22564#S2.Thmtheorem6)on admissible\-pairs\.

0\.10\.10\.20\.20\.30\.30\.40\.40\.50\.50\.60\.60\.70\.70\.80\.80\.90\.911000\.050\.050\.10\.10\.150\.150\.20\.2Input noise levelσx\\sigma\_\{x\}Average kernel sizeFigure 5:Average kernel size as a function of input noise levelσx\\sigma\_\{x\}\. ConstantNmax=300N\_\{\\max\}=300andτ𝒴=0\.03\\tau\_\{\\mathcal\{Y\}\}=0\.03,τ𝒳=2​σx\\tau\_\{\\mathcal\{X\}\}=\\sqrt\{2\}\\sigma\_\{x\}\. Corresponding values ofM′M^\{\\prime\}andτ𝒳\\tau\_\{\\mathcal\{X\}\}are in Table[8](https://arxiv.org/html/2610.22564#S9.T8)in the Appendix\.0\.10\.10\.20\.20\.30\.30\.40\.40\.50\.50\.60\.60\.70\.70\.80\.80\.90\.911000\.10\.10\.20\.2target noise levelσy\\sigma\_\{y\}Average kernel sizeAverage kernel sizeFigure 6:Average kernel size as a function of target noise levelσy\\sigma\_\{y\}\. ConstantNmax=300N\_\{\\max\}=300andτ𝒳=0\.01414\\tau\_\{\\mathcal\{X\}\}=0\.01414, andτ𝒴=σy\\tau\_\{\\mathcal\{Y\}\}=\\sigma\_\{y\}\. Corresponding values ofM′M^\{\\prime\}are in Table[9](https://arxiv.org/html/2610.22564#S9.T9)in the Appendix\.

### 3\.3Classification tasks

For all classification datasets considered, the accuracy bounds provided by Corollary[2\.11](https://arxiv.org/html/2610.22564#S2.Thmtheorem11)in conjunction with Algorithm[1](https://arxiv.org/html/2610.22564#alg1)are provided in Table[5](https://arxiv.org/html/2610.22564#S3.T5)and the parameters used for computation are provided in Table[4](https://arxiv.org/html/2610.22564#S3.T4)below\. We followed the procedure summarized above and outlined in the Appendix in Section[9\.1\.2](https://arxiv.org/html/2610.22564#S9.SS1.SSS2)\. We computed the bounds on the MNIST open\-source dataset from[Torch Vision](https://docs.pytorch.org/vision/main/generated/torchvision.datasets.MNIST.html), the CIFAR\-10 open\-source dataset from[Torch Vision](https://docs.pytorch.org/vision/main/generated/torchvision.datasets.CIFAR10.html), the RESISC45 open\-source dataset[Cheng et al\. \(2017\)](https://arxiv.org/html/2610.22564#bib.bib50)from[TorchGeo](https://docs.torchgeo.org/en/v0.3.1/_modules/torchgeo/datamodules/resisc45.html)and the EUROSAT open\-source dataset[Helber et al\. \(2019\)](https://arxiv.org/html/2610.22564#bib.bib57)from[Torch Vision](https://docs.pytorch.org/vision/main/generated/torchvision.datasets.EuroSAT.html)\. Detailed dataset descriptions, as well as the accuracy of the optimal classifier on the constructed test dataset from the Corollary[2\.11](https://arxiv.org/html/2610.22564#S2.Thmtheorem11), are in Appendix in Section[9\.1\.4](https://arxiv.org/html/2610.22564#S9.SS1.SSS4)\.

Table 4:Parameters for the classification tasks\. Here,MMdenotes the original dataset size,M′M^\{\\prime\}the constructed dataset size generated by Algorithm[1](https://arxiv.org/html/2610.22564#alg1),KKthe number of anchors,NmaxN\_\{\\max\}the maximum number of nearest neighbors andN⁡\(k\)¯\\overline\{N\(k\)\}the mean size of the feasible sets from the test dataset\.∗: for RESISC45 the mean±\\pmthe standard deviation across2020subsets of size3​k3kare:\(τ𝒳\)train=31\.5±0\.5\(\\tau\_\{\\mathcal\{X\}\}\)\_\{\\mathrm\{train\}\}=31\.5\\pm 0\.5,\(τ𝒳\)test=31\.8±0\.7\(\\tau\_\{\\mathcal\{X\}\}\)\_\{\\mathrm\{test\}\}=31\.8\\pm 0\.7,N⁡\(k\)¯=1\.58±0\.08\\overline\{N\(k\)\}=1\.58\\pm 0\.08\.Table 5:Optimal classification accuracy intervals and classifier accuracies\.Theoretical intervals from Corollary[2\.11](https://arxiv.org/html/2610.22564#S2.Thmtheorem11)are reported as percentages; explicitly, the interval is100×\[1−Kersize⁡\(𝒟M′,1\)K,1−1/2​Kersize⁡\(𝒟M′,1\)K\]\.100\\times\\left\[1\-\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},1\)\_\{K\},\\,1\-1/2\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},1\)\_\{K\}\\right\]\.Accuracies,Acc⁡\(𝒟M,ϕ\)\\operatorname\{Acc\}\(\\mathcal\{D\}\_\{M\},\\phi\), for modelsϕn\\phi\_\{n\}withn∈\{1,2,3\}n\\in\\\{1,2,3\\\}are reported on the\[0,100\]\[0,100\]scale in the three right columns\.\(1\): model\(s\) evaluated on a different test split\.∗: for RESISC45 the mean bounds across2020subsets of size3​k3kare reported\.#### 3\.3\.1Aleatoric uncertainty: dataset dependence and model independence of the accuracy bounds

00202040400\.20\.20\.40\.40\.60\.60\.80\.811EpochAccuracyEUROSAT model accuracy

0055101015150\.20\.20\.40\.40\.60\.60\.80\.811EpochMNIST model accuracytrain Accσy=0\\sigma\_\{y\}=0train Accσy=0\.2\\sigma\_\{y\}=0\.2test Accσy=0\\sigma\_\{y\}=0test Accσy=0\.2\\sigma\_\{y\}=0\.21−AK1\-\\text\{AK\}σy=0\\sigma\_\{y\}=01−1/2​AK1\-1/2\\text\{AK\}σy=0\\sigma\_\{y\}=01−AK1\-\\text\{AK\}σy=0\.2\\sigma\_\{y\}=0\.21−1/2​AK1\-1/2\\text\{AK\}σy=0\.2\\sigma\_\{y\}=0\.2

Figure 7:Accuracy of models trained on train datasets of EUROSAT and MNIST with noisy labels withσy=0\.2\\sigma\_\{y\}=0\.2\. The models trained on noisy datasets are evaluated on both the clean and noisy test and train datasets\. The lower and upper bounds from Corollary[2\.11](https://arxiv.org/html/2610.22564#S2.Thmtheorem11), abbreviated as\[1−AK,1−1/2​AK\]\[1\-\\text\{AK\},1\-1/2\\text\{AK\}\], are computed on the noisy,σy=0\.2\\sigma\_\{y\}=0\.2, and clean,σy=0\\sigma\_\{y\}=0, train and test datasets\. The number of anchor samplesKKand the quantiles for computingτ𝒳​\(q\)\\tau\_\{\\mathcal\{X\}\}\(q\)are in Table[4](https://arxiv.org/html/2610.22564#S3.T4)\. The average kernel size is computed with a largerNm​a​x=200N\_\{max\}=200\.Figure[7](https://arxiv.org/html/2610.22564#S3.F7)compares the accuracy of networks trained on noisy versions of EUROSAT and MNIST with the ambiguity\-based accuracy intervals derived from the average kernel size\. We changed the labels ofσy\\sigma\_\{y\}\-fractions of the datasets to a different, random labels\. In both datasets, adding label noise shifts the admissible accuracy range downward\. On MNIST, the clean\-data accuracy bounds are close to perfect accuracy, indicating that the task is nearly unambiguous under the chosen pseudo\-metric on the input space, while the noisy\-data accuracy bounds closely match the observed degradation in train and test accuracy\. On EUROSAT, the clean\-data accuracy bounds are already noticeably below11and reflect a higher baseline level of ambiguity\.

## 4Discussion

The deterministic bounds from Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)and Corollary[2\.11](https://arxiv.org/html/2610.22564#S2.Thmtheorem11)hold for the dataset constructed in Algorithm[1](https://arxiv.org/html/2610.22564#alg1)\. Where a priori knowledge of the input and target noise is unavailable, we selected input thresholds so the average kernel size remained stable with changes in feasible set size\. In these cases, for both regression and classification datasets, our stability analysis across quantiles for choosing input thresholdτ𝒳\\tau\_\{\\mathcal\{X\}\}based on a practical empirical heuristic and feasible set size demonstrated that the bounds can be chosen to be relatively stable\. We emphasize that the resulting kernel\-size accuracy intervals are not an intrinsic property of the dataset alone, but rather, a property of the triple\(𝒟M,d𝒳,d𝒴\)\(\\mathcal\{D\}\_\{M\},d\_\{\\mathcal\{X\}\},d\_\{\\mathcal\{Y\}\}\), and its interpretability depends on how welld𝒳d\_\{\\mathcal\{X\}\}captures task\-relevant indistinguishability and which evaluation metricd𝒴d\_\{\\mathcal\{Y\}\}is used\. After all, the evaluation metric can be optimized to obtain arbitrarily good accuracy[Redmon and Farhadi \(2018\)](https://arxiv.org/html/2610.22564#bib.bib80)\. We chose a wavelet\-based pseudo\-metric for all image\-based tasks to ensure comparability across tasks; however, other metrics may be more relevant to object classification tasks, such as MNIST or CIFAR\-10\.

Regression accuracy bounds:Table[2](https://arxiv.org/html/2610.22564#S3.T2)shows that the framework is applicable to a range of datasets of different sizes and ranging from image to tabular regression tasks\. The bounds in Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)and the regressor errors in Table[3](https://arxiv.org/html/2610.22564#S3.T3)show that the proposed intervals can be nontrivial and, in several cases, are numerically comparable to the performance reported for strong benchmark and published models\. Figure[4](https://arxiv.org/html/2610.22564#S3.F4)illustrates the accuracy\-stability trade\-off predicted by Proposition[2\.5](https://arxiv.org/html/2610.22564#S2.Thmtheorem5)\. The high\-accuracy models have training errors smaller than half of the average kernel size, but this comes at the cost of significantly larger test errors and higher empirical Lipschitz constant estimates,L^\\widehat\{L\}, substantially exceeding the Lipschitz constant of the noiseless function generating the dataset\. The models that satisfy the prescribed accuracy interval on the training set from Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9), achieve lower test errors while maintainingL^\\widehat\{L\}close to the true regularity of the underlying data\-generating function, see Table[6](https://arxiv.org/html/2610.22564#S9.T6)in the Appendix\.

Classification accuracy bounds:Table[4](https://arxiv.org/html/2610.22564#S3.T4)shows that the framework is applicable to a range of datasets of different sizes and image classification tasks\. The accuracy bounds in Corollary[2\.11](https://arxiv.org/html/2610.22564#S2.Thmtheorem11)and the classifier accuracies in Table[5](https://arxiv.org/html/2610.22564#S3.T5)show that the proposed intervals can be nontrivial and, in several cases, provide a descriptive reference scale, but benchmark accuracies on𝒟M\\mathcal\{D\}\_\{M\}, especially under different splits or protocols, are not directly comparable to the bounds on𝒟M′\\mathcal\{D\}\_\{M^\{\\prime\}\}\. The train and test accuracies of the best model for the task of mapping images \(I\) to random classes \(RC\), reported in\([Zhang et al\., 2016](https://arxiv.org/html/2610.22564#bib.bib37), Table 1\), illustrate the lower bound on the generalization gap for classification in Proposition[2\.18](https://arxiv.org/html/2610.22564#S2.Thmtheorem18)\.

Average kernel sizes and aleatoric uncertainty:For the synthetic regression example, Figures[5](https://arxiv.org/html/2610.22564#S3.F5)and[6](https://arxiv.org/html/2610.22564#S3.F6)show that the average kernel sizes increase with increasing input and target noise\. Combined with the model\-independent bounds on empirical error in Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9), this indicates that the average kernel sizes capture increasing aleatoric uncertainty in the regression task\. For MNIST and EUROSAT, Figure[9](https://arxiv.org/html/2610.22564#S9.F9)shows that the average kernel sizes increase with increasing label noise\. Together with Corollary[2\.11](https://arxiv.org/html/2610.22564#S2.Thmtheorem11)and Figure[7](https://arxiv.org/html/2610.22564#S3.F7), this suggests that, under the chosen pseudo\-metric and feasible\-set construction, the resulting accuracy bounds capture a data\-dependent component of aleatoric uncertainty\. Here we note that, in the examples provided whenever we assumed ideal, noiseless targets withτ𝒴=0\\tau\_\{\\mathcal\{Y\}\}=0, our results may underestimate the aleatoric uncertainty of the corresponding tasks\.

## 5Limitations & Future Work

As shown above, the proposed framework can provide realistic accuracy bounds for a wide range of applications and tasks\. Nevertheless, several open points limit its functionality in certain aspects and could be investigated further in future work\.

First, the resulting bounds depend on the pair\(𝒟M,d𝒳\)\(\\mathcal\{D\}\_\{M\},d\_\{\\mathcal\{X\}\}\)and the chosen evaluation metricd𝒴d\_\{\\mathcal\{Y\}\}\. The interpretability of the feasible sets and the resulting average kernel size depend on whether the chosen pseudo\-metricd𝒳d\_\{\\mathcal\{X\}\}captures task\-relevant indistinguishability\. A poor metric may either merge unrelated inputs or fail to detect genuine ambiguity\. In this work, we found that relatively simple metrics can already yield nontrivial bounds\. For image data, metrics induced by transforms need not align with semantic similarity\. Investigating different kinds of metrics, universal feature extractors \(e\.g\., pretrained foundation models\), or expert knowledge\-based feature extractors could enable targeting the task\-relevant features for the bounds more explicitly\.

Second, the feasible set construction depends on the threshold parametersτ𝒳\\tau\_\{\\mathcal\{X\}\}andτ𝒴\\tau\_\{\\mathcal\{Y\}\}\. Ideally, these can be selected from prior knowledge of input and target noise and otherwise, alternatives are selecting the input thresholdτ𝒳\\tau\_\{\\mathcal\{X\}\}with a practical empirical heuristic based on quantiles or selecting the thresholds in order to guarantee a sufficiently small lower bound to the Lipschitz constant in the accuracy\-stability trade\-off from Proposition[2\.5](https://arxiv.org/html/2610.22564#S2.Thmtheorem5); however, Assumption[2\.6](https://arxiv.org/html/2610.22564#S2.Thmtheorem6)may be difficult to verify in practice and further properties or rules for selecting the thresholds in the absence of prior knowledge on input and target noise should be evaluated at a larger scale\.

Third, Algorithm[1](https://arxiv.org/html/2610.22564#alg1)provides finite\-sample approximations of the feasible sets\. If the dataset under\-samples rare but valid targets for a given input, then the empirical average kernel size may underestimate the true spread\. Hence, the lower bound is data\-dependent and may be conservative when the dataset significantly under\-samples rare but valid targets\. An important next step is to provide construction diagnostics with guarantees, including feasible\-set size distributions, singleton fractions, in order to distinguish ambiguity arising from local input neighborhoods from ambiguity induced primarily by the target tolerance\. Here a theoretical direction for future work is to bridge the gap between the ideal distributional analogue quantity and the finite\-sample average kernel size\. This includes consistency of Algorithm[1](https://arxiv.org/html/2610.22564#alg1)asτ𝒳→0\\tau\_\{\\mathcal\{X\}\}\\to 0with growing local sample counts, and an accuracy\-stability frontier obtained by minimizing empirical loss over predictors with prescribed Lipschitz constant\.

Fourth, the optimal accuracy intervals, as in Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9),\[12​Kersize⁡\(𝒟M′,p\)K,Kersize⁡\(𝒟M′,p\)K\]\\left\[\\tfrac\{1\}\{2\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\},\\,\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\}\\right\], can be non\-sharp in some applications where additional assumptions that yield sharper bounds are satisfied\. While these provide a nontrivial model\-independent accuracy range, they may not always identify the exact optimal empirical error due to the reasons outlined above\. The proposed bounds quantify only one component of prediction difficulty, namely the ambiguity of the input\-target multiset in the chosen \(pseudo\-\)metric spaces\. They do not account directly for optimization difficulty or finite model capacity\. The optimum regressor or classifier is explicit in some special cases, in which we provide the corresponding error and accuracy in the Appendix, yet the bounds remain applicable in general metric settings where the anchor\-wise minimization need not admit a closed form and may require solving a separate optimization problem for each anchor\.

## 6Conclusion

We introduced a geometric framework for deriving deterministic, non\-asymptotic bounds on achievable empirical error and accuracy in regression and classification on general metric and pseudo\-metric spaces\. The central quantity, the average kernel size, measures target dispersion within finite feasible sets and yields a model\-independent reference scale for empirical prediction difficulty on the constructed dataset\. A complementary deterministic comparison bound relates empirical loss on the constructed dataset to empirical loss on the original dataset through a graph\-based reassignment error, showing how the discrepancy is controlled by the thresholds, the predictor regularity, and the induced reference weights\. Together with the stability result, the framework shows that fitting ambiguous targets below this scale entails increased local instability\. Under additional probabilistic assumptions, the distributional analogue average kernel size is related to Bayes risk, implies positive generalization gaps below the ambiguity\-compatible level, and admits a finite\-sample concentration guarantee under an ideal conditional\-sampling design\. The average kernel size computed by Algorithm[1](https://arxiv.org/html/2610.22564#alg1)should therefore be interpreted as a computable geometric surrogate for this ideal quantity unless further assumptions justify a statistical consistency claim\. Important directions for future work include task\-dependent pseudo\-metric design and bridging the gap between the ideal sampling theory and the finite\-sample construction used in practice\.

## 7Acknowledgements

N\. M\. Gottschling acknowledges research sponsored by the Laboratory Directed Research and Development Program of Oak Ridge National Laboratory, managed by UT\-Battelle, LLC, for the U\. S\. Department of Energy\. J\. Gawlikowski acknowledges the funding provided by the German Aerospace Center from the department EO Data Science at the Earth Observation Center\. This work was supported by the Helmholtz Association’s Initiative and Networking Fund on the HAICORE \(at\) FZJ partition\. M\. Caprio gratefully acknowledges support from the Prob\_AI Hub and the London Mathematical Society\. ChatGPT 5\.6 Sol was used to assist with proofreading\.

## References

- B\. Adcock and N\. DexterThe gap between theory and practice in function approximation with deep neural networks\.SIAM Journal on Mathematics of Data Science3\(2\),pp\. 624–655\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p4.1)\.
- Adegunet al\.\(2023\)A\. A\. Adegun, S\. Viriri, and J\. TapamoReview of deep learning methods for remote sensing satellite images classification: experimental survey and comparative analysis\.Journal of Big Data10\(1\),pp\. 93\.Cited by:[§9\.1\.4](https://arxiv.org/html/2610.22564#S9.SS1.SSS4.p4.1)\.
- Aliprantis and Border \(2006\)C\. D\. Aliprantis and K\. C\. BorderInfinite dimensional analysis: A Hitchhiker’s Guide\.Springer\.Cited by:[§2\.1](https://arxiv.org/html/2610.22564#S2.SS1.p6.1),[Definition 8\.1](https://arxiv.org/html/2610.22564#S8.Thmtheorem1)\.
- Angelopoulos and Bates \(2023\)A\. N\. Angelopoulos and S\. BatesConformal prediction: a gentle introduction\.Foundations and Trends in Machine Learning16\(4\),pp\. 494–591\.Cited by:[Remark 2\.3](https://arxiv.org/html/2610.22564#S2.Thmtheorem3.p1.1)\.
- Arestov \(1986\)V\. V\. ArestovOptimal recovery of operators and related problems\.Collection of Papers from the All\-Union School on the Theory of Functions,pp\. 3–20\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p2.1)\.
- Arlot and Massart \(2009\)S\. Arlot and P\. MassartData\-driven calibration of penalties for least\-squares regression\.\.Journal of Machine learning research10\(2\)\.Cited by:[§1](https://arxiv.org/html/2610.22564#S1.p8.1)\.
- Arnold \(1979\)S\. F\. ArnoldLinear models with exchangeably distributed errors\.Journal of the American statistical Association74\(365\),pp\. 194–199\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p3.1)\.
- Aubin \(1990\)J\. AubinSet\-valued analysis\.InMutational and Morphological Analysis: Tools for Shape Evolution and Morphogenesis,pp\. 205–264\.Cited by:[§2\.1](https://arxiv.org/html/2610.22564#S2.SS1.p5.3)\.
- Bach \(2017\)F\. BachBreaking the curse of dimensionality with convex neural networks\.Journal of Machine Learning Research18\(19\),pp\. 1–53\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p4.1)\.
- Bartlett and Mendelson \(2002\)P\. L\. Bartlett and S\. MendelsonRademacher and gaussian complexities: risk bounds and structural results\.Journal of machine learning research3\(Nov\),pp\. 463–482\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p3.1)\.
- Becket al\.\(2022\)C\. Beck, A\. Jentzen, and B\. KuckuckFull error analysis for the training of deep neural networks\.Infinite Dimensional Analysis, Quantum Probability and Related Topics25\(02\),pp\. 2150020\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p4.1)\.
- Berger \(1985\)J\. O\. BergerStatistical decision theory and bayesian analysis\.2 edition,Springer\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p5.1)\.
- Bickel and Doksum \(2015\)P\. J\. Bickel and K\. A\. DoksumMathematical statistics: basic ideas and selected topics, volumes i\-ii package\.Chapman and Hall/CRC\.Cited by:[§1](https://arxiv.org/html/2610.22564#S1.p6.2)\.
- Binevet al\.\(2024\)P\. Binev, A\. Bonito, R\. DeVore, and G\. PetrovaOptimal learning\.Calcolo61\(1\),pp\. 15\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p2.1)\.
- Bousquet and Elisseeff \(2002\)O\. Bousquet and A\. ElisseeffStability and generalization\.Journal of Machine Learning Research2,pp\. 499–526\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p7.1)\.
- Chamberlain \(2020\)G\. ChamberlainRobust decision theory and econometrics\.Annual Review of Economics12\(1\),pp\. 239–271\.Cited by:[Remark 2\.3](https://arxiv.org/html/2610.22564#S2.Thmtheorem3.p1.1)\.
- Chenet al\.\(2023\)Q\. Chen, F\. Cao, Y\. Xing, and J\. LiangEvaluating classification model against bayes error rate\.IEEE Transactions on Pattern Analysis and Machine Intelligence45\(8\),pp\. 9639–9653\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p5.1)\.
- Chenet al\.\(2025\)Q\. Chen, F\. Cao, Y\. Xing, and J\. LiangAn efficient bayes error rate estimation method\.Machine Learning114\(6\),pp\. 134\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p5.1)\.
- Chenget al\.\(2017\)G\. Cheng, J\. Han, and X\. LuRemote sensing image scene classification: benchmark and state of the art\.Proceedings of the IEEE105\(10\),pp\. 1865–1883\.External Links:[Document](https://dx.doi.org/10.1109/JPROC.2017.2675998)Cited by:[§3\.3](https://arxiv.org/html/2610.22564#S3.SS3.p1.1),[§9\.1\.4](https://arxiv.org/html/2610.22564#S9.SS1.SSS4.p3.1)\.
- Cherkasskyet al\.\(1999\)V\. Cherkassky, X\. Shao, F\. M\. Mulier, and V\. N\. VapnikModel complexity control for regression using vc generalization bounds\.IEEE transactions on Neural Networks10\(5\),pp\. 1075–1089\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p3.1)\.
- Cohenet al\.\(2009\)A\. Cohen, W\. Dahmen, and R\. DeVoreCompressed sensing and bestkk\-term approximation\.Journal of the American mathematical society22\(1\),pp\. 211–231\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p2.1)\.
- Cohenet al\.\(2022\)A\. Cohen, R\. Devore, G\. Petrova, and P\. WojtaszczykOptimal stable nonlinear approximation\.Foundations of Computational Mathematics22\(3\),pp\. 607–648\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p2.1)\.
- Cover and Hart \(1967\)T\. Cover and P\. HartNearest neighbor pattern classification\.IEEE transactions on information theory13\(1\),pp\. 21–27\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p5.1)\.
- Daubechies \(1992\)I\. DaubechiesTen lectures on wavelets\.SIAM\.Cited by:[§9\.1\.1](https://arxiv.org/html/2610.22564#S9.SS1.SSS1.p1.1)\.
- Der Kiureghian and Ditlevsen \(2009\)A\. Der Kiureghian and O\. DitlevsenAleatory or epistemic? does it matter?\.Structural safety31\(2\),pp\. 105–112\.Cited by:[§1\.1](https://arxiv.org/html/2610.22564#S1.SS1.p2.1)\.
- Devroyeet al\.\(2018\)L\. Devroye, L\. Györfi, G\. Lugosi, and H\. WalkA nearest neighbor estimate of the residual variance\.Electronic Journal of Statistics12,pp\. 1752–1778\.External Links:[Document](https://dx.doi.org/10.1214/18-EJS1438)Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p5.1)\.
- DrivenData \(2021\)DrivenDataMeet the winners of wind\-dependent variables: predict wind speeds of tropical storms\.Note:Accessed: 2026\-06\-12External Links:[Link](https://drivendata.co/blog/wind-dependent-variables-winners/)Cited by:[§9\.1\.3](https://arxiv.org/html/2610.22564#S9.SS1.SSS3.p2.1)\.
- Fano and Hawkins \(1961\)R\. M\. Fano and D\. HawkinsTransmission of information: a statistical theory of communications\.American Journal of Physics29\(11\),pp\. 793–794\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p4.1)\.
- Fu \(2021\)C\. FuPytorch\-cifar\-models\.GitHub\.Note:[https://github\.com/chenyaofo/pytorch\-cifar\-models](https://github.com/chenyaofo/pytorch-cifar-models)Pretrained CIFAR\-10 and CIFAR\-100 model weightsCited by:[§9\.1\.4](https://arxiv.org/html/2610.22564#S9.SS1.SSS4.p2.1)\.
- Gawlikowskiet al\.\(2023\)J\. Gawlikowski, C\. R\. N\. Tassi, M\. Ali, J\. Lee, M\. Humt, J\. Feng, A\. Kruspe, R\. Triebel, P\. Jung, R\. Roscher,et al\.A survey of uncertainty in deep neural networks\.Artificial Intelligence Review56\(Suppl 1\),pp\. 1513–1589\.Cited by:[§1\.1](https://arxiv.org/html/2610.22564#S1.SS1.p2.1),[§2\.2](https://arxiv.org/html/2610.22564#S2.SS2.p5.1)\.
- Gemanet al\.\(1992\)S\. Geman, E\. Bienenstock, and R\. DoursatNeural networks and the bias/variance dilemma\.Neural computation4\(1\),pp\. 1–58\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p4.1),[§2\.3](https://arxiv.org/html/2610.22564#S2.SS3.p3.1)\.
- Gilboa and Schmeidler \(1989\)I\. Gilboa and D\. SchmeidlerMaxmin expected utility with non\-unique prior\.Journal of mathematical economics18\(2\),pp\. 141–153\.Cited by:[Remark 2\.3](https://arxiv.org/html/2610.22564#S2.Thmtheorem3.p1.1)\.
- Gottschlinget al\.\(2025\)N\. M\. Gottschling, V\. Antun, A\. C\. Hansen, and B\. AdcockThe troublesome kernel: on hallucinations, no free lunches, and the accuracy\-stability tradeoff in inverse problems\.SIAM Review67\(1\),pp\. 73–104\.Cited by:[§2\.2](https://arxiv.org/html/2610.22564#S2.SS2.p1.1)\.
- Gottschlinget al\.\(2026\)N\. M\. Gottschling, P\. Campodonico, V\. Antun, and A\. C\. HansenOn the existence of optimal multi\-valued decoders and their accuracy bounds for ill\-posed inverse problems\.European Journal of Applied Mathematics,pp\. 1–33\.Cited by:[Figure 1](https://arxiv.org/html/2610.22564#S1.F1),[Figure 1](https://arxiv.org/html/2610.22564#S1.F1.5.1),[§2\.3](https://arxiv.org/html/2610.22564#S2.SS3.p1.1)\.
- Grinsztajnet al\.\(2022\)L\. Grinsztajn, E\. Oyallon, and G\. VaroquauxWhy do tree\-based models still outperform deep learning on typical tabular data?\.Advances in neural information processing systems35,pp\. 507–520\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p4.1)\.
- Groeneveld \(2019\)D\. C\. GroeneveldCritical heat flux data used to generate the 2006 groeneveld lookup tables\.Technical reportThermalhydraulics Consultants, Inc\.,Deep River, Ontario, Canada\.Note:Manuscript completed July 2016; published January 2019Cited by:[§9\.1\.3](https://arxiv.org/html/2610.22564#S9.SS1.SSS3.p6.2)\.
- Györfiet al\.\(2002\)L\. Györfi, M\. Kohler, A\. Krzyzak, and H\. WalkA distribution\-free theory of nonparametric regression\.Springer\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p6.1)\.
- Hanet al\.\(2022\)K\. Han, Y\. Wang, H\. Chen, X\. Chen, J\. Guo, Z\. Liu, Y\. Tang, A\. Xiao, C\. Xu, Y\. Xu,et al\.A survey on vision transformer\.IEEE transactions on pattern analysis and machine intelligence45\(1\),pp\. 87–110\.Cited by:[§1](https://arxiv.org/html/2610.22564#S1.p5.2)\.
- Helberet al\.\(2019\)P\. Helber, B\. Bischke, A\. Dengel, and D\. BorthEurosat: a novel dataset and deep learning benchmark for land use and land cover classification\.IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing12\(7\),pp\. 2217–2226\.Cited by:[§3\.3](https://arxiv.org/html/2610.22564#S3.SS3.p1.1),[§9\.1\.4](https://arxiv.org/html/2610.22564#S9.SS1.SSS4.p4.1)\.
- Hoeffding \(1994\)W\. HoeffdingProbability inequalities for sums of bounded random variables\.The collected works of Wassily Hoeffding,pp\. 409–426\.Cited by:[§8\.6](https://arxiv.org/html/2610.22564#S8.SS6.p1.1.1)\.
- Horniket al\.\(1989\)K\. Hornik, M\. Stinchcombe, and H\. WhiteMultilayer feedforward networks are universal approximators\.Neural networks2\(5\),pp\. 359–366\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p4.1)\.
- Jeonget al\.\(2023\)M\. Jeong, M\. Cardone, and A\. DytsoDemystifying the optimal performance of multi\-class classification\.Advances in Neural Information Processing Systems36,pp\. 31638–31664\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p5.1)\.
- Johnson and Lindenstrauss \(1984\)W\. B\. Johnson and J\. LindenstraussExtensions of Lipschitz mappings into a Hilbert space 26\.Contemporary mathematics26\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p8.1)\.
- Kallenberg \(2021\)O\. KallenbergFoundations of modern probability\.Springer\.Note:Third editionCited by:[§8](https://arxiv.org/html/2610.22564#S8.p3.1)\.
- Lathuilièreet al\.\(2019\)S\. Lathuilière, P\. Mesejo, X\. Alameda\-Pineda, and R\. HoraudA comprehensive analysis of deep regression\.IEEE transactions on pattern analysis and machine intelligence42\(9\),pp\. 2065–2081\.Cited by:[§1](https://arxiv.org/html/2610.22564#S1.p5.2)\.
- Le Cam \(2012\)L\. Le CamAsymptotic methods in statistical decision theory\.Springer Science & Business Media\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p4.1)\.
- Li \(1994\)W\. LiSharp lipschitz constants for basic optimal solutions and basic feasible solutions of linear programs\.SIAM journal on control and optimization32\(1\),pp\. 140–153\.Cited by:[§2\.1](https://arxiv.org/html/2610.22564#S2.SS1.p5.3)\.
- Magaril\-Il’yaev and Osipenko \(1991\)G\. G\. Magaril\-Il’yaev and K\. Y\. OsipenkoOptimal recovery of functionals based on inaccurate data\.Mat\. Zametki50\(6\),pp\. 85–93\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p2.1)\.
- Maiorov and Pinkus \(1999\)V\. Maiorov and A\. PinkusLower bounds for approximation by mlp neural networks\.Neurocomputing25\(1\-3\),pp\. 81–91\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p4.1)\.
- McElfreshet al\.\(2023\)D\. McElfresh, S\. Khandagale, J\. Valverde, V\. Prasad C, G\. Ramakrishnan, M\. Goldblum, and C\. WhiteWhen do neural nets outperform boosted trees on tabular data?\.Advances in Neural Information Processing Systems36,pp\. 76336–76369\.Cited by:[§1](https://arxiv.org/html/2610.22564#S1.p5.2)\.
- McShane \(1934\)E\. J\. McShaneExtension of range of functions\.Bulletin of the American Mathematical Society40\(12\),pp\. 837–842\.Cited by:[§2\.2](https://arxiv.org/html/2610.22564#S2.SS2.p11.1)\.
- Micchelli and Rivlin \(1977\)C\. A\. Micchelli and T\. J\. RivlinA survey of optimal recovery\.Optimal estimation in approximation theory,pp\. 1–54\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p2.1)\.
- Murphy \(2022\)K\. P\. MurphyProbabilistic machine learning: an introduction\.MIT press\.Cited by:[§1\.1](https://arxiv.org/html/2610.22564#S1.SS1.p2.1),[§1\.1](https://arxiv.org/html/2610.22564#S1.SS1.p4.1),[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p5.1),[§1](https://arxiv.org/html/2610.22564#S1.p6.2),[§1](https://arxiv.org/html/2610.22564#S1.p8.1)\.
- National Aeronautics and Space Administration \(2024\)National Aeronautics and Space AdministrationTropical cyclone wind estimation competition\.External Links:[Document](https://dx.doi.org/10.34911/rdnt.1x18sn),[Link](https://doi.org/10.34911/rdnt.1x18sn)Cited by:[§9\.1\.3](https://arxiv.org/html/2610.22564#S9.SS1.SSS3.p2.1)\.
- Nealet al\.\(2018\)B\. Neal, S\. Mittal, A\. Baratin, V\. Tantia, M\. Scicluna, S\. Lacoste\-Julien, and I\. MitliagkasA modern take on the bias\-variance tradeoff in neural networks\.arXiv preprint arXiv:1810\.08591\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p5.1)\.
- Northcuttet al\.\(2021\)C\. G\. Northcutt, A\. Athalye, and J\. MuellerPervasive label errors in test sets destabilize machine learning benchmarks\.arXiv preprint arXiv:2103\.14749\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p4.1)\.
- Panet al\.\(2024\)B\. Pan, W\. Liu, P\. Zhou, and D\. O\. WuPredicting the compressive strength of recycled concrete using ensemble learning model\.IEEE Access13,pp\. 2958–2969\.Cited by:[§9\.1\.3](https://arxiv.org/html/2610.22564#S9.SS1.SSS3.p5.1)\.
- Park \(2000\)C\. ParkEffect of axial heat flux distribution on critical heat flux\.Technical reportTechnical ReportKAERI/TR\-1665/2000,Korea Atomic Energy Research Institute,Daejeon, Republic of Korea\.Cited by:[§3\.2](https://arxiv.org/html/2610.22564#S3.SS2.p1.1),[§9\.1\.3](https://arxiv.org/html/2610.22564#S9.SS1.SSS3.p6.1)\.
- Pedregosaet al\.\(2011\)F\. Pedregosa, G\. Varoquaux, A\. Gramfort, V\. Michel, B\. Thirion, O\. Grisel, M\. Blondel, P\. Prettenhofer, R\. Weiss, V\. Dubourg,et al\.Scikit\-learn: machine learning in python\.the Journal of machine Learning research12,pp\. 2825–2830\.Cited by:[§9\.1\.2](https://arxiv.org/html/2610.22564#S9.SS1.SSS2.p1.2),[§9\.1\.2](https://arxiv.org/html/2610.22564#S9.SS1.SSS2.p4.1)\.
- Petersen and Voigtlaender \(2018\)P\. Petersen and F\. VoigtlaenderOptimal approximation of piecewise smooth functions using deep relu neural networks\.Neural Networks108,pp\. 296–330\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p4.1)\.
- Pinkus \(2012\)A\. PinkusN\-widths in approximation theory\.Vol\.7,Springer Science & Business Media\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p2.1)\.
- Qiet al\.\(2020\)J\. Qi, J\. Du, S\. M\. Siniscalchi, X\. Ma, and C\. LeeAnalyzing upper bounds on mean absolute errors for deep neural network\-based vector\-to\-vector regression\.IEEE Transactions on Signal Processing68,pp\. 3411–3422\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p3.1)\.
- Redmon and Farhadi \(2018\)J\. Redmon and A\. FarhadiYolov3: An incremental improvement\.arXiv preprint arXiv:1804\.02767\.Cited by:[§4](https://arxiv.org/html/2610.22564#S4.p1.1)\.
- Rufet al\.\(2018\)C\. S\. Ruf, S\. Gleason, and D\. S\. McKagueAssessment of CYGNSS wind speed retrieval uncertainty\.IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing12\(1\),pp\. 87–97\.Cited by:[§9\.1\.3](https://arxiv.org/html/2610.22564#S9.SS1.SSS3.p2.1)\.
- Segal \(2004\)M\. R\. SegalMachine learning benchmarks and random forest regression\.Cited by:[§1](https://arxiv.org/html/2610.22564#S1.p5.2)\.
- Shwartz\-Ziv and Armon \(2022\)R\. Shwartz\-Ziv and A\. ArmonTabular data: deep learning is not all you need\.Information Fusion81,pp\. 84–90\.Cited by:[§1](https://arxiv.org/html/2610.22564#S1.p5.2)\.
- Simpson \(1974\)R\. H\. SimpsonThe hurricane disaster—potential scale\.Weatherwise27\(4\),pp\. 169–186\.Cited by:[§9\.1\.3](https://arxiv.org/html/2610.22564#S9.SS1.SSS3.p2.1),[§9\.1\.3](https://arxiv.org/html/2610.22564#S9.SS1.SSS3.p3.1)\.
- Stewartet al\.\(2025\)A\. J\. Stewart, C\. Robinson, I\. A\. Corley, A\. Ortiz, J\. M\. Lavista Ferres, and A\. BanerjeeTorchgeo: deep learning with geospatial data\.ACM Transactions on Spatial Algorithms and Systems11\(4\),pp\. 1–28\.Cited by:[§9\.1\.3](https://arxiv.org/html/2610.22564#S9.SS1.SSS3.p2.1)\.
- Stone \(1977\)C\. J\. StoneConsistent nonparametric regression\.The Annals of Statistics5\(4\),pp\. 595–620\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p6.1)\.
- Torn and Snyder \(2012\)R\. D\. Torn and C\. SnyderUncertainty of tropical cyclone best\-track information\.Weather and Forecasting27\(3\),pp\. 715–729\.Cited by:[§9\.1\.3](https://arxiv.org/html/2610.22564#S9.SS1.SSS3.p2.1)\.
- Traubet al\.\(1983\)J\. F\. Traub, G\. W\. Wasilkowski, and H\. WoźniakowskiInformation, uncertainty, complexity\.Addison\-Wesley Reading, MA\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p2.1)\.
- Tsanas and Xifara \(2012\)A\. Tsanas and A\. XifaraAccurate quantitative estimation of energy performance of residential buildings using statistical machine learning tools\.Energy and buildings49,pp\. 560–567\.Cited by:[§3\.2](https://arxiv.org/html/2610.22564#S3.SS2.p1.1),[§9\.1\.3](https://arxiv.org/html/2610.22564#S9.SS1.SSS3.p4.1)\.
- Tsybakov \(2003\)A\. B\. TsybakovIntroduction à l’estimation non paramétrique\.Vol\.41,Springer Science & Business Media\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p4.1)\.
- Ushioet al\.\(2026\)R\. Ushio, T\. Ishida, and M\. SugiyamaPractical estimation of the optimal classification error with soft labels and calibration\.InInternational Conference on Learning Representations,Vol\.2026,pp\. 1604–1643\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p5.1)\.
- Vapnik \(1999\)V\. N\. VapnikAn overview of statistical learning theory\.IEEE transactions on neural networks10\(5\),pp\. 988–999\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p3.1)\.
- Vapnik \(2006\)V\. VapnikEstimation of dependences based on empirical data\.Springer Science & Business Media\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p3.1)\.
- Yanget al\.\(2020\)Z\. Yang, Y\. Yu, C\. You, J\. Steinhardt, and Y\. MaRethinking bias\-variance trade\-off for generalization of neural networks\.InInternational Conference on Machine Learning,pp\. 10767–10777\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p5.1)\.
- Yarotsky \(2017\)D\. YarotskyError bounds for approximations with deep relu networks\.Neural networks94,pp\. 103–114\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p4.1)\.
- Yeh \(1998\)I\. YehModeling of strength of high\-performance concrete using artificial neural networks\.Cement and Concrete research28\(12\),pp\. 1797–1808\.Cited by:[§3\.2](https://arxiv.org/html/2610.22564#S3.SS2.p1.1),[§9\.1\.3](https://arxiv.org/html/2610.22564#S9.SS1.SSS3.p5.1)\.
- Žegklitz and Pošík \(2017\)J\. Žegklitz and P\. PošíkSymbolic regression algorithms with built\-in linear regression\.arXiv preprint arXiv:1701\.03641\.Cited by:[§9\.1\.3](https://arxiv.org/html/2610.22564#S9.SS1.SSS3.p4.1)\.
- Zhanget al\.\(2016\)C\. Zhang, S\. Bengio, M\. Hardt, B\. Recht, and O\. VinyalsUnderstanding deep learning requires rethinking generalization\.arXiv preprint arXiv:1611\.03530\.Cited by:[§1\.1](https://arxiv.org/html/2610.22564#S1.SS1.p4.1),[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p4.1),[§4](https://arxiv.org/html/2610.22564#S4.p3.1)\.
- Zhanget al\.\(2021\)C\. Zhang, S\. Bengio, M\. Hardt, B\. Recht, and O\. VinyalsUnderstanding deep learning \(still\) requires rethinking generalization\.Communications of the ACM64\(3\),pp\. 107–115\.Cited by:[§1\.1](https://arxiv.org/html/2610.22564#S1.SS1.p4.1),[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p4.1)\.
- Zhang \(2009\)T\. ZhangSome sharp performance bounds for least squares regression with l 1 regularization\.Annals of Statistics37\(5A\),pp\. 2109 –2144\.Cited by:[§1\.3](https://arxiv.org/html/2610.22564#S1.SS3.p3.1)\.

## 8Proofs

After introducing preliminaries, we prove the main results\. Each set\-valued mappingϕ:𝒳⇉𝒴\\phi:\\mathcal\{X\}\\rightrightarrows\\mathcal\{Y\}has two natural inverses\. Theupper inverseϕu\\phi^\{u\}\(also called thestrong inverse\) of a subsetAAof𝒴\\mathcal\{Y\}is defined by

ϕu​\(A\)=\{x∈𝒳:ϕ⁡\(x\)⊂A\}\.\\phi^\{u\}\(A\)=\\\{x\\in\\mathcal\{X\}:\\phi\(x\)\\subset A\\\}\.Thelower inverseϕl\\phi^\{l\}\(also called theweak inverse\) is defined by

ϕl​\(A\)=\{x∈𝒳:ϕ⁡\(x\)∩A≠∅\}\.\\phi^\{l\}\(A\)=\\\{x\\in\\mathcal\{X\}:\\phi\(x\)\\cap A\\neq\\emptyset\\\}\.Recall that a neighborhood of a setAAis any setBBfor which there is an open setVVsatisfyingA⊂V⊂BA\\subset V\\subset B\. Any open setVVthat satisfiesA⊂VA\\subset Vis called an open neighborhood ofAA\.

###### Definition 8\.1\(\[[Aliprantis and Border, 2006](https://arxiv.org/html/2610.22564#bib.bib9), Definition 17\.2\]\)\.

A set\-valued mappingϕ:𝒳⇉𝒴\\phi:\\mathcal\{X\}\\rightrightarrows\\mathcal\{Y\}between topological spaces is:

*upper hemicontinuous*atxxif for every neighborhoodUUofϕ⁡\(x\)\\phi\(x\), there is a neighborhoodVVofxxsuch thatz∈Vz\\in Vimpliesϕ⁡\(z\)⊂U\\phi\(z\)\\subset Uor, equivalently, ifϕu​\(U\)\\phi^\{u\}\(U\)is a neighborhood ofxxin𝒳\\mathcal\{X\}\.

*lower hemicontinuous*atxxif for every open setUUthat meetsϕ⁡\(x\)\\phi\(x\), i\.e\.ϕ⁡\(x\)∩U≠∅\\phi\(x\)\\cap U\\neq\\emptyset, there is a neighborhoodVVofxxsuch thatz∈Vz\\in Vimpliesϕ⁡\(z\)∩U≠∅\\phi\(z\)\\cap U\\neq\\emptyset, equivalently, the lower inverse imageϕl​\(U\)\\phi^\{l\}\(U\)is a neighborhood ofxx\.

*continuous*atxxif it is both upper and lower hemicontinuous atxx\.

As with functions, we sayϕ\\phiis upper or lower hemicontinuous onXX, if it is upper or lower hemicontinuous at every point ofXX\. It is continuous if it is continuous at each point\.

###### Definition 8\.2\(Regular conditional distribution\)\.

LetZ:Ω→SZ:\\Omega\\to SandY:Ω→TY:\\Omega\\to Tbe random variables, whereSSandTTare measurable spaces withσ\\sigma\-algebrasℬ⁡\(S\)\\mathcal\{B\}\(S\)andℬ⁡\(T\)\\mathcal\{B\}\(T\), respectively\. A regular conditional distribution ofYYgivenZZis a Markov kernel

K:S×ℬ⁡\(T\)→\[0,1\]K:S\\times\\mathcal\{B\}\(T\)\\to\[0,1\]such that

1. 1\.for everyz∈Sz\\in S, the mapA↦K⁡\(z,A\)A\\mapsto K\(z,A\)is a probability measure on\(T,ℬ⁡\(T\)\)\(T,\\mathcal\{B\}\(T\)\);
2. 2\.for everyA∈ℬ⁡\(T\)A\\in\\mathcal\{B\}\(T\), the mapz↦K⁡\(z,A\)z\\mapsto K\(z,A\)isℬ⁡\(S\)\\mathcal\{B\}\(S\)\-measurable;
3. 3\.for everyA∈ℬ⁡\(T\)A\\in\\mathcal\{B\}\(T\)andB∈ℬ⁡\(S\)B\\in\\mathcal\{B\}\(S\), ℙ⁡\(Y∈A,Z∈B\)=∫BK⁡\(z,A\)​ℙZ​\(𝑑z\)\.\\mathbb\{P\}\(Y\\in A,\\ Z\\in B\)=\\int\_\{B\}K\(z,A\)\\,\\mathbb\{P\}\_\{Z\}\(dz\)\.

Regular conditional distributions do not always exist\. The following positive result guarantees that a regular conditional distribution exists, see[Kallenberg \[2021\]](https://arxiv.org/html/2610.22564#bib.bib5)\.

###### Theorem 8\.3\(Existence of regular conditional distributions\)\.

IfSSandTTare standard Borel spaces, then a regular conditional distribution ofYYgivenZZexists and is unique up toℙZ\\mathbb\{P\}\_\{Z\}\-almost everywhere equality\.

### 8\.1Proof of Proposition[2\.5](https://arxiv.org/html/2610.22564#S2.Thmtheorem5)

###### Proof\.

Sinced𝒴H​\(ϕ⁡\(x\),\{y\}\)<ηd\_\{\\mathcal\{Y\}\}^\{H\}\(\\phi\(x\),\\\{y\\\}\)<\\eta, we chooseδ\>0\\delta\>0such thatd𝒴H​\(ϕ⁡\(x\),\{y\}\)\+δ<ηd\_\{\\mathcal\{Y\}\}^\{H\}\(\\phi\(x\),\\\{y\\\}\)\+\\delta<\\eta\. The set

Uδ:=\{v∈𝒴:infz∈ϕ⁡\(x\)d𝒴​\(v,z\)<δ\}U\_\{\\delta\}:=\\\{v\\in\\mathcal\{Y\}:\\inf\_\{z\\in\\phi\(x\)\}d\_\{\\mathcal\{Y\}\}\(v,z\)<\\delta\\\}is an open neighborhood ofϕ⁡\(x\)\\phi\(x\)\. By upper hemicontinuity ofϕ\\phiatxx, there exists a neighborhoodB1⊂ℳ2B\_\{1\}\\subset\\mathcal\{M\}\_\{2\}ofxxsuch thatϕ⁡\(x~\)⊂Uδ\\phi\(\\tilde\{x\}\)\\subset U\_\{\\delta\}for allx~∈B1\\tilde\{x\}\\in B\_\{1\}\. Hence

supu∈ϕ⁡\(x~\)d𝒴​\(u,y\)<ηfor all​x~∈B1\.\\sup\_\{u\\in\\phi\(\\tilde\{x\}\)\}d\_\{\\mathcal\{Y\}\}\(u,y\)<\\eta\\qquad\\text\{for all \}\\tilde\{x\}\\in B\_\{1\}\.Together withsupv∈ϕ⁡\(x′\)d𝒴​\(v,y′′\)<η\\sup\_\{v\\in\\phi\(x^\{\\prime\}\)\}d\_\{\\mathcal\{Y\}\}\(v,y^\{\\prime\\prime\}\)<\\eta, the reverse triangle inequality gives, for everyx~∈B1\\tilde\{x\}\\in B\_\{1\},

d𝒴H​\(ϕ⁡\(x~\),ϕ⁡\(x′\)\)≥d𝒴​\(y,y′′\)−supu∈ϕ⁡\(x~\)d𝒴​\(u,y\)−supv∈ϕ⁡\(x′\)d𝒴​\(v,y′′\)\>d𝒴​\(y,y′′\)−2​η\.\\displaystyle d\_\{\\mathcal\{Y\}\}^\{H\}\(\\phi\(\\tilde\{x\}\),\\phi\(x^\{\\prime\}\)\)\\geq d\_\{\\mathcal\{Y\}\}\(y,y^\{\\prime\\prime\}\)\-\\sup\_\{u\\in\\phi\(\\tilde\{x\}\)\}d\_\{\\mathcal\{Y\}\}\(u,y\)\-\\sup\_\{v\\in\\phi\(x^\{\\prime\}\)\}d\_\{\\mathcal\{Y\}\}\(v,y^\{\\prime\\prime\}\)\>d\_\{\\mathcal\{Y\}\}\(y,y^\{\\prime\\prime\}\)\-2\\eta\.Sinced𝒳​\(x,x′\)<τ𝒳d\_\{\\mathcal\{X\}\}\(x,x^\{\\prime\}\)<\\tau\_\{\\mathcal\{X\}\}, there exists an open ballB2B\_\{2\}centered atxxsuch thatx′∉B2x^\{\\prime\}\\notin B\_\{2\}andd𝒳​\(x~,x′\)<τ𝒳d\_\{\\mathcal\{X\}\}\(\\tilde\{x\},x^\{\\prime\}\)<\\tau\_\{\\mathcal\{X\}\}for allx~∈B2\\tilde\{x\}\\in B\_\{2\}\. SetB:=B1∩B2B:=B\_\{1\}\\cap B\_\{2\}, which is not empty asx∈Bx\\in B\. Then, for everyx~∈B\\tilde\{x\}\\in Band everyϵ≥τ𝒳\\epsilon\\geq\\tau\_\{\\mathcal\{X\}\}, we have that0<d𝒳​\(x~,x′\)<τ𝒳0<d\_\{\\mathcal\{X\}\}\(\\tilde\{x\},x^\{\\prime\}\)<\\tau\_\{\\mathcal\{X\}\}, asx′∉B2x^\{\\prime\}\\notin B\_\{2\}andx~∈B⊂B2\\tilde\{x\}\\in B\\subset B\_\{2\}andd𝒳d\_\{\\mathcal\{X\}\}is a metric\. Thus, the pointx′x^\{\\prime\}is admissible in the definition ofLϵ​\(ϕ,x~\)L^\{\\epsilon\}\(\\phi,\\tilde\{x\}\)\. Therefore,

Lϵ​\(ϕ,x~\)≥d𝒴H​\(ϕ⁡\(x~\),ϕ⁡\(x′\)\)d𝒳​\(x~,x′\)\>d𝒴​\(y,y′′\)−2​ητ𝒳,\\displaystyle L^\{\\epsilon\}\(\\phi,\\tilde\{x\}\)\\geq\\frac\{d\_\{\\mathcal\{Y\}\}^\{H\}\(\\phi\(\\tilde\{x\}\),\\phi\(x^\{\\prime\}\)\)\}\{d\_\{\\mathcal\{X\}\}\(\\tilde\{x\},x^\{\\prime\}\)\}\>\\frac\{d\_\{\\mathcal\{Y\}\}\(y,y^\{\\prime\\prime\}\)\-2\\eta\}\{\\tau\_\{\\mathcal\{X\}\}\},which proves the result\. ∎

### 8\.2Proof of Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)

###### Proof\.

Let

FxkN⁡\(k\)=\{yk,n\}n=1N⁡\(k\),k=1,…,K,F\_\{x\_\{k\}\}^\{N\(k\)\}=\\\{y\_\{k,n\}\\\}\_\{n=1\}^\{N\(k\)\},\\qquad k=1,\\dots,K,be the finite feasible sets returned by Algorithm[1](https://arxiv.org/html/2610.22564#alg1), and let𝒟M′=\{\(yk,n,xk\):1≤k≤K,1≤n≤N\(k\)\}\\mathcal\{D\}\_\{M^\{\\prime\}\}=\\\{\(y\_\{k,n\},x\_\{k\}\):1\\leq k\\leq K,\\ 1\\leq n\\leq N\(k\)\\\}withM′=∑k=1KN⁡\(k\)M^\{\\prime\}=\\sum\_\{k=1\}^\{K\}N\(k\)\. Letϕ:ℳ2⇉𝒴\\phi:\\mathcal\{M\}\_\{2\}\\rightrightarrows\\mathcal\{Y\}be any regressor\.

Step 1: Lower bound by half of the average kernel size\.Fixk∈\{1,…,K\}k\\in\\\{1,\\dots,K\\\}and1≤n<n′≤N⁡\(k\)1\\leq n<n^\{\\prime\}\\leq N\(k\)\. For anyz¯∈ϕ⁡\(xk\)\\bar\{z\}\\in\\phi\(x\_\{k\}\), the triangle inequality gives

d𝒴​\(yk,n,yk,n′\)≤d𝒴​\(yk,n,z¯\)\+d𝒴​\(z¯,yk,n′\)\.d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,n^\{\\prime\}\}\)\\leq d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},\\bar\{z\}\)\+d\_\{\\mathcal\{Y\}\}\(\\bar\{z\},y\_\{k,n^\{\\prime\}\}\)\.Since

d𝒴H​\(\{yk,n\},ϕ⁡\(xk\)\)=supz¯∈ϕ⁡\(xk\)d𝒴​\(yk,n,z¯\),d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{k,n\}\\\},\\phi\(x\_\{k\}\)\)=\\sup\_\{\\bar\{z\}\\in\\phi\(x\_\{k\}\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},\\bar\{z\}\),we obtain

d𝒴​\(yk,n,yk,n′\)≤d𝒴H​\(\{yk,n\},ϕ⁡\(xk\)\)\+d𝒴H​\(\{yk,n′\},ϕ⁡\(xk\)\)\.d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,n^\{\\prime\}\}\)\\leq d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{k,n\}\\\},\\phi\(x\_\{k\}\)\)\+d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{k,n^\{\\prime\}\}\\\},\\phi\(x\_\{k\}\)\)\.Forp≥1p\\geq 1, the convexity ofa↦apa\\mapsto a^\{p\}implies\(a\+b\)p≤2p−1​\(ap\+bp\)\(a\+b\)^\{p\}\\leq 2^\{p\-1\}\(a^\{p\}\+b^\{p\}\)fora,b≥0a,b\\geq 0\. Consequently,

d𝒴​\(yk,n,yk,n′\)p≤2p−1​\(d𝒴H​\(\{yk,n\},ϕ⁡\(xk\)\)p\+d𝒴H​\(\{yk,n′\},ϕ⁡\(xk\)\)p\)\.d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,n^\{\\prime\}\}\)^\{p\}\\leq 2^\{p\-1\}\\left\(d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{k,n\}\\\},\\phi\(x\_\{k\}\)\)^\{p\}\+d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{k,n^\{\\prime\}\}\\\},\\phi\(x\_\{k\}\)\)^\{p\}\\right\)\.Summing over all unordered pairs1≤n<n′≤N⁡\(k\)1\\leq n<n^\{\\prime\}\\leq N\(k\), and observing that each indexnnoccurs in exactlyN⁡\(k\)−1N\(k\)\-1such pairs, gives

21\{N\(k\)\>1\}N⁡\(k\)−1​∑1≤n<n′≤N⁡\(k\)d𝒴​\(yk,n,yk,n′\)p≤2p​∑n=1N⁡\(k\)d𝒴H​\(\{yk,n\},ϕ⁡\(xk\)\)p\.\\frac\{2\\,\\mathds\{1\}\_\{\\\{N\(k\)\>1\\\}\}\}\{N\(k\)\-1\}\\sum\_\{1\\leq n<n^\{\\prime\}\\leq N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,n^\{\\prime\}\}\)^\{p\}\\leq 2^\{p\}\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{k,n\}\\\},\\phi\(x\_\{k\}\)\)^\{p\}\.WhenN⁡\(k\)≤1N\(k\)\\leq 1, the left\-hand side is zero by definition, so the inequality remains valid\. Summing overk=1,…,Kk=1,\\dots,Kand dividing by2p​M′2^\{p\}M^\{\\prime\}, we obtain

12p​M′​∑k=1K21\{N\(k\)\>1\}N⁡\(k\)−1​∑1≤n<n′≤N⁡\(k\)d𝒴​\(yk,n,yk,n′\)p≤1M′​∑k=1K∑n=1N⁡\(k\)d𝒴H​\(\{yk,n\},ϕ⁡\(xk\)\)p\.\\frac\{1\}\{2^\{p\}M^\{\\prime\}\}\\sum\_\{k=1\}^\{K\}\\frac\{2\\,\\mathds\{1\}\_\{\\\{N\(k\)\>1\\\}\}\}\{N\(k\)\-1\}\\sum\_\{1\\leq n<n^\{\\prime\}\\leq N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,n^\{\\prime\}\}\)^\{p\}\\leq\\frac\{1\}\{M^\{\\prime\}\}\\sum\_\{k=1\}^\{K\}\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{k,n\}\\\},\\phi\(x\_\{k\}\)\)^\{p\}\.By the definition of the empirical loss and of the average kernel size, this is

12p​Kersize⁡\(𝒟M′,p\)Kp≤ℒ​\(𝒟M′,ϕ,p\)p\.\\frac\{1\}\{2^\{p\}\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\}^\{p\}\\leq\\mathcal\{L\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi,p\)^\{p\}\.Takingpp\-th roots yields

12​Kersize⁡\(𝒟M′,p\)K≤ℒ⁡\(𝒟M′,ϕ,p\)\.\\frac\{1\}\{2\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\}\\leq\\mathcal\{L\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi,p\)\.Sinceϕ\\phiwas arbitrary, the first claim follows\.

Step 2: Existence of an optimal regressor\.For eachk∈\{1,…,K\}k\\in\\\{1,\\dots,K\\\}, define

fk​\(z\):=1N⁡\(k\)​∑n=1N⁡\(k\)d𝒴​\(yk,n,z\)p,z∈𝒴\.f\_\{k\}\(z\):=\\frac\{1\}\{N\(k\)\}\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},z\)^\{p\},\\qquad z\\in\\mathcal\{Y\}\.The functionfkf\_\{k\}is continuous\. We next show that it attains its minimum\. Let

rk:=max1≤n,n′≤N⁡\(k\)⁡d𝒴​\(yk,n,yk,n′\)\.r\_\{k\}:=\\max\_\{1\\leq n,n^\{\\prime\}\\leq N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,n^\{\\prime\}\}\)\.Since the group is finite,rk<∞r\_\{k\}<\\infty\. Ifd𝒴​\(z,yk,1\)\>2​rkd\_\{\\mathcal\{Y\}\}\(z,y\_\{k,1\}\)\>2r\_\{k\}, then, for everynn,

d𝒴​\(z,yk,n\)≥d𝒴​\(z,yk,1\)−d𝒴​\(yk,1,yk,n\)\>2​rk−rk=rk\.d\_\{\\mathcal\{Y\}\}\(z,y\_\{k,n\}\)\\geq d\_\{\\mathcal\{Y\}\}\(z,y\_\{k,1\}\)\-d\_\{\\mathcal\{Y\}\}\(y\_\{k,1\},y\_\{k,n\}\)\>2r\_\{k\}\-r\_\{k\}=r\_\{k\}\.Hence,fk​\(z\)\>rkpf\_\{k\}\(z\)\>r\_\{k\}^\{p\}\. On the other hand,

fk​\(yk,1\)=1N⁡\(k\)​∑n=1N⁡\(k\)d𝒴​\(yk,n,yk,1\)p≤rkp\.f\_\{k\}\(y\_\{k,1\}\)=\\frac\{1\}\{N\(k\)\}\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,1\}\)^\{p\}\\leq r\_\{k\}^\{p\}\.Therefore every minimizer offkf\_\{k\}lies in the closed ballB¯d𝒴​\(yk,1,2​rk\)\\overline\{B\}\_\{d\_\{\\mathcal\{Y\}\}\}\(y\_\{k,1\},2r\_\{k\}\)\. This ball is closed and bounded, and hence compact by Assumption[2\.1](https://arxiv.org/html/2610.22564#S2.Thmtheorem1)\. Sincefkf\_\{k\}is continuous, it attains its minimum on this compact set\. Thus, we may choose

zk∈arg⁡minz∈𝒴​fk​\(z\)\.z\_\{k\}\\in\\arg\\min\_\{z\\in\\mathcal\{Y\}\}f\_\{k\}\(z\)\.Step 3: Characterization of the unrestricted empirical optimal regressor\.Fixkk\. For any nonempty prediction setA⊂𝒴A\\subset\\mathcal\{Y\},

d𝒴H​\(\{yk,n\},A\)≥infz∈Ad𝒴​\(yk,n,z\)d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{k,n\}\\\},A\)\\geq\\inf\_\{z\\in A\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},z\)for eachnn\. More importantly, since

d𝒴H​\(\{yk,n\},A\)=max⁡\{infa∈Ad𝒴​\(yk,n,a\),supa∈Ad𝒴​\(yk,n,a\)\},d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{k,n\}\\\},A\)=\\max\\left\\\{\\inf\_\{a\\in A\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},a\),\\sup\_\{a\\in A\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},a\)\\right\\\},we have, for everynn,

d𝒴H​\(\{yk,n\},A\)≥d𝒴​\(yk,n,a\)d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{k,n\}\\\},A\)\\geq d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},a\)for everya∈Aa\\in A\. Consequently,

∑n=1N⁡\(k\)d𝒴H​\(\{yk,n\},A\)p≥∑n=1N⁡\(k\)d𝒴​\(yk,n,a\)p\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{k,n\}\\\},A\)^\{p\}\\geq\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},a\)^\{p\}for everya∈Aa\\in A, and therefore

∑n=1N⁡\(k\)d𝒴H​\(\{yk,n\},A\)p≥infz∈𝒴∑n=1N⁡\(k\)d𝒴​\(yk,n,z\)p\.\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{k,n\}\\\},A\)^\{p\}\\geq\\inf\_\{z\\in\\mathcal\{Y\}\}\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},z\)^\{p\}\.By the definition ofzkz\_\{k\},

infz∈𝒴∑n=1N⁡\(k\)d𝒴​\(yk,n,z\)p=∑n=1N⁡\(k\)d𝒴​\(yk,n,zk\)p\.\\inf\_\{z\\in\\mathcal\{Y\}\}\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},z\)^\{p\}=\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},z\_\{k\}\)^\{p\}\.Equality is attained by the singleton prediction setA=\{zk\}A=\\\{z\_\{k\}\\\}\. Since the anchor pointsx1,…,xKx\_\{1\},\\dots,x\_\{K\}are pairwise positively separated, the values of a regressor at the different anchors can be prescribed independently\. Hence the unrestricted empirical optimal regressor attains

R∗p:=infϕℒ​\(𝒟M′,ϕ,p\)p=1M′​∑k=1K∑n=1N⁡\(k\)d𝒴​\(yk,n,zk\)p\.R\_\{\*\}^\{p\}:=\\inf\_\{\\phi\}\\mathcal\{L\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi,p\)^\{p\}=\\frac\{1\}\{M^\{\\prime\}\}\\sum\_\{k=1\}^\{K\}\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},z\_\{k\}\)^\{p\}\.
Step 4: Upper bound by the average kernel size\.FixkkwithN⁡\(k\)≥2N\(k\)\\geq 2\. By the minimizing property ofzkz\_\{k\}, for everyj∈\{1,…,N⁡\(k\)\}j\\in\\\{1,\\dots,N\(k\)\\\},

∑n=1N⁡\(k\)d𝒴​\(yk,n,zk\)p≤∑n=1N⁡\(k\)d𝒴​\(yk,n,yk,j\)p\.\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},z\_\{k\}\)^\{p\}\\leq\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,j\}\)^\{p\}\.Averaging this inequality overj=1,…,N⁡\(k\)j=1,\\dots,N\(k\)gives

∑n=1N⁡\(k\)d𝒴​\(yk,n,zk\)p≤1N⁡\(k\)​∑j=1N⁡\(k\)∑n=1N⁡\(k\)d𝒴​\(yk,n,yk,j\)p\.\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},z\_\{k\}\)^\{p\}\\leq\\frac\{1\}\{N\(k\)\}\\sum\_\{j=1\}^\{N\(k\)\}\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,j\}\)^\{p\}\.The diagonal terms vanish, and symmetry of the metric implies

∑j=1N⁡\(k\)∑n=1N⁡\(k\)d𝒴​\(yk,n,yk,j\)p=2​∑1≤n<n′≤N⁡\(k\)d𝒴​\(yk,n,yk,n′\)p\.\\sum\_\{j=1\}^\{N\(k\)\}\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,j\}\)^\{p\}=2\\sum\_\{1\\leq n<n^\{\\prime\}\\leq N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,n^\{\\prime\}\}\)^\{p\}\.Therefore,

∑n=1N⁡\(k\)d𝒴​\(yk,n,zk\)p≤2N⁡\(k\)​∑1≤n<n′≤N⁡\(k\)d𝒴​\(yk,n,yk,n′\)p\.\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},z\_\{k\}\)^\{p\}\\leq\\frac\{2\}\{N\(k\)\}\\sum\_\{1\\leq n<n^\{\\prime\}\\leq N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,n^\{\\prime\}\}\)^\{p\}\.SinceN⁡\(k\)≥2N\(k\)\\geq 2,2N⁡\(k\)≤2N⁡\(k\)−1\\frac\{2\}\{N\(k\)\}\\leq\\frac\{2\}\{N\(k\)\-1\}, and hence

∑n=1N⁡\(k\)d𝒴​\(yk,n,zk\)p≤2N⁡\(k\)−1​∑1≤n<n′≤N⁡\(k\)d𝒴​\(yk,n,yk,n′\)p\.\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},z\_\{k\}\)^\{p\}\\leq\\frac\{2\}\{N\(k\)\-1\}\\sum\_\{1\\leq n<n^\{\\prime\}\\leq N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,n^\{\\prime\}\}\)^\{p\}\.ForN⁡\(k\)=1N\(k\)=1, the left\-hand side is zero aszk=yk,1z\_\{k\}=y\_\{k,1\}is an exact minimizer, while the corresponding kernel contribution is zero by definition\. Summing overkkand dividing byM′M^\{\\prime\}, we obtain

R∗p≤1M′​∑k=1K21\{N\(k\)\>1\}N⁡\(k\)−1​∑1≤n<n′≤N⁡\(k\)d𝒴​\(yk,n,yk,n′\)p\.R\_\{\*\}^\{p\}\\leq\\frac\{1\}\{M^\{\\prime\}\}\\sum\_\{k=1\}^\{K\}\\frac\{2\\,\\mathds\{1\}\_\{\\\{N\(k\)\>1\\\}\}\}\{N\(k\)\-1\}\\sum\_\{1\\leq n<n^\{\\prime\}\\leq N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k,n^\{\\prime\}\}\)^\{p\}\.Thus,R∗≤Kersize⁡\(𝒟M′,p\)KR\_\{\*\}\\leq\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\}\. Together with Step 1, this gives

12​Kersize⁡\(𝒟M′,p\)K≤infϕℒ⁡\(𝒟M′,ϕ,p\)≤Kersize⁡\(𝒟M′,p\)K\.\\frac\{1\}\{2\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\}\\leq\\inf\_\{\\phi\}\\mathcal\{L\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi,p\)\\leq\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},p\)\_\{K\}\.
Step 5: Construction of an upper hemicontinuous minimizer\.It remains to show that the unrestricted empirical optimum can be attained by an upper hemicontinuous map with nonempty compact values\. Assume first thatK≥2K\\geq 2, and definer:=13​mink≠k′​d𝒳​\(xk,xk′\)\>0r:=\\frac\{1\}\{3\}\\min\_\{k\\neq k^\{\\prime\}\}d\_\{\\mathcal\{X\}\}\(x\_\{k\},x\_\{k^\{\\prime\}\}\)\>0\. Fork=1,…,Kk=1,\\dots,K, letCk:=B¯d𝒳​\(xk,r\)C\_\{k\}:=\\overline\{B\}\_\{d\_\{\\mathcal\{X\}\}\}\(x\_\{k\},r\)\. Fork≠k′k\\neq k^\{\\prime\}, the triangle inequality impliesd𝒳​\(Ck,Ck′\)≥d𝒳​\(xk,xk′\)−2​r\>0d\_\{\\mathcal\{X\}\}\(C\_\{k\},C\_\{k^\{\\prime\}\}\)\\geq d\_\{\\mathcal\{X\}\}\(x\_\{k\},x\_\{k^\{\\prime\}\}\)\-2r\>0\. Hence the setsC1,…,CKC\_\{1\},\\dots,C\_\{K\}are pairwise disjoint\. IfK=1K=1, choose anyr\>0r\>0and defineC1C\_\{1\}in the same way\. Choose an arbitraryz0∈𝒴z\_\{0\}\\in\\mathcal\{Y\}, and define

Φ⁡\(x\)=\{\{zk\},x∈int⁡\(Ck\),\{z0,zk\},x∈∂Ck,\{z0\},x∉⋃k=1KCk\.\\Phi\(x\)=\\begin\{cases\}\\\{z\_\{k\}\\\},&x\\in\\operatorname\{int\}\(C\_\{k\}\),\\\\ \\\{z\_\{0\},z\_\{k\}\\\},&x\\in\\partial C\_\{k\},\\\\ \\\{z\_\{0\}\\\},&x\\notin\\displaystyle\\bigcup\_\{k=1\}^\{K\}C\_\{k\}\.\\end\{cases\}Every value ofΦ\\Phiis nonempty and finite, and hence compact\. We claim thatΦ\\Phiis upper hemicontinuous\. Away from the boundaries∂Ck\\partial C\_\{k\}, the map is locally constant and is therefore upper hemicontinuous\. Now letx∈∂Ckx\\in\\partial C\_\{k\}\. Since the setsCkC\_\{k\}are positively separated, there exists a neighborhoodUUofxxthat intersects noCk′C\_\{k^\{\\prime\}\}withk′≠kk^\{\\prime\}\\neq k\. Thus, for everyx′∈Ux^\{\\prime\}\\in U,Φ⁡\(x′\)∈\{\{zk\},\{z0\},\{z0,zk\}\}\\Phi\(x^\{\\prime\}\)\\in\\bigl\\\{\\\{z\_\{k\}\\\},\\\{z\_\{0\}\\\},\\\{z\_\{0\},z\_\{k\}\\\}\\bigr\\\}\. LetV⊂𝒴V\\subset\\mathcal\{Y\}be any open set containingΦ⁡\(x\)=\{z0,zk\}\\Phi\(x\)=\\\{z\_\{0\},z\_\{k\}\\\}\. Thenz0,zk∈Vz\_\{0\},z\_\{k\}\\in V, and consequently

\{zk\}⊂V,\{z0\}⊂V,\{z0,zk\}⊂V\.\\\{z\_\{k\}\\\}\\subset V,\\qquad\\\{z\_\{0\}\\\}\\subset V,\\qquad\\\{z\_\{0\},z\_\{k\}\\\}\\subset V\.Hence, after possibly shrinkingUU,Φ⁡\(x′\)⊂V\\Phi\(x^\{\\prime\}\)\\subset Vfor allx′∈Ux^\{\\prime\}\\in U\. This proves upper hemicontinuity atxx, and thereforeΦ\\Phiis upper hemicontinuous onℳ2\\mathcal\{M\}\_\{2\}\. Finally, sincexk∈int⁡\(Ck\)x\_\{k\}\\in\\operatorname\{int\}\(C\_\{k\}\),Φ⁡\(xk\)=\{zk\}\\Phi\(x\_\{k\}\)=\\\{z\_\{k\}\\\}fork=1,…,Kk=1,\\dots,K\. Therefore,

ℒ​\(𝒟M′,Φ,p\)p=1M′​∑k=1K∑n=1N⁡\(k\)d𝒴​\(yk,n,zk\)p=R∗p\.\\mathcal\{L\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\Phi,p\)^\{p\}=\\frac\{1\}\{M^\{\\prime\}\}\\sum\_\{k=1\}^\{K\}\\sum\_\{n=1\}^\{N\(k\)\}d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},z\_\{k\}\)^\{p\}=R\_\{\*\}^\{p\}\.Thus the unrestricted empirical infimum is attained by an upper hemicontinuous map with nonempty finite, hence compact, values\.Φ\\Phiis singleton\-valued on the open neighborhoodint⁡\(Ck\)\\operatorname\{int\}\(C\_\{k\}\)of every anchorxkx\_\{k\}\. Consequently,

infϕuhcℒ⁡\(𝒟M′,ϕuhc,p\)=infϕℒ⁡\(𝒟M′,ϕ,p\),\\inf\_\{\\phi\_\{\\mathrm\{uhc\}\}\}\\mathcal\{L\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi\_\{\\mathrm\{uhc\}\},p\)=\\inf\_\{\\phi\}\\mathcal\{L\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi,p\),and both infima lie between the lower and upper bound from steps11and44\. This completes the proof\. ∎

### 8\.3Proof of Proposition[2\.13](https://arxiv.org/html/2610.22564#S2.Thmtheorem13)

###### Proof\.

For each edgee=\(k,j\)∈Ee=\(k,j\)\\in E, defineae:=d𝒴H​\(\{yj\},ϕ⁡\(xk\)\)a\_\{e\}:=d\_\{\\mathcal\{Y\}\}^\{H\}\(\\\{y\_\{j\}\\\},\\phi\(x\_\{k\}\)\)andbe:=ℓr⁡\(e\)​\(ϕ\)b\_\{e\}:=\\ell\_\{r\(e\)\}\(\\phi\)\. By the choice of the reference indexr⁡\(e\)r\(e\), we have\|ae−be\|≤γe\|a\_\{e\}\-b\_\{e\}\|\\leq\\gamma\_\{e\}\. SinceM′=\|E\|M^\{\\prime\}=\|E\|,

ℒ⁡\(𝒟M′,ϕ,p\)=\(1M′​∑e∈Eaep\)1/p\.\\displaystyle\\mathcal\{L\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi,p\)=\\left\(\\frac\{1\}\{M^\{\\prime\}\}\\sum\_\{e\\in E\}a\_\{e\}^\{p\}\\right\)^\{1/p\}\.By the reverse triangle inequality for theℓp\\ell\_\{p\}\-norm,

\|ℒ⁡\(𝒟M′,ϕ,p\)−\(1M′​∑e∈Ebep\)1/p\|≤\(1M′​∑e∈E\|ae−be\|p\)1/p≤\(1M′​∑e∈Eγep\)1/p=Γp​\(ϕ\)\.\\displaystyle\\left\|\\mathcal\{L\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi,p\)\-\\left\(\\frac\{1\}\{M^\{\\prime\}\}\\sum\_\{e\\in E\}b\_\{e\}^\{p\}\\right\)^\{1/p\}\\right\|\\leq\\left\(\\frac\{1\}\{M^\{\\prime\}\}\\sum\_\{e\\in E\}\|a\_\{e\}\-b\_\{e\}\|^\{p\}\\right\)^\{1/p\}\\leq\\left\(\\frac\{1\}\{M^\{\\prime\}\}\\sum\_\{e\\in E\}\\gamma\_\{e\}^\{p\}\\right\)^\{1/p\}=\\Gamma\_\{p\}\(\\phi\)\.Next, by the definition of the reference weightswiw\_\{i\},

1M′​∑e∈Ebep=1M′​∑e∈Eℓr⁡\(e\)​\(ϕ\)p=∑m=1Mwm​ℓm​\(ϕ\)p\.\\displaystyle\\frac\{1\}\{M^\{\\prime\}\}\\sum\_\{e\\in E\}b\_\{e\}^\{p\}=\\frac\{1\}\{M^\{\\prime\}\}\\sum\_\{e\\in E\}\\ell\_\{r\(e\)\}\(\\phi\)^\{p\}=\\sum\_\{m=1\}^\{M\}w\_\{m\}\\ell\_\{m\}\(\\phi\)^\{p\}\.Hence, using0≤ℓm​\(ϕ\)≤Bϕ0\\leq\\ell\_\{m\}\(\\phi\)\\leq B\_\{\\phi\}for allm∈\{1,…,M\}m\\in\\\{1,\\ldots,M\\\},

\|∑m=1Mwm​ℓm​\(ϕ\)p−1M​∑m=1Mℓm​\(ϕ\)p\|\\displaystyle\\left\|\\sum\_\{m=1\}^\{M\}w\_\{m\}\\ell\_\{m\}\(\\phi\)^\{p\}\-\\frac\{1\}\{M\}\\sum\_\{m=1\}^\{M\}\\ell\_\{m\}\(\\phi\)^\{p\}\\right\|=\|∑m=1M\(wm−1M\)​ℓm​\(ϕ\)p\|\\displaystyle=\\left\|\\sum\_\{m=1\}^\{M\}\\left\(w\_\{m\}\-\\frac\{1\}\{M\}\\right\)\\ell\_\{m\}\(\\phi\)^\{p\}\\right\|≤∑m=1M\|wm−1M\|​ℓm​\(ϕ\)p≤Bϕp​∑m=1M\|wm−1M\|\.\\displaystyle\\leq\\sum\_\{m=1\}^\{M\}\\left\|w\_\{m\}\-\\frac\{1\}\{M\}\\right\|\\ell\_\{m\}\(\\phi\)^\{p\}\\leq B\_\{\\phi\}^\{p\}\\sum\_\{m=1\}^\{M\}\\left\|w\_\{m\}\-\\frac\{1\}\{M\}\\right\|\.For nonnegatives,ts,tandp≥1p\\geq 1, the mapu↦u1/pu\\mapsto u^\{1/p\}satisfies\|s1/p−t1/p\|≤\|s−t\|1/p\|s^\{1/p\}\-t^\{1/p\}\|\\leq\|s\-t\|^\{1/p\}\. Therefore,

\|\(∑m=1Mwm​ℓm​\(ϕ\)p\)1/p−\(1M​∑m=1Mℓm​\(ϕ\)p\)1/p\|\\displaystyle\\left\|\\left\(\\sum\_\{m=1\}^\{M\}w\_\{m\}\\ell\_\{m\}\(\\phi\)^\{p\}\\right\)^\{1/p\}\-\\left\(\\frac\{1\}\{M\}\\sum\_\{m=1\}^\{M\}\\ell\_\{m\}\(\\phi\)^\{p\}\\right\)^\{1/p\}\\right\|≤Bϕ​\(∑m=1M\|wm−1M\|\)1/p\.\\displaystyle\\leq B\_\{\\phi\}\\left\(\\sum\_\{m=1\}^\{M\}\\left\|w\_\{m\}\-\\frac\{1\}\{M\}\\right\|\\right\)^\{1/p\}\.Combining the preceding two inequalities with the triangle inequality gives the claimed bound

\|ℒ⁡\(𝒟M′,ϕ,p\)−ℒ⁡\(𝒟M,ϕ,p\)\|≤Γp​\(ϕ\)\+Bϕ​\(∑m=1M\|wm−1M\|\)1/p\\displaystyle\\left\|\\mathcal\{L\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},\\phi,p\)\-\\mathcal\{L\}\(\\mathcal\{D\}\_\{M\},\\phi,p\)\\right\|\\leq\\Gamma\_\{p\}\(\\phi\)\+B\_\{\\phi\}\\left\(\\sum\_\{m=1\}^\{M\}\\left\|w\_\{m\}\-\\frac\{1\}\{M\}\\right\|\\right\)^\{1/p\}∎

### 8\.4Proof of Proposition[2\.17](https://arxiv.org/html/2610.22564#S2.Thmtheorem17)

###### Proof\.

Conditional onX¯\\overline\{X\}, letY′Y^\{\\prime\}be an independent copy ofYY\. Then𝔼⁡\[‖Y−Y′‖22∣X¯\]=2​𝔼​\[‖Y−m⁡\(X¯\)‖22∣X¯\]\\mathbb\{E\}\[\\\|Y\-Y^\{\\prime\}\\\|\_\{2\}^\{2\}\\mid\\overline\{X\}\]=2\\,\\mathbb\{E\}\[\\\|Y\-m\(\\overline\{X\}\)\\\|\_\{2\}^\{2\}\\mid\\overline\{X\}\]\. The conditional Pythagorean identity gives𝔼⁡\[‖Y−ϕ¯​\(X¯\)‖22∣X¯\]=𝔼⁡\[‖Y−m⁡\(X¯\)‖22∣X¯\]\+‖m⁡\(X¯\)−ϕ¯​\(X¯\)‖22\\mathbb\{E\}\[\\\|Y\-\\overline\{\\phi\}\(\\overline\{X\}\)\\\|\_\{2\}^\{2\}\\mid\\overline\{X\}\]=\\mathbb\{E\}\[\\\|Y\-m\(\\overline\{X\}\)\\\|\_\{2\}^\{2\}\\mid\\overline\{X\}\]\+\\\|m\(\\overline\{X\}\)\-\\overline\{\\phi\}\(\\overline\{X\}\)\\\|\_\{2\}^\{2\}\. Taking expectations proves the result\. ∎

### 8\.5Proof of Proposition[2\.18](https://arxiv.org/html/2610.22564#S2.Thmtheorem18)

###### Proof\.

Regression generalization gap:Letϕ¯:ℳ¯2→𝒴\\overline\{\\phi\}:\\overline\{\\mathcal\{M\}\}\_\{2\}\\to\\mathcal\{Y\}be a measurable regressor such thatℒ⁡\(𝒟μ,ϕ¯,p\)<∞\\mathcal\{L\}\(\\mathcal\{D\}\_\{\\mu\},\\overline\{\\phi\},p\)<\\infty\. FixX¯\\overline\{X\}\. LetY,Y′∼i\.i\.d\.μ\(⋅∣X¯\)Y,Y^\{\\prime\}\\overset\{i\.i\.d\.\}\{\\sim\}\\mu\(\\cdot\\mid\\overline\{X\}\)\. By the triangle inequality,d𝒴​\(Y,Y′\)≤d𝒴​\(Y,ϕ¯​\(X¯\)\)\+d𝒴​\(ϕ¯​\(X¯\),Y′\)d\_\{\\mathcal\{Y\}\}\(Y,Y^\{\\prime\}\)\\leq d\_\{\\mathcal\{Y\}\}\(Y,\\overline\{\\phi\}\(\\overline\{X\}\)\)\+d\_\{\\mathcal\{Y\}\}\(\\overline\{\\phi\}\(\\overline\{X\}\),Y^\{\\prime\}\)\. Applying\(a\+b\)p≤2p−1​\(ap\+bp\)\(a\+b\)^\{p\}\\leq 2^\{p\-1\}\(a^\{p\}\+b^\{p\}\)givesd𝒴​\(Y,Y′\)p≤2p−1​\(d𝒴​\(Y,ϕ¯​\(X¯\)\)p\+d𝒴​\(Y′,ϕ¯​\(X¯\)\)p\)d\_\{\\mathcal\{Y\}\}\(Y,Y^\{\\prime\}\)^\{p\}\\leq 2^\{p\-1\}\\big\(d\_\{\\mathcal\{Y\}\}\(Y,\\overline\{\\phi\}\(\\overline\{X\}\)\)^\{p\}\+d\_\{\\mathcal\{Y\}\}\(Y^\{\\prime\},\\overline\{\\phi\}\(\\overline\{X\}\)\)^\{p\}\\big\)\. Now taking the conditional expectation givenX¯\\overline\{X\}, gives

𝔼⁡\[d𝒴​\(Y,Y′\)p∣X¯\]≤2p−1​\(𝔼⁡\[d𝒴​\(Y,ϕ¯​\(X¯\)\)p∣X¯\]\+𝔼⁡\[d𝒴​\(Y′,ϕ¯​\(X¯\)\)p∣X¯\]\)\.\\mathbb\{E\}\[d\_\{\\mathcal\{Y\}\}\(Y,Y^\{\\prime\}\)^\{p\}\\mid\\overline\{X\}\]\\leq 2^\{p\-1\}\\Big\(\\mathbb\{E\}\[d\_\{\\mathcal\{Y\}\}\(Y,\\overline\{\\phi\}\(\\overline\{X\}\)\)^\{p\}\\mid\\overline\{X\}\]\+\\mathbb\{E\}\[d\_\{\\mathcal\{Y\}\}\(Y^\{\\prime\},\\overline\{\\phi\}\(\\overline\{X\}\)\)^\{p\}\\mid\\overline\{X\}\]\\Big\)\.SinceYYandY′Y^\{\\prime\}are i\.i\.d\. conditional onX¯\\overline\{X\},𝔼⁡\[d𝒴​\(Y′,ϕ¯​\(X¯\)\)p∣X¯\]=𝔼⁡\[d𝒴​\(Y,ϕ¯​\(X¯\)\)p∣X¯\]\\mathbb\{E\}\[d\_\{\\mathcal\{Y\}\}\(Y^\{\\prime\},\\overline\{\\phi\}\(\\overline\{X\}\)\)^\{p\}\\mid\\overline\{X\}\]=\\mathbb\{E\}\[d\_\{\\mathcal\{Y\}\}\(Y,\\overline\{\\phi\}\(\\overline\{X\}\)\)^\{p\}\\mid\\overline\{X\}\]\. Hence,2−p​𝔼​\[d𝒴​\(Y,Y′\)p∣X¯\]≤𝔼⁡\[d𝒴​\(Y,ϕ¯​\(X¯\)\)p∣X¯\]2^\{\-p\}\\mathbb\{E\}\[d\_\{\\mathcal\{Y\}\}\(Y,Y^\{\\prime\}\)^\{p\}\\mid\\overline\{X\}\]\\leq\\mathbb\{E\}\[d\_\{\\mathcal\{Y\}\}\(Y,\\overline\{\\phi\}\(\\overline\{X\}\)\)^\{p\}\\mid\\overline\{X\}\]\. Taking the expectation overX¯\\overline\{X\}and using the tower property on the right hand side, yields

2−p​𝔼X¯​𝔼Y,Y′\|X¯​\[d𝒴​\(Y,Y′\)p\]≤𝔼\(Y,X¯\)​\[d𝒴​\(ϕ¯​\(X¯\),Y\)p\]\.2^\{\-p\}\\mathbb\{E\}\_\{\\overline\{X\}\}\\mathbb\{E\}\_\{Y,Y^\{\\prime\}\\mid\\overline\{X\}\}\[d\_\{\\mathcal\{Y\}\}\(Y,Y^\{\\prime\}\)^\{p\}\]\\leq\\mathbb\{E\}\_\{\(Y,\\overline\{X\}\)\}\[d\_\{\\mathcal\{Y\}\}\(\\overline\{\\phi\}\(\\overline\{X\}\),Y\)^\{p\}\]\.Now taking the1/p1/p\-th power on both sides yields

2−1​\(𝔼X¯​𝔼Y,Y′\|X¯​\[d𝒴​\(Y,Y′\)p\]\)1/p≤𝔼\(Y,X¯\)​\[d𝒴​\(ϕ¯​\(X¯\),Y\)p\]1/p2^\{\-1\}\\left\(\\mathbb\{E\}\_\{\\overline\{X\}\}\\mathbb\{E\}\_\{Y,Y^\{\\prime\}\\mid\\overline\{X\}\}\[d\_\{\\mathcal\{Y\}\}\(Y,Y^\{\\prime\}\)^\{p\}\]\\right\)^\{1/p\}\\leq\\mathbb\{E\}\_\{\(Y,\\overline\{X\}\)\}\[d\_\{\\mathcal\{Y\}\}\(\\overline\{\\phi\}\(\\overline\{X\}\),Y\)^\{p\}\]^\{1/p\}Thus, asKersize⁡\(𝒟μ,p\):=\(𝔼X¯​𝔼Y,Y′\|X¯​\[d𝒴​\(Y,Y′\)p\]\)1/p\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},p\):=\\Big\(\\mathbb\{E\}\_\{\\overline\{X\}\}\\mathbb\{E\}\_\{Y,Y^\{\\prime\}\\mid\\overline\{X\}\}\[d\_\{\\mathcal\{Y\}\}\(Y,Y^\{\\prime\}\)^\{p\}\]\\Big\)^\{1/p\}we have that2−1​Kersize⁡\(𝒟μ,p\)≤ℒ⁡\(𝒟μ,ϕ¯,p\)2^\{\-1\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},p\)\\leq\\mathcal\{L\}\(\\mathcal\{D\}\_\{\\mu\},\\overline\{\\phi\},p\)\. Finally, since empirical risk is bounded byϵ\\epsilon, we have that−ϵ≤−ℒ⁡\(𝒟M,ϕ,p\)\-\\epsilon\\leq\-\\mathcal\{L\}\(\\mathcal\{D\}\_\{M\},\\phi,p\), and, thus2−1​Kersize⁡\(𝒟μ,p\)−ϵ≤ℒ⁡\(𝒟μ,ϕ¯,p\)−ℒ⁡\(𝒟M,ϕ,p\)2^\{\-1\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},p\)\-\\epsilon\\leq\\mathcal\{L\}\(\\mathcal\{D\}\_\{\\mu\},\\overline\{\\phi\},p\)\-\\mathcal\{L\}\(\\mathcal\{D\}\_\{M\},\\phi,p\)\. The Euclidean sharpening follows from Proposition[2\.17](https://arxiv.org/html/2610.22564#S2.Thmtheorem17)\.Classification generalization gap:The proof follows the same structure as for the regression case by boundingAcc⁡\(𝒟μ,ϕ¯\):=1−𝔼\(Y,X¯\)∼μ​\[dH​\(Y,ϕ¯​\(X¯\)\)\]\\operatorname\{Acc\}\(\\mathcal\{D\}\_\{\\mu\},\\overline\{\\phi\}\):=1\-\\mathbb\{E\}\_\{\(Y,\\overline\{X\}\)\\sim\\mu\}\[d\_\{H\}\(Y,\\overline\{\\phi\}\(\\overline\{X\}\)\)\]from above\. ∎

### 8\.6Proof of Proposition[2\.19](https://arxiv.org/html/2610.22564#S2.Thmtheorem19)

###### Proof\.

For eachkk, letUk:=2NK​\(NK−1\)​∑1≤n<n′≤NKd𝒴​\(Yk,n,Yk,n′\)pU\_\{k\}:=\\frac\{2\}\{N\_\{K\}\(N\_\{K\}\-1\)\}\\sum\_\{1\\leq n<n^\{\\prime\}\\leq N\_\{K\}\}d\_\{\\mathcal\{Y\}\}\(Y\_\{k,n\},Y\_\{k,n^\{\\prime\}\}\)^\{p\}\. Conditional onX¯k\\overline\{X\}\_\{k\}, the order\-two U\-statistic is unbiased, so𝔼⁡\[Uk∣X¯k\]=𝔼⁡\[d𝒴​\(Y,Y′\)p∣X¯k\]\\mathbb\{E\}\[U\_\{k\}\\mid\\overline\{X\}\_\{k\}\]=\\mathbb\{E\}\[d\_\{\\mathcal\{Y\}\}\(Y,Y^\{\\prime\}\)^\{p\}\\mid\\overline\{X\}\_\{k\}\]\. Taking expectations gives𝔼​Uk=Kersize⁡\(𝒟μ,p\)p\\mathbb\{E\}U\_\{k\}=\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},p\)^\{p\}\. The variablesU1,…,UKU\_\{1\},\\ldots,U\_\{K\}are independent and satisfy0≤Uk≤vmax0\\leq U\_\{k\}\\leq v\_\{\\max\}\. Sinceκ^K,NKp=K−1​∑k=1KUk\\widehat\{\\kappa\}\_\{K,N\_\{K\}\}^\{p\}=K^\{\-1\}\\sum\_\{k=1\}^\{K\}U\_\{k\}, Hoeffding’s inequality[Hoeffding \[1994\]](https://arxiv.org/html/2610.22564#bib.bib14)gives the stated bound\. ∎

## 9Appendix

### 9\.1Experiment details

#### 9\.1\.1Pseudo\-metric on image data

Across all image\-based tasks we used the same metric to ensure comparability of image\-based features\. The metric on images was the composition of theℓ2\\ell\_\{2\}norm with discrete wavelet featuresgg\. The image feature was obtained by the concatenation of the four subbands obtained from a single\-level two\-dimensional discrete wavelet transform \(DWT\) applied independently to each channel[Daubechies \[1992\]](https://arxiv.org/html/2610.22564#bib.bib55)\. Given an imagex∈ℝC×H×Wx\\in\\mathbb\{R\}^\{C\\times H\\times W\}, the resulting feature vector is denoted bygwav​\(x\)∈ℝDg\_\{\\mathrm\{wav\}\}\(x\)\\in\\mathbb\{R\}^\{D\}\. The DWT was computed using a chosen wavelet basis; in all experiments, we used the Haar wavelet basis\. Specifically, for each channel, the transform decomposes the image into an approximation subband, denoted by LL \(low\-low\), and three detail subbands: LH \(low\-high\), HL \(high\-low\), and HH \(high\-high\)\. These subbands correspond to the responses of low\- and high\-frequency filters applied along the two spatial dimensions\. The four resulting subbands were flattened and concatenated to form the final feature,gwav​\(x\)g\_\{\\mathrm\{wav\}\}\(x\)\. For wavelets with standard dyadic downsampling and even spatial dimensions, the resulting feature dimension isD=C​H​WD=CHW\. The image similarity was measured by the metric

d𝒳​\(x,x′\)=‖g⁡\(x\)−g⁡\(x′\)‖2\.\\displaystyle d\_\{\\mathcal\{X\}\}\(x,x^\{\\prime\}\)=\\left\\\|g\(x\)\-g\(x^\{\\prime\}\)\\right\\\|\_\{2\}\.\(9\.1\)More generally, this construction can be viewed as a feature\-induced pseudo\-metric on the original image space: if the feature mapggis not injective, distinct images may have identical feature representations and therefore zero distance\. For the specific implementation considered here, all four subbands of the Haar DWT are retained, so the transform is invertible under the corresponding DWT conventions\. The pseudo\-metric terminology is therefore primarily relevant to the general feature\-map formulation, particularly whenggis replaced by a potentially non\-injective feature encoder\.

#### 9\.1\.2Feasible set construction

We sampled finite feasible sets using Algorithm[1](https://arxiv.org/html/2610.22564#alg1)\. For image\-based experiments, neighboring inputs were identified using the wavelet\-induced distanced𝒳d\_\{\\mathcal\{X\}\}in \([9\.1](https://arxiv.org/html/2610.22564#S9.E1)\)\. Threshold choice followed a fixed rule throughout the experiments; whenever prior knowledge supplied an input\-noise model and/or a target/label measurement\-noise model, we set the thresholdsτ𝒳\\tau\_\{\\mathcal\{X\}\}andτ𝒴\\tau\_\{\\mathcal\{Y\}\}to the corresponding conservative worst\-case noise bounds\. If such prior information was unavailable, we estimatedτ𝒳\\tau\_\{\\mathcal\{X\}\}using the nearest\-neighbor quantile rule in \([9\.2](https://arxiv.org/html/2610.22564#S9.E2)\) and setτ𝒴=0\\tau\_\{\\mathcal\{Y\}\}=0unless target\-noise information was available\. Given the thresholdsτ𝒳\\tau\_\{\\mathcal\{X\}\}andτ𝒴\\tau\_\{\\mathcal\{Y\}\}approximately satisfying Assumption[2\.6](https://arxiv.org/html/2610.22564#S2.Thmtheorem6), and an anchor\(yk,xk\)∈𝒟M\(y\_\{k\},x\_\{k\}\)\\in\\mathcal\{D\}\_\{M\}, the targetyk,n∈π1​\(𝒟M\)y\_\{k,n\}\\in\\pi\_\{1\}\(\\mathcal\{D\}\_\{M\}\)of a sample\(yk,n,xk,n\)∈𝒟M\(y\_\{k,n\},x\_\{k,n\}\)\\in\\mathcal\{D\}\_\{M\}was admitted to the feasible setFxkN⁡\(k\)F\_\{x\_\{k\}\}^\{N\(k\)\}wheneverd𝒳​\(xk,n,xk\)≤τ𝒳​\(xk\)d\_\{\\mathcal\{X\}\}\(x\_\{k,n\},x\_\{k\}\)\\leq\\tau\_\{\\mathcal\{X\}\}\(x\_\{k\}\)ord𝒴​\(yk,n,yk\)≤τ𝒴​\(yk\)d\_\{\\mathcal\{Y\}\}\(y\_\{k,n\},y\_\{k\}\)\\leq\\tau\_\{\\mathcal\{Y\}\}\(y\_\{k\}\)\. Thus,FxkN⁡\(k\)F\_\{x\_\{k\}\}^\{N\(k\)\}contains targets associated with samples that are close to the anchor either in input space or in target space\. For one\-hot labels, we setτ𝒴=0\\tau\_\{\\mathcal\{Y\}\}=0\. In the case that prior knowledge did not supply an input\-noise model, we used the following dataset\-dependent procedure for the input threshold

τ𝒳​\(q\)=Quantileq⁡\(\{d𝒳​\(xm,x\(1\)\(m\)\)\}m=1M\),\\displaystyle\\tau\_\{\\mathcal\{X\}\}\(q\)=\\operatorname\{Quantile\}\_\{q\}\\left\(\\left\\\{d\_\{\\mathcal\{X\}\}\(x\_\{m\},x\_\{\(1\)\}^\{\(m\)\}\)\\right\\\}\_\{m=1\}^\{M\}\\right\),\(9\.2\)wherex\(1\)\(m\)x\_\{\(1\)\}^\{\(m\)\}denotes the closest non\-self neighbor ofxmx\_\{m\}\. The nearest neighbors for the dataset\-dependent input threshold selection were computed with the nearest neighbor algorithm from[Pedregosa et al\. \[2011\]](https://arxiv.org/html/2610.22564#bib.bib79)\.222If the target noise is unknown, one could use the analogous target\-space nearest\-neighbor quantiles,τ𝒴​\(q\)=Quantileq⁡\(\{d𝒴​\(ym,y\(1\)\(m\)\)\}1≤m≤M\)\\tau\_\{\\mathcal\{Y\}\}\(q\)=\\operatorname\{Quantile\}\_\{q\}\(\\\{d\_\{\\mathcal\{Y\}\}\(y\_\{m\},y\_\{\(1\)\}^\{\(m\)\}\)\\\}\_\{1\\leq m\\leq M\}\)\.We used the standard settings, the metric corresponding to the choice ofd𝒳d\_\{\\mathcal\{X\}\}and reported the maximum number of nearest neighborsNmaxN\_\{\\max\}used in nearest neighbor algorithm from[Pedregosa et al\. \[2011\]](https://arxiv.org/html/2610.22564#bib.bib79)in the experiments\.333Note that the maximum number of nearest neighborsNmaxN\_\{\\max\}for computing the thresholdτ𝒳​\(q\)\\tau\_\{\\mathcal\{X\}\}\(q\)for a given quantileqqis not equal to the number of maximal elementsNmaxfN^\{f\}\_\{\\max\}in a given feasible set obtained by Algorithm[1](https://arxiv.org/html/2610.22564#alg1)\.Additionally, we chose the maximum number of nearest neighborsNmaxN\_\{\\max\}such that the average kernel size converged with an ablation study outlined below\. If the worst\-case noise threshold was unknown, in our experiments we did not estimateτ𝒴\\tau\_\{\\mathcal\{Y\}\}via quantiles and setτ𝒴=0\\tau\_\{\\mathcal\{Y\}\}=0, thereby assuming noiseless targets\.

The quantile parameterqqfor choosing the thresholdτ𝒳​\(q\)\\tau\_\{\\mathcal\{X\}\}\(q\)in \([9\.2](https://arxiv.org/html/2610.22564#S9.E2)\) determines the locality scale at which samples are treated as indistinguishable with respect to the pseudo\-metricd𝒳d\_\{\\mathcal\{X\}\}: smaller values ofqqenforce more local feasible sets, whereas larger values increase sample support but may merge points that are no longer similar\. To focus on local neighborhoods we restricted the quantile toq∈\[0\.01,0\.1\]q\\in\[0\.01,0\.1\], that is, to the lower tail of the nearest\-neighbor distance distribution\. Within this range,qqwas chosen by a*bandwidth stability heuristic*rather than by an optimality criterion: we selected the smallestqqlying in a region where the estimated average kernel size changed only mildly across neighboring values ofqq\. We identified such a region by requiring both small relative changes in the average kernel size and approximately small local curvature, and then choose the smallestqqin that plateau\. This favors the most local scale at which the estimated ambiguity is not unduly sensitive to the threshold choice\. We emphasize that this is a practical empirical heuristic for selecting a stable locality scale, not a claim of statistical optimality\. To make the dependence onqqtransparent, we reported full sensitivity curves in Section[9\.2](https://arxiv.org/html/2610.22564#S9.SS2)below, which contains additional ablation studies, and verified that the average kernel size remained qualitatively stable throughout the selected range\.

The values ofqq,τ𝒳\\tau\_\{\\mathcal\{X\}\}, andτ𝒴\\tau\_\{\\mathcal\{Y\}\}and the average feasible set sizeN⁡\(k\)¯\\overline\{N\(k\)\}, as well asM′M^\{\\prime\}and the number of anchor samplesKK, are reported for each experiment\.

Ablation study on maximum number of nearest neighbors and quantiles:We assessed sensitivity to the quantileqqand maximum number of nearest neighborsNmaxN\_\{\\max\}used in nearest neighbor algorithm from[Pedregosa et al\. \[2011\]](https://arxiv.org/html/2610.22564#bib.bib79)for computing the thresholdτ𝒳​\(q\)\\tau\_\{\\mathcal\{X\}\}\(q\)and variedq∈\{0\.01,0\.02,0\.03,0\.05,0\.06,0\.08,0\.1\}q\\in\\\{0\.01,0\.02,0\.03,0\.05,0\.06,0\.08,0\.1\\\}andNmax∈\{10,20,30,40,50,100,200,300,450\}N\_\{\\max\}\\in\\\{10,20,30,40,50,100,200,300,450\\\}\. In the ablation over the neighborhood size we selectedNmaxN\_\{\\max\}such that the average kernel size remained constant for largerNmaxN\_\{\\max\}\. For varying the neighborhood size we set a convergence criterion at10−410^\{\-4\}\. For completeness, we extended the ablation study on quantiles to

q∈\{0\.01,0\.02,0\.03,0\.05,0\.06,0\.08,0\.1,0\.2,0\.3,0\.4,0\.5,0\.6,0\.7,0\.8,0\.9,1\.0\},q\\in\\\{0\.01,0\.02,0\.03,0\.05,0\.06,0\.08,0\.1,0\.2,0\.3,0\.4,0\.5,0\.6,0\.7,0\.8,0\.9,1\.0\\\},although we do not recommend extending beyond the quantileq=0\.1q=0\.1, as the resulting thresholdτ𝒳​\(q\)\\tau\_\{\\mathcal\{X\}\}\(q\)is unlikely to satisfy Assumption[2\.6](https://arxiv.org/html/2610.22564#S2.Thmtheorem6)for larger quantiles\. For each parameter choice, we recomputed the nearest\-neighbor graph, thresholdτ𝒳\\tau\_\{\\mathcal\{X\}\}, feasible sets, and average kernel size\. This provides an empirical assessment of the stability of the resulting feasible\-set geometry and is reported in Section[9\.2](https://arxiv.org/html/2610.22564#S9.SS2)\.

#### 9\.1\.3Regression dataset details

For thesynthetic regressiondataset, we computed the average kernel size from feasible sets as a function of the maximum number of nearest neighbors and reached convergence with threshold10−410^\{\-4\}atNmax=300N\_\{\\max\}=300, see Figure[10](https://arxiv.org/html/2610.22564#S9.F10)\. We generated a mesh grid ofM=900M=900noisy input points\(x1,x2\)∈\[−1,1\]2\(x\_\{1\},x\_\{2\}\)\\in\[\-1,1\]^\{2\}and a noisy surface from the regression target functionf⁡\(x1,x2\)=sin⁡\(1\+0\.9​x12\+x22\)f\(x\_\{1\},x\_\{2\}\)=\\sin\\\!\\left\(1\+0\.9\\sqrt\{x\_\{1\}^\{2\}\+x\_\{2\}^\{2\}\}\\right\)evaluated on the mesh grid of input points, where we added uniform input noiseU⁡\(\[0,0\.01\]2\)U\(\[0,0\.01\]^\{2\}\)and target noiseU⁡\(\[0,0\.03\]\)U\(\[0,0\.03\]\)\. Because bounded input and target noise were prescribed in the data\-generation process, we setτ𝒳\\tau\_\{\\mathcal\{X\}\}andτ𝒴\\tau\_\{\\mathcal\{Y\}\}equal to the corresponding worst\-case noise magnitudes\. Thus, we choseτ𝒳=0\.014=0\.012\+0\.012\\tau\_\{\\mathcal\{X\}\}=0\.014=\\sqrt\{0\.01^\{2\}\+0\.01^\{2\}\}andτ𝒴=0\.03\\tau\_\{\\mathcal\{Y\}\}=0\.03\. We trained three regressors to approximate the target functionfffrom samples in a train dataset𝒟Mtrain\\mathcal\{D\}\_\{M\_\{\\mathrm\{train\}\}\}and evaluated their predictive error on held\-out test data\. We considered a Gaussian Process regressorϕ1​s​t\\phi\_\{1st\}, a multilayer perceptron \(MLP\) regressorϕ2​n​d\\phi\_\{2nd\}, and a Support Vector Regression \(SVR\) model with a radial basis function \(RBF\) kernel, denoted byϕ3​r​d\\phi\_\{3rd\}\. We report the RMSE of each model on both the original test dataset𝒟Mtest\\mathcal\{D\}\_\{M\_\{\\mathrm\{test\}\}\}and the constructed test dataset𝒟Mtest′\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{test\}\}\}generated by Algorithm[1](https://arxiv.org/html/2610.22564#alg1)\. The error of the optimal regressor on𝒟Mtest′\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{test\}\}\}is given byR∗=0\.01656R\_\{\*\}=0\.01656\. As a noiseless control, we repeated the feasible\-set construction on data generated from the deterministic relationY=f⁡\(X\)Y=f\(X\), for which the Bayes RMSE is zero\. For all tested positive input thresholds withτ𝒴=0\\tau\_\{\\mathcal\{Y\}\}=0, the empirical average kernel size was also zero on both train and test splits\. Hence, in this setting the geometric threshold construction did not itself induce target ambiguity\. For a comparison to the Bayes risk, we assume the additive noise model

Y=f⁡\(X\)\+ε,ε∼U⁡\(\[0,0\.03\]\),Y=f\(X\)\+\\varepsilon,\\qquad\\varepsilon\\sim U\(\[0,0\.03\]\),withε\\varepsilonindependent ofXX\. HenceVar⁡\(Y∣X\)=Var⁡\(ε\)=0\.03212\\operatorname\{Var\}\(Y\\mid X\)=\\operatorname\{Var\}\(\\varepsilon\)=\\tfrac\{0\.03^\{2\}\}\{12\}, so the Bayes RMSE is0\.0312≈0\.00866\\frac\{0\.03\}\{\\sqrt\{12\}\}\\approx 0\.00866\. By Proposition[2\.17](https://arxiv.org/html/2610.22564#S2.Thmtheorem17), the corresponding population comparison quantity is12​Kersize⁡\(𝒟μ,2\)\\tfrac\{1\}\{\\sqrt\{2\}\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{\\mu\},2\)\. As we do not observe𝒟μ\\mathcal\{D\}\_\{\\mu\}, we compute the empirical proxy12​Kersize⁡\(𝒟Mtest′,2\)K\\tfrac\{1\}\{\\sqrt\{2\}\}\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{test\}\}\},2\)\_\{K\}\. Forτ𝒳∈\{10−5,0\.01,0\.04,0\.1\}\\tau\_\{\\mathcal\{X\}\}\\in\\\{10^\{\-5\},0\.01,0\.04,0\.1\\\}, the empirical results are identical, indicating that the input\-threshold criterion is inactive in this regime\. The corresponding test values of the average kernel size are

0\.007509,0\.011363,0\.015147,0\.0225620\.007509,\\quad 0\.011363,\\quad 0\.015147,\\quad 0\.022562for corresponding values ofτ𝒴=0\.01,0\.015,0\.02,0\.03\\tau\_\{\\mathcal\{Y\}\}=0\.01,0\.015,0\.02,0\.03, respectively\. Comparing with the Bayes benchmark under the assumption that the noise is independently sampled of the input,0\.008660\.00866, we find that forτ𝒴=0\.01\\tau\_\{\\mathcal\{Y\}\}=0\.01the average kernel size the closest, whereas larger output thresholds increasingly overestimate the irreducible error under this independence assumption\. Under target threshold misspecification forτ𝒴=0\.01,0\.015,0\.02,0\.03\\tau\_\{\\mathcal\{Y\}\}=0\.01,0\.015,0\.02,0\.03, we tested Assumption[2\.6](https://arxiv.org/html/2610.22564#S2.Thmtheorem6)as follows: a candidate reassignment\(j,k\)\(j,k\)is called admissible if the observed target valueyjy\_\{j\}lies in the model\-consistent interval associated with the anchor inputXkX\_\{k\}, namely

f⁡\(Xk\)≤yj≤f⁡\(Xk\)\+0\.03\.f\(X\_\{k\}\)\\leq y\_\{j\}\\leq f\(X\_\{k\}\)\+0\.03\.Accordingly, the test precision is defined as

Precisiontest=\#​\{accepted test pairs​\(j,k\)​that are admissible\}\#​\{accepted test pairs​\(j,k\)\}\.\\mathrm\{Precision\}\_\{\\mathrm\{test\}\}=\\frac\{\\\#\\\{\\text\{accepted test pairs \}\(j,k\)\\text\{ that are admissible\}\\\}\}\{\\\#\\\{\\text\{accepted test pairs \}\(j,k\)\\\}\}\.Its empirical value decreases from

0\.8760to0\.8082,0\.7314,0\.57000\.8760\\quad\\text\{to\}\\quad 0\.8082,\\ 0\.7314,\\ 0\.5700asτ𝒴\\tau\_\{\\mathcal\{Y\}\}increases\.

For theTropical Cycloneopen\-source dataset from[Huggingface](https://huggingface.co/datasets/TCBench/TCBench), the input images were converted to tensors\. We did not assume an explicit image\-space noise model and therefore choseτ𝒳\\tau\_\{\\mathcal\{X\}\}with the quantile heuristic\. For the wind\-speed targets, we used a heteroskedastic measurement\-noise model outlined below and setτ𝒴​\(y\)\\tau\_\{\\mathcal\{Y\}\}\(y\)accordingly\. We computed the average kernel size from feasible sets as a function of the maximum number of nearest neighbors and reached convergence with threshold10−410^\{\-4\}atNmax=300N\_\{\\max\}=300, see Figure[10](https://arxiv.org/html/2610.22564#S9.F10)\. For the ablation over quantiles see Figure[12](https://arxiv.org/html/2610.22564#S9.F12)\. For the tropical cyclone regression tasks in Table[3](https://arxiv.org/html/2610.22564#S3.T3), the maximum sustained wind speed is predicted from a triplet of consecutive satellite images or from the storm category \(SC\) defined by the Saffir\-Simpson scale[Simpson \[1974\]](https://arxiv.org/html/2610.22564#bib.bib48)\. We report the optimal accuracy intervals from Theorem[2\.9](https://arxiv.org/html/2610.22564#S2.Thmtheorem9)mean over2020random subsets of sizeK=1​kK=1ksampled from the train and test sets,Kersize¯train=7\.65±0\.19\\overline\{\\operatorname\{Kersize\}\}\_\{\\mathrm\{train\}\}=7\.65\\pm 0\.19,Kersize¯test=6\.76±0\.15\\overline\{\\operatorname\{Kersize\}\}\_\{\\mathrm\{test\}\}=6\.76\\pm 0\.15\. The RMSE values, in knots, of the leaderboard winning models of[DrivenData \[2021\]](https://arxiv.org/html/2610.22564#bib.bib49)were computed on the test dataset\. The dataset consists of single\-channel long\-wave infrared satellite images acquired every 15 minutes, paired with one\-minute maximum sustained wind speeds in knots\. Using the challenge’s storm\-level splits andTorchGeodata loader[Stewart et al\. \[2025\]](https://arxiv.org/html/2610.22564#bib.bib47), we obtained approximately70​k70\\mathrm\{k\}training and44​k44\\mathrm\{k\}test samples\. We resized images to366×366366\\times 366pixels and standardized the wavelet features on the train and test splits\. The wind\-speed annotations are from[National Aeronautics and Space Administration \[2024\]](https://arxiv.org/html/2610.22564#bib.bib54)\. As these annotations are operational intensity estimates rather than direct point measurements, we modeled their noise as heteroskedastic, with uncertainty increasing with wind speed\. This is motivated by previous studies of tropical\-cyclone intensity and wind\-speed retrieval uncertainty[Torn and Snyder \[2012\]](https://arxiv.org/html/2610.22564#bib.bib52),[Ruf et al\. \[2018\]](https://arxiv.org/html/2610.22564#bib.bib53), including approximately1\.4​m​s−11\.4\\penalty\\ \\mathrm\{m\\,s^\{\-1\}\}low\-wind and17\.2%17\.2\\%high\-wind uncertainties[Ruf et al\. \[2018\]](https://arxiv.org/html/2610.22564#bib.bib53)\. With wind speedyymeasured in knots, we used the phenomenological uncertainty model

τ𝒴​\(y\)=\{2\.7,y<39,0\.17​y,y≥39,\\tau\_\{\\mathcal\{Y\}\}\(y\)=\\begin\{cases\}2\.7,&y<39,\\\\ 0\.17y,&y\\geq 39,\\end\{cases\}where3939knots approximates20​m​s−120\\penalty\\ \\mathrm\{m\\,s^\{\-1\}\},2\.72\.7knots corresponds to approximately1\.39​m​s−11\.39\\penalty\\ \\mathrm\{m\\,s^\{\-1\}\}, and the high\-wind branch represents approximately17%17\\%relative uncertainty\. These values motivated our label\-noise model but are not intended as a direct recalibration of the uncertainty estimates\. Forτ𝒳=0\.0\\tau\_\{\\mathcal\{X\}\}=0\.0and the same heteroskedastic noise model forτ𝒴\\tau\_\{\\mathcal\{Y\}\}with otherwise the same parameters, we have thatKersize⁡\(𝒟Mtest′,2\)K=5\.91\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{test\}\}\},2\)\_\{K\}=5\.91kts\. For the same input threshold andτ𝒴=0\.01\\tau\_\{\\mathcal\{Y\}\}=0\.01with otherwise the same parameters, we have thatKersize⁡\(𝒟Mtest′,2\)K=2\.36\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{test\}\}\},2\)\_\{K\}=2\.36kts\. The error of the optimal regressor on𝒟Mtest′\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{test\}\}\}is given byR∗=4\.3215±0\.1095R\_\{\*\}=4\.3215\\pm 0\.1095\.

As a sanity check, we considered theTropical Cyclone Storm Categories \(SC\)dataset, we used only the labels from the tropical cyclone open\-source dataset from[Huggingface](https://huggingface.co/datasets/TCBench/TCBench)and consider the task of predicting the wind speed from the hurricane and storm categories of the Saffir\-Simpson scale[Simpson \[1974\]](https://arxiv.org/html/2610.22564#bib.bib48)\. We computed the average kernel size from the input of the storm category and bins containing the associated wind speeds in the train and test datasets\. We assumed noiseless targets and setτ𝒴=0\\tau\_\{\\mathcal\{Y\}\}=0\. Here we obtained accuracy bounds on the train dataset of\[3\.34,6\.68\]\[3\.34,6\.68\]and\[3\.23,6\.45\]\[3\.23,6\.45\]on the test dataset\. Note that these intervals are in the same order of magnitude as the ones computed on the tropical cyclone dataset reported in Table[3](https://arxiv.org/html/2610.22564#S3.T3)\.

ForUCI Energy Efficiencyopen\-source datasets[Tsanas and Xifara \[2012\]](https://arxiv.org/html/2610.22564#bib.bib59)from[UCI](https://archive.ics.uci.edu/dataset/242/energy+efficiency)with targetsY1Y\_\{1\}andY2Y\_\{2\}, we standardized the input variables using the full set\. No measurement\-noise models were available, soτ𝒳\\tau\_\{\\mathcal\{X\}\}was selected by the quantile\-based rule andτ𝒴=0\\tau\_\{\\mathcal\{Y\}\}=0\. We computed the average kernel size from feasible sets as a function of the maximum number of nearest neighbors and reached convergence with threshold10−410^\{\-4\}atNmax=100N\_\{\\max\}=100, see Figure[10](https://arxiv.org/html/2610.22564#S9.F10)\. For the ablation over quantiles see Figure[12](https://arxiv.org/html/2610.22564#S9.F12)\. This dataset[Tsanas and Xifara \[2012\]](https://arxiv.org/html/2610.22564#bib.bib59)contains eight input variables \(relative compactness, surface area, wall area, roof area, overall height, orientation, glazing area, glazing area distribution\) and two target variables, the heating load \(Y1Y\_\{1\}\) and cooling load \(Y2Y\_\{2\}\)\. The best model errors in RMSE were from\[[Žegklitz and Pošík, 2017](https://arxiv.org/html/2610.22564#bib.bib58), Table 5\]\. We assumed noiseless targets and setτ𝒴=0\\tau\_\{\\mathcal\{Y\}\}=0, which means that the target criterion was inactive in Algorithm[1](https://arxiv.org/html/2610.22564#alg1)\. The error of the optimal regressor on𝒟Mtest′\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{test\}\}\}is given byR∗=0\.2767R\_\{\*\}=0\.2767forY1Y\_\{1\}and byR∗=0\.7734R\_\{\*\}=0\.7734forY2Y\_\{2\}\.

For theUCI Concrete Compressive Strengthopen\-source dataset[Yeh \[1998\]](https://arxiv.org/html/2610.22564#bib.bib61)from[UCI](https://archive.ics.uci.edu/dataset/165/concrete+compressive+strength), we standardized the input variables using the full dataset\. No measurement\-noise models were available, soτ𝒳\\tau\_\{\\mathcal\{X\}\}was selected by the quantile\-based rule andτ𝒴=0\\tau\_\{\\mathcal\{Y\}\}=0\. We computed the average kernel size from feasible sets as a function of the maximum number of nearest neighbors and reached convergence with threshold10−410^\{\-4\}atNmax=50N\_\{\\max\}=50, see Figure[11](https://arxiv.org/html/2610.22564#S9.F11)\. For the ablation over quantiles see Figure[12](https://arxiv.org/html/2610.22564#S9.F12)\. For this dataset[Yeh \[1998\]](https://arxiv.org/html/2610.22564#bib.bib61)there are eight input variables \(cement, blast furnace slag, fly ash, water, superplasticizer, coarse aggregate, fine aggregate, and age\) and one target variable, the concrete compressive strength\. The best model errors in RMSE were from the benchmark results reported in\[[Pan et al\., 2024](https://arxiv.org/html/2610.22564#bib.bib60), Table 10\]\. The error of the optimal regressor on𝒟Mtest′\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{test\}\}\}is given byR∗=1\.7136R\_\{\*\}=1\.7136\.

For theKAERI Critical Heat Flux \(CHF\)open\-source dataset with uniform axial heating[Park \[2000\]](https://arxiv.org/html/2610.22564#bib.bib62)from[Kaggle](https://www.kaggle.com/datasets/kaustubhdhote/critical-heat-flux-dataset/data), we standardized the input variables using the full set\. We computed the average kernel size from feasible sets as a function of the maximum number of nearest neighbors and reached convergence with threshold10−410^\{\-4\}atNmax=50N\_\{\\max\}=50, see Figure[11](https://arxiv.org/html/2610.22564#S9.F11)\. We used five input variables \(diameter, heated length, pressure, mass flux, and equilibrium quality\) and one target variable, the critical heat flux\. We setτ𝒴\\tau\_\{\\mathcal\{Y\}\}equal to the worst\-case noise magnitude of a heteroskedastic noise model\. To account for input measurement uncertainty, we assigned uncertainties of±1%\\pm 1\\%for diameter and length,±0\.5%\\pm 0\.5\\%for pressure,±2%\\pm 2\\%for mass flux, and±0\.01\\pm 0\.01absolute for equilibrium quality\. For observationkk, the resulting input uncertainty radius was computed usingτ𝒳,k=\(∑i\(σi,k/si\)2\)1/2\\tau\_\{\\mathcal\{X\},k\}=\\left\(\\sum\_\{i\}\\left\(\\sigma\_\{i,k\}/s\_\{i\}\\right\)^\{2\}\\right\)^\{1/2\}, whereσi,k\\sigma\_\{i,k\}denotes the assumed physical measurement uncertainty of featureiifor observationkk, andsis\_\{i\}denotes the standard deviation of featureiicomputed on the full dataset\. We used the dimensionless worst\-case thresholdτ𝒳=maxk⁡τ𝒳,k=0\.171840\\tau\_\{\\mathcal\{X\}\}=\\max\_\{k\}\\tau\_\{\\mathcal\{X\},k\}=0\.171840\. We modeled target measurement uncertainty as heteroskedastic, where for a critical heat flux measurementyyinkW/m2\\mathrm\{kW/m^\{2\}\}, we define

τ𝒴​\(y\)=σfloor2\+\(r​y\)2,\\tau\_\{\\mathcal\{Y\}\}\(y\)=\\sqrt\{\\sigma\_\{\\mathrm\{floor\}\}^\{2\}\+\\left\(ry\\right\)^\{2\}\},whereσfloor=1​kW/m2\\sigma\_\{\\mathrm\{floor\}\}=1\\mathrm\{kW/m^\{2\}\}represents a constant absolute uncertainty andr=0\.1r=0\.1represents a10%10\\%relative uncertainty between targets as reported in\[[Groeneveld, 2019](https://arxiv.org/html/2610.22564#bib.bib63), Section 2\.4\]\. This is an approximate heteroskedastic measurement model and should not be interpreted as independently verified measurement uncertainties\. The best model errors were from Extra Trees, Random Forest, and Histogram Gradient Boosting regressors trained onMtrain=521M\_\{\\mathrm\{train\}\}=521samples and tested onMtest=130M\_\{\\mathrm\{test\}\}=130samples\. As we compute the average kernel size on the full dataset we do not obtain a constructed dataset solely for the test dataset and, thus, do not report the models’ errors on this\. Forτ𝒳=0\.0\\tau\_\{\\mathcal\{X\}\}=0\.0and the same heteroskedastic noise model forτ𝒴\\tau\_\{\\mathcal\{Y\}\}with otherwise the same parameters, we have thatKersize⁡\(𝒟M′,2\)M=191\.9​kW/m2\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},2\)\_\{M\}=191\.9\\mathrm\{kW/m^\{2\}\}\. Forτ𝒳=0\.171840\\tau\_\{\\mathcal\{X\}\}=0\.171840andτ𝒴=0\.01\\tau\_\{\\mathcal\{Y\}\}=0\.01with otherwise the same parameters, we have thatKersize⁡\(𝒟M′,2\)M=341\.4​kW/m2\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},2\)\_\{M\}=341\.4\\mathrm\{kW/m^\{2\}\}\. The larger average kernel size forτ𝒴=0\.01\\tau\_\{\\mathcal\{Y\}\}=0\.01may be due to aggregation pathologies\. The error of the optimal regressor on𝒟M′\\mathcal\{D\}\_\{M^\{\\prime\}\}is given byR∗=149\.574​kW/m2R\_\{\*\}=149\.574\\mathrm\{kW/m^\{2\}\}\.

#### 9\.1\.4Classification dataset details

For theMNISTopen\-source dataset from[Torch Vision](https://docs.pytorch.org/vision/main/generated/torchvision.datasets.MNIST.html), we converted the input images to tensors and normalized them using the MNIST training\-set channel means and standard deviations\. We computed the average kernel size from feasible sets as a function of the maximum number of nearest neighbors and reached convergence with threshold10−410^\{\-4\}atNmax=50N\_\{\\max\}=50; see Figure[13](https://arxiv.org/html/2610.22564#S9.F13)\. MNIST contains single\-channel grayscale images of handwritten digits of size28×2828\\times 28from00to99\. For MNIST, we computed the accuracies on the test set and the constructed test set for an EfficientNet B0,ϕ2​n​d\\phi\_\{2nd\}andϕ3​r​d\\phi\_\{3rd\}with further random initializations of this model\. The accuracy of the optimal classifier on𝒟Mtest′\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{test\}\}\}is given byAcc∗=100\.00\\operatorname\{Acc\}\_\{\*\}=100\.00\.

For theCIFAR\-10open\-source dataset from[Torch Vision](https://docs.pytorch.org/vision/main/generated/torchvision.datasets.CIFAR10.html), we converted the input images to tensors and normalized them using the CIFAR\-10 training\-set channel means and standard deviations\. We computed the average kernel size from feasible sets as a function of the maximum number of nearest neighbors and reached convergence with threshold10−410^\{\-4\}atNmax=50N\_\{\\max\}=50, see Figure[13](https://arxiv.org/html/2610.22564#S9.F13)\. CIFAR\-10 contains three\-channel color images of objects of size32×3232\\times 32from1010different classes\. For CIFAR\-10, we computed the accuracies on the test set and the constructed test set for a pretrained ResNet56,ϕ2​n​d\\phi\_\{2nd\}, and pretrained ShuffleNetV2,ϕ3​r​d\\phi\_\{3rd\}, from[Fu \[2021\]](https://arxiv.org/html/2610.22564#bib.bib56)and retrained on the train dataset\. The accuracy forϕ1​s​t\\phi\_\{1st\}is reported from the CIFAR\-10 Kaggle[leaderboard](https://www.kaggle.com/competitions/mu-cifar10/leaderboard)\. The accuracy of the optimal classifier on𝒟Mtest′\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{test\}\}\}is given byAcc∗=88\.43\\operatorname\{Acc\}\_\{\*\}=88\.43\.

For theRESISC45open\-source dataset[Cheng et al\. \[2017\]](https://arxiv.org/html/2610.22564#bib.bib50)from[TorchGeo](https://docs.torchgeo.org/en/v0.3.1/_modules/torchgeo/datamodules/resisc45.html), the input images were converted to tensors\. We computed the average kernel size from feasible sets as a function of the maximum number of nearest neighbors and reached convergence with threshold10−410^\{\-4\}atNmax=200N\_\{\\max\}=200, see Figure[13](https://arxiv.org/html/2610.22564#S9.F13)\. The RESISC45 dataset[Cheng et al\. \[2017\]](https://arxiv.org/html/2610.22564#bib.bib50)is a publicly available benchmark for remote\-sensing scene classification\. It contains approximately31\.5​k31\.5kimages spanning4545land\-use and scene categories, with substantial variation in spatial resolution, viewpoint, illumination, and background\. The task is to map each RGB image of size256×256256\\times 256to one of the4545landcover classes\. The accuracies on the test dataset with a20/8020/80train/test split are from the best models from\[[Cheng et al\., 2017](https://arxiv.org/html/2610.22564#bib.bib50), Table 6\]\. For RESISC45, the train and test intervals were computed from the mean average kernel sizes over2020randomly selected subsets of3​k3\\mathrm\{k\}samples,100​Kersize¯train=16\.15±2\.37%100\\,\\overline\{\\operatorname\{Kersize\}\}\_\{\\mathrm\{train\}\}=16\.15\\pm 2\.37\\%and100​Kersize¯test=17\.64±1\.73%100\\,\\overline\{\\operatorname\{Kersize\}\}\_\{\\mathrm\{test\}\}=17\.64\\pm 1\.73\\%\. The values shown in the ablation figures, such as Figure[8](https://arxiv.org/html/2610.22564#S9.F8), correspond to individual subsets and are not used directly to compute these intervals\. The accuracy of the optimal classifier on𝒟Mtest′\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{test\}\}\}is given byAcc∗=91\.33\\operatorname\{Acc\}\_\{\*\}=91\.33\.

For theEUROSATopen\-source dataset[Helber et al\. \[2019\]](https://arxiv.org/html/2610.22564#bib.bib57)we used the RGB version of the dataset provided[by TorchGeo on HuggingFace](https://huggingface.co/datasets/torchgeo/eurosat)together with the provided split into training, validation and testing\. The input images were converted to tensors and normalized to to \[\-1,1\]\. We computed the average kernel size from feasible sets as a function of the maximum number of nearest neighbors and reached convergence atNmax=200N\_\{\\max\}=200, see Figure[13](https://arxiv.org/html/2610.22564#S9.F13)\. The EUROSAT dataset[Helber et al\. \[2019\]](https://arxiv.org/html/2610.22564#bib.bib57)is a publicly available benchmark for land\-use and land\-cover classification based on Sentinel\-2 satellite imagery\. It contains27​k27klabeled image patches distributed across1010classes, including forests, residential areas, agricultural land, rivers, and industrial sites\. The dataset provides both RGB and multispectral imagery and captures substantial variation in geographic location, land\-cover structure, and spectral characteristics\. We chose the classification task mapping RGB images of size64×6464\\times 64to1010different landcover classes\. The best model’s test\-set accuracies is from\[[Adegun et al\., 2023](https://arxiv.org/html/2610.22564#bib.bib51), Table 5\]and a locally trained DNNs\. The accuracy of the optimal classifier on𝒟Mtest′\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{test\}\}\}is given byAcc∗=97\.94\\operatorname\{Acc\}\_\{\*\}=97\.94\.

0\.10\.10\.20\.20\.30\.30\.40\.4000\.50\.511qRSq\_\{\\mathrm\{RS\}\}Kersize⁡\(𝒟M′,1\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},1\)\_\{K\}andτ𝒳\\tau\_\{\\mathcal\{X\}\}RESISC45 quantile ablationAK\\mathrm\{AK\}trainAK\\mathrm\{AK\}testτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-3 trainτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-3 test0\.10\.10\.20\.20\.30\.30\.40\.4000\.50\.511qMNq\_\{\\mathrm\{MN\}\}MNIST quantile ablationAK\\mathrm\{AK\}trainAK\\mathrm\{AK\}testτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-2 trainτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-2 test0\.10\.10\.20\.20\.30\.30\.40\.4000\.50\.511qESq\_\{\\mathrm\{ES\}\}QuantileKersize⁡\(𝒟M′,1\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},1\)\_\{K\}andτ𝒳\\tau\_\{\\mathcal\{X\}\}EUROSAT quantile ablationAK\\mathrm\{AK\}trainAK\\mathrm\{AK\}testτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-2 trainτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-2 test0\.10\.10\.20\.20\.30\.30\.40\.4000\.50\.511qC10q\_\{\\mathrm\{C10\}\}QuantileCIFAR\-10 quantile ablationAK\\mathrm\{AK\}trainAK\\mathrm\{AK\}testτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-2 trainτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-2 testFigure 8:Average kernel size,Kersize⁡\(𝒟M′,1\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},1\)\_\{K\}\(AK\\mathrm\{AK\}\), as a function of the quantileqqfor the classification datasets\. The additional ticks on the x\-axis indicate the quantiles for the computation ofτ𝒳​\(q\)\\tau\_\{\\mathcal\{X\}\}\(q\)\. The number of anchor samplesKKare in Table[4](https://arxiv.org/html/2610.22564#S3.T4)\.In addition to Figure[8](https://arxiv.org/html/2610.22564#S9.F8)indicating the choice of quantiles for the input space thresholdsτ𝒳\\tau\_\{\\mathcal\{X\}\}, the Figure[14](https://arxiv.org/html/2610.22564#S9.F14)contains a full ablation across all quantilesq∈\[0,1\]q\\in\[0,1\]\.

#### 9\.1\.5Sensitivity of the average kernel size to noise

We applied different levels of label noise on MNIST and EUROSAT and computed the average kernel sizes across quantiles\. Figure[9](https://arxiv.org/html/2610.22564#S9.F9)shows the estimated average kernel size as a function of the quantileqqused to compute the thresholdτ𝒳​\(q\)\\tau\_\{\\mathcal\{X\}\}\(q\)\. For both datasets, the average kernel size increases with both the quantileqqand the target noise levelσy\\sigma\_\{y\}\. Larger quantiles produce larger thresholdsτ𝒳​\(q\)\\tau\_\{\\mathcal\{X\}\}\(q\), thus Algorithm[1](https://arxiv.org/html/2610.22564#alg1)yields larger feasible sets and therefore more heterogeneous targets in a given feasible set, while larger noise levels increase label dispersion within these sets\. The MNISTσy=0\\sigma\_\{y\}=0curve in Figure[9](https://arxiv.org/html/2610.22564#S9.F9)remains near zero for small quantiles\. In contrast, EUROSAT exhibits substantial average kernel size already at moderate quantiles, indicating greater intrinsic ambiguity under the chosen pseudo\-metric\. Overall, the plots show that the average kernel size increases consistently with increasing aleatoric label uncertainty\.

000\.20\.20\.40\.40\.60\.60\.80\.811000\.20\.20\.40\.40\.60\.60\.80\.8QuantileKersize⁡\(𝒟M′,1\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},1\)\_\{K\}EUROSAT with label noiseσy\\sigma\_\{y\}=cleanσy\\sigma\_\{y\}=0\.1σy\\sigma\_\{y\}=0\.2σy\\sigma\_\{y\}=0\.3σy\\sigma\_\{y\}=0\.4σy\\sigma\_\{y\}=0\.5σy\\sigma\_\{y\}=0\.6σy\\sigma\_\{y\}=0\.7σy\\sigma\_\{y\}=0\.8σy\\sigma\_\{y\}=0\.9σy\\sigma\_\{y\}=1\.0

000\.20\.20\.40\.40\.60\.60\.80\.811000\.20\.20\.40\.40\.60\.60\.80\.8QuantileMNIST with label noise

Figure 9:EUROSAT and MNIST train datasets plots of average kernel size for different label noise levels versus the quantileqqused for computing the thresholdτ𝒳​\(q\)\\tau\_\{\\mathcal\{X\}\}\(q\)\. The number of anchor samplesKKis the full train set size \(cmp\. Table[4](https://arxiv.org/html/2610.22564#S3.T4)\) and the average kernel size is computed withNm​a​x=200N\_\{max\}=200\.

### 9\.2Ablation studies

101050501001002002003003004504500022446688Kersize⁡\(𝒟M′,2\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},2\)\_\{K\}andτ𝒳\\tau\_\{\\mathcal\{X\}\}Tropical CycloneNm​a​xN\_\{max\}ablationAK \(train\)τ𝒳/500\\tau\_\{\\mathcal\{X\}\}/500\(train\)AK \(test\)τ𝒳/500\\tau\_\{\\mathcal\{X\}\}/500\(test\)10105050100100200200300300450450001122⋅10−2\\cdot 10^\{\-2\}Synthetic regressionNm​a​xN\_\{max\}ablationAK \(train\)AK \(test\)τ𝒳\\tau\_\{\\mathcal\{X\}\}\(train\)τ𝒳\\tau\_\{\\mathcal\{X\}\}\(test\)101050507070100100200200300300000\.20\.20\.40\.40\.60\.6Energy efficiencyY1Y\_\{1\}Nm​a​xN\_\{max\}ablationAKτ𝒳\\tau\_\{\\mathcal\{X\}\}101050507070100100200200300300000\.50\.5111\.51\.5NmaxN\_\{\\max\}Energy efficiencyY2Y\_\{2\}Nm​a​xN\_\{max\}ablationAKτ𝒳\\tau\_\{\\mathcal\{X\}\}Figure 10:Average kernel size,A​KAKor alsoKersize⁡\(𝒟M′,2\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},2\)\_\{K\}, for regression datasets as a function of the maximum number of nearest neighborsNm​a​xN\_\{max\}used in the thresholdτ𝒳\\tau\_\{\\mathcal\{X\}\}and feasible set computation\. For synthetic regression the thresholds are chosen based on the worst\-case noise and otherwise, the input threshold is chosen as theqt​hq^\{th\}quantile of the nearest\-neighbor distances according to \([9\.2](https://arxiv.org/html/2610.22564#S9.E2)\)\. The quantileqqand number of anchor samplesKKfor train and test splits can be found in Table[2](https://arxiv.org/html/2610.22564#S3.T2)\.10105050707010010020020030030000112233Kersize⁡\(𝒟M′,2\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},2\)\_\{K\}andτ𝒳\\tau\_\{\\mathcal\{X\}\}Concrete strengthNm​a​xN\_\{max\}ablationAKτ𝒳\\tau\_\{\\mathcal\{X\}\}10105050707010010020020030030000100100200200Nm​a​xN\_\{max\}Critical heat fluxNm​a​xN\_\{max\}ablationAKτ𝒳\\tau\_\{\\mathcal\{X\}\}Figure 11:Average kernel size,A​KAKor alsoKersize⁡\(𝒟M′,2\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},2\)\_\{K\}, for regression datasets as a function of the maximum number of nearest neighborsNm​a​xN\_\{max\}used in the thresholdτ𝒳\\tau\_\{\\mathcal\{X\}\}and feasible set computation\. For CHF the thresholds are chosen based on the worst\-case noise and for concrete strength the input threshold is chosen as theqt​hq^\{th\}quantile of the nearest\-neighbor distances according to \([9\.2](https://arxiv.org/html/2610.22564#S9.E2)\)\. The quantileqqand number of anchor samplesKKfor train and test splits can be found in Table[2](https://arxiv.org/html/2610.22564#S3.T2)\.Table 6:Different regressors errors in RMSE\. The average kernel size is computed from the reference dataset𝒟Mtrain′\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{train\}\}\}\. Modelsϕno\\phi\_\{n\}^\{o\}, the GP and SVR, satisfyRMSEtrain<12​Kersize\\mathrm\{RMSE\}\_\{\\mathrm\{train\}\}<\\frac\{1\}\{2\}\\operatorname\{Kersize\}, whereas modelsϕn\\phi\_\{n\}satisfy12​Kersize≤RMSEtrain≤Kersize\\frac\{1\}\{2\}\\operatorname\{Kersize\}\\leq\\mathrm\{RMSE\}\_\{\\mathrm\{train\}\}\\leq\\operatorname\{Kersize\}\. The table reports the training RMSE, the test RMSE, the RMSE on the constructed dataset𝒟Mtest′\\mathcal\{D\}\_\{M^\{\\prime\}\_\{\\mathrm\{test\}\}\}, and the empirical Lipschitz estimateL^\\widehat\{L\}\.Mtrain=90M\_\{\\mathrm\{train\}\}=90,Mtest=810M\_\{\\mathrm\{test\}\}=810,Mtrain′=650M^\{\\prime\}\_\{\\mathrm\{train\}\}=650andMtest′=42\.9​kM^\{\\prime\}\_\{\\mathrm\{test\}\}=42\.9k\.Table 7:We setη=RMSEtrain\\eta=\\text\{RMSE\}\_\{\\mathrm\{train\}\}and compute the quantity1/τ𝒳​\(τ𝒴−2​η\)1/\\tau\_\{\\mathcal\{X\}\}\(\\tau\_\{\\mathcal\{Y\}\}\-2\\eta\)which relates to the lower bound in Proposition[2\.5](https://arxiv.org/html/2610.22564#S2.Thmtheorem5)by taking the worst\-case distance of similar targets and instead of the pointwise error the average error\.Table 8:Average kernel size,A​KAKor alsoKersize⁡\(𝒟M′,2\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},2\)\_\{K\}, for increasing input noise levels\.
Table 9:Average kernel size,A​KAKor alsoKersize⁡\(𝒟M′,2\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},2\)\_\{K\}, for increasing target noise levels\.

2⋅10−22\\cdot 10^\{\-2\}3⋅10−23\\cdot 10^\{\-2\}4⋅10−24\\cdot 10^\{\-2\}5⋅10−25\\cdot 10^\{\-2\}6⋅10−26\\cdot 10^\{\-2\}7⋅10−27\\cdot 10^\{\-2\}8⋅10−28\\cdot 10^\{\-2\}9⋅10−29\\cdot 10^\{\-2\}0\.10\.122334455667788Kersize⁡\(𝒟M′,2\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},2\)\_\{K\}andτ𝒳​\(q\)\\tau\_\{\\mathcal\{X\}\}\(q\)Tropical Cyclone quantile ablationAK \(train\)AK \(test\)τ𝒳/100\\tau\_\{\\mathcal\{X\}\}/100\(train\)τ𝒳/100\\tau\_\{\\mathcal\{X\}\}/100\(test\)2⋅10−22\\cdot 10^\{\-2\}3⋅10−23\\cdot 10^\{\-2\}4⋅10−24\\cdot 10^\{\-2\}5⋅10−25\\cdot 10^\{\-2\}6⋅10−26\\cdot 10^\{\-2\}7⋅10−27\\cdot 10^\{\-2\}8⋅10−28\\cdot 10^\{\-2\}9⋅10−29\\cdot 10^\{\-2\}0\.10\.10\.50\.50\.540\.540\.580\.580\.620\.620\.660\.660\.70\.7Energy efficiencyY1Y\_\{1\}quantile ablationAKτ𝒳\\tau\_\{\\mathcal\{X\}\}2⋅10−22\\cdot 10^\{\-2\}3⋅10−23\\cdot 10^\{\-2\}4⋅10−24\\cdot 10^\{\-2\}5⋅10−25\\cdot 10^\{\-2\}6⋅10−26\\cdot 10^\{\-2\}7⋅10−27\\cdot 10^\{\-2\}8⋅10−28\\cdot 10^\{\-2\}9⋅10−29\\cdot 10^\{\-2\}0\.10\.1000\.40\.40\.80\.81\.21\.21\.61\.6Energy efficiencyY2Y\_\{2\}quantile ablationAK Y2τ𝒳\\tau\_\{\\mathcal\{X\}\}Y22⋅10−22\\cdot 10^\{\-2\}3⋅10−23\\cdot 10^\{\-2\}4⋅10−24\\cdot 10^\{\-2\}5⋅10−25\\cdot 10^\{\-2\}6⋅10−26\\cdot 10^\{\-2\}7⋅10−27\\cdot 10^\{\-2\}8⋅10−28\\cdot 10^\{\-2\}9⋅10−29\\cdot 10^\{\-2\}0\.10\.10\.50\.5111\.51\.5222\.52\.533qqConcrete strength quantile ablationAK100​τ𝒳100\\tau\_\{\\mathcal\{X\}\}Figure 12:Average kernel size,A​KAKor alsoKersize⁡\(𝒟M′,2\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},2\)\_\{K\}, and scaled thresholdsτ𝒳​\(q\)\\tau\_\{\\mathcal\{X\}\}\(q\)as functions of the quantile parameterqqfor the regression datasets\. Computed on subsets ofK=1​kK=1ksamples from the tropical cyclone training and test datasets\. The thresholdτ𝒳​\(q\)\\tau\_\{\\mathcal\{X\}\}\(q\)is computed for each quantileqq\. The number of anchor samplesKKandNmaxN\_\{\\max\}are in Table[2](https://arxiv.org/html/2610.22564#S3.T2)\.10105050100100200200300300450450005⋅10−25\\cdot 10^\{\-2\}0\.10\.10\.150\.15Kersize⁡\(𝒟M′,1\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},1\)\_\{K\}andτ𝒳\\tau\_\{\\mathcal\{X\}\}CIFAR\-10Nm​a​xN\_\{max\}ablationAK \(train\)AK \(test\)τ𝒳/500\\tau\_\{\\mathcal\{X\}\}/500\(train\)τ𝒳/500\\tau\_\{\\mathcal\{X\}\}/500\(test\)10105050100100200200300300450450002244⋅10−2\\cdot 10^\{\-2\}MNISTNm​a​xN\_\{max\}ablationAK \(train\)AK \(test\)τ𝒳/500\\tau\_\{\\mathcal\{X\}\}/500\(train\)τ𝒳/500\\tau\_\{\\mathcal\{X\}\}/500\(test\)10105050100100200200300300450450005⋅10−25\\cdot 10^\{\-2\}0\.10\.10\.150\.150\.20\.2RESISC45Nm​a​xN\_\{max\}ablationAK \(train\)AK \(test\)τ𝒳/500\\tau\_\{\\mathcal\{X\}\}/500\(train\)τ𝒳/500\\tau\_\{\\mathcal\{X\}\}/500\(test\)10105050100100200200300300450450002244⋅10−2\\cdot 10^\{\-2\}Nm​a​xN\_\{max\}EUROSATNm​a​xN\_\{max\}ablationAK \(train\)AK \(test\)τ𝒳/500\\tau\_\{\\mathcal\{X\}\}/500\(train\)τ𝒳/500\\tau\_\{\\mathcal\{X\}\}/500\(test\)Figure 13:Average kernel size,A​KAKor alsoKersize⁡\(𝒟M′,1\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},1\)\_\{K\}, for classification datasets as a function of the maximum number of nearest neighborsNm​a​xN\_\{max\}used in the thresholdτ𝒳\\tau\_\{\\mathcal\{X\}\}computation\. The threshold is chosen as theqt​hq^\{th\}quantile of the nearest\-neighbor distances according to \([9\.2](https://arxiv.org/html/2610.22564#S9.E2)\)\. The quantileqqand number of anchor samplesKKfor train and test splits can be found in Table[4](https://arxiv.org/html/2610.22564#S3.T4)\.0\.10\.10\.20\.20\.30\.30\.40\.40\.50\.50\.60\.60\.70\.70\.80\.80\.90\.911000\.20\.20\.40\.40\.60\.60\.80\.811QuantileKersize⁡\(𝒟M′,1\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},1\)\_\{K\}andτ𝒳\\tau\_\{\\mathcal\{X\}\}Classification datasets quantile ablationAK\\mathrm\{AK\}C10 trainAK\\mathrm\{AK\}C10 testτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-2 C10 testτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-2 C10 trainAK\\mathrm\{AK\}ES trainAK\\mathrm\{AK\}ES testτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-2 ES trainτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-2 ES testAK\\mathrm\{AK\}RS trainAK\\mathrm\{AK\}RS testτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-3 RS trainτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-3 RS testAK\\mathrm\{AK\}MN trainAK\\mathrm\{AK\}MN testτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-2 MN trainτ𝒳\\tau\_\{\\mathcal\{X\}\}e\-2 MN testFigure 14:Average kernel size,A​KAKor alsoKersize⁡\(𝒟M′,1\)K\\operatorname\{Kersize\}\(\\mathcal\{D\}\_\{M^\{\\prime\}\},1\)\_\{K\}, andτ𝒳​\(q\)\\tau\_\{\\mathcal\{X\}\}\(q\)as a function of the quantile parameterqqfor the different classification datasets, MNIST \(MN\), CIFAR\-10 \(C10\), EUROSAT \(ES\) and RESISC45 \(RS\)\. The thresholdτ𝒳​\(q\)\\tau\_\{\\mathcal\{X\}\}\(q\)is chosen for each quantileqqaccording to \([9\.2](https://arxiv.org/html/2610.22564#S9.E2)\)\. The number of anchor samplesKKfor train and test splits can be found in Table[4](https://arxiv.org/html/2610.22564#S3.T4)\.