NPSL: Tractable and Robust Classification under Selective Labels

Many binary classification problems involve learning from data with partially missing labels. In the selective label setting, a prior decision determines which labels are observed. For example, banks observe repayment outcomes only for applicants who were granted a loan. Error control is then difficult because the observations with labels may not be representative of all observations. We study classification in this setting using the Neyman–Pearson (NP) framework, which seeks to control the prioritized type I error while minimizing the type II error. We propose NPSL (Neyman–Pearson under Selective Labels), using structural assumptions about the unlabeled population to construct a set of plausible labelings. Given an independently trained scoring function, NPSL selects a threshold that ensures the empirical type I error is at most a user-specified target across all plausible labelings simultaneously. Although the number of possible labelings grows exponentially, we show that this can be done in polynomial time. Under additional conditions, NPSL converges to the optimal robust threshold — the smallest threshold that still satisfies the type I error constraint across all plausible distributions. Synthetic experiments empirically show that NPSL provides reliable type I error control while achieving lower type II error than benchmark methods that satisfy the NP constraint. A case study using loan application data illustrates risk control of NPSL with artificially hidden outcomes.