An exact solver for the Weston-Watkins SVM subproblem

Yutong Wang, Clayton Scott
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:10894-10904, 2021.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-wang21u, title = {An exact solver for the Weston-Watkins SVM subproblem}, author = {Wang, Yutong and Scott, Clayton}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {10894--10904}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/wang21u/wang21u.pdf}, url = {https://proceedings.mlr.press/v139/wang21u.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T An exact solver for the Weston-Watkins SVM subproblem %A Yutong Wang %A Clayton Scott %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-wang21u %I PMLR %P 10894--10904 %U https://proceedings.mlr.press/v139/wang21u.html %V 139 %X 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.
APA
Wang, Y. & Scott, C.. (2021). An exact solver for the Weston-Watkins SVM subproblem. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:10894-10904 Available from https://proceedings.mlr.press/v139/wang21u.html.

Related Material