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

This repository contains code and example notebooks for the Deterministic Bounds on Accuracy and Stability of Metric-Space Regression and Classification as introduced in this preprint .

The repository further contains all computations needed to reproduce the results of this paper. Additionally, a specific framework is currently under preparation.

If you use the code and find it useful, please cite the paper.

@article{gottschling2026deterministic,
  author  = {Gottschling, Nina Maria and Gawlikowski, Jakob and Caprio, Michele},
  title   = {Deterministic Bounds on Accuracy and Stability of Metric-Space Regression and Classification},
  year    = {2026},
  journal = {arXiv preprint arXiv:2610.22564},
  url     = {https://arxiv.org/abs/2610.22564}
}

Installation

The project requires Python 3.8 or newer and has been tested on Unix (Linux and macOS).

1. Clone the repository

git clone https://github.com/nm19000/AccuracyBoundsRegression.git
cd AccuracyBoundsRegression

2. Install

Choose the variant you need:

Variant	What you get
core	the accuracy_bounds package only
examples	+ Jupyter, torchvision and everything needed to run the example notebooks

With pip

python -m venv .venv
source .venv/bin/activate
pip install -e ".[examples]" # for runnable examples
# pip install -e "." #  for core only

Example Applications

The repository comes with various example notebooks for regression and classification tasks (see Installation for how to run them). For MNIST and EuroSAT the folders also contain training scripts for training with label noise; these require the torch variant.

Regression Examples

Classification Examples

Contributions

In the following the main contributions of these implementations and the underlying paper are summarized.

Main Theorem: Accuracy Bounds based on Average Kernel Size

The framework provides model-independent accuracy bounds for both regression and classification. Please refer to the paper for a comprehensive introduction of the framework and definitions. For regression, the average kernel size measures the typical spread of target values associated with inputs that are indistinguishable under the chosen input metric. For any predictor, the empirical error is bounded below by half of this quantity, and the optimal error over continuous regressors lies within the interval

$$\frac{1}{2}\mathop{\mathrm{Kersize}}(\mathcal{D}_{M'},p)_K\;\leq\;\inf_{\phi}\mathcal{L}(\mathcal{D}_{M'},\phi,p)\;\leq\;\mathop{\mathrm{Kersize}}(\mathcal{D}_{M'},p)_K.$$

Thus, a nonzero average kernel size identifies a component of prediction error that cannot be removed solely by changing the model architecture or optimization procedure. For classification, using the normalized Hamming distance, the same quantity gives an upper bound on achievable accuracy:

$$\mathop{\mathrm{Acc}}(\mathcal{D}_{M'},\phi)\;\leq\;1-\frac{1}{2}\mathop{\mathrm{Kersize}}(\mathcal{D}_{M'},1)_K.$$

For continuous classifiers, the optimal accuracy is bounded between $1-\mathop{\mathrm{Kersize}}$ and $1-\tfrac{1}{2}\mathop{\mathrm{Kersize}}$.

Feasible-Set Sampling

The bounds are estimated directly from data using feasible-set sampling. Given an anchor pair $(y_k,x_k)$, the algorithm collects targets $y_{k,n}$ from samples whose inputs satisfy

$$d_{\mathcal X}(x_{k,n},x_k)\leq \tau_{\mathcal X}(x_k)$$

or whose targets satisfy

$$d_{\mathcal Y}(y_{k,n},y_k)\leq \tau_{\mathcal Y}(y_k).$$

These targets form an approximate feasible set $F_{x_k}^{N(k)}$, representing plausible outputs for locally indistinguishable inputs. The average kernel size is then computed from pairwise target distances within the sampled feasible sets. Its value, and therefore the resulting accuracy bounds, depends on the selected input and target metrics, thresholds, number of anchors, and maximum feasible-set size. Smaller thresholds produce more local estimates, while larger thresholds provide more samples but may combine less comparable observations.

Accuracy Bounds for Inverse Problems

Computation of worst-case and average kernel size for an inverse problem with noise of the form:

$$\text{recover } x \in \mathcal{M}_1 \subset \mathbb{C}^{d_1} \text{ given noisy measurements } y = F(x,e)\in \mathbb{C}^{d_2} \text{ of } x \text{ and } e \in \\mathcal{E}\subset \mathbb{C}^{d_3}.$$

The lower bound to the average error of any approximate inverse map is the average kernel size. The definition of and algorithms for computing the average kernel size are to be found in the following preprint.

The lower bound to the worst-case error of any approximate inverse map is the worst-case kernel size. The definition of the worst-case kernel size can be found in the following preprint.

Citation

If you use this code in your research, please cite our paper:

@article{gottschling2026deterministic,
  author  = {Gottschling, Nina Maria and Gawlikowski, Jakob and Caprio, Michele},
  title   = {Deterministic Bounds on Accuracy and Stability of Metric-Space Regression and Classification},
  year    = {2026},
  journal = {arXiv preprint arXiv:2610.22564},
  url     = {https://arxiv.org/abs/2610.22564}
}