Distribution-Free Inference for the Regression Function of Binary
  Classification
Ambrus Tamás Balázs Csanád Csáji
One of the key objects of binary classification is the regression function,
i.e., the conditional expectation of the class labels given the inputs. With
the regression function not only a Bayes optimal classifier can be defined, but
it also encodes the corresponding misclassification probabilities. The paper
presents a resampling framework to construct exact, distribution-free and
non-asymptotically guaranteed confidence regions for the true regression
function for any user-chosen confidence level. Then, specific algorithms are
suggested to demonstrate the framework. It is proved that the constructed
confidence regions are strongly consistent, that is, any false model is
excluded in the long run with probability one. The exclusion is quantified with
probably approximately correct type bounds, as well. Finally, the algorithms
are validated via numerical experiments, and the methods are compared to
approximate asymptotic confidence ellipsoids.