Non-asymptotic Analysis of $\ell_1$-norm Support Vector Machines

Support vector machines (SVMs) with the <inline-formula> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math></inline-formula>-penalty became a standard tool in the analysis of high-dimensional classification problems with sparsity constraints in many applications, including bioinformatics and signal processing. We give non-asymptotic results on the performance of <inline-formula> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math></inline-formula>-SVM in identification of sparse classifiers. We show that an <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula>-dimensional <inline-formula> <tex-math notation="LaTeX">$s$ </tex-math></inline-formula>-sparse classification vector can be (with high probability) well approximated from only <inline-formula> <tex-math notation="LaTeX">$O(s\log (N))$ </tex-math></inline-formula> Gaussian trials. We derive similar estimates also in the presence of misclassifications and for the so-called doubly regularized SVM, which combines the <inline-formula> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math></inline-formula>- and the <inline-formula> <tex-math notation="LaTeX">$\ell _{2}$ </tex-math></inline-formula>-penalty. Similar bounds were obtained earlier in the analysis of LASSO and 1-Bit compressed sensing.