Deterministic Bounds on Accuracy and Stability of Metric-Space Regression and Classification

Nina Maria Gottschling; Jakob Gawlikowski; Michele Caprio

cs.LGOct 15, 2026

Deterministic Bounds on Accuracy and Stability of Metric-Space Regression and Classification

Authors: Nina Maria Gottschling, Jakob Gawlikowski, Michele Caprio

Organizations: Computing and Computational Sciences, Oak Ridge National Laboratory, Oak Ridge, Tennessee. · German Aerospace Center (DLR), Remote Sensing Technology Institute, Wessling, Germany. · 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 times the square root of two. 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.

Figures & tables

Figure 1: Accuracy bounds: from data ambiguity to a reference scale on the constructed dataset. For an input $x$ , the thresholds define a feasible set $F_{x}$ (Definition 1.1 ) of target values lying within the worst-case noise distance. The target values within this set may differ. The average kernel size, $K$ , 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) , 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 between $K/2$ and $K$ . Model errors reported on the original dataset are shown for descriptive comparison. Both the finite feasible sets and the value of $K$ depend 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 , are invoked.

Quantity	Object	Model-class dependent?	Sampling assumptions	Directly computable from one dataset?
Bayes risk	Distribution decision risk	No	A data-generating law is required	Generally not
Conditional variance	Distribution conditional dispersion	No	Usually i.i.d. sampling plus regularity or replication	Only under additional structure
VC/Rademacher complexity	Model-class complexity	Yes	Usually i.i.d. sampling	Sometimes, bounds a restricted class
Average kernel size (proposed)	Quantity in accuracy bounds	No	None for the deterministic Theorem 2.9	Yes, once metrics and thresholds are fixed
Distributional analogue average kernel size (proposed)	Conditional pairwise dispersion	No	Standard Borel setting and integrability	Not without a sampling or estimation scheme

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

Dataset	$d_{\mathcal{X}}$	$d_{\mathcal{Y}}$	$p$	$M_{\mathrm{train}}$	$M_{\mathrm{test}}$	$M^{\prime}_{\mathrm{test}}$	$K_{\mathrm{train}}$	$K_{\mathrm{test}}$	$N_{\max}$	$\overline{N(k)}$	q	$(\tau_{\mathcal{X}})_{\mathrm{train}}$	$(\tau_{\mathcal{X}})_{\mathrm{test}}$
Synthetic	$\ell_{2}$	$\ell_{2}$	$2$	$90$	$810$	$42.9k$	$90$	$810$	$300$	$53.1$	-	$0.014$	$0.014$
Tropical Cyclone ∗	Wavelet- $\ell_{2}$	$\ell_{2}$	$2$	$70k$	$44k$	$153.7k$	$1k$	$1k$	$300$	$153.7$	$0.1$	$284.7$	$227.7$
Energy Efficiency $Y_{1}$	$\ell_{2}$	$\ell_{2}$	$2$	$768$	-	$1.3k$	$768$	-	$300$	$1.75$	$0.02$	$0.65$	-
Energy Efficiency $Y_{2}$	$\ell_{2}$	$\ell_{2}$	$2$	$768$	-	$1.3k$	$768$	-	$300$	$1.75$	$0.02$	$0.65$	-
Concrete Strength	$\ell_{2}$	$\ell_{2}$	$2$	$1030$	-	$1.1k$	$1030$	-	$300$	$1.10$	$0.02$	$0.0$	-
Critical Heat Flux	$\ell_{2}$	$\ell_{2}$	$2$	$651$	-	$59.2k$	$651$	-	$300$	$90.9$	-	$0.17$	-

Table 2: Parameters for the regression tasks . Here,

M

denotes the original dataset size,

M^{\prime}

the constructed dataset size generated by Algorithm 1 ,

K

the number of anchors,

N_{\max}

the maximum number of nearest neighbors and

\overline{N(k)}

the mean size of the feasible sets from the test dataset. ∗ : for tropical cyclone the mean

\pm

the standard deviation of

\tau_{\mathcal{X}}

across

20

subsets of size

1k

are:

(\overline{\tau_{\mathcal{X}}})_{\mathrm{train}}=284.7\pm 11.5

(\overline{\tau_{\mathcal{X}}})_{\mathrm{test}}=227.7\pm 8.9

\overline{N(k)}=169.4\pm 2.7

Dataset	Interval train	Interval test	$\phi_{1st}$ , $M_{\mathrm{test}}$	$M^{\prime}_{\mathrm{test}}$	$\phi_{2nd}$ , $M_{\mathrm{test}}$	$M^{\prime}_{\mathrm{test}}$	$\phi_{3rd}$ , $M_{\mathrm{test}}$	$M^{\prime}_{\mathrm{test}}$
Synthetic	$[0.0102,0.0203]$	$[0.0113,0.0225]$	$0.0169$	$0.0221$	$0.0161$	$0.0225$	$0.0607$	$0.0720$
Tropical Cyclone ∗	$[3.83,7.65]$	$[3.38,6.76]$	$6.26$	-	$6.42$	-	$6.46$	-
Energy Efficiency $Y_{1}$ (1)	$[0.28,0.55]$	-	$0.51$	-	$0.56$	-	$0.67$	-
Energy Efficiency $Y_{2}$ (1)	$[0.78,1.55]$	-	$1.28$	-	$1.64$	-	$1.79$	-
Concrete Strength (1)	$[1.41,2.81]$	-	$1.97$	-	$2.08$	-	$2.10$	-
Critical Heat Flux (1)	$[106.49,212.97]$	-	$247.76$	-	$251.46$	-	$266.98$	-

Table 3: Optimal regression accuracy intervals and regressor errors . The theoretical interval from Theorem 2.9 is

\left[1/2\operatorname{Kersize}(\mathcal{D}_{M^{\prime}},p)_{K},\,\operatorname{Kersize}(\mathcal{D}_{M^{\prime}},p)_{K}\right]

. All scores for models

\phi_{n}

with

n\in\{1,2,3\}

are RMSE values,

\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 across

20

subsets of size

1k

are reported.

Panel of Figure 4 — Figure 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 $\mathcal{D}_{M^{\prime}_{\mathrm{train}}}$ . Regression models $\phi_{\mathrm{n}}^{o}$ satisfy $\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 $\phi_{\mathrm{n}}$ satisfy $\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 were $N_{\mathrm{max}}=300$ , $\tau_{\mathcal{X}}=0.014$ and $\tau_{\mathcal{Y}}=0.03$ . The exact numerical values and errors on the constructed test dataset are reported in the Appendix in Table 6 .

Dataset	$d_{\mathcal{X}}$	$d_{\mathcal{Y}}$	$p$	$M_{\mathrm{train}}$	$M_{\mathrm{test}}$	$M^{\prime}_{\mathrm{test}}$	$K_{\mathrm{train}}$	$K_{\mathrm{test}}$	$N_{\max}$	$\overline{N(k)}$	$q$	$(\tau_{\mathcal{X}})_{\mathrm{train}}$	$(\tau_{\mathcal{X}})_{\mathrm{test}}$
MNIST	Wavelet- $\ell_{2}$	$d_{H}$	$1$	$50k$	$10k$	$25.1k$	$50k$	$10k$	$200$	$2.51$	$0.1$	$4.73$	$5.38$
CIFAR-10	Wavelet- $\ell_{2}$	$d_{H}$	$1$	$40k$	$10k$	$13.0k$	$40k$	$10k$	$200$	$1.30$	$0.05$	$27.4$	$30.8$
RESISC45 ∗	Wavelet- $\ell_{2}$	$d_{H}$	$1$	$25.2k$	$6.3k$	$4.7k$	$3k$	$3k$	$200$	$1.58$	$0.05$	$31.5$	$31.8$
EUROSAT	Wavelet- $\ell_{2}$	$d_{H}$	$1$	$16.2k$	$5.4k$	$15.0k$	$16.2k$	$5.4k$	$200$	$2.77$	$0.09$	$2.44$	$2.70$

Table 4: Parameters for the classification tasks . Here,

M

denotes the original dataset size,

M^{\prime}

the constructed dataset size generated by Algorithm 1 ,

K

the number of anchors,

N_{\max}

the maximum number of nearest neighbors and

\overline{N(k)}

the mean size of the feasible sets from the test dataset. ∗ : for RESISC45 the mean

\pm

the standard deviation across

20

subsets of size

3k

are:

(\tau_{\mathcal{X}})_{\mathrm{train}}=31.5\pm 0.5

(\tau_{\mathcal{X}})_{\mathrm{test}}=31.8\pm 0.7

\overline{N(k)}=1.58\pm 0.08

Dataset	Interval train	Interval test	$\phi_{1st}$ , $M_{\mathrm{test}}$	$\phi_{2nd}$ , $M_{\mathrm{test}}$	$M^{\prime}_{\mathrm{test}}$	$\phi_{3rd}$ , $M_{\mathrm{test}}$	$M^{\prime}_{\mathrm{test}}$
MNIST	$[100.0,100.0]$	$[100.0,100.0]$	$99.53$	$99.45$	$99.78$	$99.43$	$99.77$
CIFAR-10	$[85.61,92.81]$	$[83.76,91.88]$	$89.61$ (1)	$91.19$	$79.30$	$83.20$	$73.25$
RESISC45 ∗,(1)	$[83.85,91.93]$	$[82.36,91.18]$	$90.36\pm 0.18$	$86.02\pm 0.18$	-	$85.16\pm 0.18$	-
EUROSAT	$[97.78,98.89]$	$[96.89,98.44]$	$98.00$ (1)	$98.00$ (1)	-	$97.06$	$96.63$

Table 5: Optimal classification accuracy intervals and classifier accuracies. Theoretical intervals from Corollary 2.11 are reported as percentages; explicitly, the interval is

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,

\operatorname{Acc}(\mathcal{D}_{M},\phi)

, for models

\phi_{n}

with

n\in\{1,2,3\}

are reported on the

[0,100]

scale in the three right columns. (1) : model(s) evaluated on a different test split. ∗ : for RESISC45 the mean bounds across

20

subsets of size

3k

are reported.

Panel of Figure 8 — Figure 8: Average kernel size, $\operatorname{Kersize}(\mathcal{D}_{M^{\prime}},1)_{K}$ ( $\mathrm{AK}$ ), as a function of the quantile $q$ for the classification datasets. The additional ticks on the x-axis indicate the quantiles for the computation of $\tau_{\mathcal{X}}(q)$ . The number of anchor samples $K$ are in Table 4 .

Panel of Figure 9 — Figure 9: EUROSAT and MNIST train datasets plots of average kernel size for different label noise levels versus the quantile $q$ used for computing the threshold $\tau_{\mathcal{X}}(q)$ . The number of anchor samples $K$ is the full train set size (cmp. Table 4 ) and the average kernel size is computed with $N_{max}=200$ .

Panel of Figure 10 — Figure 10: Average kernel size, $AK$ or also $\operatorname{Kersize}(\mathcal{D}_{M^{\prime}},2)_{K}$ , for regression datasets as a function of the maximum number of nearest neighbors $N_{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 the $q^{th}$ quantile of the nearest-neighbor distances according to ( 9.2 ). The quantile $q$ and number of anchor samples $K$ for train and test splits can be found in Table 2 .

Panel of Figure 11 — Figure 11: Average kernel size, $AK$ or also $\operatorname{Kersize}(\mathcal{D}_{M^{\prime}},2)_{K}$ , for regression datasets as a function of the maximum number of nearest neighbors $N_{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 the $q^{th}$ quantile of the nearest-neighbor distances according to ( 9.2 ). The quantile $q$ and number of anchor samples $K$ for train and test splits can be found in Table 2 .

Model	RMSE train	RMSE test	RMSE ${}_{D^{\prime}}$	$\widehat{L}$
$\phi_{\mathrm{GP}}^{o}$	0.000297	0.150666	0.145760	2.113529
$\phi_{\mathrm{GP}}$	0.014644	0.016850	0.021984	0.930406
$\phi_{\mathrm{SVR}}^{o}$	0.000177	0.309775	0.304252	3.889222
$\phi_{\mathrm{SVR}}$	0.013384	0.016177	0.022371	0.921996

Table 6: Different regressors errors in RMSE. The average kernel size is computed from the reference dataset

\mathcal{D}_{M^{\prime}_{\mathrm{train}}}

. Models

\phi_{n}^{o}

, the GP and SVR, satisfy

\mathrm{RMSE}_{\mathrm{train}}<\frac{1}{2}\operatorname{Kersize}

, whereas models

\phi_{n}

satisfy

\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

\mathcal{D}_{M^{\prime}_{\mathrm{test}}}

, and the empirical Lipschitz estimate

\widehat{L}

M_{\mathrm{train}}=90

M_{\mathrm{test}}=810

M^{\prime}_{\mathrm{train}}=650

and

M^{\prime}_{\mathrm{test}}=42.9k

Model	RMSE train	$1/\tau_{\mathcal{X}}(\tau_{\mathcal{Y}}-2\eta)$	$\widehat{L}$
$\phi_{\mathrm{GP}}^{o}$	0.0003	2.100	2.11
$\phi_{\mathrm{GP}}$	0.0146	0.051	0.930
$\phi_{\mathrm{SVR}}^{o}$	0.0002	2.118	3.889
$\phi_{\mathrm{SVR}}$	0.0134	0.231	0.922

Table 7: We set

\eta=\text{RMSE}_{\mathrm{train}}

and compute the quantity

1/\tau_{\mathcal{X}}(\tau_{\mathcal{Y}}-2\eta)

which relates to the lower bound in Proposition 2.5 by taking the worst-case distance of similar targets and instead of the pointwise error the average error.

Table 17

Panel of Figure 12 — Figure 12: Average kernel size, $AK$ or also $\operatorname{Kersize}(\mathcal{D}_{M^{\prime}},2)_{K}$ , and scaled thresholds $\tau_{\mathcal{X}}(q)$ as functions of the quantile parameter $q$ for the regression datasets. Computed on subsets of $K=1k$ samples from the tropical cyclone training and test datasets. The threshold $\tau_{\mathcal{X}}(q)$ is computed for each quantile $q$ . The number of anchor samples $K$ and $N_{\max}$ are in Table 2 .

Panel of Figure 13 — Figure 13: Average kernel size, $AK$ or also $\operatorname{Kersize}(\mathcal{D}_{M^{\prime}},1)_{K}$ , for classification datasets as a function of the maximum number of nearest neighbors $N_{max}$ used in the threshold $\tau_{\mathcal{X}}$ computation. The threshold is chosen as the $q^{th}$ quantile of the nearest-neighbor distances according to ( 9.2 ). The quantile $q$ and number of anchor samples $K$ for train and test splits can be found in Table 4 .

Panel of Figure 14 — Figure 14: Average kernel size, $AK$ or also $\operatorname{Kersize}(\mathcal{D}_{M^{\prime}},1)_{K}$ , and $\tau_{\mathcal{X}}(q)$ as a function of the quantile parameter $q$ for the different classification datasets, MNIST (MN), CIFAR-10 (C10), EUROSAT (ES) and RESISC45 (RS). The threshold $\tau_{\mathcal{X}}(q)$ is chosen for each quantile $q$ according to ( 9.2 ). The number of anchor samples $K$ for train and test splits can be found in Table 4 .

Statistical Learning Theory

Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.

See all 584 papers

May 10, 2026

On Uniform Error Bounds for Kernel Regression under Non-Gaussian Noise

Providing non-conservative uncertainty quantification for function estimates derived from noisy observations remains a fundamental challenge in statistical machine learning, particularly for applications in safety-critical domains. In this work, we propose novel non-asymptotic probabilistic uniform error bounds for kernel-based regression. Compared to related bounds in the literature that are restricted to (conditionally) independent sub-Gaussian noise, our bounds allow to consider a broad class of non-Gaussian distributions, such as sub-Gaussian, bounded, sub-exponential, and variance/moment-bounded noise. Moreover, our results apply to correlated and uncorrelated noise. We compare our proposed error bounds with existing results in terms of the induced uncertainty region and their performance in safe control, demonstrating the tightness of the proposed bounds.

Johannes Teutsch, Oleksii Molodchyk, Marion Leibold +2

Chair of Automatic Control Engineering, Department of Computer Engineering, Technical University of Munich, 80333 Munich, Germany · Institute of Control Systems, Hamburg University of Technology, 21073 Hamburg, Germany · Department of Electrical and Computer Engineering, National University of Singapore, 117583 Singapore

Kernel Regression Uncertainty Quantification Nonparametric Regression Convergence Analysis Kernel Methods Statistical Learning Theory

Ask PDF

Oct 16, 2026

On the tradeoff between robustness and geometric accuracy in adversarial training

For non-parametric binary classification in the presence of an adversary, we prove an optimal quantitative estimate for adversarial classifiers controlling geometric accuracy, as measured by the Hausdorff distance to the Bayes classifier, in terms or their robustness, as encoded by the adversarial budget

\varepsilon

. This rigorously shows that robust classifiers sacrifice at most

O(\sqrt{\varepsilon})

O(\varepsilon)

in accuracy, depending on the regularity of the underlying Bayes classifier. In contrast to prior work on the incompatibility of robustness and accuracy over low-complexity hypothesis classes, our work shows that high-complexity hypothesis classes allow for robust classifiers with precisely quantified accuracy. Our results apply for adversaries determined by any norm on Euclidean space and in both the infinite and finite data settings.

Rachel Morris, Ryan Murray, Kerrek Stinson

Adversarial Robustness Robust Classification Classification Adversarial Training

Ask PDF

May 5, 2026

Realizable Bayes-Consistency for General Metric Losses

We study strong universal Bayes-consistency in the realizable setting for learning with general metric losses, extending classical characterizations beyond

0

1

classification (Bousquet et al., 2020; Hanneke et al., 2021) and real-valued regression (Attias et al., 2024). Given an instance space

(X,ρ)

, a label space

(Y,\ell)

with possibly unbounded loss, and a hypothesis class

H \subseteq Y^{X}

, we resolve the realizable case of an open problem presented in Tsir Cohen and Kontorovich (2022). Specifically, we find the necessary and sufficient conditions on the hypothesis class

H

under which there exists a distribution-free learning rule whose risk converges almost surely to the best-in-class risk (which is zero) for every realizable data-generating distribution. Our main contribution is this sharp characterization in terms of a combinatorial obstruction: Similarly to Attias et al. (2024), we introduce the notion of an infinite non-decreasing

(γ_k)

-Littlestone tree, where

γ_k \to \infty

. This extends the Littlestone tree structure used in Bousquet et al. (2020) to the metric loss setting.

Dan Tsir Cohen, Steve Hanneke, Aryeh Kontorovich

1Ben-Gurion University of the Negev · 2Purdue University, USA.

Statistical Learning Theory

Ask PDF

Abstract

Statistical Learning Theory

Explore similar work

On Uniform Error Bounds for Kernel Regression under Non-Gaussian Noise

On the tradeoff between robustness and geometric accuracy in adversarial training

Realizable Bayes-Consistency for General Metric Losses