Interior point methods for massive support vector machines. Data Mining Institute

We investigate the use of interior point 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 vol-ume of data, which can lead to quadratic programs with between 10 and 100 million variables and a dense Q matrix. We use OOQP, an object-oriented interior point code, to solve these problem because it allows us to easily tailor the required linear algebra to the application. Our linear algebra implementation uses a proximal point modification to the under-lying algorithm, and exploits the Sherman-Morrison-Woodbury formula and the Schur complement to facilitate efficient linear system solution. Since we target massive problems, 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 the reliability and scalability of the method