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
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
Figure 1: Multiclass classification boundary ξ⋆(β,s) of ( 20 ). Left: boundary as a function of the feature-rarity exponent β , for several values of the class-growth parameter s . Right: boundary as a function of s , for several values of β . Dashed lines represent the large s approximation 2sr . The case s→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 (β,r) values for C∈{2,5,10} , under the Gaussian multiclass Rare-and-Weak Useful Feature model with p=2,000 , nMonte=150 . The x-axis is the sparsity exponent β 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. β for a fixed r value and several value of C ( p=2,000 , nMonte=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 ( α=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.
Baseline (all features)
DP-HCT -selected features
Dataset
n/p/C
SVM
LoR
SVM
LoR
# Sel.
Heart-Circadian (F)
130/46120/8
14.7±2.4
32.4±4.5
74.8±6.1
76.3±4.9
460±47
Worm-Bacteria (KW)
72/672/4
24.2±4.2
71.5±5.1
53.4±7.7
80.5±5.4
56±5
Blood-Diet (F)
70/736/4
47.5±5.0
60.8±7.1
78.8±4.1
82.9±3.9
108±7
Zebrafish-BPF (KW)
62/117/4
64.8±5.9
59.8±5.7
72.9±7.7
73.9±7.0
38±3
Biliary-miRNA (KW)
36/803/3
71.7±6.1
83.3±5.0
90.0±4.4
96.7±2.2
62±38
Table 1: CV accuracy (mean ± 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∈{2,3,4,5,7,10} . Color encodes misclassification rate. Solid white: the multiclass boundary r=ξ⋆(β,s) of ( 20 ). Dotted white: the fixed-class Donoho–Jin boundary r=ρ⋆(β) . 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 , β=0.6 . Middle : FDR vs. r for C=5 , β=0.8 . Right : FDR vs. the number of classes C∈{2,…,10} for r=1 , β=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 ( α=0.05 ); dashed grey: the nominal level 0.10 . Shaded bands are 95% confidence intervals of the Monte Carlo mean ( p=2,000 , nMonte=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/17/16/16/16/16/16/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/18/18/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/18/17/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/16/15/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/12/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±1.9
29.9±3.5
—
DP-HCT
69.3±5.5
75.2±4.7
1.0%
Worm-Bacteria (KW)
Baseline
22.9±4.2
71.5±5.5
—
DP-HCT
55.2±6.1
80.3±5.6
8.9%
Blood-Diet (F)
Baseline
41.0±5.0
58.2±5.3
—
DP-HCT
76.9±5.4
80.1±4.0
14.6%
Appendix
Table 3: CV accuracy (mean ± 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 γ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 γ0=1/2 ; error bars indicate ± SEM over the pooled CV folds ( 10 folds ×3 repeats; 7 folds for Heart-Circadian); the uniform chance level 1/C is shown as a dashed horizontal line.
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.
Rittwika Kansabanik, Adrian Barbu
Department of Statistics, Florida State University
Feature rankings are widely used in supervised feature selection because they are simple, scalable and easy to interpret. Variables are first ranked by a relevance score, and a subset is then obtained by retaining the top-ranked variables. Although the first stage has been extensively studied, the second is often governed by an arbitrary cardinality, an empirical threshold or cross-validation, without a direct interpretation. This raises a basic question: given a feature ranking, when is there enough accumulated class-separation evidence to stop selecting features? This paper develops a distributional framework for transforming supervised feature rankings into class-independent subsets through an explicit risk-calibrated stopping rule. For each variable and each pair of classes, marginal separation is measured by the Bhattacharyya coefficient between the corresponding class-conditional distributions. The proposed method selects a single global subset shared by all classes by retaining the shortest prefix of a ranking whose residual product overlap falls below a prescribed threshold for every relevant class contrast. We derive binary and multiclass Bayes-risk bounds for the labelled product marginal problem, and obtain prior-dependent and prior-free calibrations of the residual-overlap threshold from a target all-pairs risk level. An empirical comparison on high-dimensional genomic datasets illustrates that the rule can reduce tens of thousands of variables to a few dozen while maintaining predictive performance statistically comparable to the all-features baseline. As the stopping rule only requires one-dimensional marginal overlap estimates and scans a precomputed ranking, it is well suited to very high-dimensional settings where exhaustive subset search is infeasible and interpretable truncation of feature rankings is essential.
Jesus S. Aguilar-Ruiz
School of Engineering Pablo de Olavide University ES-41013 Seville, Spain
Weighted sums of random kitchen sinks (W-RKS) is a commonly used feature extraction technique for supervised learning tasks. A major drawback of this method is the redundancy and ineffectiveness of many extracted random features. This paper investigates efficient methods for reducing such redundancy in multi-class classification problems. We specifically formulate feature selection as a variant of the sequentially nested model selection problem and introduce the Successive Empirical Excess Risk Difference Maximization (SEED-MAX) algorithm. It recursively computes empirical risks to identify the most parsimonious yet informative set of features. We derive an analytical lower bound for the probability of correct feature selection by the SEED-MAX algorithm. This lower bound on the probability of correct feature selection can be made arbitrarily close to one by increasing the training dataset size. To further enhance the rate of pruning, we evaluate the features retained by SEED-MAX using the Fisher test (F-Test). Empirical evaluations on UCR time-series classification datasets show that the sequential application of SEED-MAX with the Fisher test achieves approximately 92 percent rate of pruning with negligible degradation in classification accuracy. Implementations of the SEED-MAX and SEED-MAX-F-Test methods are available at https://github.com/OmidiAmin/seed-max-ftest.
Mohammad Amin Omidi, Babak Seyfe, Shahrokh Valaee
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