Classification with Abstention Under Class-Conditional Error Constraints

Mohammadreza M. Kalan; Yuyang Deng; Sanaz Hamidi

cs.LGSep 18, 2026

Classification with Abstention Under Class-Conditional Error Constraints

Authors: Mohammadreza M. Kalan, Yuyang Deng, Sanaz Hamidi

Organizations: Univ Rennes, Ensai, CNRS, CREST–UMR 9194, F-35000 Rennes, France · Columbia University, Department of Statistics

Abstract

We study binary classification with abstention under separate class-conditional error constraints, with the objective of minimizing abstention while keeping both errors below prescribed thresholds. We characterize the distribution-free minimax rate of excess abstention risk, up to logarithmic factors, in terms of the complexity of the hypothesis class and the sample size. To make the framework amenable to computation with models such as neural networks, we introduce surrogate-loss formulations and derive finite-sample guarantees for excess surrogate ambiguity risk. We formulate the resulting learning task as a constrained optimization problem and characterize its computational complexity in the convex setting. Finally, we evaluate our approach on various datasets and compare its performance with a competing method for this problem.

Figures & tables

Figure 1: Illustration of the lower bound construction in Theorem 3 . Here, $m=\left\lfloor\frac{d_{\mathcal{H}}-2}{2}\right\rfloor\sim d_{\mathcal{H}}$ . The unknown sign vector $\sigma\in\{-1,+1\}^{m}$ determines, in each pair $(x_{1,i},x_{2,i})$ , which point is $a_{i}^{\sigma}$ and which is $b_{i}^{\sigma}$ . The oracle accepts $a_{i}^{\sigma}$ for class $0$ and $b_{i}^{\sigma}$ for class $1$ , satisfying $R_{0}=\alpha_{0}$ and $R_{1}=\alpha_{1}$ with zero ambiguity. Since the mass gap is only of order $\gamma\sim\sqrt{d_{\mathcal{H}}/n}$ , the different values of $\sigma$ are difficult to distinguish; errors in recovering $\sigma$ , together with the feasibility constraints, force overlap between the two regions, yielding an $\Omega\left(\sqrt{d_{\mathcal{H}}/n}\right)$ excess ambiguity lower bound.

Method	$R_{0}$	$R_{1}$	$R_{\mathrm{amb}}$
Lei ( Lei, 2014 )	$0.0333\pm 0.0351$	$0.0524\pm 0.0290$	$0.3505\pm 0.1152$
MLP, hinge, additive	$0.0400\pm 0.0344$	$0.0524\pm 0.0375$	$0.3086\pm 0.1153$
MLP, hinge, product	$0.0467\pm 0.0358$	$0.0540\pm 0.0383$	$0.2591\pm 0.1029$

Table 1: Test performance on the Vertebral Column dataset ( Barreto and Neto, 2005 ) with target class-conditional error levels

\alpha_{0}=\alpha_{1}=0.05

. We compare Lei’s method ( Lei, 2014 ) with three-layer MLPs trained using hinge loss under the additive and product surrogate formulations. Values are means

\pm

standard deviations over ten runs.

R_{0}

and

R_{1}

denote class-conditional errors, and

R_{\mathrm{amb}}

denotes ambiguity risk.

Method	$R_{0}$	$R_{1}$	$R_{\mathrm{amb}}$
Lei ( Lei, 2014 )	$0.0501\pm 0.0046$	$0.0485\pm 0.0064$	$0.5966\pm 0.0197$
MLP, hinge, additive	$0.0316\pm 0.0204$	$0.0520\pm 0.0232$	$0.5107\pm 0.0889$
MLP, hinge, product	$0.0418\pm 0.0091$	$0.0493\pm 0.0092$	$0.4332\pm 0.0263$

Table 2: Test performance on the MAGIC Gamma Telescope dataset ( Bock, 2004 ) with target class-conditional error levels

\alpha_{0}=\alpha_{1}=0.05

. We compare Lei’s method ( Lei, 2014 ) with three-layer MLPs trained using hinge loss under the additive and product surrogate formulations. Values are means

\pm

standard deviations over ten runs.

R_{0}

and

R_{1}

denote class-conditional errors, and

R_{\mathrm{amb}}

denotes ambiguity risk.

Method	$R_{0}$	$R_{1}$	$R_{\mathrm{amb}}$
Lei ( Lei, 2014 )	$0.0351\pm 0.0361$	$0.0252\pm 0.0163$	$0.2293\pm 0.4065$
Linear, hinge, product	$0.0505\pm 0.0279$	$0.0450\pm 0.0147$	$0.0077\pm 0.0090$
Linear, hinge, additive	$0.0459\pm 0.0242$	$0.0450\pm 0.0147$	$0.0117\pm 0.0098$
MLP, hinge, product	$0.0658\pm 0.0321$	$0.0396\pm 0.0114$	$0.0072\pm 0.0085$
MLP, hinge, additive	$0.0523\pm 0.0268$	$0.0495\pm 0.0196$	$0.0050\pm 0.0113$
MLP, squared hinge, product	$0.0459\pm 0.0270$	$0.0423\pm 0.0113$	$0.0158\pm 0.0133$

Table 3: Test performance for Subject 4 of the BCI Competition IV Dataset 2b ( Leeb et al., 2008 ) with target class-conditional error levels

\alpha_{0}=\alpha_{1}=0.05

. We compare Lei’s method ( Lei, 2014 ) with linear and MLP models using hinge or squared hinge loss under the additive and product formulations. Values are means

\pm

standard deviations over ten runs.

R_{0}

and

R_{1}

denote class-conditional errors, and

R_{\mathrm{amb}}

denotes ambiguity risk.

Method	$R_{0}$	$R_{1}$	$R_{\mathrm{amb}}$
Lei ( Lei, 2014 )	$0.0531\pm 0.0122$	$0.0540\pm 0.0069$	$0.5606\pm 0.0257$
MLP, hinge, product	$0.0551\pm 0.0204$	$0.0479\pm 0.0151$	$0.4482\pm 0.0341$
MLP, hinge, additive	$0.0387\pm 0.0308$	$0.0462\pm 0.0170$	$0.5292\pm 0.0607$

Table 4: Test performance on the Phoneme dataset ( 31 ) with target class-conditional error levels

\alpha_{0}=\alpha_{1}=0.05

. We compare the method of Lei ( Lei, 2014 ) with MLP models trained using hinge loss under the additive and product formulations. Values are means

\pm

standard deviations over ten runs.

R_{0}

and

R_{1}

denote class-conditional errors, and

R_{\mathrm{amb}}

denotes ambiguity risk.

Method	$R_{0}$	$R_{1}$	$R_{\mathrm{amb}}$
Lei ( Lei, 2014 )	$0.0538\pm 0.0093$	$0.0505\pm 0.0059$	$0.2833\pm 0.1541$
MLP, hinge, product	$0.0437\pm 0.0154$	$0.0543\pm 0.0116$	$0.0166\pm 0.0123$
MLP, hinge, additive	$0.0441\pm 0.0203$	$0.0527\pm 0.0127$	$0.0644\pm 0.0527$

Table 5: Test performance on the Sensorless Drive Diagnosis dataset ( Bator, 2013 ) (classes 6 versus 9) with target class-conditional error levels

\alpha_{0}=\alpha_{1}=0.05

. We compare the method of Lei ( Lei, 2014 ) with MLP models trained using hinge loss under the additive and product formulations. Values are means

\pm

standard deviations over ten runs.

R_{0}

and

R_{1}

denote class-conditional errors, and

R_{\mathrm{amb}}

denotes ambiguity risk.

Method	$R_{0}$	$R_{1}$	$R_{\mathrm{amb}}$
Lei ( Lei, 2014 )	$0.0485\pm 0.0051$	$0.0510\pm 0.0104$	$0.6038\pm 0.0207$
MLP, hinge, product	$0.0611\pm 0.0092$	$0.0519\pm 0.0103$	$0.4089\pm 0.0392$
MLP, hinge, additive	$0.0473\pm 0.0173$	$0.0490\pm 0.0195$	$0.5056\pm 0.0921$
MLP, squared hinge, product	$0.0512\pm 0.0109$	$0.0479\pm 0.0098$	$0.4415\pm 0.0441$
MLP, squared hinge, additive	$0.0655\pm 0.0193$	$0.0496\pm 0.0174$	$0.4565\pm 0.0754$

Table 6: Test performance on the 10-dimensional Gaussian dataset with

X\mid Y=0\sim\mathcal{N}(\mathbf{0}_{10},I_{10})

and

X\mid Y=1\sim\mathcal{N}(0.5\mathbf{1}_{10},2I_{10})

, using 7,000 training observations and target error levels

\alpha_{0}=\alpha_{1}=0.05

. Values are means

\pm

standard deviations over ten runs.

R_{0}

and

R_{1}

denote class-conditional errors, and

R_{\mathrm{amb}}

denotes ambiguity risk.

Binary Classification

Binary classification assigns examples to one of two classes while balancing accuracy, calibration, class imbalance, and the costs of different errors.

See all 64 papers

Oct 7, 2026

Extreme Binary Classification: Extreme Value Theory for Extreme Constraint on False Negative

While binary classification is one of the most extensively studied problems in machine learning, the regime in which the goal is to learn a classifier with an almost zero false negative rate remains largely unexplored. In this paper, we introduce the Extreme Binary Classification problem, where the objective is to learn a classifier whose false negative rate

α

is constrained by

ε_{N_1}=o_{N_1\to\infty}(1/N_1)

, with

N_1

denoting the number of positive examples in the training set. To address this problem, we propose a threshold adaptation method theoretically grounded in guarantees derived from Extreme Value Theory, together with a feature selection procedure based on a permutation test applied to sample maxima. Experimental results on four real-world datasets of varying sizes demonstrate that our approach compares favorably with state-of-the-art methods. In addition, we illustrate its interpretability through an application to a cancer screening dataset.

Samuel Gruffaz, Muhammad Fawad, Jaakko Nevalainen

Tampere university, Finland

Binary Classification

Ask PDF

Feb 20, 2026

Distribution-Free Sequential Prediction with Abstentions

We study a sequential prediction problem in which an adversary is allowed to inject arbitrarily many adversarial instances in a stream of i.i.d. instances, but at each round, the learner may also abstain from making a prediction without incurring any penalty if the instance was indeed corrupted. This semi-adversarial setting naturally sits between the classical stochastic case with i.i.d. instances for which function classes with finite VC dimension are learnable; and the adversarial case with arbitrary instances, known to be significantly more restrictive. For this problem, Goel et al. (2023) showed that, if the learner knows the distribution

μ

of clean samples in advance, learning can be achieved for all VC classes without restrictions on adversary corruptions. This is, however, a strong assumption in both theory and practice: a natural question is whether similar learning guarantees can be achieved without prior distributional knowledge, as is standard in classical learning frameworks (e.g., PAC learning or asymptotic consistency) and other non-i.i.d. models (e.g., smoothed online learning). We therefore focus on the distribution-free setting where

μ

is unknown and propose an algorithm AbstainBoost based on a boosting procedure of weak learners, which guarantees sublinear error for general VC classes in distribution-free abstention learning for oblivious adversaries. These algorithms also enjoy similar guarantees for adaptive adversaries, for structured function classes including linear classifiers. These results are complemented with corresponding lower bounds, which reveal an interesting polynomial trade-off between misclassification error and number of erroneous abstentions.

Jialin Yu, Moïse Blanchard

Georgia Institute of Technology

Statistical Learning Theory Selective Prediction

Ask PDF

Jan 13, 2025

BOLT: Universal Classifier Training via a Bayes-Error Upper Bound

This work introduces a novel approach to compute a universal upper bound on the Bayes error rate (BER) from classifier-output samples, which serves as a Bayes-error-related performance criterion for the underlying classification task. We show that the bound is tight in the binary case and characterize the max-sum gap that appears in the aggregate multiclass formulation. Based on this bound, we define a new loss function, called Bayes optimal learning threshold (BOLT), for training parameterized classifiers. For each data sample, the BOLT loss computes a term whose expectation upper-bounds the Bayes error, so that during training the model parameters can be updated toward minimizing this bound. Numerical experiments with both synthetic and real-world datasets show that, in the reported settings, BOLT training often attains lower held-out classification error than cross-entropy training.

Mohammadreza Tavasoli Naeini, Ali Bereyhi, Morteza Noshad +2

University of Michigan · University of Toronto · Stanford University

Multiclass Classification

Ask PDF

Abstract

Binary Classification

Explore similar work

Extreme Binary Classification: Extreme Value Theory for Extreme Constraint on False Negative

Distribution-Free Sequential Prediction with Abstentions

BOLT: Universal Classifier Training via a Bayes-Error Upper Bound