This paper considers convex quadratic programs associated with the training of
support vector machines (SVM). Exploiting the special structure of the SVM problem a
new type of active set method with long cycles and stable rank-one-updates is proposed
and tested (CMU: cycling method with updates). The structure of the problem allows
for a repeated simple increase of the set of inactive constraints while controlling its size.
This is followed by minimization steps with cheap updates of a matrix factorization.
A widely used approach for solving SVM problems is the alternating direction
method SMO, a method that is very efficient for low accuracy. The new active set
approach allows for higher accuracy results at moderate computational cost. To relate
both approaches, the effect of the accuracy on the running time and on the predictive
quality of the SVM is compared with some numerical examples. A surprising result of
the numerical examples is that only a very small number of cycles (each consisting of
less than 2n steps) was used for CMU.
Article