Sparse high-dimensional fractional-norm support vector machine via DC programming.

Abstract: This paper considers a class of feature selecting support vector machines (SVMs) based on -norm regularization, where . The standard SVM [Vapnik, V., 1995. The Nature of Statistical Learning Theory. Springer, NY.] minimizes the hinge loss function subject to the -norm penalty. Recently, -norm SVM ( -SVM) [Bradley, P., Mangasarian, O., 1998. Feature selection via concave minimization and support vector machines. In: Machine Learning Proceedings of the Fifteenth International Conference (ICML98). Citeseer, pp. 82–90.] was suggested for feature selection and has gained great popularity since its introduction. -norm penalization would result in more powerful sparsification, but exact solution is NP-hard. This raises the question of whether fractional-norm ( for between 0 and 1) penalization can yield benefits over the existing , and approximated approaches for SVMs. The major obstacle to answering this is that the resulting objective functions are non-convex. This paper addresses the difficult optimization problems of fractional-norm SVM by introducing a new algorithm based on the Difference of Convex functions (DC) programming techniques [Pham Dinh, T., Le Thi, H., 1998. A DC optimization algorithm for solving the trust-region subproblem. SIAM J. Optim. 8 (2), 476–505. Le Thi, H., Pham Dinh, T., 2008. A continuous approach for the concave cost supply problem via DC programming and DCA. Discrete Appl. Math. 156 (3), 325–338.], which efficiently solves a reweighted -SVM problem at each iteration. Numerical results on seven real world biomedical datasets support the effectiveness of the proposed approach compared to other commonly-used sparse SVM methods, including -SVM, and recent approximated -SVM approaches. [Copyright &y& Elsevier]