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

Gabriel Moryoussef, Alon KipnisarXiv 2026 · arXiv

In high-dimensional data analysis—think genomics or metabolomics—we are often searching for a "needle in a haystack": a tiny subset of useful features buried among thousands of irrelevant ones. While we’ve had a solid theoretical grasp of this for binary (two-class) problems for nearly two decades, the multiclass case has remained a bit of a "Wild West." A new paper from researchers at Carnegie Mellon and Reichman University finally brings law and order to this regime.

TL;DR

The authors introduce Diversity Pursuit Higher Criticism Thresholding (DP-HCT), a feature-screening method that optimally identifies rare, weak signals in multiclass data. They prove that as the number of classes grows, classification becomes strictly harder, and they derive the fundamental "phase transition" boundary where successful classification becomes possible.

What Problem Does This Paper Address?

Modern datasets often have a "rare-and-weak" structure: only a vanishingly small fraction of features are informative, and the signal in any single feature is too weak to be detected reliably on its own.

In binary classification, the "Higher Criticism" (HC) framework established by Donoho and Jin provides an optimal way to set a threshold for feature selection. However, multiclass problems introduce a new wrinkle: a feature might be useful because it shows high "diversity" across many classes, even if it doesn't clearly separate any specific pair of classes. The authors set out to determine the fundamental limits of classification in this setting—especially when the number of classes is large—and to find a selection procedure that reaches those limits.

Methods

The authors propose a three-step pipeline called DP-HCT:

  1. Per-feature Diversity Testing: Instead of pairwise comparisons, they use a global diversity test like one-way ANOVA or the Kruskal–Wallis test for every feature to generate a collection of $p$-values.
  2. Higher Criticism Thresholding: They apply the HC statistic to these $p$-values. HC is a "second-level" significance test that looks for an unusual "pile-up" of small $p$-values, allowing the algorithm to automatically pick a near-optimal threshold without knowing the underlying signal strength or rarity.
  3. Classification: They use a simple centroid-similarity classifier on the selected features.

To prove this works, they developed the Multiclass Rare-and-Weak (MCRW) model, which simulates high-dimensional Gaussian data where useful features have class-mean differences pointing in random directions.

Datasets

The researchers validated their work using both synthetic simulations and five real-world biological benchmarks where $p \gg n$ (many more features than samples):

  • Heart-Circadian: Gene expression in mouse hearts ($C=8$ classes).
  • Worm-Bacteria: C. elegans gene expression on different diets ($C=4$).
  • Blood-Diet: Human metabolomics data ($C=4$).
  • Zebrafish-BPF: Metabolomics from zebrafish liver ($C=4$).
  • Biliary-miRNA: miRNA expression in tissue samples ($C=3$).

Key Insights and Ideas

  • The "Growing Class" Penalty: The most striking finding is that if the number of classes $C$ grows with the number of features $p$, the problem becomes fundamentally harder. The "phase transition" boundary—the line between "classification is impossible" and "perfect classification is possible"—shifts upward.
  • Degrees of Freedom Matter: This shift is driven by the increasing degrees of freedom in the diversity tests (like ANOVA). More classes mean more ways for noise to look like signal, requiring a stronger true signal to overcome the "noise floor."
  • Optimal Adaptivity: DP-HCT is "parameter-free" in the sense that it doesn't need to know how rare or how weak the features are. It "adapts" to the data to find the best threshold.
The multiclass classification boundary $\xi^*(\beta, s)$ shifts upward as the class-growth parameter $s$ increases, indicating that more signal is required for successful classification when there are many classes.

Key Results

  • Theoretical Optimality: The authors derived a new phase transition curve, $\xi^*(\beta, s)$. They proved that if the signal strength $r$ is above this curve, DP-HCT achieves asymptotically perfect accuracy. If it's below, no classifier can do better than random chance.
  • Massive Accuracy Boosts: On the Heart-Circadian dataset, a standard SVM achieved only 14.7% accuracy on the full feature set. After DP-HCT screening, accuracy skyrocketed to 74.8%.
  • Robustness to Noise: In "stress tests," the DP-HCT pipeline maintained its performance even when thousands of pure-noise features were added to the data, whereas baseline methods (like standard Logistic Regression) degraded quickly.
Heatmaps showing the misclassification rate. The solid white line is the theoretical boundary derived in the paper; configurations with black frames are where classification is significantly better than chance. Note how the boundary rises as the number of classes $C$ increases.

Limitations and Future Work

While the theory is robust, the authors note a few areas for expansion:

  • Unbalanced Designs: The current theoretical proofs assume an equal number of samples per class. Real-world data is rarely so neat.
  • Sample Size Regimes: The analysis focuses on a regime where the number of samples $n$ grows very slowly relative to features $p$. Exploring "polynomial growth" regimes ($n = p^\theta$) is a logical next step.
  • Clustering: The authors believe the "diversity pursuit" logic could be applied to high-dimensional clustering problems, where class labels aren't known in advance.

Summary updated

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.
BibTeX
@misc{moryoussef2026multiclass,
  author = {Gabriel Moryoussef and Alon Kipnis},
  title = {{Multiclass Classification with Rare Useful Features: Fundamental Limits and the Optimality of Diversity Pursuit Higher Criticism Thresholding}},
  year = {2026},
  eprint = {2611.02255},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.02255},
}
Figure