# Towards optimally abstaining from prediction with OOD test examples

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 33 references that are in the map.
- First posted on arXiv 28 May 2021.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Fast classification rates without standard margin assumptions](https://mlsanity.com/paper/1910.12756/) (2019)
- [A note on polynomial solvability of the CDT problem](https://mlsanity.com/paper/1406.6429/) (2014)

## Built on by (most cited first, 1 of 1)

- [Uncertainty Quantification for Rule-Based Models](https://mlsanity.com/paper/2211.01915/) (2022)

## Abstract (arXiv)

A common challenge across all areas of machine learning is that training data is not distributed like test data, due to natural shifts, "blind spots," or adversarial examples; such test examples are referred to as out-of-distribution (OOD) test examples. We consider a model where one may abstain from predicting, at a fixed cost. In particular, our transductive abstention algorithm takes labeled training examples and unlabeled test examples as input, and provides predictions with optimal prediction loss guarantees. The loss bounds match standard generalization bounds when test examples are i.i.d. from the training distribution, but add an additional term that is the cost of abstaining times the statistical distance between the train and test distribution (or the fraction of adversarial examples). For linear regression, we give a polynomial-time algorithm based on Celis-Dennis-Tapia optimization algorithms. For binary classification, we show how to efficiently implement it using a proper agnostic learner (i.e., an Empirical Risk Minimizer) for the class of interest. Our work builds on a recent abstention algorithm of Goldwasser, Kalais, and Montasser (2020) for transductive binary classification.