Towards optimally abstaining from prediction with OOD test examples

Adam Tauman Kalai, Varun KanadeNeurIPS 2021 · OpenReview

In the high-stakes world of machine learning—think medical diagnoses or autonomous driving—a wrong prediction can be far more costly than no prediction at all. But how does a model know when to stay silent? A paper by Adam Tauman Kalai and Varun Kanade, titled "Towards optimally abstaining from prediction with OOD test examples," provides a rigorous framework for models to "abstain" from predicting when they encounter out-of-distribution (OOD) or adversarial data.

The Challenge of Out-of-Distribution Data

Standard machine learning assumes that your test data looks like your training data (the i.i.d. assumption). In reality, this is rarely true. Models encounter "blind spots"—regions of the input space where training data was sparse or non-existent—due to natural distribution shifts (e.g., a medical model trained pre-COVID encountering COVID-19 scans) or deliberate adversarial attacks.

Illustration of the abstention mechanism on out-of-distribution test points.

While we know it's impossible to guarantee accuracy on arbitrary test data, we can guarantee performance if the model is allowed to abstain. The challenge is doing this optimally: abstaining enough to avoid costly errors, but not so much that the model becomes useless.

Transductive Abstention Methodology

The researchers propose a transductive abstention approach. "Transductive" means the algorithm is given both the labeled training set and the unlabeled test set at the same time. By looking at unlabeled test data, the model can achieve optimal loss guarantees that gracefully degrade based on the statistical distance between the training and test distributions.

The Min-Max Abstention (MMA) Framework

The core idea is game-theoretic. The algorithm tries to find a set of points to abstain on that minimizes the worst-case loss over all possible "true" functions that are consistent with the training data.

  1. For Binary Classification: The authors use a "FLIP" trick. They show that the min-max problem can be reduced to a standard Empirical Risk Minimization (ERM) problem. By creating a synthetic dataset where some test examples have "flipped" labels, they can use an off-the-shelf classifier to find the most "confusing" points to abstain on.
  2. For Linear Regression: The problem is trickier because squared loss is continuous and non-convex to maximize. They solve this by framing it as a Celis-Dennis-Tapia (CDT) optimization problem, which allows for polynomial-time solutions for maximizing squared error over ellipsoidal constraints.

Key Insights and Results

  • The "Unknown Unknown" is Manageable: Surprisingly, the authors show that even if you don't know exactly where the test distribution $Q$ differs from the training distribution $P$, you can achieve bounds nearly as good as if you did know.
  • Total Variation Distance as the Tax: The "cost" of distribution shift is directly tied to the Total Variation (TV) distance between $P$ and $Q$. The loss bound is essentially: (Standard Generalization Error) + (Abstention Cost $\times$ Statistical Distance).
  • Transduction is Essential: To handle arbitrary OOD examples, the model must see the unlabeled test examples. This allows it to identify which points lie in "blind spots" relative to the training data.
  • Adversarial Robustness: The framework is naturally robust to "white-box" adversaries. If an adversary corrupts a fraction of the test set, the model's loss only increases by that fraction multiplied by the abstention cost.
  • Classification Bounds: The algorithm achieves an expected loss of $\alpha|P - Q|_{TV} + \tilde{O}(d/n)$, where $\alpha$ is the cost of abstaining, $d$ is the VC-dimension, and $n$ is the number of samples. This matches the "Fundamental Theorem of Statistical Learning" when distributions match ($P=Q$).
  • Regression Efficiency: For linear regression, they provide the first fully polynomial-time algorithm for optimal transductive abstention.

Limitations and Future Work

While theoretically rigorous, the paper notes several practical limitations:

  • Computational Complexity: While the reduction to ERM is "efficient" in a complexity theory sense, ERM itself is NP-hard for many complex function classes (like deep neural networks). In practice, one would have to rely on heuristic ERM solvers.
  • Variance Issues: "High probability" bounds are difficult to achieve because of the inherent variance in how test samples are distributed, leading to a lower bound of $\Omega(\alpha/\sqrt{n})$ in some cases.
  • Agnostic Settings: The current work assumes a "realizable" setting (there exists a perfect function in the class $F$). Extending this to the "agnostic" setting—where even the best function in $F$ makes mistakes—is a significant open challenge.

Finally, the authors warn of potential societal impacts: while abstention can improve safety, it shouldn't be used as an excuse to ignore underrepresented groups in data collection, as different abstention rates across groups could lead to new forms of unfairness.

Summary updated

Abstract

A common challenge across all areas of machine learning is that training data is not distributed like test data, due to natural shifts or adversarial examples; such 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 recent work of Goldwasser, Kalais, and Montasser (2020) who gave error and abstention guarantees for transductive binary classification.
BibTeX
@inproceedings{kalai2021towards,
  author = {Adam Tauman Kalai and Varun Kanade},
  title = {{Towards optimally abstaining from prediction with OOD test examples}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=P9_gOq5w7Eb},
}
Figure