The Use of Preconditioning for Training Support Vector Machines

Abstract

Since the introduction of support vector machines (SVMs), much work has been done to make these machines more efficient in classification. In our work, we incorporated the preconditioned conjugate gradient method (PCG) with an adaptive constraint reduction method developed in 2007 to improve the efficiency of training the SVM when using an Interior-Point Method. We reduced the computational effort in assembling the matrix of normal equations by excluding unnecessary constraints. By using PCG and refactoring the preconditioner only when necessary, we also reduced the time to solve the system of normal equations. We also compared two methods to update the preconditioner. Both methods consider the two most recent diagonal matrices in the normal equations. The first method chooses the indices to be updated based on the difference between the diagonal elements while the second method chooses based on the ratio of these elements. Promising numerical results for dense matrix problems are reported.