Non-asymptotic Analysis of $\ell_1$-norm Support Vector Machines
This provides non-asymptotic guarantees for sparse classification in applications like bioinformatics and signal processing, addressing a known bottleneck with incremental theoretical advancement.
The paper tackles the problem of analyzing the performance of ℓ₁-norm Support Vector Machines for identifying sparse classifiers in high-dimensional settings, showing that a d-dimensional s-sparse vector can be well approximated with high probability from only O(s log(d)) Gaussian trials.
Support Vector Machines (SVM) with $\ell_1$ penalty became a standard tool in analysis of highdimensional classification problems with sparsity constraints in many applications including bioinformatics and signal processing. Although SVM have been studied intensively in the literature, this paper has to our knowledge first non-asymptotic results on the performance of $\ell_1$-SVM in identification of sparse classifiers. We show that a $d$-dimensional $s$-sparse classification vector can be (with high probability) well approximated from only $O(s\log(d))$ Gaussian trials. The methods used in the proof include concentration of measure and probability in Banach spaces.