CS Paper Radar

High-Dimensional Statistical Inference for Sparse Support Vector Machines

Peng Zeng, Hanwen Huang

cs.LG stat.MLstat.ME ·submitted 2026-10-06 13:40 UTC · v1

Abstract

Using a replica-symmetric high-dimensional characterization, we develop an inferential framework for sparse support vector machines when the sample size and number of features grow proportionally. The main challenge is the nonsmooth hinge loss, which prevents direct application of debiasing arguments developed for smooth classification losses. We overcome this difficulty by representing the $L_1$-penalized support vector machine (SVM) as a linear program and identifying the hinge-loss subgradient through its dual variables. This yields a computationally accessible debiased estimator whose coordinates are asymptotically Gaussian under the proportional asymptotic regime. The resulting distributional characterization provides confidence intervals and hypothesis tests for individual features and enables false-discovery-rate-controlled variable selection. Extensive simulations examine calibration, power, and variable-selection performance under a range of covariance structures, including strongly correlated designs. An analysis of high-dimensional breast cancer gene-expression data illustrates how the proposed inference can distinguish statistically significant features from variables selected by the original sparse SVM.

Comment
7 figures

Closest papers

Nearest neighbours by meaning across the whole index.

A Nonconvex Framework for Joint Sparse Sample Weighting and Parameter Estimation

cs.LG math.OCstat.ML ·2026-10-25 ·Hassan Nojavan, Chul Moon, Miju Ahn
benchmark similarity 0.62
Abstract · 40 pages, 5 figures

We propose a joint sparse sample weighting and parameter estimation (SWAPE) framework that jointly optimizes model parameters and sample weights to train a model while simultaneously assigning an individual weight to each training data point. Our framework accommodates several widely used loss functions for the model parameters, including convex, weakly convex, and difference-of-convex loss, and weakly convex sparsity functions to control the complexity of the sample weights. To solve the resulting bivariate problem, we propose an alternating minimization method in which the subproblems for updating the model parameters and weights are each approximated using majorize-minimize techniques. We provide several approximation methods for the loss functions considered in this paper, and show the overall algorithm's convergence. Numerical experiments on various learning tasks and data anomaly settings demonstrate the effectiveness of the proposed framework in minimizing the impact of undesirable data points compared to benchmark methods.

0.16

Scale-invariant Optimal Sampling for Rare-events Data with Sparse Models

cs.LG stat.ML ·2026-08-23 ·Jing Wang, HaiYing Wang, Qiang Zhang, Hao Helen Zhang
similarity 0.61
Abstract

Subsampling is effective in tackling computational challenges for massive data with rare events. Overly aggressive subsampling may adversely affect estimation efficiency, and optimal subsampling is essential to mitigate the information loss. However, existing optimal subsampling probabilities depend on data scales, and some scaling transformations may result in inefficient subsamples. This problem is more significant when there are inactive features, because their influence on the subsampling probabilities can be arbitrarily magnified by inappropriate scaling transformations. We tackle this challenge and introduce a scale-invariant optimal subsampling function in the context of sparse models, where inactive features are commonly assumed. Instead of focusing on estimating model parameters, we define an optimal subsampling function to minimize the prediction error, using adaptive lasso to outline the estimation procedure and study its theoretical guarantee. We first introduce the adaptive lasso estimator for rare-events data and establish its oracle properties, thereby validating the use of subsampling. Then we derive a scale-invariant optimal subsampling function that minimizes the prediction error of the inverse probability weighted (IPW) adaptive lasso. Finally, we present an estimator based on the maximum sampled conditional likelihood (MSCL) to further improve the estimation efficiency. We conduct numerical experiments using both simulated and real-world data sets to demonstrate the performance of the proposed methods.

0.22

Support Vector Machines Directly Minimise KL Divergence

cs.LG stat.ML ·2026-11-03 ·Ivan Silajev
similarity 0.61
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

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

Sparse and robust geometric twin support vector machine via asymmetric RoBoSS loss function

cs.LG ·2026-08-12 ·Kai Qi, Xinji Huang, Hongchun Wang
similarity 0.60
Abstract

In real-world scenarios, the training data usually contains redundant features, label noise and feature noise, which provide severe challenges for the efficiency of machine learning methods. Since standard support vector machine (SVM) adopts $l_2$-norm penalty and hinge loss function, it lacks the ability of selecting significant features and is sensitive to noise. To address these issues, this paper proposes a novel asymmetric, robust, bounded, sparse and smooth (aR) loss function for $l_1$-norm penalized geometric twin SVM (aRSGTSVM) to handle classification and regression tasks. The $l_1$-norm penalty can achieve the feature selection. The proposed aR loss function can not only effectively mitigate the impact of label noise, but also significantly enhance the stability to resampling noise, i.e., the zero-mean feature noise around the boundary hyperplanes. Furthermore, a statistical analysis of the robustness of aRSGTSVM was also conducted using the influence function. Since aRSGTSVM involves nonconvex and nonsmooth optimization, we develop a fast and stable proximal gradient descent based solving algorithm. Compared with related state-of-the-art methods, experimental results demonstrate the superiority of the proposed aRSGTSVM on both synthetic and UCI datasets. Furthermore, we apply aRSGTSVM to index tracking tasks, where results for tracking the different indices in the China stock market show that it can achieve satisfactory performance.

0.04

Revisited Support Vector Machines: A Unified Joint Optimization Framework with Nyström Approximation for Scalable Adaptive Learning

cs.LG ·2026-10-11 ·Nassou Gongon Benjamin, Noulapeu Ngaffo, Patrick Njionou Sadjang
similarity 0.60
Abstract

The theoretical elegance of Support Vector Machines (SVMs), grounded in statistical learning theory, establishes them as a reference for robust classification. However, in the era of Big Data, classical SVMs face two major bottlenecks: the prohibitive cubic complexity $\mathcal{O}(N^3)$ of training and the rigidity of static kernels. Traditional methodologies treat kernel selection as a discrete, "brute-force" GridSearch problem, effectively decoupling the learning of data representation from the optimization of the decision boundary. This paper proposes a paradigm shift with a so-called "Revisited SVM", a unified framework that recasts the learning process as a continuous %bi-level joint optimization problem. We derive a novel objective function $J(α, θ)$ that allows for the simultaneous optimization of dual Lagrange multipliers and kernel hyper-parameters. To solve this challenging non-convex problem efficiently, we introduce a hybrid Block Coordinate Ascent (BCA) algorithm, tightly integrated with Nyström-based low-rank approximation, which drastically reduces computational complexity to $\mathcal{O}(Nm)$. Extensive experiments conducted across four heterogeneous domains (Bioinformatics, Finance, Cybersecurity, and Computer Vision) demonstrate that our approach not only matches but often exceeds exhaustive GridSearch accuracy, while delivering training speedups of up to 100x. Notably, on the complex NSL-KDD intrusion detection dataset, our adaptive kernel approach achieves 96.25\% accuracy compared to a mere 50\% for standard baselines, proving its unique ability to model complex non-linear manifolds in high-dimensional spaces. We validate our results using rigorous statistical tests and provide a theoretical convergence analysis of the proposed algorithm.

0.18

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

Asymptotic Properties of Support Vector Machines in High-Dimension, Low-Sample-Size Settings under a Spiked Model

cs.LG stat.ML ·2026-09-30 ·Yugo Nakayama
unusual similarity 0.59
Abstract

In this paper, we consider asymptotic properties of the support vector machine (SVM) in high-dimension, low-sample-size (HDLSS) settings under a spiked model. The existing theory of the SVM in the HDLSS context relies on the geometric representation of HDLSS data, which requires that the eigenvalues of the covariance matrices are not dominant. We first show that the geometric representation does not hold under the spiked model. We show that the Gram matrix of HDLSS data converges in distribution to a random matrix, namely, the HDLSS data converge to a random configuration in a finite-dimensional space whose dimension is given by the number of the spikes. We show that the misclassification rates of the SVM do not tend to zero, that is, the SVM does not hold the consistency property. We also show that the bias-corrected SVM (BC-SVM) does not give preferable performance in this setting because the bias term itself should be modified. In order to overcome such difficulties, we propose a spike-corrected SVM (SC-SVM). We show that the SC-SVM holds the consistency property when the sample size goes to infinity, and that the growth of the sample size is essential in the sense that any projection-based procedure fails when the sample size is fixed. Finally, we check the performance of the classifiers by numerical simulations.

0.24