Binary statistical decision making—choosing between two states based on statistical evidence—is foundational to machine learning tasks like out-of-distribution (OOD) detection and selective classification. Historically, deriving optimal strategies for these constrained problems has been a piecemeal process. This paper introduces a comprehensive mathematical framework that unifies and solves a wide range of Constrained Binary Decision Making (BDM) problems, reducing complex optimization challenges to a simple, threshold-based strategy.
The Challenge of Binary Decision Making
In machine learning, we frequently make binary choices (e.g., accepting a sample for classification versus rejecting it as an outlier) while balancing competing objectives, such as maximizing accuracy while capping the false positive rate.
While the Neyman-Pearson lemma solved a foundational version of this problem decades ago, extending it to modern paradigms like selective classification (where a model can choose to abstain from predicting) took years of isolated research. As new challenges emerge—such as Selective Classification in the Presence of OOD Data (SCOD)—practitioners frequently fall back on sub-optimal heuristics because the underlying constrained optimization math is daunting. This paper aims to replace those heuristics with a robust, "one-size-fits-all" mathematical tool.
A Unified Mathematical Framework
The authors formulate BDM as a generic constrained optimization problem involving Lebesgue measurable functions. Unlike traditional approaches that rely on Lagrange duality (which typically requires functions to be differentiable), this paper introduces a more general proof technique.
They define an optimization problem that minimizes an objective (like risk) subject to up to two constraints (like coverage and error rates). The core contribution, Theorem 1, characterizes the structure of every optimal solution within this formulation, proving that six distinct BDM problems are actually just special cases of one general equation.
The Optimal Strategy: Thresholding Uncertainty
The framework reveals that the optimal decision strategy, $c^*(x)$, consistently follows a straightforward threshold-based rule:
- Calculate an uncertainty score $s(x)$ for the input.
- If $s(x)$ is below a threshold $\lambda$, accept the sample.
- If $s(x)$ is above $\lambda$, reject it.
- If $s(x)$ equals $\lambda$, apply a randomization parameter $\tau$.
Crucially, the paper shows that this optimal score $s(x)$ is typically a simple linear combination of the conditional risk (the model's likelihood of being wrong, representing aleatoric uncertainty) and the likelihood ratio (the sample's likelihood of being OOD, representing distribution uncertainty). This is a major insight for practitioners: there is no need to invent complex, non-linear heuristics to combine different detectors. The optimal approach is a linear combination of their respective scores.
Key Theoretical Results
As a purely theoretical contribution, the paper validates its framework by re-deriving and extending known optimal strategies without relying on specific datasets. The authors successfully:
- Re-derive classic strategies: The Neyman-Pearson strategy, as well as optimal solutions for Bounded-Abstention and Bounded-Improvement models.
- Generalize SCOD: Provide a generalized solution for the SCOD problem, which was previously solved only for specific continuous cases.
- Introduce novel variants: Formulate and solve two new SCOD variants—one enforcing hard constraints on both True Positive and False Positive Rates, and another focusing on Precision-Recall constraints.
Practical Implications and Limitations
This unification drastically simplifies model development. Instead of attempting to "learn" a complex binary decision function from scratch, developers only need to approximate two components (risk and likelihood ratio) and tune three scalar parameters ($\theta, \tau, \beta$) on a validation set. The theorem makes no assumptions about the instance space, meaning it works equally well for discrete data (like text) and continuous data (like images).
However, the framework does have limitations:
- Constraint Scaling: The current proof covers problems with up to two constraints. Extending this to $N$ constraints remains an open problem due to increasing combinatorial complexity.
- Estimation Error: The theory assumes accurate estimation of underlying probability distributions. In practice, the real-world optimality of the strategy will be limited by how well a neural network can approximate the conditional risk and likelihood ratios.
- Parameter Tuning: While the framework identifies the form of the optimal strategy, the specific scalar parameters still require manual tuning for every specific problem and dataset.
Summary updated