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.
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.
- 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.
- 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