Deterministic Bounds on Accuracy and Stability of Metric-Space Regression and Classification
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.
Related
- Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability
- A deterministic analysis of a class of nonlinear regression methods
- Privacy-accuracy trade-off optimization in sensitive surveys through regression estimation
- Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression
- Nearly Sharp Uniform Projection Bounds and Superlinear Vitushkin Inequalities for Deterministic Self-Similar Sets
BibTeX
@misc{gottschling2026deterministic,
title = {{Deterministic Bounds on Accuracy and Stability of Metric-Space Regression and Classification}},
author = {Nina Maria Gottschling and Jakob Gawlikowski and Michele Caprio},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22564},
eprint = {2610.22564},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22564},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Deterministic Bounds on Accuracy and Stability of Metric-Space Regression and Classification
AU - Nina Maria Gottschling
AU - Jakob Gawlikowski
AU - Michele Caprio
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.22564
UR - https://arxiv.org/abs/2610.22564
AB - 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.
ER -