CS Paper Radar

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

Gabriel Moryoussef, Alon Kipnis

cs.LG stat.MLmath.ST ·submitted 2026-11-01 22:19 UTC · v1
top venue

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.

Comment
Accepted at NeurIPS 2026. 43 pages, including references and supplementary material

Closest papers

Nearest neighbours by meaning across the whole index.

Random Feature Pruning for Multi-Class Classification

cs.LG ·2026-10-10 ·Mohammad Amin Omidi, Babak Seyfe, Shahrokh Valaee
theorycode/data similarity 0.58
Abstract · 43 Pages, 6 Figures

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.

0.45

A Canary in the Neural Mine: Catching an Image Classifier's Silent, Confident Failures

cs.CV cs.AI ·2026-10-19 ·Wonseok Shin, Songkuk Kim
similarity 0.53
Abstract

Deployed vision models auto-accept confident predictions, so high-confidence errors propagate silently. Maximum Softmax Probability (MSP), the standard failure predictor, has a structural blind spot: as a scalar read from the classifier head, it is first-order blind to feature variation orthogonal to its confidence gradient. Through a factorial analysis of feature-space detectors, we identify a conditional-redundancy principle explaining why they fail to complement MSP: the class-separability geometry they measure is already encoded in MSP and collapses under fusion. The signal that survives is class-conditional typicality on the off-manifold residual---and because this residual's distribution varies by backbone, from near-Gaussian to heavy-tailed, it must be estimated non-parametrically. We instantiate these findings as CANARY, a training-free detector that computes a per-class kNN distance on the PCA residual of the penultimate feature, percentile-calibrates it on validation data, and fuses it with MSP through a single validation-tuned weight. CANARY's benefit follows a headroom law: gains grow as baseline MSP quality falls, so a single clean-validation number forecasts the improvement. With every parameter selected on in-distribution data alone, CANARY matches or improves 382 of 385 shift cells (e-AURC; 379 on AUROC) across five backbones, with worst-case regression within seed noise ($-0.0002$ AUROC) and the largest gains on natural distribution shifts (ImageNet-A/R, ObjectNet)---where deployed models are most exposed.

0.24

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

cs.LG stat.MLstat.APstat.ME ·2026-10-07 ·Samuel Gruffaz, Muhammad Fawad, Jaakko Nevalainen
similarity 0.53
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.

0.28

Density-Ratio Rescoring for Imbalanced Classification Using Raking Duals and Classifier Scores

cs.LG stat.ML ·2026-09-20 ·Dongha Kim, Seunghwan Park
survey similarity 0.53
Abstract · 38 pages, 12 figures; includes all appendices. Updated title and competing-interest disclosure; corrected reference ordering. Results unchan…

Density-Ratio Rescoring (DRR) augments a classifier trained at the original class prior with a survey-raking dual score. Raking reweights the majority sample to match minority feature moments within a tolerance. DRR marginally standardizes the dual and base scores and combines them with a fixed weight of one half, using the fitted dual directly for prediction without resampling or refitting the base classifier. Under exact population matching and a correctly specified log-linear tilt model, the dual equals the log density ratio up to an additive constant. A class-separation analysis characterizes the signal strength and correlation conditions under which fusion improves separation under common within-class covariance. On 24 tabular benchmarks, evaluated over 30 trials and five base learners, DRR at the D=128 random-feature setting improves average precision over the standardized base on every dataset, with a mean gain of 0.034. It exceeds the shared-dual raking-and-relabeling resampler on 22 of 24 datasets, with a mean gain of $0.092$, and on all eight one-versus-rest tasks of a shared gene-expression cohort. These results demonstrate the effectiveness of using raking duals as reusable scores for improving rare-class ranking while retaining classifiers trained at the original prior.

0.32

Detection and Classification in Latent Spaces: High-Dimensional Analysis and Validation

cs.LG stat.ML ·2026-11-13 ·Enis Chenchene, Anil S. Baslamisli, Paolo Braca
similarity 0.53
Abstract

Foundation models produce high-dimensional latent representations in which suitably designed statistical decision rules can be effective yet analytically tractable. We study such detectors in the high-dimensional regime, where latent dimension and training sample size grow proportionally. For linear and quadratic statistics, we derive explicit large-deviation characterizations of false-alarm and miss-detection performance under the Neyman-Pearson paradigm, and show how the binary analysis extends to multi-class classification. The resulting error probabilities and corresponding decay rates exhibit non-monotonic dependence on the shape parameter, including double-descent and, in some regimes, multiple-descent. Experiments on vision, text, and audio datasets using modern foundation models show close agreement between theoretical predictions and empirical performance. In particular, the proposed framework allows us to set a prescribed false-alarm level and accurately predict the corresponding miss-detection probability. Overall, our results provide a theoretically grounded and interpretable framework with competitive empirical performance across different modalities.

0.24

Comparing Classification and Feature Learning by Analyzing Their Loss Functions in Normalized Spaces with Different Scale Factors

cs.LG cs.CV ·2026-11-05 ·Qiufu Li, Huibin Xiao, Linlin Shen, Weijia Fan, Xi Jia +1 more
similarity 0.53
Abstract

Classification and feature learning are two closely interrelated fundamental tasks. Feature learning in supervised settings is typically achieved by training classification models, under the common assumption that higher classification accuracy implies better feature quality. In this paper, we first point out that classification accuracy reflects the sample-wise local properties of a model on a dataset, whereas feature learning aims to learn features with good dataset-level global properties, such as intra-class compactness and inter-class separability. From the first principle of feature learning, we redesign the binary cross-entropy (BCE) loss, a counterpart of the cross-entropy (CE) loss used in classification. Then, in normalized feature space, we analyze the minima of the BCE and CE losses and show that both can lead to neural collapse, where sample features from different classes become maximally compact and maximally separated. More importantly, by investigating the convergence behaviors of the two losses as the scale factor $γ$ varies in the normalized space, we reveal how classification accuracy and feature quality change differently across spaces of different sizes. Under a fixed training strategy, a very large $γ$ achieves perfect classification accuracy but slows convergence toward the ideal feature geometry, whereas a very small $γ$ makes classification highly sensitive to small perturbations. A moderate $γ$ is therefore necessary for simultaneously achieving reliable classification and well-structured features. Extensive experiments validate these findings and demonstrate that BCE loss exhibits advantages in long-tail and open-set recognitions, as it better aligns with the global requirements of feature learning.

0.27

Cross-Prompt Inference Mitigates Rare-Class Suppression in Imbalanced VLM Finetuning

cs.CV ·2026-10-15 ·Emanuel Ben Baruch, Sivan Biham, Alon Shoshan, Yochai Zvik, Avi Ben-Cohen
similarity 0.52
Abstract

When a vision-language model is finetuned on class-imbalanced data, rare-class recall can fall well below the model's own zero-shot performance. In this regime, we uncover a surprising matched-prompt penalty whereby the standard choice of reusing the descriptive finetuning prompt at inference can yield lower rare-class recall than using a different descriptive prompt. We call this inference-time strategy cross-prompt inference. We evaluate diverse VLMs across six datasets and find that cross-prompt inference consistently recovers rare-class recall, with varying trade-offs in frequent-class recall. The effect reflects a train-eval prompt interaction rather than prompt quality alone, and does not arise with non-descriptive prompt changes. It is strongest when imbalance and visual confusability produce substantial rare-class suppression, and is weak or absent when such suppression does not occur. Using Tuning Contribution (TuCo), which decomposes a model's computation into pretrained and finetuning parts, we find that cross-prompt inference reduces reliance on finetuning-induced computation and shifts the model toward its pretrained component. Reducing that finetuning contribution also substantially reduces the cross-prompt advantage. These results show that rare-class knowledge suppressed by imbalanced finetuning can remain accessible under a different inference prompt.

0.21

Feature Normalization under Finite Training Budgets

cs.LG stat.MLmath.OC ·2026-10-12 ·Johan Larsson
similarity 0.52
Abstract · 45 pages

Standardizing a rare feature can help stochastic gradient descent learn its effect within a finite budget, but it also changes the noise cost of learning. We characterize the lowest rare-subgroup risks attainable by standardized and unscaled training when each chooses a nonnegative constant learning rate and a deterministic stopping time under the same observation cap. For two independent binary features, we derive both optimized risks as prevalence vanishes while the expected number of rare observations remains finite. Uniform control over rates and stopping times reduces each limiting oracle to a scalar minimization. With positive noise, the preferred scaling changes exactly once as we move signal to the rare feature while the limiting risk at initialization stays fixed and positive. The formulas also explain how noise and budget affect the comparison. Separate finite-prevalence bounds favor standardization on a rare-dominant signal family and unscaled training on a common-dominant family. The results concern final iterates with population preprocessing and fresh observations. Exact-moment searches assess the approximation at finite prevalence. In a controlled study, both orderings persist under observation reuse, estimated preprocessing, and intercept fitting when tuning choices are fixed before evaluation. Selecting a predictor after observing training can reverse an ordering, even when selection uses exact population risk.

0.34