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; 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.
