Successive overrelaxation for support vector machines

Successive overrelaxation (SOR) for symmetric linear complementarity proble ms and quadratic programs is used to train a support vector machine (SVM) f or discriminating between the elements of two massive datasets, each with m illions of points. Because SOR handles one point at a Lime, similar to Plat t's sequential minimal optimization (SMO) algorithm which handles two const raints at a time and Joachims' SVMlight which handles a small number of poi nts at a time, SOB can process very large datasets that need not reside in memory, The algorithm converges linearly to a solution. Encouraging numeric al results are presented on datasets with up to 10 000 000 points. Such mas sive discrimination problems cannot be processed by conventional linear or quadratic programming methods, and to our knowledge have not been solved by other methods. On smaller problems, SOB was faster than SVMlight and compa rable or faster than SMO.