Non-asymptotic Analysis of _1-norm Support Vector Machines

Abstract

Support Vector Machines (SVM) with _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 _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(d)) Gaussian trials. The methods used in the proof include concentration of measure and probability in Banach spaces.

Tasks

Reproductions