# Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithms

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 101 references that are in the map.
- First posted on arXiv 23 Oct 2023.

## Builds on (most cited first, 30 of 41)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Generalized Cross Entropy Loss for Training Deep Neural Networks with Noisy Labels](https://mlsanity.com/paper/1805.07836/) (2018)
- [On Faithfulness and Factuality in Abstractive Summarization](https://mlsanity.com/paper/2005.00661/) (2020)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Selective Classification for Deep Neural Networks](https://mlsanity.com/paper/1705.08500/) (2017)
- [Robust Loss Functions under Label Noise for Deep Neural Networks](https://mlsanity.com/paper/1712.09482/) (2017)
- [SelectiveNet: A Deep Neural Network with an Integrated Reject Option](https://mlsanity.com/paper/1901.09192/) (2019)
- [Consistent Estimators for Learning to Defer to an Expert](https://mlsanity.com/paper/2006.01862/) (2020)
- [Predict Responsibly: Improving Fairness and Accuracy by Learning to Defer](https://mlsanity.com/paper/1711.06664/) (2017)
- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Learning to Complement Humans](https://mlsanity.com/paper/2005.00582/) (2020)
- [The Algorithmic Automation Problem: Prediction, Triage, and Human Effort](https://mlsanity.com/paper/1903.12220/) (2019)
- [Controlled Hallucinations: Learning to Generate Faithfully from Noisy Data](https://mlsanity.com/paper/2010.05873/) (2020)
- [Differentiable Learning Under Triage](https://mlsanity.com/paper/2103.08902/) (2021)
- [Deep Gamblers: Learning to Abstain with Portfolio Theory](https://mlsanity.com/paper/1907.00208/) (2019)
- [Who Should Predict? Exact Algorithms For Learning to Defer to Humans](https://mlsanity.com/paper/2301.06197/) (2023)
- [Calibrated Learning to Defer with One-vs-All Classifiers](https://mlsanity.com/paper/2202.03673/) (2022)
- [Direct Uncertainty Prediction for Medical Second Opinions](https://mlsanity.com/paper/1807.01771/) (2018)
- [Learning to Defer to Multiple Experts: Consistent Surrogate Losses, Confidence Calibration, and Conformal Ensembles](https://mlsanity.com/paper/2210.16955/) (2022)
- [Classification with Rejection Based on Cost-sensitive Classification](https://mlsanity.com/paper/2010.11748/) (2020)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [On the Calibration of Multiclass Classification with Rejection](https://mlsanity.com/paper/1901.10655/) (2019)
- [Selective Classification via One-Sided Prediction](https://mlsanity.com/paper/2010.07853/) (2020)
- [Learning to Reject with a Fixed Predictor: Application to Decontextualization](https://mlsanity.com/paper/2301.09044/) (2023)

## Built on by (most cited first, 30 of 36)

- [Regression with Multi-Expert Deferral](https://mlsanity.com/paper/2403.19494/) (2024)
- [Realizable H-Consistent and Bayes-Consistent Loss Functions for Learning to Defer](https://mlsanity.com/paper/2407.13732/) (2024)
- [A Universal Growth Rate for Learning with Smooth Surrogate Losses](https://mlsanity.com/paper/2405.05968/) (2024)
- [Cardinality-Aware Set Prediction and Top-k Classification](https://mlsanity.com/paper/2407.07140/) (2024)
- [Multi-Label Learning with Stronger Consistency Guarantees](https://mlsanity.com/paper/2407.13746/) (2024)
- [H-Consistency Guarantees for Regression](https://mlsanity.com/paper/2403.19480/) (2024)
- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)
- [A Two-Stage Learning-to-Defer Approach for Multi-Task Learning](https://mlsanity.com/paper/2410.15729/) (2024)
- [Mastering Multiple-Expert Routing: Realizable H-Consistency and Strong Guarantees for Learning to Defer](https://mlsanity.com/paper/2506.20650/) (2025)
- [Optimal Query Allocation in Extractive QA with LLMs: A Learning-to-Defer Framework with Theoretical Guarantees](https://mlsanity.com/paper/2410.15761/) (2024)
- [Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data](https://mlsanity.com/paper/2502.10381/) (2025)
- [Budgeted Multiple-Expert Deferral](https://mlsanity.com/paper/2510.26706/) (2025)
- [Improved Balanced Classification with Theoretically Grounded Loss Functions](https://mlsanity.com/paper/2512.23947/) (2025)
- [Why Ask One When You Can Ask k? Learning-to-Defer to the Top-k Experts](https://mlsanity.com/paper/2504.12988/) (2025)
- [Beyond Tsybakov: Model Margin Noise and H-Consistency Bounds](https://mlsanity.com/paper/2511.15816/) (2025)
- [Principled Algorithms for Optimizing Generalized Metrics in Binary Classification](https://mlsanity.com/paper/2512.23133/) (2025)
- [Top-k Classification and Cardinality-Aware Prediction](https://mlsanity.com/paper/2403.19625/) (2024)
- [A Unifying Post-Processing Framework for Multi-Objective Learn-to-Defer Problems](https://mlsanity.com/paper/2407.12710/) (2024)
- [Adversarial Robustness in One-Stage Learning-to-Defer](https://mlsanity.com/paper/2510.10988/) (2025)
- [Learning to Partially Defer for Sequences](https://mlsanity.com/paper/2502.01459/) (2025)
- [A Theoretical Framework for Modular Learning of Robust Generative Models](https://mlsanity.com/paper/2602.17554/) (2026)
- [Partial-Label Learning with a Reject Option](https://mlsanity.com/paper/2402.00592/) (2024)
- [Rejection via Learning Density Ratios](https://mlsanity.com/paper/2405.18686/) (2024)
- [Consistent Learning-to-Defer with Expert-Conditional Advice](https://mlsanity.com/paper/2603.14324/) (2026)
- [Learning to Help in Multi-Class Settings](https://mlsanity.com/paper/2501.13810/) (2025)
- [Partial-Label Learning with Conformal Candidate Cleaning](https://mlsanity.com/paper/2502.07661/) (2025)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Optimized Deferral for Imbalanced Settings](https://mlsanity.com/paper/2604.27723/) (2026)
- [Linear-Core Surrogates: Smooth Loss Functions with Linear Rates for Classification and Structured Prediction](https://mlsanity.com/paper/2604.27742/) (2026)
- [A Connection Between Learning to Reject and Bhattacharyya Divergences](https://mlsanity.com/paper/2505.05273/) (2025)

## Abstract (arXiv)

We study the key framework of learning with abstention in the multi-class classification setting. In this setting, the learner can choose to abstain from making a prediction with some pre-defined cost. We present a series of new theoretical and algorithmic results for this learning problem in the predictor-rejector framework. We introduce several new families of surrogate losses for which we prove strong non-asymptotic and hypothesis set-specific consistency guarantees, thereby resolving positively two existing open questions. These guarantees provide upper bounds on the estimation error of the abstention loss function in terms of that of the surrogate loss. We analyze both a single-stage setting where the predictor and rejector are learned simultaneously and a two-stage setting crucial in applications, where the predictor is learned in a first stage using a standard surrogate loss such as cross-entropy. These guarantees suggest new multi-class abstention algorithms based on minimizing these surrogate losses. We also report the results of extensive experiments comparing these algorithms to the current state-of-the-art algorithms on CIFAR-10, CIFAR-100 and SVHN datasets. Our results demonstrate empirically the benefit of our new surrogate losses and show the remarkable performance of our broadly applicable two-stage abstention algorithm.