# Sparse SVM with Hard-Margin Loss: a Newton-Augmented Lagrangian Method in Reduced Dimensions

arXiv: https://arxiv.org/abs/2307.16281 · HTML: https://mlsanity.com/paper/2307.16281/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jul 2023.

## Built on by (most cited first, 2 of 2)

- [The kernel of graph indices for vector search](https://mlsanity.com/paper/2506.20584/) (2025)
- [Local Duality for Sparse Support Vector Machines](https://mlsanity.com/paper/2601.20170/) (2026)

## Abstract (arXiv)

The hard margin loss function has been at the core of the support vector machine (SVM) research from the very beginning due to its generalization capability.On the other hand, the cardinality constraint has been widely used for feature selection, leading to sparse solutions. This paper studies the sparse SVM with the hard-margin loss (SSVM-HM) that integrates the virtues of both worlds. However, SSVM-HM is one of the most challenging models to solve. In this paper, we cast the problem as a composite optimization with the cardinality constraint. We characterize its local minimizers in terms of rm P-stationarity that well captures the combinatorial structure of the problem. We then propose an inexact proximal augmented Lagrangian method (iPAL). The different parts of the inexactness measurements from the rm P-stationarity are controlled at different scales in a way that the generated sequence converges both globally and at a linear rate. This matches the best convergence theory for composite optimization. To make iPAL practically efficient, we propose a gradient-Newton method in a subspace for the iPAL subproblem. This is accomplished by detecting active samples and features with the help of the proximal operator of the hard margin loss and the projection of cardinality constraint. Extensive numerical results on both simulated and real datasets demonstrate that the proposed method is fast, produces sparse solution of high accuracy, and can lead to effective reduction on active samples and features when compared with several leading solvers.