Block-Coordinate Frank-Wolfe Optimization for Structural SVMs

Simon Lacoste-Julien, Martin Jaggi, Mark Schmidt, Patrick Pletscher
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(1):53-61, 2013.

Abstract

We propose a randomized block-coordinate variant of the classic Frank-Wolfe algorithm for convex optimization with block-separable constraints. Despite its lower iteration cost, we show that it achieves a similar convergence rate in duality gap as the full Frank-Wolfe algorithm. We also show that, when applied to the dual structural support vector machine (SVM) objective, this yields an online algorithm that has the same low iteration complexity as primal stochastic subgradient methods. However, unlike stochastic subgradient methods, the block-coordinate Frank-Wolfe algorithm allows us to compute the optimal step-size and yields a computable duality gap guarantee. Our experiments indicate that this simple algorithm outperforms competing structural SVM solvers.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-lacoste-julien13, title = {Block-Coordinate {Frank-Wolfe} Optimization for Structural {SVMs}}, author = {Lacoste-Julien, Simon and Jaggi, Martin and Schmidt, Mark and Pletscher, Patrick}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {53--61}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/lacoste-julien13.pdf}, url = {https://proceedings.mlr.press/v28/lacoste-julien13.html}, abstract = {We propose a randomized block-coordinate variant of the classic Frank-Wolfe algorithm for convex optimization with block-separable constraints. Despite its lower iteration cost, we show that it achieves a similar convergence rate in duality gap as the full Frank-Wolfe algorithm. We also show that, when applied to the dual structural support vector machine (SVM) objective, this yields an online algorithm that has the same low iteration complexity as primal stochastic subgradient methods. However, unlike stochastic subgradient methods, the block-coordinate Frank-Wolfe algorithm allows us to compute the optimal step-size and yields a computable duality gap guarantee. Our experiments indicate that this simple algorithm outperforms competing structural SVM solvers.} }
Endnote
%0 Conference Paper %T Block-Coordinate Frank-Wolfe Optimization for Structural SVMs %A Simon Lacoste-Julien %A Martin Jaggi %A Mark Schmidt %A Patrick Pletscher %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-lacoste-julien13 %I PMLR %P 53--61 %U https://proceedings.mlr.press/v28/lacoste-julien13.html %V 28 %N 1 %X We propose a randomized block-coordinate variant of the classic Frank-Wolfe algorithm for convex optimization with block-separable constraints. Despite its lower iteration cost, we show that it achieves a similar convergence rate in duality gap as the full Frank-Wolfe algorithm. We also show that, when applied to the dual structural support vector machine (SVM) objective, this yields an online algorithm that has the same low iteration complexity as primal stochastic subgradient methods. However, unlike stochastic subgradient methods, the block-coordinate Frank-Wolfe algorithm allows us to compute the optimal step-size and yields a computable duality gap guarantee. Our experiments indicate that this simple algorithm outperforms competing structural SVM solvers.
RIS
TY - CPAPER TI - Block-Coordinate Frank-Wolfe Optimization for Structural SVMs AU - Simon Lacoste-Julien AU - Martin Jaggi AU - Mark Schmidt AU - Patrick Pletscher BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/02/13 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-lacoste-julien13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 1 SP - 53 EP - 61 L1 - http://proceedings.mlr.press/v28/lacoste-julien13.pdf UR - https://proceedings.mlr.press/v28/lacoste-julien13.html AB - We propose a randomized block-coordinate variant of the classic Frank-Wolfe algorithm for convex optimization with block-separable constraints. Despite its lower iteration cost, we show that it achieves a similar convergence rate in duality gap as the full Frank-Wolfe algorithm. We also show that, when applied to the dual structural support vector machine (SVM) objective, this yields an online algorithm that has the same low iteration complexity as primal stochastic subgradient methods. However, unlike stochastic subgradient methods, the block-coordinate Frank-Wolfe algorithm allows us to compute the optimal step-size and yields a computable duality gap guarantee. Our experiments indicate that this simple algorithm outperforms competing structural SVM solvers. ER -
APA
Lacoste-Julien, S., Jaggi, M., Schmidt, M. & Pletscher, P.. (2013). Block-Coordinate Frank-Wolfe Optimization for Structural SVMs. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(1):53-61 Available from https://proceedings.mlr.press/v28/lacoste-julien13.html.

Related Material