CS Paper Radar

A Fast Algorithm for the Familywise Loss

Leelavathi Raja, Amirreza Eshraghi, Vinay Prabhakar, Mark Blacher, Han Bao, Yutong Wang

cs.LG ·submitted 2026-11-14 01:16 UTC · v1
theory

Abstract

The familywise (FW) loss for multiclass classification, introduced by Duchi, Ruan, and Khosravi, achieves universal equivalence to the 0-1 loss, and thus has stronger theoretical properties than cross entropy (CE). Prior work, however, left open whether FW is as computationally efficient as CE. First, on the theoretical side, we prove that the FW gradient can be computed in $O(K)$ time, where $K$ is the number of classes. Second, on the practical side, we develop optimized kernels for computing the forward and backward passes of FW which outperform CE in terms of speed on both CPU and GPU.

Closest papers

Nearest neighbours by meaning across the whole index.

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.58
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

Convex losses and their applications to SVM, SVR, and Shallow Neural Networks

cs.LG ·2026-08-14 ·Filippo Portera
theory similarity 0.57
Abstract · Further experiments

We propose multiple new convex losses for SVM and Neural Networks, applied to binary classification tasks. While there are practical limitations in exploiting them with the dual SVM models, we are able to use them with SVM primal formulation and Neural Networks. In detail, the primal SVM problem with the modified losses has been solved with the Particle Swarm Optimization algorithm. We prove that the proposed losses are a generalization of the standard loss, and we experiment them with several small data-sets. This preliminary study shows that using pattern correlations inside the loss function could in theory enhance the generalization performances on some data-sets. To evaluate the performance of each loss, we adopt a Nested Cross-Validation procedure. Results show that generalization measures are the same with or without the new losses.

0.04

Neural Collapse on Imbalanced Datasets and Open-Set Scenario

cs.LG ·2026-11-05 ·Qiufu Li, Huibing Xiao, Linlin Shen, Yongdong Huang
theory similarity 0.56
Abstract

Neural collapse (NC) describes the elegant geometric structure that sample features and classifier vectors exhibit when a classification model's loss reaches its minimum. Class imbalance, however, generally distorts standard NC. In this paper, we theoretically reformulate NC on imbalanced datasets and in open-set settings. Our analysis is based on an optimization problem over class-wise averaged losses, rather than the global averaged losses used in prior NC studies. We prove that when class-wise averaged losses attain their minima, standard NC is achieved on balanced or imbalanced datasets, for both cross-entropy (CE) and binary cross-entropy (BCE) losses. We further extend the analysis to an open-set-inspired scenario, where some classes contain no training samples yet are still assigned classifier vectors in the losses. We find that in this scenario, when class-wise averaged losses reach their minima, standard NC still emerges on the known classes with training samples, while the classifier vectors of unknown classes without training samples overlap with each other and become orthogonal to those of the known classes. Finally, we analyze Softmax- and Sigmoid-based contrastive losses re-balanced by inverse sample frequency, proving that at their minima on balanced or imbalanced datasets, sample features of different classes likewise form standard NC.

0.26

The Implicit Bias of Hyperbolic Representation Learning for Multiclass Data: A Busemann Risk Perspective

cs.LG ·2026-10-05 ·Xingrun Li, Sho Kuno, Yusuke Mukuta, Xin Yang, Tatsuya Harada
top venuetheory similarity 0.55
Abstract · Accepted at NeurIPS 2026 as a Spotlight

We study the implicit bias of Riemannian gradient flow for hyperbolic multiclass classification with fixed class prototypes in hyperbolic space $\mathbb H^n$. Our framework accommodates general permutation invariant relative margin (PERM) losses, a class that includes cross entropy and other standard multiclass losses. Our analysis is based on a decomposition: at large radius, the distance to each prototype splits into a radial term and a direction dependent term described by the Busemann function. This yields two main results. First, we prove a radial dichotomy: the sign of a drift coefficient $μ$ determines whether the radius is pushed toward the ideal boundary or back toward the interior; if the positive drift persists, then $r(t)=\tfrac12\log t+O(1)$, while persistent negative drift returns the trajectory to the large radius threshold in finite time. Second, we show that large-radius directions can approach critical points of the Busemann risk on $\partial\mathbb H^n$, even during radial return. These results provide a rigorous large-radius perspective on two phenomena we refer to as boundary saturation and near-boundary clustering in hyperbolic representation learning.

0.42

Multiclass Linear Perceptrons with Multiplicative Margins

cs.LG cs.NE ·2026-08-30 ·Dmitri Rachkovskij, Evgeny Osipov, Olexander Volkov, Daswin De Silva, Denis Kleyko
published similarity 0.54
Abstract · 38 figures

This paper introduces a family of multiclass linear Perceptron classifiers with a multiplicative margin mechanism (MMPerc), as an alternative to standard margin-free and additive margin Perceptrons. The multiplicative formulation enforces classification confidence by requiring the true class score to exceed that of competing classes by a specified fraction of itself, rather than by a fixed additive threshold. This avoids dependence on score magnitudes arising from varied norms of data and class weight vectors. We propose several architectural and algorithmic variants of MMPerc, derive associated loss functions and mistake bounds for both linearly separable and non-separable data, and analyze key design considerations, including bias, margin threshold selection, and training modes. Extensive experiments on synthetic and real datasets show that MMPerc classifiers typically outperform the standard Perceptron, as well as classic baselines such as Support Vector Machines and Ridge classifiers. Owing to their simplicity, minimalistic design, and computational efficiency, MMPerc classifiers are promising candidates for conventional machine learning tasks, linear evaluation of Deep Neural Networks, integration with Hyperdimensional Computing / Vector Symbolic Architecture representations, and deployment in resource-constrained applications.

0.39

SGD in Multiclass Logistic Regression: Sequential Learning and Scaling Laws

cs.LG stat.ML ·2026-09-07 ·Konstantinos Christopher Tsiolis, Denny Wu, Christos Thrampoulidis, Murat A. Erdogdu
top venuehot direction similarity 0.53
Abstract · NeurIPS 2026 Camera-Ready

We study the training dynamics of multiclass logistic regression on high-dimensional mixture models with a large number of classes and establish precise scaling laws governing the cross-entropy risk under gradient-based optimization. We show that learning proceeds sequentially across classes, from most to least frequent. When the class priors follow a power law distribution, the risk dynamics decompose into three phases: an initial plateau until the first class is learned, a power-law decay regime during which sequential learning occurs, and a final convergence regime. We then analyze how model capacity interacts with optimization under a fixed compute budget. When the effective dimension is restricted via projection onto leading principal components, the risk decomposes into a capacity term (a power law in the retained dimension) and an optimization term (a power law in training time). Optimizing this tradeoff yields a compute-optimal scaling law for logistic regression, with explicit prescriptions for model size and training time as functions of compute. These results extend theoretical scaling laws from linear regression to multiclass classification, while connecting to empirical scaling laws observed in large-scale neural networks.

0.51

Rethinking Class Imbalance for Single-Cell Foundation Models: A Systematic Benchmark Across Architectures and Long-Tail Loss Functions

cs.LG ·2026-09-20 ·Zeyu Dong, Jiahui Zhong
benchmark similarity 0.53
Abstract

Single-cell foundation models (scGPT, scBERT, Geneformer) achieve cell-type classification accuracy up to 97.5% in our experiments, yet this aggregate accuracy can mask systematic failure on rare, often disease-relevant cell populations that long-tail loss functions are widely assumed to address. We present a systematic benchmark of six long-tail loss functions (cross-entropy, weighted CE, class-balanced loss, focal loss, LDAM, logit-adjusted softmax) across three architectures and three datasets (Multiple Sclerosis, Zheng68K, human Pancreas), totaling 162 controlled training runs (3 backbones x 3 datasets x 6 losses x 3 seeds). The gap between overall accuracy, Macro-F1, and rare-class recall under plain cross-entropy is consistent across all nine (architecture, dataset) settings, driven by dataset structure rather than pretraining. Rare-class failure itself splits into two regimes with distinct embedding-geometry signatures, visible before any loss is chosen: some classes are recoverable by the right loss, while others retain linear separability yet are absorbed into unrelated classes' neighborhoods under every evaluated loss and architecture. Among the recoverable classes, the efficacy of reweighting is predicted by a class's absolute training-set size, rather than its share of the dataset or the dataset's overall imbalance ratio. Class-balanced loss and LDAM are the most consistent choices across all nine settings, while logit adjustment trades rare-class precision for recall rather than improving both. Our results give both a reusable benchmark and mechanism-grounded practical guidelines for combining foundation models with imbalanced biological data.

0.36

Informative Label Missingness in Multiclass Classification Information Geometry and Excess Risk

cs.LG stat.ML ·2026-08-31 ·Fariborz Setoudehtazang, Geoffrey J. McLachlan
similarity 0.53
Abstract

Informative label missingness can change the usual efficiency ordering between completely and partially labelled classifiers because the pattern of missing labels may itself carry information about the classification model. We develop a general likelihood-based theory for this phenomenon in parametric multiclass classification. An efficient-information decomposition separates information lost through unavailable class memberships from information contributed by the missing-label mechanism. We then derive a quadratic expansion of plug-in excess risk over the active pairwise faces of the multiclass Bayes boundary, showing that classification efficiency depends on how information gains and losses align with directions that perturb the decision boundary. This yields a classification-weighted generalized-eigenvalue criterion under which informative partial classification may have smaller asymptotic classification risk without globally dominating complete classification in Fisher information. Near missing completely at random, with the marginal missing-label proportion fixed, redistribution of missing labels changes lost class-label information at first order, whereas efficient information from the missingness pattern appears only at second order. Three-class quadratic discriminant calculations, finite-sample experiments, and a semi-synthetic multiclass application illustrate the resulting regime-dependent behaviour.

0.56