A Suite of Simple Algorithms for Support Vector Machine Optimization
Recently Mangasarian and Musicant [1] suggested an interesting modification of the SVM objective with 2-norm loss, called the Lagrangian SVM (LSVM), that leads to a simple optimization algorithm. The LSVM algorithm is simple enough that it can applied even when the training size is large (millions of samples) and has been experimentally found to have generalization performance similar to standard SVMs [1]. This paper takes inspiration from [1] and develops a suite of simple algorithms for SVM optimization. The algorithms use the special structure of the SVM QP problem a suggest a set of solutions. Algorithms are developed for both 1-norm and 2-norm loss functions as well as for bias-regularization and fixed bias. The algorithm developed here for the special LSVM problem is more efficient than the one in [1]. In many applications the SVM QP problem is so large that the so-called kernel matrix cannot be stored efficiently. In such cases we suggest a novel lower-dimensional approximation of the kernel matrix. There are many criteria with respect to which these approximations can be obtained and we give a generic result on the influence of quality of the approximation of the kernel matrix on the quality of the solution to the original SVM optimization problem. A similar idea was proposed in Fine and Schienberg [2].