An exact solver for the Weston-Watkins SVM subproblem

Yutong Wang · Clay Scott


Keywords: [ Kernel Methods ] [ Algorithms ]

[ Abstract ]
[ Slides
[ Paper ]
[ Visit Poster at Spot B5 in Virtual World ] [ Visit Poster at Spot C6 in Virtual World ]
Wed 21 Jul 9 a.m. PDT — 11 a.m. PDT
Spotlight presentation: Kernel Methods
Wed 21 Jul 7 a.m. PDT — 8 a.m. PDT


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.

Chat is not available.