Regularized nonsmooth Newton method for multi-class support vector machines

Multi-class classification is an important and on-going research subject in machine learning. Recently, the nu-K-SVCR method was proposed by the authors for multi-class classification. As many optimization problems have to be solved in multi-class classification, it is extremely important to develop an algorithm that can solve those optimization problems efficiently. In this article, the optimization problem in the nu-K-SVCR method is reformulated as an affine box constrained variational inequality problem with a positive semi-definite matrix, and a regularized version of the nonsmooth Newton method that uses the D-gap function as a merit function is applied to solve the resulting problems. The proposed algorithm fully exploits the typical feature of the nu-K-SVCR method, which enables us to reduce the size of Newton equations significantly. This indicates that the algorithm can be implemented efficiently in practice. The preliminary numerical experiments on benchmark data sets show that the proposed method is considerably faster than the standard Matlab routine used in the original nu-K-SVCR method.