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

Extreme Binary Classification: Extreme Value Theory for Extreme Constraint on False Negative
Oct 7, 2026Samuel Gruffaz, Muhammad Fawad, Jaakko NevalainenBinary Classification
Tampere university, Finland
Distribution-Free Sequential Prediction with Abstentions
Feb 20, 2026Jialin Yu, Moïse BlanchardStatistical Learning Theory Selective Prediction
Georgia Institute of Technology
BOLT: Universal Classifier Training via a Bayes-Error Upper Bound
Jan 13, 2025Mohammadreza Tavasoli Naeini, Ali Bereyhi, Morteza Noshad +2Multiclass Classification
University of Michigan · University of Toronto · Stanford University

Oct 7, 2026J/K move · Enter open · S save

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

Samuel Gruffaz, Muhammad Fawad, Jaakko Nevalainen

Tampere university, Finland

Binary Classification

Open paper AskPDF arXiv

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.

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