CS Paper Radar

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

Filippo Portera

cs.LG ·submitted 2026-08-14 13:21 UTC · v2
theory

Abstract

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.

Comment
Further experiments

Closest papers

Nearest neighbours by meaning across the whole index.

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

Support Vector Machines Directly Minimise KL Divergence

cs.LG stat.ML ·2026-11-03 ·Ivan Silajev
similarity 0.59
Abstract · 14 pages, 1 table, v2 includes section on optimal solution

Support vector machines (SVMs) are fundamentally grounded in geometric margin maximisation and currently lack a mainstream probabilistic interpretation. This keeps them theoretically isolated from probabilistic machine learning models that are naturally comparable and combinable. In this paper, we bridge this gap by proving that the dual objectives of both support vector classification and support vector regression are exact, constrained Kullback-Leibler (KL) divergence minimisation tasks between two Gaussian measures. We further show that this same divergence formulation recovers the exact objective function for kernel ridge regression when domain constraints are removed and $L^2$ regularisation is applied. By demonstrating that SVM duals directly minimise relative entropy, our results provide a unified information-theoretic model for standard kernel machines and lay the foundation for unifying broader kernel-based algorithms under probability theory.

0.23

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

A Fast Algorithm for the Familywise Loss

cs.LG ·2026-11-14 ·Leelavathi Raja, Amirreza Eshraghi, Vinay Prabhakar, Mark Blacher, Han Bao +1 more
theory similarity 0.57
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.

0.24

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

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

Revisiting Thinning Methods for Kernel Learning Problems

cs.LG cs.AI ·2026-09-07 ·Blanca Cano-Camarero, Yago R. Aguado-Carrillo-de-Albornoz, Ángela Fernández-Pascual, José R. Dorronsoro
similarity 0.54
Abstract

Kernel methods are widely used because of their strong theoretical guarantees and empirical performance. However, their high computational cost limits their applicability to large-scale datasets. To address this shortcoming, several approaches use Maximum Mean Discrepancy to construct representative subsets that preserve the properties of the full dataset in a Reproducing Kernel Hilbert Space. We introduce Backward Kernel Herding, an algorithm that addresses this problem by iteratively removing points from the dataset, achieving results comparable to current state-of-the-art approaches while accelerating the subsampling process in realistic scenarios where the reduced size is less than half of the dataset. Moreover, we overcome a limitation of Kernel Thinning by proposing an extension that enables the construction of subsets of arbitrary size rather that restricting to successive halvings. Finally, we conduct an extensive experimental comparison focusing on the most relevant kernel learning procedures: Gaussian Processes and Kernel Support Vector Machines. The results show that Backward Kernel Herding consistently achieves competitive performance with the most favorable training-time efficiency, while the proposed Flexible Kernel Thinning frequently achieves the best predictive performance. These gains become especially pronounced for moderate compression ratios, highlighting the benefits of incorporating supervised information into the thinning process. In terms of memory consumption, Flexible Kernel Thinning is also competitive, whereas Backward Kernel Herding remains an alternative when computational efficiency is the primary objective. Overall, no single method dominates across all scenarios, underscoring the importance of selecting the reduction strategy according to the desired trade-off between predictive performance, training cost, and memory requirements.

0.19

Classification with Large-Step Gradient Descent: Unifying Self-Stabilization and Convergence Rates

cs.LG math.OC ·2026-11-12 ·Salma Tarmoun, Lachlan Ewen MacDonald, Konstantinos Emmanouilidis, Ziqing Xu, René Vidal
similarity 0.54
Abstract

Neural networks are often trained with gradient descent (GD) using step sizes that exceed classical stability thresholds, a regime where standard convergence theory no longer applies. Despite exhibiting non-monotonic loss and oscillatory dynamics, this regime frequently leads to faster convergence and better generalization. Existing theoretical perspectives offer complementary but incomplete insights: one identifies a self-stabilization mechanism that drives GD toward flat regions but does not yield convergence rates; another derives rigorous rates for specific losses but does not explain the underlying stabilization mechanism; and a third unifies these views for overparameterized least squares, but relies on the existence of a minimizer manifold, which is absent in classification settings. In this work, we extend this unified geometric perspective to exponential-tail losses, including logistic and cross-entropy losses in separable linear classification, where the loss infimum is not attained at any finite parameter. We identify a curvature-defined reference subspace that replaces the role of the minimizer manifold, yielding a coupled dynamical system in which orthogonal oscillations are damped by parallel progress along directions of decreasing sharpness. Under regularity conditions, which we verify for logistic and multiclass cross-entropy losses on symmetric data models, we derive explicit bounds for the iterates, not just the loss, covering both the unstable and stable regimes, and revealing a three-phase damping structure in the latter. Our analysis further uncovers a transient implicit bias induced by large step sizes: although GD converges asymptotically to the max-margin direction, large steps can leave persistent orthogonal residuals and, in certain geometries, amplify them, affecting finite-time alignment with the max-margin direction.

0.06