Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs

Anton Osokin, Jean-Baptiste Alayrac, Isabella Lukasewitz, Puneet Dokania, Simon Lacoste-Julien
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:593-602, 2016.

Abstract

In this paper, we propose several improvements on the block-coordinate Frank-Wolfe (BCFW) algorithm from Lacoste-Julien et al. (2013) recently used to optimize the structured support vector machine (SSVM) objective in the context of structured prediction, though it has wider applications. The key intuition behind our improvements is that the estimates of block gaps maintained by BCFW reveal the block suboptimality that can be used as an *adaptive* criterion. First, we sample objects at each iteration of BCFW in an adaptive non-uniform way via gap-based sampling. Second, we incorporate pairwise and away-step variants of Frank-Wolfe into the block-coordinate setting. Third, we cache oracle calls with a cache-hit criterion based on the block gaps. Fourth, we provide the first method to compute an approximate regularization path for SSVM. Finally, we provide an exhaustive empirical evaluation of all our methods on four structured prediction datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-osokin16, title = {Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs}, author = {Osokin, Anton and Alayrac, Jean-Baptiste and Lukasewitz, Isabella and Dokania, Puneet and Lacoste-Julien, Simon}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {593--602}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/osokin16.pdf}, url = {https://proceedings.mlr.press/v48/osokin16.html}, abstract = {In this paper, we propose several improvements on the block-coordinate Frank-Wolfe (BCFW) algorithm from Lacoste-Julien et al. (2013) recently used to optimize the structured support vector machine (SSVM) objective in the context of structured prediction, though it has wider applications. The key intuition behind our improvements is that the estimates of block gaps maintained by BCFW reveal the block suboptimality that can be used as an *adaptive* criterion. First, we sample objects at each iteration of BCFW in an adaptive non-uniform way via gap-based sampling. Second, we incorporate pairwise and away-step variants of Frank-Wolfe into the block-coordinate setting. Third, we cache oracle calls with a cache-hit criterion based on the block gaps. Fourth, we provide the first method to compute an approximate regularization path for SSVM. Finally, we provide an exhaustive empirical evaluation of all our methods on four structured prediction datasets.} }
Endnote
%0 Conference Paper %T Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs %A Anton Osokin %A Jean-Baptiste Alayrac %A Isabella Lukasewitz %A Puneet Dokania %A Simon Lacoste-Julien %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-osokin16 %I PMLR %P 593--602 %U https://proceedings.mlr.press/v48/osokin16.html %V 48 %X In this paper, we propose several improvements on the block-coordinate Frank-Wolfe (BCFW) algorithm from Lacoste-Julien et al. (2013) recently used to optimize the structured support vector machine (SSVM) objective in the context of structured prediction, though it has wider applications. The key intuition behind our improvements is that the estimates of block gaps maintained by BCFW reveal the block suboptimality that can be used as an *adaptive* criterion. First, we sample objects at each iteration of BCFW in an adaptive non-uniform way via gap-based sampling. Second, we incorporate pairwise and away-step variants of Frank-Wolfe into the block-coordinate setting. Third, we cache oracle calls with a cache-hit criterion based on the block gaps. Fourth, we provide the first method to compute an approximate regularization path for SSVM. Finally, we provide an exhaustive empirical evaluation of all our methods on four structured prediction datasets.
RIS
TY - CPAPER TI - Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs AU - Anton Osokin AU - Jean-Baptiste Alayrac AU - Isabella Lukasewitz AU - Puneet Dokania AU - Simon Lacoste-Julien BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-osokin16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 593 EP - 602 L1 - http://proceedings.mlr.press/v48/osokin16.pdf UR - https://proceedings.mlr.press/v48/osokin16.html AB - In this paper, we propose several improvements on the block-coordinate Frank-Wolfe (BCFW) algorithm from Lacoste-Julien et al. (2013) recently used to optimize the structured support vector machine (SSVM) objective in the context of structured prediction, though it has wider applications. The key intuition behind our improvements is that the estimates of block gaps maintained by BCFW reveal the block suboptimality that can be used as an *adaptive* criterion. First, we sample objects at each iteration of BCFW in an adaptive non-uniform way via gap-based sampling. Second, we incorporate pairwise and away-step variants of Frank-Wolfe into the block-coordinate setting. Third, we cache oracle calls with a cache-hit criterion based on the block gaps. Fourth, we provide the first method to compute an approximate regularization path for SSVM. Finally, we provide an exhaustive empirical evaluation of all our methods on four structured prediction datasets. ER -
APA
Osokin, A., Alayrac, J., Lukasewitz, I., Dokania, P. & Lacoste-Julien, S.. (2016). Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:593-602 Available from https://proceedings.mlr.press/v48/osokin16.html.

Related Material