betaFeedback

WorksMathematics

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

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.

Introduction

Modern classification problems often involve high-dimensional representations, where the number of measured features pp is large but the discriminating information is concentrated in a small subset of coordinates. This sparse-useful-feature structure arises naturally in genomics, text, tabular data, and learned representations, and it motivates feature-screening methods that identify informative coordinates before classification. Such identification is also known to be crucial when data are scarce or the noise level is high [18, 13, 15, 3]. Understanding when classification is possible in this rare-and-weak useful-feature regime is important for assessing sample complexity, the value of feature engineering, and the role of dimensionality reduction or feature screening.

40th Conference on Neural Information Processing Systems (NeurIPS 2026).

In the binary case, rare-and-weak useful-feature models provide a sharp theoretical framework for understanding this phenomenon [11]. They characterize regimes in which classification is possible despite individual signals being weak [19, 13, 27]. However, multiclass classification introduces qualitatively new issues. A feature may be useful not because it separates one class from another, but because it induces a pattern of variation across many classes [6, 1, 32, 20]. This raises a basic question: how does the number of classes affect the boundary between possible and impossible classification?

We address this question through a Gaussian multiclass Rare-and-Weak Useful Feature model in which class centroids are largely identical, except in a small fraction of the coordinates which individually exhibit statistically detectable diversity signal across classes. This model is designed to isolate the effect of the number of classes on classification in high-dimensions. Our main contribution is a phase-transition analysis for this model that separates classification with accuracy tending to one from classification with accuracy tending to chance level. When the number of classes is fixed, the classification boundary agrees with the binary rare/weak theory [11, 13, 19, 12]. In contrast, when the number of classes grows logarithmically with the number of features, a new phase transition emerges, capturing the additional difficulty introduced by many classes.

The achievability side of the theory is established by a simple diversity-based screening procedure that computes a diversity score for each feature individually, then applies the higher-criticism threshold for selecting features [11]. We call this screening procedure Diversity Pursuit Higher Criticism Thresholding (DP-HCT). Under the rare-and-weak useful feature model, DP-HCT followed by a simple centroid-similarity classifier asymptotically achieves perfect classification throughout the region where nontrivial classification is possible. Complementing this theoretical characterization of the classification boundary, experiments on several real-world multiclass benchmarks show performance gains from DP-HCT.

Contributions

  1. A fundamental limit for multiclass classification with rare and weak useful features. We introduce a multiclass Rare-and-Weak Useful Feature model in which the number of classes grows logarithmically with the number of features pp. The model is governed by three calibration parameters: β\beta, which controls feature rarity; ss, which controls the growth rate of the number of classes; and rr, which controls signal strength. Our main result establishes a sharp phase transition as p→∞p \to\infty: there exists a function ξ⋆(β,s)\xi^{\star}(\beta,s) such that if r<ξ⋆(β,s)r < \xi^{\star}(\beta,s), no classifier achieves accuracy beyond chance asymptotically, whereas if r>ξ⋆(β,s)r > \xi^{\star}(\beta,s), classification with accuracy tending to one is possible. The function ξ⋆(β,s)\xi^{\star}(\beta,s) is illustrated in Figure 1.

Multiclass classification boundary curves

Figure 1. Multiclass classification boundary ξ⋆(β,s)\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 ss. Right: boundary as a function of ss, for several values of β\beta. Dashed lines represent the large ss approximation 2sr\sqrt{2sr}. The case s→0s \to0 corresponds to the binary Rare-and-Weak Useful Feature boundary [11, 19]. Larger ss shifts the boundary upward, indicating the larger signal strength rr required for nontrivial classification.

  1. Constructive achievability via Diversity Pursuit Higher Criticism Thresholding. We prove that this fundamental limit is attained by a simple diversity-based screening procedure. Specifically, when r>ξ⋆(β,s)r > \xi^\star(\beta,s), applying higher-criticism thresholding to ANOVA pp-values, followed by a centroid-similarity classifier on the selected features, achieves classification accuracy tending to one.

  1. Numerical validation and empirical evidence on multiclass benchmarks. We run large-scale Monte Carlo experiments across the model’s defining parameters. The simulations show that HC thresholding, despite not using the model parameters, closely tracks the oracle threshold and yields empirical accuracy consistent with the predicted phase-transition curve ξ⋆(β,s)\xi^\star(\beta,s). We also compare classification post-DP-HCT to alternative screening rules, including Bonferroni and Benjamini–Hochberg FDR [5]. Finally, we evaluate classification post-DP-HCT on five real multiclass benchmarks: gene expression (Heart-Circadian, Worm-Bacteria), metabolomics (Blood-Diet, Zebrafish-BPF) and miRNA expression (Biliary-miRNA). Across these datasets, DP-HCT substantially improves the kernel SVM and logistic-regression baselines, providing proof-of-concept evidence for diversity-based HC screening in multiclass problems.

Significance of the contributions compared to previous work. The phase transition expression we derive provides an accurate description of the effect of the number of classes on the possibility of successful classification. By using this expression as a pivot, one can assess the sample complexity of classification problems or the amount of feature engineering needed to achieve successful classification. Similar attempts in related models are provided in Abramovich et al. [ [2], Thrampoulidis et al. [ [32]. To the best of our knowledge, our setting is the first to incorporate the number of classes in an asymptotic phase transition analysis.

Classification under a rare-and-weak useful-feature setting has been studied by Donoho and Jin [ [11, 13], who also proposed using higher criticism for feature screening. The impossibility of classification in such a model was established in Jin [ [19]. Our work is best seen as an extension of this result to the multiclass setting with an increasing number of classes. Our phase transition curve accounts for the change in the full useful-feature tail rate caused by the added degrees of freedom, an effect absent from the binary and fixed-class settings. Other rare-and-weak useful-feature settings can be found in Azar and Nadler [ [3], Verzelen and Arias-Castro [ [33] and references therein. More closely related to the multiclass setting, the works Jin and Wang [ [20], Jin et al. [ [21], Ma et al. [ [28] proposed using higher criticism to identify useful features for clustering. Their setting can also be seen as a diversity-seeking situation among several groups, for which higher criticism has provided promising empirical results. The associated theoretical analysis, however, does not incorporate growth in the number of groups. We believe that ideas from our work can refine the theoretical understanding of clustering as well.

Analysis Overview The contributions combine several techniques. We derive the useful-feature tail exponent directly from the noncentral chi-square moment-generating function, using a Chernoff bound and an exponential tilting adjusted to the increase in the degrees of freedom. This analysis extends the fixed-degree chi-square approximations in Kipnis [ [22], Donoho and Jin [ [10]. Concentration of the within-class variance transfers this exponent to the exact ANOVA F-test pp-values. We distinguish two regimes: C=o(log⁡p)C = o(\log p), including fixed CC, which recovers the binary boundary; and C−1∼2slog⁡pC - 1 \sim2s \log p with fixed s>0s > 0, which yields the growing-class boundary.

When CC is fixed (or grows as o(log⁡p)o(\log p)), the analysis recovers the classical Gaussian boundary [10, 11]; when C∼2slog⁡pC \sim2s \log p, it produces a strictly different boundary. The new boundary represents an increase in the difficulty of classification due to the increased number of classes.

The impossibility region follows from a truncated likelihood-ratio second-moment argument for the joint training and test experiment. Above the boundary, HC attains a polynomially large score, which guarantees polynomially many useful selections and a favorable ratio of squared useful selections to total selections. Uniform threshold bounds transfer these properties to the data-chosen threshold.

Organization Section 2 introduces DP-HCT for feature screening. In Section 3, we specify the multiclass Rare-and-Weak Useful Feature framework. In Section 4, we derive the asymptotic phase transition for successful classification and we show that DP-HCT based on ANOVA and a centroid-similarity classifier achieves the theoretical detectability region. Section 5 reports simulation and real-data results. Additional simulation results and full proofs are provided in the Supplementary Material.

Algorithm 1 DP-HCT: Diversity Pursuit with Higher Criticism Thresholding.

Require: training data {(Xi,Yi)}i=1n\{(X_i,Y_i)\}_{i=1}^{n}; diversity test DD;

  1. for j=1,…,pj=1,\ldots,p do

  2. compute DjD_j on {(Xi,j,Yi)}i=1n\{(X_{i,j},Y_i)\}_{i=1}^{n}; obtain p-value πj\pi_j.

  3. end for

  4. sort: π(1)≤π(2)≤⋯≤π(p)\pi_{(1)}\leq\pi_{(2)}\leq\cdots\leq\pi_{(p)}.

  5. for j=1,…,⌊γ0p⌋j=1,\ldots,\lfloor\gamma_0p\rfloor, set HCp,j←p(j/p−π(j))/(j/p)(1−j/p)\mathrm{HC}_{p,j}\leftarrow\sqrt{p}(j/p-\pi_{(j)})/\sqrt{(j/p)(1-j/p)}.

  6. j⋆←arg max⁡1≤j≤⌊γ0p⌋HCp,jj^\star\leftarrow\operatorname{arg\,max}_{1\leq j\leq\lfloor\gamma_0p\rfloor}\mathrm{HC}_{p,j};

  7. J^←{j∈[p]:πj≤π(j⋆)}\widehat{J}\leftarrow\{j\in[p]:\pi_j\leq\pi_{(j^\star)}\}. Ensure: selected set J^\widehat{J}

Diversity Pursuit with HC Thresholding

We now introduce the DP-HCT feature-screening procedure. Subsequent sections justify this procedure theoretically and empirically.

Feature screening

We have a training dataset {(Xi,Yi)}i=1n\{(X_i,Y_i)\}_{i=1}^{n} with Xi∈RpX_i\in\mathbb{R}^{p} and Yi∈[C]:={1,…,C}Y_i\in[C]:=\{1,\ldots,C\}. For j∈[p]j\in[p] and c∈[C]c\in[C], let Pc,jP_{c,j} denote the class-conditional marginal distribution of feature jj. A feature jj is useless (a.k.a. null) if

H0(j):P1,j=P2,j=⋯=PC,j,(1)H_0^{(j)}: P_{1,j}=P_{2,j}=\cdots=P_{C,j}, \tag*{(1)}

and useful otherwise. Our goal is to improve classification performance by removing useless features. We propose the following DP-HCTscreening procedure, which decomposes into three steps.

(i) Per-feature diversity testing. For each jj, compute a test statistic DjD_j of (1) on {(Xi,j,Yi)}i=1n\{(X_{i,j},Y_i)\}_{i=1}^{n} and convert it to a p-value πj∈[0,1]\pi_j\in[0,1].

(ii) Higher Criticism Thresholding. Let π(1)≤⋯≤π(p)\pi_{(1)}\leq\cdots\leq\pi_{(p)} denote the order statistics of {πj}j=1p\{\pi_j\}_{j=1}^{p}. The Higher Criticism Thresholding (HCT) procedure selects a set of indices J^⊆[p]\widehat{J}\subseteq[p] whose p-values are below a threshold π(j⋆)\pi_{(j^\star)}, where j⋆j^\star is the index that maximizes the Higher Criticism statistic. Specifically, with

HCp,j≜p⋅j/p−π(j)tj(1−tj),j=1,…,p,\mathrm{HC}_{p,j}\triangleq\sqrt{p}\cdot\frac{j/p-\pi_{(j)}}{\sqrt{t_j(1-t_j)}},\qquad j=1,\ldots,p,

where tj:=j/pt_j:=j/p. The HC statistic and the HCT are defined as in Donoho and Jin [ [11, 13, 12]:

HCp:=HCp,j⋆,j⋆:=arg max⁡1≤j≤⌊pγ0⌋ HCp,j,(2)\mathrm{HC}_p:=\mathrm{HC}_{p,j^\star},\qquad j^\star:=\underset{1\leq j\leq\lfloor p\gamma_0\rfloor}{\operatorname{arg\,max}}\ \mathrm{HC}_{p,j}, \tag*{(2)}

where γ0\gamma_0 is a tunable parameter that reflects prior knowledge about the proportion of useful features; we used γ0=1/2\gamma_0=1/2 in all evaluations.

(iii) Selection. The higher criticism-selected set is

J^:={j∈[p]:πj≤π(j⋆)}.\widehat{J}:=\{j\in[p]:\pi_j\leq\pi_{(j^\star)}\}.

The selection procedure (i)-(iii) is summarized in Algorithm 1.

Given the selected set J^\widehat{J}, we define the feature-screened data as

Xi[J^]:=(Xi,j)j∈J^∈R∣J^∣.(3)X_i[\widehat{J}]:=(X_{i,j})_{j\in\widehat{J}}\in\mathbb{R}^{|\widehat{J}|}. \tag*{(3)}

We train a multiclass classifier h^\widehat{h} on {(Xi[J^],Yi)}i=1n\{(X_i[\widehat{J}],Y_i)\}_{i=1}^{n}. For a test point Xn+1X_{n+1}, predict Y^n+1:=h^(Xn+1[J^])\widehat{Y}_{n+1}:=\widehat{h}(X_{n+1}[\widehat{J}]).

Diversity Statistics

Any per-feature test of (1) that produces a null-calibrated p-value fits the template, and different tests can even be applied to different features. Two canonical tests that we explain in detail and apply in practice are the classical Analysis of Variance (ANOVA) F-test and the Kruskal–Wallis test [24]. Aside from these tests, other procedures can be used as diversity statistics, such as the Friedman test and permutation-based tests [25 Ch. 7]. Post-hoc tests such as Tukey’s method [25 Ch. 9] may be useful in extensions of the framework to hierarchical features.

ANOVA F-test. Let nc:=∣{i:Yi=c}∣n_c := |\{i : Y_i = c\}| be the number of observations in class cc and assume nc≥2n_c \ge2. At feature jj, denote the class sample mean by

μ^c,j:=1nc∑i:Yi=cXi,j,c=1,…,C,(4)\hat{\mu}_{c,j} := \frac{1}{n_c} \sum_{i : Y_i = c} X_{i,j}, \qquad c = 1,\ldots,C, \tag*{(4)}

Define the within- and between-class sums of squares as

References

  1. [1]Felix Abramovich and Marianna Pensky. Classification with many classes: Challenges and pluses. Journal of Multivariate Analysis, 174:104536, 2019. doi: 10.1016/j.jmva.2019.104536.DOI
  2. [2]Felix Abramovich, Vadim Grinshtein, and Tomer Levy. Multiclass classification by sparse multinomial logistic regression. IEEE Transactions on Information Theory, 67(7):4637–4646, 2021.arxiv.org/abs/2003.01951
  3. [3]Eyar Azar and Boaz Nadler. Semi-supervised sparse gaussian classification: Provable benefits of unlabeled data. Advances in Neural Information Processing Systems, 37:20132–20169, 2024.arxiv.org/abs/2409.03335
  4. [4]Jinho Baik, Gérard Ben Arous, and Sandrine Péché. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. The Annals of Probability, 33(5):1643–1697, 2005. doi: 10.1214/009117905000000233.
  5. [5]Yoav Benjamini and Yosef Hochberg. Controlling the false discovery rate: A practical and powerful approach to multiple testing. Journal of the Royal Statistical Society, Series B, 57(1):289–300, 1995.
  6. [6]Peter J Bickel, Ya’acov Ritov, and Alexandre B Tsybakov. Hierarchical selection of variables in sparse high-dimensional regression. In Borrowing strength: theory powering applications—a Festschrift for Lawrence D. Brown, volume 6, pages 56–70. Institute of Mathematical Statistics, 2010.
  7. [7]Molly S. Bray, Chad A. Shaw, Michael W. S. Moore, Rebeca A. P. Garcia, Marcelo M. Zanqueta, David J. Durgan, Woo Jung Jeong, Ju-Yun Tsai, Heiko Bugger, Dongfang Zhang, et al. Disruption of the circadian clock within the cardiomyocyte influences myocardial contractile function, metabolism, and gene expression. American Journal of Physiology-Heart and Circulatory Physiology, 294(2):H1036–H1047, 2008.
  8. [8]Cristina Butucea and Yuri I. Ingster. Detection of a sparse submatrix of a high-dimensional noisy matrix. Bernoulli, 19(5B):2652–2688, 2013.
  9. [9]Joseph D. Coolon, Kenneth L. Jones, Timothy C. Todd, Bryan C. Carr, and Michael A. Herman. Caenorhabditis elegans genomic response to soil bacteria predicts environment-specific genetic effects on life history traits. PLoS Genetics, 5(6):e1000503, 2009.
  10. [10]David Donoho and Jiashun Jin. Higher criticism for detecting sparse heterogeneous mixtures. Annals of Statistics, 32(3):962–994, 2004.DOI
  11. [11]David Donoho and Jiashun Jin. Higher criticism thresholding: Optimal feature selection when useful features are rare and weak. Proceedings of the National Academy of Sciences, 105(39):14790–14795, 2008.
  12. [12]David Donoho and Jiashun Jin. Higher criticism for large-scale inference, especially for rare and weak effects. Statistical Science, 30(1):1–25, 2015.
  13. [13]David L. Donoho and Jiashun Jin. Feature selection by higher criticism thresholding achieves the optimal phase diagram. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 367(1906):4449–4470, 2009.
  14. [14]Ahmed El Alaoui, Florent Krzakala, and Michael I. Jordan. Fundamental limits of detection in the spiked Wigner model. The Annals of Statistics, 48(2):863–885, 2020. doi: 10.1214/19-AOS1826.
  15. [15]Jianqing Fan and Yingying Fan. High dimensional classification using features annealed independence rules. Annals of statistics, 36(6):2605, 2008.
  16. [16]Jane Ferguson. TIPs metabolomics (Metabolomics Workbench study ST002019, project PR001282). NIH Common Fund National Metabolomics Data Repository, Metabolomics Workbench, 2022. Vanderbilt University Medical Center. https://doi.org/10.21228/M8Q51.
  17. [17]Qiuyuan Guo. Metabolomics analysis of zebrafish liver under long-term BPF exposure (Metabolomics Workbench study ST003804, project PR002378). NIH Common Fund National Metabolomics Data Repository, Metabolomics Workbench, 2025. Washington University in St. Louis. https://doi.org/10.21228/M87Z5M.
  18. [18]Yuri I Ingster, Christophe Pouet, and Alexandre B Tsybakov. Classification of sparse high-dimensional vectors. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 367(1906):4427–4448, 2009.DOI
  19. [19]Jiashun Jin. Impossibility of successful classification when useful features are rare and weak. Proceedings of the National Academy of Sciences, 106(22):8859–8864, 2009.DOI
  20. [20]Jiashun Jin and Wanjie Wang. Influential features pca for high dimensional clustering. The Annals of Statistics, pages 2323–2359, 2016.DOI
  21. [21]Jiashun Jin, Zheng Tracy Ke, and Wanjie Wang. Phase transitions for high dimensional clustering and related problems. The Annals of Statistics, 45(5):2151–2189, 2017.
  22. [22]Alon Kipnis. Unification of rare and weak multiple testing models using moderate deviations analysis and log-chisquared p-values. Statistica Sinica, 35:1155–1181, 2025.
  23. [23]Bartosz Krawczyk. Learning from imbalanced data: open challenges and future directions. Progress in artificial intelligence, 5(4):221–232, 2016.DOI
  24. [24]William H. Kruskal and W. Allen Wallis. Use of ranks in one-criterion variance analysis. Journal of the American Statistical Association, 47(260):583–621, 1952.DOI
  25. [25]Erich L Lehmann and Joseph P Romano. Testing statistical hypotheses. Springer Science & Business Media, 2006.
  26. [26]Markus A. Loeffler, Jing Hu, Marcus Kirchner, Xiaoyu Wei, Yue Xiao, Thomas Albrecht, Carolina De La Torre, Carsten Sticht, et al. miRNA profiling of biliary intraepithelial neoplasia reveals stepwise tumorigenesis in distal cholangiocarcinoma via the miR-451a/ATF2 axis. The Journal of Pathology, 252(3):239–251, 2020.DOI
  27. [27]Bruno Loureiro, Gabriele Sicuro, Cédric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborová. Learning gaussian mixtures with generalized linear models: Precise asymptotics in high-dimensions. Advances in Neural Information Processing Systems, 34:10144–10157, 2021.
  28. [28]Chen Ma, Wanjie Wang, and Shuhao Fan. i-if-learn: Iterative feature selection and unsupervised learning for high-dimensional complex data. arXiv preprint arXiv:2603.24025, 2026.arxiv.org/abs/2603.24025
  29. [29]Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, and Ankur Moitra. Optimality and sub-optimality of PCA I: Spiked random matrix models. The Annals of Statistics, 46(5):2416–2451, 2018. doi: 10.1214/17-AOS1625.DOI
  30. [30]Ivo V Stoepker, Rui M Castro, Ery Arias-Castro, and Edwin van den Heuvel. Anomaly detection for a large number of streams: A permutation-based higher criticism approach. Journal of the American Statistical Association, 119(545):461–474, 2024.
  31. [31]Manish Sud, Eoin Fahy, Dawn Cotter, Kenan Azam, Ilango Vadivelu, Charles Burant, Arthur Edison, Oliver Fiehn, Richard Higashi, K. Sreekumaran Nair, Susan Sumner, and Shankar Subramaniam. Metabolomics Workbench: An international repository for metabolomics data and metadata, metabolite standards, protocols, tutorials and training, and analysis tools. Nucleic Acids Research, 44(D1):D463–D470, 2016. doi: 10.1093/nar/gkv1042.DOI
  32. [32]Christos Thrampoulidis, Samet Oymak, and Mahdi Soltanolkotabi. Theoretical insights into multiclass classification: A high-dimensional asymptotic view. Advances in Neural Information Processing Systems, 33:8907–8920, 2020.arxiv.org/abs/2011.07729
  33. [33]Nicolas Verzelen and Ery Arias-Castro. Detection and feature selection in sparse mixture models. Annals of Statistics, 45(5):1920–1950, 2017. doi: 10.1214/16-AOS1513. URL https://hal.inrae.fr/hal-02624460.DOI

Paper details

vlnc:W_2c8h5em7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents