Classification with Reject Option: Distribution-free Error Guarantees via Conformal Prediction
Johan Hallberg Szabadváry, Tuwe Löfström, Ulf Johansson, Cecilia Sönströd, Ernst Ahlberg, Lars Carlsson · 2025
Read Classification with Reject Option: Distribution-free Error Guarantees via Conformal Prediction by Johan Hallberg Szabadváry, Tuwe Löfström, Ulf Johansson, Cecilia Sönströd, Ernst Ahlberg, Lars Carlsson (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-21802.txt.
Introduction
Johan Hallberg Szabadváry and co-authors formalize classifiers that may refuse to answer, in a 2025 machine learning paper. Ordinary models always emit a prediction, even when they are probably wrong, which is dangerous in high-stakes use. A reject option lets the model abstain on the shakiest cases.
The authors build the refusal rule from conformal prediction, whose sets carry distribution-free error guarantees. In binary problems the sets can hold one label, both, or none; accepting only singletons yields a classifier with abstention. They prove the resulting error rate and give finite-sample estimates. Worked examples span several conformal setups, from exact to cheaper batch versions.
Catalog record
| CREATOR | Johan Hallberg Szabadváry, Tuwe Löfström, Ulf Johansson, Cecilia Sönströd, Ernst Ahlberg, Lars Carlsson |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-21802
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Classification with Reject Option: Distribution-free Error Guarantees via Conformal Prediction Johan Hallberg Szabadváry, Tuwe Löfström, Ulf Johansson, Cecilia Sönströd, Ernst Ahlberg, Lars Carlsson Abstract Machine learning (ML) models always make a prediction, even when they are likely to be wrong. This causes problems in practical applications, as we do not know if we should trust a prediction. ML with reject option addresses this issue by abstaining from making a prediction if it is likely to be incorrect. In this work, we formalise the approach to ML with reject option in binary classification, deriving theoretical guarantees on the resulting error rate. This is achieved through conformal prediction (CP), which produce prediction sets with distribution-free validity guarantees. In binary classification, CP can output prediction sets containing exactly one, two or no labels. By accepting only the singleton predictions, we turn CP into a binary classifier with reject option. Here, CP is formally put in the framework of predicting with reject option. We state and prove the resulting error rate, and give finite sample estimates. Numerical examples provide illustrations of derived error rate through several different conformal prediction settings, ranging from full conformal prediction to offline batch inductive conformal prediction. The former has a direct link to sharp validity guarantees, whereas the latter is more fuzzy in terms of validity guarantees but can be used in practice. Error-reject curves illustrate the trade-off between error rate and reject rate, and can serve to aid a user to set an acceptable error rate or reject rate in practice. [orcid=0000-0001-7240-8919] [orcid=0000-0003-0274-9026] [orcid=0000-0003-0412-6199] [orcid=0009-0009-0404-2586] [orcid=0000-0003-2050-9069] [orcid=0000-0001-9491-4134] {graphicalabstract} † † highlights: Proven Distribution-Free Error Rates for Singleton Predictions: Delivered theoretical guarantees on error rates for accepted singleton predictions, resolving inaccuracies found in prior works. Refinement of Reject Option in Conformal Prediction: Clarified the relationship between error rate and reject rate using error-reject curves, offering a more accurate approach than existing models. Practical Implementation Guidelines for Reject Option Models: Presented clear practical insights for implementing conformal predictors with reject options, providing empirical guidance for managing trade-offs in real-world applications. Corrected Error Rate Analysis for Conformal Prediction with Reject Option: Provided a rigorous and corrected analysis of the error rate for binary classification with reject option, addressing weaknesses in previous studies. keywords reject option ,conformal prediction ,binary classification ,abstain prediction ,refrain prediction ,error-reject curve † † corresponding: Corresponding author 1 Introduction Traditional machine learning (ML) models always make a prediction, even when it is likely that the prediction will be incorrect. This is often undesirable, as in the case of decision support applications, where we want to be able to trust the information we are given. Machine learning with reject option aims to avoid making predictions when they are likely to be wrong, increasing the trustworthiness of a model. Most of this work trace back to C-K. Chow (1957) and C. Chow (1970) . In these papers a theoretical framework is established for optimum rejection rules and in particular the relation between rejection rate and the error rate for the accepted predictions. A rejection is achieved by allowing the model to abstain from giving predictions for some objects. The rejected objects can further be divided into two categories, ambiguity rejection and novelty rejection. For a more comprehensive description, see Hendrickx et al. (2024) . The main contribution of this work, is a method for ML with reject option with a provable distribution-free error rate. While optimal strategies for reject option has been studied in e.g. Franc et al. (2023) , Cortes et al. (2016) , and Hendrickx et al. (2024) , no strategy to the best of our knowledge provides a distribution-free error rate. We achieve this through Conformal prediction (CP) ( Vovk et al. (2022) ) , a method to generate prediction sets with guarantees on the error rate, although defined for set predictions. The key property of conformal predictors is that their predictions are valid, meaning, in the strongest formulation, that errors, i.e. the true label is not included in the prediction set, are independent, and happen with a user specified probability. In recent years, work has been done suggesting that validity is supported for singleton predictions, i.e. just one label is within the prediction set, see e.g. Linusson et al. (2016) , Linusson et al. (2018) and Johansson et al. (2023) . By rejecting all but the singleton predictions, one can view conformal prediction as a case of ML with reject option. For another example of this, see e.g. Bortolussi et al. (2019) . Common for these works is that they each present different procedures for creating singleton predictions with an associated error rate and empirical results have been presented to support the different procedures, respectively. However, none of the above works use the correct singleton error rates, and different formulas are used in different papers, which leads to confusion about what is theoretically justifiable. The formula appearing in Linusson et al. (2016) and Bortolussi et al. (2019) is close to being correct, but since both works consider CP in the inductive, offline setting, the overall error rate must be adjusted accordingly, which they fail to account for, making their singleton error rate approximately correct only for large calibration sets. We present the relevant theory in Section A.4 , and the correct singleton error rate in Section B.2 , which is of the PAC type, including two parameters. This work resolves the confusion by providing the theoretical singleton error rates in the online setting (where the formula appearing in Linusson et al. (2016) actually holds) as well as the offline setting, with the relevant modifications to account for training conditional validity. Moreover, we formally describe the model with reject option that results from using CP in this mode, aligning the notation with that of Hendrickx et al. (2024) . A self-contained introduction to conformal prediction as well as statements of the error rates in different scenarios are given in the appendices. The rest of the paper is structured as follows. We give a brief introduction to classification with regret option in Section 2 , followed by an informal introduction to conformal prediction in Section 3 . Section 4 makes precise the connection between ML with reject option and CP, defining formally the CP rejector, which abstains from making predictions whenever the prediction set is not a singleton. We then move on to prove the error rate of CP rejectors in Section 5 . Section 6 is devoted to numerical illustrations of the singleton error rates. Observations and discussions conclude, and the interested reader will find more details on conformal prediction and singleton validity in the appendices. 2 Classification with reject option In ML with reject option, the label space is extended to include a new label \circledR , which indicates a rejection. Formally, a model with rejection m:\boldsymbol{X}\to\boldsymbol{Y}\cup\{\circledR\} is represented by a pair (h,r) where h:\boldsymbol{X}\to\boldsymbol{Y} is the predictor and r:\mathcal{R}\to\mathbb{R} is the rejector. Here \mathcal{R} may be for example \boldsymbol{X} so that r takes examples as input, the unit interval so that r takes a confidence level as input, or even both. When the rejector determines that a prediction is likely to be wrong, m outputs \circledR . Otherwise, the predictors output is accepted: m(x)=\begin{cases}$\circledR$&\text{if the