# Resampled Confidence Regions with Exponential Shrinkage for the Regression Function of Binary Classification

arXiv: https://arxiv.org/abs/2308.01835 · HTML: https://mlsanity.com/paper/2308.01835/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 31 references that are in the map.
- First posted on arXiv 3 Aug 2023.

## Builds on (most cited first, 5 of 5)

- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Sign-Perturbed Sums: A New System Identification Approach for Constructing Exact Non-Asymptotic Confidence Regions in Linear Regression Models](https://mlsanity.com/paper/1807.08216/) (2018)
- [Semi-Parametric Uncertainty Bounds for Binary Classification](https://mlsanity.com/paper/1903.09790/) (2019)
- [Exact Distribution-Free Hypothesis Tests for the Regression Function of Binary Classification via Conditional Kernel Mean Embeddings](https://mlsanity.com/paper/2103.05126/) (2021)

## Abstract (arXiv)

The regression function is one of the key objects of binary classification, since it not only determines a Bayes optimal classifier, hence, defines an optimal decision boundary, but also encodes the conditional distribution of the output given the input. In this paper we build distribution-free confidence regions for the regression function for any user-chosen confidence level and any finite sample size based on a resampling test. These regions are abstract, as the model class can be almost arbitrary, e.g., it does not have to be finitely parameterized. We prove the strong uniform consistency of a new empirical risk minimization based approach for model classes with finite pseudo-dimensions and inverse Lipschitz parameterizations. We provide exponential probably approximately correct bounds on the L2 sizes of these regions, and demonstrate the ideas on specific models. Additionally, we also consider a k-nearest neighbors based method, for which we prove strong pointwise bounds on the probability of exclusion. Finally, the constructions are illustrated on a logistic model class and compared to the asymptotic ellipsoids of the maximum likelihood estimator.