Multiclass Classification with Rare Useful Features: Fundamental Limits and the Optimality of Diversity Pursuit Higher Criticism Thresholding

Gabriel Moryoussef; Alon Kipnis

stat.MLNov 1, 2026

Multiclass Classification with Rare Useful Features: Fundamental Limits and the Optimality of Diversity Pursuit Higher Criticism Thresholding

Authors: Gabriel Moryoussef, Alon Kipnis

Organizations: Department of Statistics and Data Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA · Efi Arazi School of Computer Science, Reichman University, Herzliya, Israel

Abstract

We consider classification in high-dimensional feature spaces where only a vanishing fraction of features are useful and the number of classes may be large. While this rare-and-weak useful-feature regime is well understood in the binary setting, its multiclass version raises new questions: a feature can be useful for class discrimination without separating any specific pair of classes. We focus on a rare feature diversity model, in which most features are useless, but a small fraction promote discrimination among classes in a way that can be detected by a per-feature diversity test, such as one-way ANOVA or the Kruskal-Wallis test. For this setting, we propose Diversity Pursuit Higher Criticism Thresholding (DP-HCT), a feature-screening procedure that applies a higher-criticism threshold to the collection of p-values obtained from per-feature diversity tests. We justify DP-HCT under a Gaussian multiclass Rare-and-Weak Useful Feature model with class-mean contrasts of fixed magnitude in random directions, extending the binary model of Donoho and Jin (2008). When the number of classes is fixed, our model recovers the binary phase transition. When the number of classes grows logarithmically with the number of features, however, we derive a new and strictly harder phase transition, driven by the growing degrees of freedom and their effect on the useful-feature tail rate. We show that whenever classification beyond chance is possible, DP-HCT with ANOVA, followed by a simple classifier based on similarity to class means, achieves asymptotically perfect accuracy. Experiments on real multiclass classification benchmarks demonstrate substantial improvements, and numerical simulations confirm that the derived phase-transition curve accurately predicts the finite-sample behavior of DP-HCT in the growing-class regime.

Figures & tables

Panel of Figure 1 — Figure 1: Multiclass classification boundary $\xi^{\star}(\beta,s)$ of ( 20 ). Left: boundary as a function of the feature-rarity exponent $\beta$ , for several values of the class-growth parameter $s$ . Right: boundary as a function of $s$ , for several values of $\beta$ . Dashed lines represent the large $s$ approximation $\sqrt{2sr}$ . The case $s\to 0$ corresponds to the binary Rare-and-Weak Useful Feature boundary ( Donoho and Jin, 2008 ; Jin, 2009 ) . Larger $s$ shifts the boundary upward, indicating the larger signal strength $r$ required for nontrivial classification.

Figure 2: DP-HCT misclassification phase transition . Misclassification rate (color) over a grid of $(\beta,r)$ values for $C\in\{2,5,10\}$ , under the Gaussian multiclass Rare-and-Weak Useful Feature model with $p=2{,}000$ , $n_{\mathrm{Monte}}=150$ . The x-axis is the sparsity exponent $\beta$ and the y-axis is the calibrated signal strength $r$ . Configurations in which the misclassification rate is above chance are marked with black frames. Solid white: the theoretical phase transition curve (Theorem 2 ). Dotted white: the phase transition curve corresponding to a fixed number of classes, derived in Donoho and Jin (2008) .

Figure 3: Threshold comparison: classification error vs. $\beta$ for a fixed $r$ value and several value of $C$ ( $p=2{,}000$ , $n_{\mathrm{Monte}}=150$ ). Solid black: ideal threshold of ( 14 ); dashed blue: DP-HCT ; dash-dot orange: Benjamini-Hochberg’s False-Discovery Rate (BH-FDR) at level $0.10$ ; dotted green: Bonferroni ( $\alpha=0.05$ ). Dashed grey: chance-level error $1-1/C$ . It can be seen that DP-HCT classification performance closely follows the ideal threshold’s performance.

Dataset	$n/p/C$	SVM	LoR	SVM	LoR	# Sel.
		Baseline (all features)		DP-HCT -selected features
Heart-Circadian (F)	$130/46120/8$	$14.7{\pm}2.4$	$32.4{\pm}4.5$	$\mathbf{74.8{\pm}6.1}$	$\mathbf{76.3{\pm}4.9}$	$460{\pm}47$
Worm-Bacteria (KW)	$72/672/4$	$24.2{\pm}4.2$	$71.5{\pm}5.1$	$\mathbf{53.4{\pm}7.7}$	$\mathbf{80.5{\pm}5.4}$	$56{\pm}5$
Blood-Diet (F)	$70/736/4$	$47.5{\pm}5.0$	$60.8{\pm}7.1$	$\mathbf{78.8{\pm}4.1}$	$\mathbf{82.9{\pm}3.9}$	$108{\pm}7$
Zebrafish-BPF (KW)	$62/117/4$	$64.8{\pm}5.9$	$59.8{\pm}5.7$	$\mathbf{72.9{\pm}7.7}$	$\mathbf{73.9{\pm}7.0}$	$38{\pm}3$
Biliary-miRNA (KW)	$36/803/3$	$71.7{\pm}6.1$	$83.3{\pm}5.0$	$\mathbf{90.0{\pm}4.4}$	$\mathbf{96.7{\pm}2.2}$	$62{\pm}38$

Table 1: CV accuracy (mean

\pm

SEM, %) for classification post- DP-HCT feature screening with ANOVA F ("F") or KW ("KW") tests; results are averaged over 10-fold, unit stratified cross-validation (7-fold for Heart-Circadian). “# Sel.” is the mean number of features retained by DP-HCT .

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Ideal-threshold misclassification rate heatmaps for $C\in\{2,3,4,5,7,10\}$ . Color encodes misclassification rate. Solid white: the multiclass boundary $r=\xi^{\star}(\beta,s)$ of ( 20 ). Dotted white: the fixed-class Donoho–Jin boundary $r=\rho^{\star}(\beta)$ . The transition from high to low error closely tracks the multiclass boundary; as $C$ increases, the boundary rises, reflecting the harder multiclass discrimination problem.

Figure 5: Empirical false-discovery rate of the threshold rules. The empirical FDR is the average, over Monte Carlo draws, of the proportion of selected features that are null. Left : FDR vs. $r$ for $C=5$ , $\beta=0.6$ . Middle : FDR vs. $r$ for $C=5$ , $\beta=0.8$ . Right : FDR vs. the number of classes $C\in\{2,\dots,10\}$ for $r=1$ , $\beta=0.6$ . Solid black: ideal threshold of ( 14 ); dashed blue: DP-HCT ; dash-dot orange: Benjamini–Hochberg’s False-Discovery Rate ( $q=0.10$ ); dotted green: Bonferroni ( $\alpha=0.05$ ); dashed grey: the nominal level $0.10$ . Shaded bands are $95\%$ confidence intervals of the Monte Carlo mean ( $p=2{,}000$ , $n_{\mathrm{Monte}}=300$ ). Draws in which DP-HCT does not reject the global null (HC statistic below $1.9$ ) select no features and count as an FDR of zero. The figure shows that DP-HCT closely tracks the ideal threshold in the regime where detection is possible. These two rules are tuned for classification rather than for error control, and therefore admit many false discoveries. BH attains its nominal level and Bonferroni is conservative.

Dataset	Description	$n$	$p$	$C$	Class sizes	Units
Heart-Circadian (GSE10045) [ Bray et al., 2008 ]	Cardiac expression in wild-type and transgenic mice sampled every three hours. Classes are Zeitgeber times; genotypes and cardiac chambers are pooled. Units are animals.	$130$	$46{,}120$	$8$	$19/\allowbreak 17/\allowbreak 16/\allowbreak 16/\allowbreak 16/\allowbreak 16/\allowbreak 16/\allowbreak 14$	$66$
Worm-Bacteria (GSE15923) [ Coolon et al., 2009 ]	Two-color expression arrays from C. elegans grown on four bacterial environments, which define the classes. Units are arrays, each contributing two channel samples.	$72$	$672$	$4$	$18/\allowbreak 18/\allowbreak 18/\allowbreak 18$	$38$
Blood-Diet (ST002019) [ Ferguson, 2022 ]	Blood LC–MS metabolomics. Classes combine diet (pre/post) and study phase (1/2). Units are participants, each sampled at two visits.	$70$	$736$	$4$	$18/\allowbreak 18/\allowbreak 17/\allowbreak 17$	$35$
Zebrafish-BPF (ST003804) [ Guo, 2025 ]	Zebrafish liver LC–MS metabolomics after long-term bisphenol F exposure. Classes are four exposure groups; samples are independent fish.	$62$	$117$	$4$	$16/\allowbreak 16/\allowbreak 15/\allowbreak 15$	$62$
Biliary-miRNA (GSE140001) [ Loeffler et al., 2020 ]	miRNA expression in distal cholangiocarcinoma. Classes are three tissue types; each patient contributes one sample of each type and is a unit.	$36$	$803$	$3$	$12/\allowbreak 12/\allowbreak 12$	$12$

Appendix

Table 2: Five real-data benchmarks, their sizes, and additional relevant information. “Units” is the number of independent patients, participants, animals or arrays (equal to

n

when samples are independent).

Dataset	Method	SVM	LoR	Frac. sel.
Heart-Circadian (F)	Baseline	$13.6{\pm}1.9$	$29.9{\pm}3.5$	—
Heart-Circadian (F)	DP-HCT	$\mathbf{69.3{\pm}5.5}$	$\mathbf{75.2{\pm}4.7}$	$1.0\%$
Worm-Bacteria (KW)	Baseline	$22.9{\pm}4.2$	$71.5{\pm}5.5$	—
Worm-Bacteria (KW)	DP-HCT	$\mathbf{55.2{\pm}6.1}$	$\mathbf{80.3{\pm}5.6}$	$8.9\%$
Blood-Diet (F)	Baseline	$41.0{\pm}5.0$	$58.2{\pm}5.3$	—
Blood-Diet (F)	DP-HCT	$\mathbf{76.9{\pm}5.4}$	$\mathbf{80.1{\pm}4.0}$	$14.6\%$

Appendix

Table 3: CV accuracy (mean

\pm

SEM, %) for the five datasets, averaged over five CV runs with different seeds (the SEM is the mean within-run SEM across folds). The diversity test is given next to each dataset (F = ANOVA F, KW = Kruskal–Wallis); raw p-values; HC with

\gamma_{0}=1/2

. “Frac. sel.” = mean fraction of features selected by HC.

Figure 6: Classification with LoR pre- and post-feature screening by DP-HCT with added noise (left column) or nuisance features (right column). p-values are obtained either from ANOVA F (ANOVA) or Kruskal–Wallis (KW) as indicated for each panel; HC with $\gamma_{0}=1/2$ ; error bars indicate $\pm$ SEM over the pooled CV folds ( $10$ folds $\times$ $3$ repeats; $7$ folds for Heart-Circadian); the uniform chance level $1/C$ is shown as a dashed horizontal line.

Multiclass Classification

Multiclass classification assigns inputs to one of several labels while addressing uncertainty, class imbalance, and errors across classes.

See all 99 papers

Feature Selection for Latent Factor Models
Dec 13, 2024Rittwika Kansabanik, Adrian BarbuFeature Selection
Department of Statistics, Florida State University
When to Truncate a Feature Ranking: A Residual-Overlap Stopping Rule for Subset Selection
Jun 30, 2026Jesus S. Aguilar-RuizFeature Selection
School of Engineering Pablo de Olavide University ES-41013 Seville, Spain
Random Feature Pruning for Multi-Class Classification
Oct 10, 2026Mohammad Amin Omidi, Babak Seyfe, Shahrokh ValaeeFeature Selection Random Feature Methods
Information Theoretic Learning Systems Laboratory (ITLSL), Department of Electrical Engineering, Shahed University, Tehran, Iran · Department of Electrical and Computer Engineering, University of Toronto, Toronto, Canada

Dec 13, 2024J/K move · Enter open · S save

Feature Selection for Latent Factor Models

Rittwika Kansabanik, Adrian Barbu

Department of Statistics, Florida State University

Feature Selection

Open paper AskPDF arXiv

Feature selection is crucial for pinpointing relevant features in high-dimensional datasets, mitigating the 'curse of dimensionality,' and enhancing machine learning performance. Traditional feature selection methods for classification use data from all classes to select features for each class. This paper explores feature selection methods that select features for each class separately, using class models based on low-rank generative methods and introducing a signal-to-noise ratio (SNR) feature selection criterion. This novel approach offers a theoretically sound guarantee of feature recovery under specific assumptions and has been demonstrated to outperform some existing feature selection methods on standard classification datasets. Additionally, it can be easily applied in a class-incremental learning setup, yielding performance comparable to that of some current methods.

Abstract

Multiclass Classification

Explore similar work

Feature Selection for Latent Factor Models

When to Truncate a Feature Ranking: A Residual-Overlap Stopping Rule for Subset Selection

Random Feature Pruning for Multi-Class Classification