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

Nina Maria Gottschling; Jakob Gawlikowski; Michele Caprio

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.

Figure 3

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.

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 .

Figure 7

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.

Figure 7: Accuracy of models trained on train datasets of EUROSAT and MNIST with noisy labels with

\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 , abbreviated as

[1-\text{AK},1-1/2\text{AK}]

, are computed on the noisy,

\sigma_{y}=0.2

, and clean,

\sigma_{y}=0

, train and test datasets. The number of anchor samples

K

and the quantiles for computing

\tau_{\mathcal{X}}(q)

are in Table 4 . The average kernel size is computed with a larger

N_{max}=200

.

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 .

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

.

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 .

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

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 .

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 .

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 .

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

Abstract

Figures & tables

Statistical Learning Theory

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

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