CS Paper Radar

Multiclass Linear Perceptrons with Multiplicative Margins

Dmitri Rachkovskij, Evgeny Osipov, Olexander Volkov, Daswin De Silva, Denis Kleyko

cs.LG cs.NE ·submitted 2026-08-30 20:32 UTC · v1
published

Abstract

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.

Comment
38 figures
Journal ref
Neural Computation (2026) 38(4): 602-650
DOI
10.1162/NECO.a.1502

Closest papers

Nearest neighbours by meaning across the whole index.

Rationally Linearized MLPs

cs.LG ·2026-10-09 ·Arijit Sehanobish, Byeongchan Kim, Avinava Dubey, Min-hwan Oh, Krzysztof Choromanski
similarity 0.59
Abstract · Preprint. Comments welcome

We present Rationally Linearized Multilayer Perceptrons(RaLiMPs), a new approach to efficiently linearizing MLPs using low-degree rational approximations of standard activation functions. Inspired by polynomial-based MLP linearization, we show that rational approximations can provide accurate representations at substantially lower degree. RaLiMPs exploit these approximations to construct kernel representations with narrow bottlenecks, enabling efficient composition across MLP layers. We provide theoretical guarantees for the resulting approximation and evaluate RaLiMPs across applications ranging from implicit 3D models to large language models. Our experiments demonstrate favorable accuracy--efficiency tradeoffs, with RaLiMPs achieving competitive or improved accuracy while substantially reducing inference cost.

0.37

Using Set Learning to Improve Set-Valued Classifiers on Long-tailed Data

cs.LG cs.CV ·2026-10-20 ·Kevin Kasa, Scott C. Lowe, Graham W. Taylor
similarity 0.58
Abstract

Set-valued classification (SVC) offers a practical approach to communicating uncertainty while maintaining accuracy by predicting variable-sized sets per input rather than fixed-sized sets (e.g. top-1 or top-5). However, set-valued classifiers (SVCs) exhibit significantly degraded performance on long-tailed and imbalanced datasets, a setting for which they are ostensibly well-suited. This becomes apparent under macro-average evaluation, which weighs all classes equally. SVCs are typically formed during a post-hoc calibration stage, so little is known about how training dynamics affect their behaviour. In this work, we investigate how different neural network training strategies and loss functions impact downstream SVC performance on highly imbalanced data. In addition to methods such as label smoothing and class-balancing, we investigate whether loss functions that operate over sets of examples in a batch, rather than treating all examples as independent, lead to better downstream SVCs. We adapt the recently proposed odd-K-out (OKO) loss function, which learns from sets of training samples, improving its sample efficiency whilst introducing algorithmic modifications that reduce its computational overhead from 3.2x to just 1.36x that of standard cross-entropy training. Experiments on highly long-tailed datasets demonstrate our modified OKO approach significantly improves macro-accuracy across multiple SVC methods - including top-k, average-k, and conformal prediction - while maintaining competitive micro-accuracy. This improved performance on minority classes occurs without substantially increasing prediction set sizes, suggesting that carefully constructed set-based training can produce networks better suited to imbalanced data.

0.28

On the Two Faces of Adam in Separable Linear Classification

cs.LG ·2026-09-27 ·Chen Fan, Csaba Szepesvári
similarity 0.58
Abstract

We consider the behavior of deterministic, full-batch, bias-corrected Adam in separable linear classification with softmax parametrization under log-loss. In this setting, under a wide range of conditions Adam is known to approach max-norm-margin optimality when its stability constant $ε$ is zero, while with a positive $ε$, it is known to approach Euclidean-margin optimality. Our main contribution is the quantitative description of Adam's behavior for small fixed positive $ε$. We give sufficient conditions under which an Adam-trained classifier nearly maximizes the max-norm margin before the updates become gradient-like. We also show that the classifier reaches a fixed target Euclidean margin only much later. Specifically, we show that for polynomially decreasing stepsizes with exponent \(a\), where \(1/3<a<1\), the updates become approximately proportional to the negative gradient after $Θ(\log(1/ε)^{1/(1-a)})$ iterations. At that time, the classifier still nearly maximizes the max-norm margin. Reaching a fixed target Euclidean margin above that of every max-norm-optimal classifier, but below the optimum, is shown to require $ε^{-Θ(1)/(1-a)}$ iterations. Under inverse-linear stepsize decay (\(a=1\)), the update transition takes polynomially many iterations, whereas reaching the target margin takes exponentially many. Experiments support these predictions. The later change in the classifier can improve or worsen generalization after training error reaches zero, connecting the analysis to grokking and its reverse.

0.22

DAL: Dynamic Angular Loss for Imbalanced Medical Image Classification

cs.CV ·2026-11-18 ·Salman Mohammad, Furkan Kasım, Manuel Günther
publishedtheorycode/data similarity 0.58
Abstract · Accepted at the British Machine Vision Conference (BMVC) 2026. 18 pages, 5 figures, 4 tables. Code: https://github.com/msalman95/DA

Class imbalance remains a major obstacle in medical image classification, where rare but clinically important classes are often overshadowed by majority categories. Although current strategies for reducing bias, including angle-based softmax (ABS) losses, offer strong discriminative features, their behavior in settings with a small number of severely imbalanced classes remains insufficiently understood. Previous approaches that estimate the intrinsic parameters of ABS rely on the assumption of many classes, which does not hold in medical settings. We derive data-driven upper and lower bounds for the scale parameter and an upper bound for the angular margin using negative-angle statistics, and use these to drive a batch-adaptive angular margin (BAAM), which we combine with dynamically-weighted cross entropy (DWCE) to define our dynamic angular loss (DAL). Across four highly imbalanced medical image classification benchmarks spanning dermatology, ophthalmology, and gastrointestinal endoscopy, our method consistently achieves superior balanced accuracy and the lowest coefficient of variation of per-class recall. Although this entails a small performance reduction on majority classes, the gains on minority categories are substantial, yielding a reliable and equitable overall classifier. Our source code is available at: https://github.com/msalman95/DAL.

0.58

Classification with Abstention Under Class-Conditional Error Constraints

cs.LG stat.ML ·2026-09-18 ·Mohammadreza M. Kalan, Yuyang Deng, Sanaz Hamidi
similarity 0.57
Abstract

We study binary classification with abstention under separate class-conditional error constraints, with the objective of minimizing abstention while keeping both errors below prescribed thresholds. We characterize the distribution-free minimax rate of excess abstention risk, up to logarithmic factors, in terms of the complexity of the hypothesis class and the sample size. To make the framework amenable to computation with models such as neural networks, we introduce surrogate-loss formulations and derive finite-sample guarantees for excess surrogate ambiguity risk. We formulate the resulting learning task as a constrained optimization problem and characterize its computational complexity in the convex setting. Finally, we evaluate our approach on various datasets and compare its performance with a competing method for this problem.

0.37

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

cs.LG ·2026-08-14 ·Filippo Portera
theory similarity 0.56
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

Supervised Hebbian Class Networks: Learning Without Backpropagation

cs.LG ·2026-11-18 ·John Loverich
similarity 0.56
Abstract

This paper introduces Supervised Hebbian Class Networks as a method for training multi- layer perceptrons and convolutional networks without gradient calculations or backpropa- gation. Each neuron in a learned layer is assigned a class, while connections follow the usual fully connected or convolutional pattern. The method combines a class-based supervision rule shared across layers with a Lion optimizer adapted to Hebbian activity products. All layers train together throughout the run, and their activities provide class predictions di- rectly, without a separately trained classifier. The experiments test the method on MNIST with a multilayer perceptron and on CIFAR-10 with a convolutional networ

0.25

Predicted Class Correction: Conformal Thresholds for Classes with No Calibration Data

cs.LG cs.CV ·2026-10-18 ·One Octadion, Novanto Yudistira, Yuta Nakashima
similarity 0.56
Abstract · 23 pages including supplementary material, 4 figures

Class-conditional conformal prediction calibrates a separate score threshold for every class and therefore requires labelled calibration examples of every class. In long-tailed deployments these are exactly what is missing: rare classes are left with few or no held-out examples, and existing methods are either undefined for them or fall back to the shared marginal threshold. We ask whether the per-class correction can instead be predicted from descriptors of the class that require no labels at all. We propose Predicted Class Correction (PCC), which regresses the offset between the per-class and the marginal conformal quantile on geometric descriptors of the classifier head, shrinks the prediction by a scalar selected on the labelled classes, and refits a single marginal offset. The descriptors depend only on the model's weights, so a class with zero calibration examples still receives its own threshold, and since only one scalar is calibrated, split conformal's marginal guarantee is retained. On ImageNet, PCC improves worst-class coverage on such classes by 0.058 [0.006, 0.110] at matched average set size, 42% of an oracle that sees the test labels. Of eight baselines on the same splits, six change the statistic by exactly zero and the best reaches 0.016 with an interval containing zero, so PCC is the only one distinguishable from no improvement; the gain persists with only 100 labelled classes out of 1000. A second finding concerns evaluation: worst-class coverage becomes unmeasurable before it becomes unachievable. Below roughly 35 test examples per class no improvement can be shown even for an oracle, so a null result there reflects the evaluation set, not the method. Restricting evaluation above this depth recovers a significant improvement on Pl@ntNet-300K, where the effect had appeared absent.

0.17