AUC Optimization with a Reject Option

Song-Qing Shen, Bin-Bin Yang, Wei GaoAAAI 2020 · OpenReview

Abstract

Making an erroneous decision may cause serious results in diverse mission-critical tasks such as medical diagnosis and bioinformatics. Previous work focuses on classification with a reject option, i.e., abstain rather than classify an instance of low confidence. Most mission-critical tasks are always accompanied with class imbalance and cost sensitivity, where AUC has been shown a preferable measure than accuracy in classification. In this work, we propose the framework of AUC optimization with a reject option, and the basic idea is to withhold the decision of ranking a pair of positive and negative instances with a lower cost, rather than mis-ranking. We obtain the Bayes optimal solution for ranking, and learn the reject function and score function for ranking, simultaneously. An online algorithm has been developed for AUC optimization with a reject option, by considering the convex relaxation and plug-in rule. We verify, both theoretically and empirically, the effectiveness of the proposed algorithm.

Introduction

In high-stakes fields like medical diagnosis or toxic chemical detection, the cost of a false prediction is often far greater than the cost of abstaining. Traditionally, machine learning addresses this through a reject option (also known as selective classification), where a model chooses to remain silent when its confidence is low. However, most existing literature focuses on optimizing for accuracy, which can be misleading in the presence of severe class imbalance.

Researchers from Nanjing University, in a paper presented at AAAI-20, argue that for these mission-critical tasks, we should instead optimize for the Area Under the ROC Curve (AUC). They introduce a novel framework and an efficient online algorithm, referred to as AOWR (AUC Optimization With a Reject option), to address this gap. Unlike standard methods that reject individual labels, AOWR learns to withhold ranking decisions for pairs of instances when the risk of mis-ranking exceeds a predefined cost.

Methodology

Pairwise Rejection Framework

The fundamental challenge in optimizing AUC with a reject option is that AUC is defined over pairs of instances. While traditional methods ask if a single instance should be classified, the AOWR framework asks: "Should I attempt to rank this positive-negative pair, or is the uncertainty too high?"

The authors introduce a cost $d$ for rejecting the ranking of a pair. If the potential loss of a wrong ranking is higher than $d$, the model abstains. This creates a mathematically grounded trade-off between the reject rate and the average AUC of the remaining decisions.

Theoretical Foundations and Online Learning

The researchers theoretically derived the Bayes optimal solution for this task. They proved that the optimal score function depends on the ratio of conditional probabilities, specifically $f^*(x) = 1 - 1/\eta(x)$, where $\eta(x)$ is the probability of an instance being positive.

To make the framework practical for large-scale data, they developed an online algorithm. AUC is a global metric, making it computationally expensive to calculate over all possible pairs in a dataset. AOWR overcomes this by using a plug-in rule (estimating probabilities via logistic regression) and a convex surrogate loss (square loss). By maintaining and updating the mean and covariance matrices of the features for both classes, the algorithm can compute gradients incrementally without needing to revisit every previous pair. This ensures a regret bound of $O(1/T)$ for separable data, indicating fast convergence.

Experimental Evaluation

The AOWR algorithm was tested against traditional rejection baselines, including Logistic Regression with Rejection (LR-R) and SVM with a bounded weight (SVM-BW), across ten diverse benchmark datasets from the LIBSVM repository.

Across all datasets, AOWR consistently outperformed the baselines. As the cost of rejection $d$ decreases—allowing the model to reject more uncertain pairs—the average AUC on the remaining pairs increases significantly.

Figure 1: The AOWR algorithm (blue) shows a superior trade-off between reject rate and average AUC on the acoustic dataset compared to LR-R and SVM-BW baselines.

Handling Imbalance

A key strength of AOWR is its performance on "severely" imbalanced datasets. Traditional rejection methods often fail to improve AUC in these scenarios because they do not explicitly account for the skewed class distribution. AOWR, by focusing on the pairwise ranking relationship, remains robust.

Figure 4: On the imbalanced w8a dataset, AOWR maintains high AUC performance even as the reject rate increases, whereas baseline methods struggle to scale or improve.

Conclusion

This work presents the first comprehensive framework for AUC optimization with a reject option. By shifting the focus from individual labels to pairwise rankings, AOWR provides a more reliable decision-making tool for imbalanced, mission-critical tasks. The combination of a solid theoretical foundation and an efficient online implementation makes it a promising approach for real-world applications in medical and industrial diagnostics. Future research may explore extending this framework to non-linear kernels and deep learning architectures.

Reference: Shen, S.-Q., Yang, B.-B., & Gao, W. (2020). AUC Optimization with a Reject Option. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04), 5684-5691.

Summary updated

Abstract

Making an erroneous decision may cause serious results in diverse mission-critical tasks such as medical diagnosis and bioinformatics. Previous work focuses on classification with a reject option, i.e., abstain rather than classify an instance of low confidence. Most mission-critical tasks are always accompanied with class imbalance and cost sensitivity, where AUC has been shown a preferable measure than accuracy in classification. In this work, we propose the framework of AUC optimization with a reject option, and the basic idea is to withhold the decision of ranking a pair of positive and negative instances with a lower cost, rather than mis-ranking. We obtain the Bayes optimal solution for ranking, and learn the reject function and score function for ranking, simultaneously. An online algorithm has been developed for AUC optimization with a reject option, by considering the convex relaxation and plug-in rule. We verify, both theoretically and empirically, the effectiveness of the proposed algorithm.
BibTeX
@inproceedings{shen2020auc,
  author = {Song-Qing Shen and Bin-Bin Yang and Wei Gao},
  title = {{AUC Optimization with a Reject Option}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=nH9Wz8mOgYK},
}

Loading related content...

Figure