# Consistent Algorithms for Multiclass Classification with a Reject Option

arXiv: https://arxiv.org/abs/1505.04137 · HTML: https://mlsanity.com/paper/1505.04137/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2015.

## Built on by (most cited first, 7 of 7)

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)
- [Regression with Cost-based Rejection](https://mlsanity.com/paper/2311.04550/) (2023)
- [Consistency Conditions for Differentiable Surrogate Losses](https://mlsanity.com/paper/2505.13760/) (2025)
- [Learning Acceptance Regions for Many Classes with Anomaly Detection](https://mlsanity.com/paper/2209.09963/) (2022)
- [Policy Learning with Abstention](https://mlsanity.com/paper/2510.19672/) (2025)
- [Classification with Abstention Under Class-Conditional Error Constraints](https://mlsanity.com/paper/2609.22632/) (2026)

## Abstract (arXiv)

We consider the problem of n-class classification (n≥ 2), where the classifier can choose to abstain from making predictions at a given cost, say, a factor α of the cost of misclassification. Designing consistent algorithms for such n-class classification problems with a `reject option' is the main goal of this paper, thereby extending and generalizing previously known results for n=2. We show that the Crammer-Singer surrogate and the one vs all hinge loss, albeit with a different predictor than the standard argmax, yield consistent algorithms for this problem when α=frac12. More interestingly, we design a new convex surrogate that is also consistent for this problem when α=frac12 and operates on a much lower dimensional space (log(n) as opposed to n). We also generalize all three surrogates to be consistent for any α∈[0, frac12].