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

Samuel Gruffaz; Muhammad Fawad; Jaakko Nevalainen

stat.MLOct 7, 2026

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

Authors: Samuel Gruffaz, Muhammad Fawad, Jaakko Nevalainen

Organizations: Tampere university, Finland

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Illustration of the progression from a standard classifier (left) to a cost-sensitive classifier (middle) and finally to our extreme classifier (right). As the cost of false negatives increases, the decision threshold is shifted to favor sensitivity. Our extreme classifier further adjusts the threshold to provide strong control over false negatives while mitigating overfitting.

Rank	ScreenX	Corruption	Credit	Mean Rank
1	Mul-Q=0.95 (Ours)	MulLog-Q=0.9 (Ours)	Mul-Q=0.1	MulLog-Q=0.9 (Ours)
2	Mul-Q=0.9 (Ours)	MulLog-Q=0.95 (Ours)	Mul-Q=0.9	MulLog-Q=0.95 (Ours)
3	Conservative Ensemble	MulLog-Q=0.1 (Ours)	Mul-Q=0.95	Conservative Ensemble
4	MulLog-Q=0.95 (Ours)	Mul-Q=0.9 (Ours)	MulLog-Q=0.9 (Ours)	Mul-Q=0.9 (Ours)
5	CS-Logistic	Mul-Q=0.1 (Ours)	MulLog-Q=0.95 (Ours)	Mul-Q=0.95 (Ours)

Table 1: Summary of Benchmark Results, ranking is performed by

TN/\max(FN,0.1)

Appendix figures & tables20 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Illustration of the Generalized Extreme Value (GEV) density for different values of the tail index

\xi

Figure 3: Illustration of Proposition 3 . The histogram of the excesses

E_{k}=N_{k}-Q_{u}\mid N_{k}>Q_{u},\qquad N_{k}\sim\mathcal{N}(0,1),

above the

u

-quantile

Q_{u}

is well approximated by a GPD with

\xi=0

when

u

is sufficiently large.

Panel of Figure 4 — Figure 4: Illustration of the distribution used in the synthetic experiments using their histograms on 3000 samples.

Panel of Figure 5 — Figure 5: Comparison of the false negative rate ( FN ) when $X_{e}\sim\text{Exp}(5)$ . Notice that the practical estimator follows the same false negative constraint $1/(N_{1}\log(N_{1}))$ as the theoretical one as long as $Q_{b}\geq 0.9$ for any $N_{1}\in\{25,100,500\}$ . We report the variability across $10\,000$ repetitions using shaded bands corresponding to $\pm\sigma$ , $\pm 2\sigma$ , and $\pm 3\sigma$ , where $\sigma$ denotes the standard deviation of FN over the $10\,000$ repetitions.

Panel of Figure 6 — Figure 6: Comparison of the false negative rate ( FN ) when $X_{e}\sim G_{\xi,1}$ with $\xi=-10^{-5}$ . Notice that the practical estimator follows the same false negative constraint $1/(N_{1}\log(N_{1}))$ as the theoretical one as long as $Q_{b}\geq 0.9$ for any $N_{1}\in\{25,100,500\}$ . We report the variability across $10\,000$ repetitions using shaded bands corresponding to $\pm\sigma$ , $\pm 2\sigma$ , and $\pm 3\sigma$ , where $\sigma$ denotes the standard deviation of FN over the $10\,000$ repetitions.

Rank	ScreenX	Corruption	Credit	Mean Rank
1	Easy Ensemble	Conservative Ensemble	Conservative Ensemble	MulLog-Q=0.1 (Ours)
2	CS-NTA-XGBoost	CS-NTA-Logistic	CS-NTA-Logistic	CS-NTA-XGBoost
3	CS-XGBoost	Balanced Random Forest	NP-Logistic	Easy Ensemble
4	MulLog-Q=0.1 (Ours)	Easy Ensemble	CS-NTA-XGBoost	NP-Logistic
5	Mul-Q=0.1 (Ours)	CS-SVC-RBF	MulLog-Q=0.1 (Ours)	CS-NTA-Logistic

Appendix

Table 2: Summary of Benchmark Results, ranking is performed by

TN/\max(FN,1)

and not

TN/\max(FN,0.1)

Dataset	ScreenX
	FN	TN	TN/max(FN,0.1)	TN/max(FN,1)
Method
Mul-Q=0.95 (Ours)	0.3 $\pm$ 0.2	5.5 $\pm$ 0.4	26.9 $\pm$ 16.1	5.5 $\pm$ 0.4
Mul-Q=0.9 (Ours)	0.4 $\pm$ 0.2	6.8 $\pm$ 0.5	24.7 $\pm$ 17.4	6.8 $\pm$ 0.5
Conservative Ensemble	0.2 $\pm$ 0.1	3.5 $\pm$ 0.6	20.9 $\pm$ 6.6	3.5 $\pm$ 0.6
MulLog-Q=0.95 (Ours)	0.5 $\pm$ 0.2	5.6 $\pm$ 0.3	14.6 $\pm$ 7.4	5.6 $\pm$ 0.3

Appendix

Table 3: ScreenX benchmark results. We report the mean

\pm

one standard deviation, computed over 10 repetitions with different random seeds, where each repetition corresponds to the mean performance across a 5-fold cross-validation.

Dataset	Corruption
	FN	TN	TN/max(FN,0.1)	TN/max(FN,1)
Method
MulLog-Q=0.9 (Ours)	0.0 $\pm$ 0.0	650.4 $\pm$ 14.4	6503.8 $\pm$ 144.0	650.4 $\pm$ 14.4
MulLog-Q=0.95 (Ours)	0.0 $\pm$ 0.0	588.0 $\pm$ 12.5	5880.0 $\pm$ 125.2	588.0 $\pm$ 12.5
MulLog-Q=0.1 (Ours)	0.3 $\pm$ 0.1	1208.9 $\pm$ 40.3	4848.9 $\pm$ 1605.5	1208.9 $\pm$ 40.3
Mul-Q=0.9 (Ours)	0.0 $\pm$ 0.0	438.2 $\pm$ 0.0	4382.0 $\pm$ 0.0	438.2 $\pm$ 0.0

Appendix

Table 4: Corruption benchmark results. We report the mean

\pm

one standard deviation, computed over 10 repetitions with different random seeds, where each repetition corresponds to the mean performance across a 5-fold cross-validation.

Dataset	Credit
	FN	TN	TN/max(FN,0.1)	TN/max(FN,1)
Method
Mul-Q=0.1 (Ours)	0.2 $\pm$ 0.1	6732.6 $\pm$ 872.8	38852.9 $\pm$ 16596.4	6732.6 $\pm$ 872.8
Mul-Q=0.9 (Ours)	0.1 $\pm$ 0.2	4377.2 $\pm$ 726.5	37114.9 $\pm$ 15397.2	4377.2 $\pm$ 726.5
Mul-Q=0.95 (Ours)	0.1 $\pm$ 0.2	4102.0 $\pm$ 882.4	34913.9 $\pm$ 15585.8	4102.0 $\pm$ 882.4
MulLog-Q=0.9 (Ours)	0.3 $\pm$ 0.1	7240.4 $\pm$ 763.7	30633.0 $\pm$ 11490.8	7240.4 $\pm$ 763.7

Appendix

Table 5: Credit benchmark results. We report the mean

\pm

one standard deviation, computed over 10 repetitions with different random seeds, where each repetition corresponds to the mean performance across a 5-fold cross-validation.

Dataset	Breast Cancer
	FN	TN	TN/max(FN,0.1)	TN/max(FN,1)
Method
CS-Logistic	0.0 $\pm$ 0.0	32.4 $\pm$ 0.2	323.8 $\pm$ 1.8	32.4 $\pm$ 0.2
CS-NTA-Logistic	0.0 $\pm$ 0.0	31.6 $\pm$ 0.6	316.4 $\pm$ 6.2	31.6 $\pm$ 0.6
Conservative Ensemble	0.0 $\pm$ 0.0	31.0 $\pm$ 0.9	309.6 $\pm$ 9.2	31.0 $\pm$ 0.9
Log-Q=0.9 (Ours)	0.1 $\pm$ 0.3	37.7 $\pm$ 0.6	296.0 $\pm$ 132.8	37.7 $\pm$ 0.6

Appendix

Table 6: Breast Cancer benchmark results. We report the mean

\pm

one standard deviation, computed over 10 repetitions with different random seeds, where each repetition corresponds to the mean performance across a 5-fold cross-validation.

Figure 7: Boxplot of Ratio(

c=0.1

) for the Top 5 Method on the dataset ScreenX.

Figure 8: Boxplot of Ratio(

c=0.1

) for the Top 5 Method on the dataset Corruption. The tiny box observed for Mul-Q=0.9 and Mul-Q=0.95 may appear unusual at first glance. However, we have carefully verified the results and confirmed that they are not due to an implementation error. The learning procedure is fully deterministic, with no source of randomness, and the different cross-validation seeds ultimately produce data splits that yield the same average performance across folds.

Figure 9: Boxplot of Ratio(

c=0.1

) for the Top 5 Method on the dataset Credit.

Figure 10: Boxplot of Ratio(

c=0.1

) for the Top 5 Method on the dataset Breast Cancer.

Feature	EBC-Min	XGBoost	Logistic	Decision Tree	Random Forest
X1	1.000	0.0461	0.3135	0.0000	0.0084
X2	0.025	0.0241	-0.4158	0.0000	0.0383
X3	0.950	0.1074	0.4017	0.0933	0.1066
X4	1.000	0.1414	1.1880	0.2244	0.1531
X5	0.925	0.0468	0.6842	0.0220	0.0615
X6	0.075	0.0368	0.0228	0.0211	0.0558

Appendix

Table 7: Feature importance/coefficient summary across methods. EBC-Min records the frequency where the minimum of the negative sample distribution is significantly lower than the positive sample distribution across 40 train-test splits, same for EBC-Max after applying

x\mapsto-x

to the data.

Rank	XGBoost	Logistic	Decision Tree	Random Forest	Highest Frequency Summary
1	X12	X12	X10	X4	X12
2	X10	X4	X12	X10	X10
3	X4	X8	X4	X4	X4
4	X3	X5	X8	X12	X3,X5
5	X8	X9	X3	X8	X8

Appendix

Table 8: Top 5 features ranked by absolute importance/coefficient for each method. In comparaison, the features always selected by our features selection mechanism are X1,X4,X8,X10,X12 and X3,X5 are selected more than

90\%

time of the 40 train-test split.

Figure 11: Barplot of the training time for the different methods on the dataset ScreenX. Runtime measurements were obtained on a CPU-only server with 4 GB of RAM.

Figure 12: Barplot of the training time for the different methods on the dataset Credit. Runtime measurements were obtained on a CPU-only server with 4 GB of RAM.

Figure 13: Barplot of the training time for the different methods on the dataset Corruption. Runtime measurements were obtained on a CPU-only server with 4 GB of RAM.

Figure 14: Barplot of the training time for the different methods on the dataset Breast Cancer. Runtime measurements were obtained on a CPU-only server with 4 GB of RAM.

Explore similar work

Imbalanced Classification under Capacity Constraints
May 5, 2026Daniel Fraiman, Ricardo FraimanImbalanced Classification Class Imbalance
Departamento de Matem´atica y Ciencias, Universidad de San Andr´es, Buenos Aires, Argentina · CONICET, Argentina. · PEDECIBA, Matem´atica, Uruguay.
Large margin classifier with graph-based adaptive regularization
May 3, 2026Vítor M. Hanriot, Turíbio T. Salis, Luiz C. B. Torres +2Classifier Class Imbalance
Graduate Program in Electrical Engineering - Universidade Federal de Minas Gerais - Av. Antônio Carlos 6627, 31270-901, Belo Horizonte, MG, Brazil · Department of Computer and Systems - Universidade Federal de Ouro Preto - João Monlevade 35931-022, Brazil.
Universality of Benign Overfitting in Binary Linear Classification
Jan 17, 2025Ichiro Hashimoto, Stanislav Volgushev, Piotr ZwiernikOverfitting Empirical Risk Minimization
Department of Statistical Sciences, University of Toronto

May 5, 2026, stat.MLJ/K move · Enter open · S save

Imbalanced Classification under Capacity Constraints

Daniel Fraiman, Ricardo Fraiman

Departamento de Matem´atica y Ciencias, Universidad de San Andr´es, Buenos Aires, Argentina · CONICET, Argentina. · PEDECIBA, Matem´atica, Uruguay.

Imbalanced Classification Class Imbalance Credit Risk Prediction Empirical Risk Minimization Fraud Detection

Open paper AskPDF arXiv

Detecting observations from a minority class under severe class imbalance is a central challenge in applications such as fraud detection, medical screening, and industrial quality control. In these settings, each positive prediction triggers a costly follow-up action, an MRI scan, a transaction audit, whose execution is subject to real operational constraints. This paper proposes a formal classification framework under capacity constraints: given a user-defined bound limit

b

on the proportion of observations that can be labeled as belonging to the minority class, the goal is to find the classifier that maximizes sensitivity on that class. We characterize the optimal classifier under this constraint and establish its equivalence with the classical Bayes classifier under a reweighting of the prior probabilities. We also introduce a capacity-adjusted performance metric

M

that accounts for the effective detection rate when the capacity constraint is binding. The framework is implemented on top of standard learning methods, k-NN, SVM, random forests, and neural networks, and statistical consistency is established for each. We further show that these methods reduce to post-hoc thresholding when no hyperparameters are oriented toward the capacity-constrained objective, and introduce a capacity-aware support vector machine that exploits the constraint during training and achieves the strongest empirical performance. Experiments on the Taiwanese credit card default dataset confirm that capacity-constrained classifiers substantially outperform both classical approaches and SMOTE under high imbalance regimes. The framework extends naturally to multiclass settings and online environments.

Abstract

Explore similar work

Imbalanced Classification under Capacity Constraints

Large margin classifier with graph-based adaptive regularization

Universality of Benign Overfitting in Binary Linear Classification