Dual coordinate solvers for large-scale structural SVMs

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 [4, 15]; 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 series of recognition systems [19, 7, 21, 12] for articulated pose estimation, facial analysis, 3D object recognition, and action classification, all with publicly-available code. This writeup describes the solver in detail. Approach: Our approach is closely based on data-subsampling algorithms for collecting hard exam-ples [9, 10, 6], combined with the dual coordinate quadratic programming (QP) solver described in liblinea