stat.MLNov 10, 2026

Outliers and the Hard-Margin Linear SVM in High-Dimension, Low-Sample-Size Settings

Authors: Yugo Nakayama

Organizations: Independent researcher

Abstract

We study how outliers affect the hard-margin linear support vector machine when the dimension grows while the sample sizes remain fixed. For one-sided contamination, the centered Gram matrix converges to a constant inlier block plus an outlier-diagonal component, and the limiting dual problem has a closed-form solution. All outliers act through one effective distance. This representation yields explicit thresholds for loss of inlier support, margin shrinkage. intercept displacement, and asymptotic misclassification. We then treat contamination in both classes. The limiting intercept is the multiplier of the class-balance constraint, and the two classes pull it in opposite directions. Consequently, at most one class can collapse or be asymptotically misclassified, whereas symmetric contamination leaves the limiting discriminant function unchanged even though the margin shrinks. Seven numerical experiments verify the dual allocation, phase transitions, and discriminant limits.

Figures & tables

Explore similar work

Sep 30, 2026

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

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.
Jun 4, 2026

Robust and sparse support vector machine via hybrid truncated loss for supervised classification

The support vector machine (SVM) is a widely used classifier, but choosing an appropriate loss function remains difficult. Convex losses such as the hinge loss and least-squares loss are sensitive to outliers, while bounded non-convex losses often lead to high computational cost. To address this, we propose a hybrid truncated loss function (LhtL_{\mathrm{ht}}) that is both sparse and bounded, and build the LhtL_{\mathrm{ht}}-SVM model for single-view classification. We introduce the P-stationary point and use it to establish the first-order necessary and sufficient optimality conditions. Based on these conditions, we design an alternating direction method of multipliers with a working-set strategy that reduces computational cost and achieves global convergence. We further extend LhtL_{\mathrm{ht}}-SVM to multi-view learning by adding structural information and view weights, resulting in MvLhtL_{\mathrm{ht}}-SVM, which follows both the consensus and complementarity principles. Experiments on synthetic, real-world, and image datasets show that LhtL_{\mathrm{ht}}-SVM achieves higher accuracy with fewer support vectors and better noise robustness than five single-view methods, while MvLhtL_{\mathrm{ht}}-SVM outperforms six multi-view methods in accuracy, precision, recall, and F1-score.
Sep 15, 2026

Sharp margin-based generalization bounds for realizable SVM

Let the exact homogeneous hard-margin support vector machine be trained on mm independent observations from a Borel probability law on a real Hilbert space. We prove that, with score zero counted as an error, there is a universal numerical constant CC such that \Pp(γm>0,\Risk(um)>Cm(Km+log⁡1δ))≤δ.\Pp\left( γ_m>0,\quad \Risk(u_m)> \frac{C}{m} \left( K_m+\log\frac1δ \right) \right) \le δ. Here γmγ_m is the empirical homogeneous margin, umu_m is the exact minimum-norm unit-margin separator, rmr_m is the largest training radius, and Km:=rm2\normum2=rm2/γm2K_m:=r_m^2\norm{u_m}^2=r_m^2/γ_m^2 on {γm>0}\{γ_m>0\}. The proof is driven by a deterministic deletion problem. Given vectors x1,…,xnx_1,\ldots,x_n in the unit ball, delete a set BB of constraints and let uBu_B be the closest point to the origin that satisfies every retained unit-margin constraint. Suppose that \normuB2≤k\norm{u_B}^2\le k and that every deleted vector has nonpositive score under uBu_B. We prove that a family of such deletion sets of cardinality qq has size at most exp⁡(8k+2q)\exp(8k+2q). The conceptual step is an exact identity obtained from the KKT representation of uBu_B. For a random deletion set, the identity converts the mean squared spread of the separators into a weighted sum of score deficits. It therefore forces a coordinate whose deletion status separates the two conditional means by a quantitatively large amount. Revealing that coordinate decreases the conditional separator variance enough to control the binary entropy of the split. An entropy induction gives the deletion count, and an exact factorial ghost-sample identity converts that count into the stated high-probability SVM bound.