Dual coordinate solvers for large-scale structural SVMs
This work addresses scalability issues for machine learning practitioners dealing with large datasets, though it is incremental as it builds on existing SVM methods.
The authors tackled the problem of training linear SVMs on large datasets that do not fit in memory, by developing an algorithm that efficiently handles out-of-core data while maintaining stability similar to batch methods. They applied this solver to tasks like pose estimation and object recognition, providing publicly-available code.
This manuscript describes a method for training linear SVMs (including binary SVMs, SVM regression, and structural SVMs) from large, out-of-core training datasets. Current strategies for large-scale learning fall into one of two camps; batch algorithms which solve the learning problem given a finite datasets, and online algorithms which can process out-of-core datasets. The former typically requires datasets small enough to fit in memory. The latter is often phrased as a stochastic optimization problem; such algorithms enjoy strong theoretical properties but often require manual tuned annealing schedules, and may converge slowly for problems with large output spaces (e.g., structural SVMs). We discuss an algorithm for an "intermediate" regime in which the data is too large to fit in memory, but the active constraints (support vectors) are small enough to remain in memory. In this case, one can design rather efficient learning algorithms that are as stable as batch algorithms, but capable of processing out-of-core datasets. We have developed such a MATLAB-based solver and used it to train a collection of recognition systems for articulated pose estimation, facial analysis, 3D object recognition, and action classification, all with publicly-available code. This writeup describes the solver in detail.