An Exact Solver for the Weston-Watkins SVM Subproblem
This work addresses a computational bottleneck in multiclass SVM training, offering incremental improvements for machine learning practitioners.
The paper tackles the subproblem in Weston-Watkins SVM solvers by developing an exact algorithm using a novel reparametrization, resulting in significant speed-ups for large numbers of classes and enabling a proof of linear convergence.
Recent empirical evidence suggests that the Weston-Watkins support vector machine is among the best performing multiclass extensions of the binary SVM. Current state-of-the-art solvers repeatedly solve a particular subproblem approximately using an iterative strategy. In this work, we propose an algorithm that solves the subproblem exactly using a novel reparametrization of the Weston-Watkins dual problem. For linear WW-SVMs, our solver shows significant speed-up over the state-of-the-art solver when the number of classes is large. Our exact subproblem solver also allows us to prove linear convergence of the overall solver.