On the Convergence of Hybrid Decomposition Methods for SVM Training

Area 09 – Ingegneria industriale e dell'informazione

Support Vector Machines (SVM) is a widely adopted technique both for classi¯cation and regression problems. Training of SVM requires to solve a linearly constrained convex quadratic problem. In real applications the number of training data may be very huge and the Hessian matrix cannot be stored. In order to take into account this issue a common strategy consists in using decomposition algorithms which at each iteration operate only on a small subset of variables, usually referred to as the working set. The convergence properties of a decomposition method strongly depend on the rule for selecting the working set. On the other hand training time can be significantly reduced by using a caching technique, that allocates some memory space to store the recently used columns of the Hessian matrix. In order to take into account both theoretical requirements and computational issues related to a caching technique, wepropose a hybrid decomposition algorithm model embedding the most violating pair rule and possibly any other working set selection rule. We prove the global convergence of the proposed hybrid algorithm model. Furthermore, we present two specific practical realizations of the general hybrid model where a caching strategy can be advantageously exploited.

SINTESI