PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Nina Maria Gottschling, Jakob Gawlikowski, Michele Caprio

arXiv:2610.22564v1cs.LGmath.OC

TL;DR

When inputs do not determine unique targets, noise and limited information make the input–target relation ambiguous. The paper uses data-dependent feasible sets to derive model-independent bounds; experiments show average kernel sizes rising with noise, while the framework provides a reference scale for prediction difficulty on a constructed dataset.

  • Problem

    A given input may admit multiple targets, and noisy samples generally do not reveal whether the input, target, or both were corrupted.

    Source: §1 · p. 2, §1.1 · p. 4

  • Method

    The framework uses data-dependent feasible sets and average kernel size to derive deterministic, non-asymptotic, model-independent bounds on empirical error and accuracy.

    Source: §1 · p. 3, §6 · p. 23

  • Results

    Average kernel sizes increase with input and target noise in synthetic regression and with label noise on MNIST and EUROSAT.

    Source: §4 · p. 22

  • Takeaways & Limitations

    The average kernel size provides a model-independent reference scale for empirical prediction difficulty on the constructed dataset.

    Source: §6 · p. 23

    The bounds depend on the chosen input pseudo-metric, target metric, and feasible-set construction, and do not directly account for optimization difficulty, finite model capacity, or model misspecification.

    Source: §1.2 · p. 6

Abstract

from arXiv · show

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.

1 Introduction

The paper models input-target ambiguity with feasible sets and derives model-independent bounds on prediction performance. It connects these finite-data bounds to stability, probabilistic results, and practical dataset assessment.

1 Introduction

  • Feasible sets represent the admissible targets for each input, including cases where one observed input may correspond to multiple targets.The framework uses a pseudo-metric on inputs and a metric on targets.Source: §1 · pp. 1–2

1.1 Challenges

  • Non-unique targets can impose intrinsic prediction error, while computable model-independent finite-dataset bounds are needed to assess achievable performance before extensive model selection.Expressive models may fit training data without resolving ambiguity in the input-target relation.Source: §1.1 · p. 4

1.2 Contributions

  • The framework gives deterministic, non-asymptotic bounds on best achievable empirical error and accuracy, an accuracy-stability trade-off, and a comparison bound between constructed and original datasets.The lower bounds hold across regressors and classifiers; the comparison bound applies to Lipschitz predictors under stated finite-set conditions.Source: §1.2 · pp. 4–5
  • Under probabilistic assumptions, the distributional analogue relates to Bayes risk and errors below the conditional ambiguity scale entail a positive generalization gap; experiments examine bounds across tasks and settings.An ideal two-stage sampling design also yields a finite-sample concentration bound for an estimator, distinct from Algorithm 1’s geometric quantity.Source: §1.2 · p. 5

1.3 Relation to previous work

  • The approach differs from model-class or sampling-based bounds by using finite feasible-set geometry to quantify ambiguity on realized datasets.Its distributional results connect conditional ambiguity to Bayes risk and generalization gaps under additional assumptions.Source: §1.3 · pp. 6–7

1.4 Outlook and impact

  • The bounds can inform dataset assessment and model selection before training, but do not guarantee that tuning or a particular model will attain the indicated improvement.The explicit optimal predictor can be computationally expensive because it requires an optimization problem for each input.Source: §1.4 · pp. 7–8

1.5 Outline

  • The paper presents deterministic finite-sample bounds, then probabilistic connections to Bayes risk and generalization gaps, followed by experiments across datasets and metrics.Proofs and reproducibility materials are provided later in the manuscript and appendix.Source: §1.5 · p. 8

2 Main results

The main results use a model-independent geometric framework to bound empirical error and classification accuracy on a noise-compatible constructed dataset, and to characterize how empirical losses transfer between constructed and original datasets. They also interpret ambiguity probabilistically, give conditions for a positive generalization gap, and distinguish an ideal conditional-sampling estimator from the finite-data geometric surrogate.

2.1 Problem formulation

  • The framework models inputs with a pseudo-metric and targets with a metric, assuming closed bounded target sets are compact; this accommodates indistinguishable preprocessed inputs and practical data representations.The metric-space setup also permits set-valued predictors, including finite collections of predictions.Source: §2.1 · pp. 8–10
  • Set-valued prediction loss uses worst-case Hausdorff distance, so enlarging a prediction set cannot reduce loss; coverage-oriented conventions that reward containing the target do not directly satisfy these lower bounds.This convention is intended for downstream decisions requiring uniform control over outcomes treated as possible.Source: §2.1 · p. 9

2.2 Dataset-level stability and accuracy bounds

  • When distinct targets correspond to nearby or identical inputs, high pointwise accuracy can force local instability, and sufficiently small error is incompatible with global stability as input separation tends to zero.Proposition 2.5 allows the target predicted at a nearby input to be a dataset target paired with a different input, a weaker condition than requiring the paired target.Source: §2.2 · p. 10
  • Average kernel size is a sample-weighted average of within-feasible-set target distances, with feasible sets built from input and target thresholds compatible with the underlying admissible multiset.The thresholds may represent worst-case input or target noise; the disjunctive rule reflects uncertainty about the corruption source, and feasible-set frequencies do not imply conditional probabilities.Source: §2.2 · pp. 11–12
  • On the constructed dataset, average kernel size lower-bounds every regressor’s empirical error, and the bound is attained by an upper hemicontinuous regressor; allowing discontinuous set-valued regressors does not improve the optimum.With pairwise distinct anchor inputs, the infimum over upper hemicontinuous regressors equals the infimum over all nonempty bounded-valued maps; under additional linear-space assumptions a continuous single-valued extension attains the minimum.Source: §2.2 · pp. 12–13
  • For classification with normalized Hamming loss, average kernel size gives an upper bound on achievable accuracy, attained by an upper hemicontinuous classifier.The result assumes the stated classification and compactness conditions and uses p = 1; the bound follows from the regression result.Source: §2.2 · p. 13
  • With bounded thresholds and balanced reference weights, empirical losses on the constructed and original datasets differ by at most max{Lτ_X, τ_Y} for an L-Lipschitz regressor.The thresholds control the geometric error term; controlling it alone does not ensure nontrivial transfer of lower bounds, and target-based reassignments can make the induced accuracy bounds vacuous.Source: §2.2 · p. 14

2.3 Non-Vanishing Generalization Gaps

  • Under standard Borel assumptions and finite second moments, squared Euclidean risk decomposes into half the squared distributional kernel size plus squared distance to the conditional mean, which attains the infimum.For classification, the distributional analogue uses Hamming distance; the kernel size quantifies irreducible error associated with aleatoric uncertainty or non-identifiability.Source: §2.3 · p. 15
  • If empirical training loss is ε below 1/2 Kersize(Dµ, p), the generalization gap is at least 1/2 Kersize(Dµ, p) − ε; analogous accuracy bounds apply to classifiers.For p = 2 with Euclidean loss, the passages note a sharper exact Bayes bound when Kersize(Dµ, 2) > 2ε.Source: §2.3 · p. 16
  • With independently sampled anchors and conditionally independent repeated targets, the estimator converges in probability to Kersize(Dµ, p)^p as K → ∞ for any NK ≥ 2.This result concerns an ideal two-stage conditional-sampling design.Source: §2.3 · p. 16
  • The ideal estimator is not a consistency theorem for Algorithm 1’s deterministic geometric surrogate, whose selected observations may be reused, dependent, and drawn from overlapping feasible sets.Consistency for the surrogate would require additional assumptions on neighborhood shrinkage, within-neighborhood sample sizes, conditional-law continuity, sample reuse, and selection-induced weights.Source: §2.3 · p. 16

3 Applications

The experiments apply the feasible-set construction to regression and classification datasets, producing model-independent bounds and comparing them with model performance. They also examine accuracy-stability behavior, noise sensitivity, and how label ambiguity relates to classification accuracy.

3 Applications

  • The experiments construct finite feasible sets and datasets, compute average kernel size, and use the resulting theorems to bound empirical regression loss and classification error.The comparisons include original datasets and, where models are available, constructed datasets.Source: §3 · p. 17

3.1 Theoretical assumptions and guarantees versus experimental procedure

  • When noise models are available, thresholds use conservative worst-case noise magnitudes; otherwise, input thresholds use a quantile heuristic and targets are assumed noiseless.For large or high-dimensional datasets, bounds may be estimated from random anchor subsets, for which Assumption 2.6 is not satisfied.Source: §3.1 · p. 17

3.2 Regression tasks

  • Regression bounds are computed across synthetic, tabular, and image tasks, with Table 3 reporting theoretical intervals and model RMSE values.The regression datasets include Tropical Cyclone, Energy Efficiency, Concrete Compressive Strength, and Critical Heat Flux.Source: §3.2 · p. 18, Table 3 · p. 18

3.2.1 Relation to the accuracy-stability trade-off

  • Models below half the average kernel size on training data have higher test errors and empirical Lipschitz estimates; models within the prescribed interval have lower test errors.The latter models’ empirical Lipschitz estimates remain close to the noiseless generating function’s regularity.Source: Figure 4 · p. 19, §3.2.1 · p. 19

3.2.2 Sensitivity of the average kernel size to noise

  • The synthetic regression sensitivity experiments vary input or target noise and adjust feasible-set thresholds accordingly, with average kernel size shown against each noise level.The dataset size is M = 2.5k; Figures 5 and 6 plot average kernel size against input and target noise, respectively.Source: §3.2.2 · p. 19, Figure 5 · p. 20, Figure 6 · p. 20

3.3 Classification tasks

  • Classification bounds and model accuracies are reported for MNIST, CIFAR-10, RESISC45, and EUROSAT.Table 5 presents the intervals from Corollary 2.11 alongside classifier accuracies.Source: §3.3 · p. 19, Table 5 · p. 20

3.3.1 Aleatoric uncertainty: dataset dependence and model independence of the accuracy bounds

  • On MNIST, noisy-label accuracy bounds closely match observed degradation, while clean bounds are near-perfect; EUROSAT clean bounds are already below 1.Adding label noise shifts the admissible accuracy range downward in both datasets.Source: §3.3.1 · p. 20, Figure 7 · p. 21

4 Discussion

The bounds provide a reference scale on constructed datasets, with interpretation tied to the chosen metrics and feasible-set construction. Experiments also indicate that average kernel size tracks noise-related ambiguity, subject to the stated assumptions.

4 Discussion

  • The intervals can be nontrivial, but are not intrinsic to a dataset alone: they depend on the input pseudo-metric, target metric, and feasible-set construction.Benchmark accuracies on original datasets, especially under differing splits or protocols, are not directly comparable to bounds on constructed datasets.Source: §4 · p. 21
  • High-accuracy synthetic-regression models have higher test errors and empirical Lipschitz estimates, while models within the prescribed training interval have lower test errors and estimates near the true regularity.For examples assuming ideal noiseless targets, results may underestimate task aleatoric uncertainty.Source: §4 · pp. 21–22
  • Average kernel size increases with input and target noise in synthetic regression and with label noise on MNIST and EUROSAT.These findings suggest it captures a data-dependent component of aleatoric uncertainty under the chosen pseudo-metric and feasible-set construction.Source: §4 · p. 22

5 Limitations & Future Work

The bounds depend on metric choices, thresholds, and finite-sample feasible sets, and they quantify ambiguity rather than every source of prediction difficulty. The paper identifies metric design, threshold selection, and the gap between ideal sampling theory and the finite-sample construction as future-work directions.

5 Limitations & Future Work

  • A pseudo-metric that misses task-relevant indistinguishability can merge unrelated inputs or miss genuine ambiguity; image-transform metrics may also diverge from semantic similarity.The authors propose investigating task-dependent metrics, universal feature extractors, and expert-informed features.Source: §5 · p. 22
  • Finite-sample feasible sets can underestimate target spread when rare but valid targets are under-sampled, making the lower bound conservative.The authors identify construction diagnostics and consistency links to the ideal distributional quantity as future work.Source: §5 · p. 22
  • The bounds quantify ambiguity in the chosen metric spaces, not optimization difficulty or finite model capacity, and may be non-sharp when additional assumptions permit tighter bounds.In general metric settings, anchor-wise minimization may require a separate optimization problem for each anchor.Source: §5 · p. 22

6 Conclusion

The paper develops deterministic empirical bounds from feasible-set geometry and relates a distributional analogue to Bayes risk and generalization gaps under additional assumptions. Algorithm 1’s average kernel size is a data-dependent geometric surrogate unless further assumptions justify a statistical consistency claim.

6 Conclusion

  • The framework derives deterministic, non-asymptotic empirical error and accuracy bounds for regression and classification on metric and pseudo-metric spaces.Its average kernel size measures target dispersion in finite feasible sets and supplies a model-independent reference scale on the constructed dataset.Source: §6 · p. 23
  • Under additional probabilistic assumptions, the distributional analogue relates to Bayes risk, implies positive generalization gaps below the ambiguity-compatible level, and admits finite-sample concentration under ideal conditional sampling.The deterministic comparison bound relates constructed-dataset loss to original-dataset loss through graph-based reassignment error.Source: §6 · p. 23
  • Algorithm 1’s average kernel size is a computable geometric surrogate for the ideal distributional quantity unless additional assumptions justify a statistical consistency claim.Task-dependent pseudo-metric design and bridging ideal sampling theory with the finite-sample construction are identified as future directions.Source: §6 · p. 23

8 Proofs

The proofs establish the topological and probabilistic tools used in the results, then derive empirical bounds, comparison bounds, and distributional consequences from the feasible-set ambiguity framework.

8 Proofs

  • Under standard Borel assumptions, regular conditional distributions exist and are unique up to almost-everywhere equality; the proofs also specify upper and lower hemicontinuity.Continuity of a set-valued map is defined as both upper and lower hemicontinuity.Source: §8 · p. 28

8.1 Proof of Proposition 2.5

  • Upper hemicontinuity controls predictions near an input while a separated neighborhood keeps a nearby sample admissible in the locality bound.The proof combines these neighborhood properties with the reverse triangle inequality.Source: §8.1 · pp. 28–29

8.2 Proof of Theorem 2.9

  • The unrestricted empirical optimum lies between one-half and all of the average kernel size, and is attained by an upper hemicontinuous map with compact values.The proof characterizes the optimum using singleton predictions at separated anchors.Source: §8.2 · pp. 30–32

8.3 Proof of Proposition 2.13

  • The comparison proof bounds edge-based quantities using reference indices and weights, then combines those inequalities with the triangle inequality.For each edge, the quantities a_e and b_e differ by at most γ_e.Source: §8.3 · p. 32

8.4 Proof of Proposition 2.17

  • For Euclidean squared loss, an independent conditional copy gives twice the conditional variance, while the conditional Pythagorean identity separates Bayes error from prediction error.Taking expectations yields the stated identity.Source: §8.4 · p. 33

8.5 Proof of Proposition 2.18

  • A conditionally independent target pair yields a distributional lower bound; training below the ambiguity scale implies a strictly positive regression generalization gap.The proof also applies the same structure to bound classification accuracy.Source: §8.5 · p. 33

8.6 Proof of Proposition 2.19

  • The concentration proof treats within-input pairwise distances as an unbiased order-two U-statistic and applies Hoeffding’s inequality to bounded independent terms.The U-statistics have expectation equal to the distributional average kernel size raised to p.Source: §8.6 · p. 33

9 Appendix

The appendix details image metrics and feasible-set construction, and reports dataset-specific regression and classification bounds alongside sensitivity and ablation analyses. These analyses examine ambiguity estimates and average kernel size under different noise, threshold, quantile, and nearest-neighbor choices.

9.1.1 Pseudo-metric on image data

  • The image distance used the ℓ2 norm of concatenated Haar-DWT subbands; although general feature maps can induce a pseudo-metric, retaining all four Haar subbands makes this implementation invertible.The feature concatenates the approximation and three detail subbands; with standard dyadic downsampling and even image dimensions, its dimension is CHW.Source: §9.1.1 · p. 34

9.1.2 Feasible set construction

  • When noise bounds were known, feasible-set thresholds used conservative worst-case bounds; otherwise, input thresholds used a nearest-neighbor quantile rule and target thresholds defaulted to zero absent target-noise information.The chosen q was the smallest value on a stable plateau within [0.01, 0.1], a practical heuristic rather than an optimality criterion.Source: §9.1.2 · pp. 34–35

9.2 Ablation studies

  • The appendix ablations varied nearest-neighbor count, input quantile, and input or target noise to examine average-kernel-size sensitivity; the supplied passages do not report their full quantitative outcomes.The quantile sensitivity curves cover q ∈ [0, 1], while the nearest-neighbor ablation used a 10−4 convergence criterion.Source: §9.1.2 · p. 35, §9.1.4 · p. 39, Table 8 · p. 42

9.1.3 Regression dataset details

  • For synthetic regression, τY=0.01, 0.015, 0.02, 0.03 yielded test average kernel sizes 0.007509, 0.011363, 0.015147, 0.022562; τY=0.01 was closest to Bayes RMSE 0.00866.In the noiseless control, average kernel size was zero on train and test splits for all tested positive input thresholds with τY=0.Source: §9.1.3 · p. 36
  • For tropical-cyclone regression, average kernel sizes were 7.65 ± 0.19 on training and 6.76 ± 0.15 on testing, while constructed-test optimal-regressor RMSE was 4.3215 ± 0.1095.For storm-category prediction, train and test accuracy bounds were [3.34, 6.68] and [3.23, 6.45]; Energy Y1 and Y2 optimal-regressor RMSEs were 0.2767 and 0.7734.Source: §9.1.3 · pp. 36–37
  • For CHF, average kernel size was 191.9 kW/m2 at τX=0 and 341.4 kW/m2 at τX=0.171840 with τY=0.01; the larger value may reflect aggregation pathologies.The constructed-data optimal-regressor error was R*=149.574 kW/m2; the target-noise model was approximate, not independently verified.Source: §9.1.3 · pp. 37–38

9.1.4 Classification dataset details

  • On constructed test sets, optimal classifier accuracy was 100.00 for MNIST, 88.43 for CIFAR-10, 91.33 for RESISC45, and 97.94 for EUROSAT.For RESISC45, the reported mean average-kernel-size intervals were 16.15 ± 2.37% for train and 17.64 ± 1.73% for test.Source: §9.1.4 · pp. 38–39

9.1.5 Sensitivity of the average kernel size to noise

  • For MNIST and EUROSAT, average kernel size increased with quantile and target-noise level; EUROSAT showed substantial ambiguity at moderate quantiles, while noiseless MNIST stayed near zero at small quantiles.The authors attribute the increase to larger thresholds producing larger feasible sets and greater target heterogeneity, while label noise increases dispersion within those sets.Source: §9.1.5 · pp. 39–40

9.2 Ablation studies

  • For regression, Figure 12 plots average kernel size and scaled thresholds against quantile q on 1k-sample tropical-cyclone training and test subsets.The number of anchor samples K and Nmax are given in Table 2.Source: Figure 12 · p. 43
  • For classification, Figure 13 plots average kernel size against Nmax, using the qth quantile of nearest-neighbor distances for the threshold.The quantile q and anchor-sample counts K for train and test splits are given in Table 4.Source: Figure 13 · p. 44
  • For MNIST, CIFAR-10, EUROSAT, and RESISC45, Figure 14 plots average kernel size and the threshold against quantile q.Anchor-sample counts K for train and test splits are given in Table 4.Source: Figure 14 · p. 45
Loading 2610.22564v1…