Solution of massive support vector machine problems
Abstract
We investigate the use of interior-point and semismooth methods for solving
quadratic programming problems with a small number of linear constraints,
where the quadratic term consists of a low-rank update to a positive
semi-definite matrix. Several formulations of the support vector machine
fit into this category. An interesting feature of these particular problems
is the volume of data, which can lead to quadratic programs with between 10
and 100 million variables and, if written explicitly, a dense $Q$ matrix.
Our codes are based on OOQP, an object-oriented interior-point code, with the
linear algebra specialized for the support vector machine application.
For the targeted massive problems, all of the data is stored out of core and
we overlap computation and I/O to reduce overhead. Results are reported for
several linear support vector machine formulations demonstrating that the
methods are reliable and scalable and comparing the two approaches.