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

This paper considers a class of feature selecting support vector machines (SVMs) based on Lq-norm regularization, where q∈(0,1). The standard SVM [Vapnik, V., 1995. The Nature of Statistical Learning Theory. Springer, NY.] minimizes the hinge loss function subject to the L2-norm penalty. Recently, L1-norm SVM (L1-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. L0-norm penalization would result in more powerful sparsification, but exact solution is NP-hard. This raises the question of whether fractional-norm (Lq for q between 0 and 1) penalization can yield benefits over the existing L1, and approximated L0 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 L1-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 L1-SVM, and recent approximated L0-SVM approaches.