# Theoretically Grounded Loss Functions and Algorithms for Score-Based Multi-Class Abstention

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

## Key facts

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

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

- [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)
- [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)
- [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)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [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)
- [Revisiting Discriminative vs. Generative Classifiers: Theory and Implications](https://mlsanity.com/paper/2302.02334/) (2023)
- [Classification with abstention but without disparities](https://mlsanity.com/paper/2102.12258/) (2021)
- [Ranking with Abstention](https://mlsanity.com/paper/2307.02035/) (2023)
- [A Finer Calibration Analysis for Adversarial Robustness](https://mlsanity.com/paper/2105.01550/) (2021)

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

- [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)
- [Cascade-Aware Training of Language Models](https://mlsanity.com/paper/2406.00060/) (2024)
- [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)
- [Hierarchical Selective Classification](https://mlsanity.com/paper/2405.11533/) (2024)
- [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)
- [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)
- [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)
- [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)
- [From Deferral to Learning: Online In-Context Knowledge Distillation for LLM Cascades](https://mlsanity.com/paper/2509.22984/) (2025)
- [Calibrating conditional risk](https://mlsanity.com/paper/2604.20409/) (2026)
- [Online Learning-to-Defer with Varying Experts](https://mlsanity.com/paper/2605.12340/) (2026)
- [On the Bayes Inconsistency of Disagreement Discrepancy Surrogates](https://mlsanity.com/paper/2512.05931/) (2025)

## Abstract (arXiv)

Learning with abstention is a key scenario where the learner can abstain from making a prediction at some cost. In this paper, we analyze the score-based formulation of learning with abstention in the multi-class classification setting. We introduce new families of surrogate losses for the abstention loss function, which include the state-of-the-art surrogate losses in the single-stage setting and a novel family of loss functions in the two-stage setting. We prove strong non-asymptotic and hypothesis set-specific consistency guarantees for these surrogate losses, which upper-bound the estimation error of the abstention loss function in terms of the estimation error of the surrogate loss. Our bounds can help compare different score-based surrogates and guide the design of novel abstention algorithms by minimizing the proposed surrogate losses. We experimentally evaluate our new algorithms on CIFAR-10, CIFAR-100, and SVHN datasets and the practical significance of our new surrogate losses and two-stage abstention algorithms. Our results also show that the relative performance of the state-of-the-art score-based surrogate losses can vary across datasets.