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


* Both authors contributed equally.


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.


[paper] [arXiv] [HAL] [ICML talk]


    author      = {Osokin, Anton and Alayrac, Jean-Baptiste and Lukasewitz, Isabella and Dokania, Puneet K. and Lacoste-Julien, Simon},
    title       = {Minding the Gaps for Block {F}rank-{W}olfe Optimization of Structured {SVM}s},
    booktitle   = {Proceedings of The 33rd International Conference on Machine Learning (ICML)},
    year        = {2016}


[github] [zip, 200 Kb]



The original OCR dataset for Optical Character Recognition is available here.
Run download_ocr.m to download and see demo_ocr.m for an example of usage.


The original CoNLL dataset for the task of text chunking is available here.
For convenience, we provide the CoNLL dataset converted to our format: CONLL.zip [5 Mb].
Run download_conll.m to download and see demo_conll.m for an example of usage.


The original HorseSeg dataset for binary semantic image segmentation is available on its website. Dataset consists of annotations HDSeg.tar [350 Mb] and images under the ImageNet license. Follow the instructions of README in HDSeg.tar to get the HorseSeg images. Precomputed oversegmentation are available here: data.tar [5.3 Gb].

For convenience, we provide the HorseSeg datasets converted to our format (does not contain original images): Run download_horseSeg.m to download and see demo_horseSeg.m for an example of usage.


The original Leeds Sports Pose (LSP) dataset for the task of human pose estimation is available here. The pretrained CNN of Chen & Yuille (2014) is available here.
For convenience, we provide the LSP dataset converted to our format. We provide the following files: Run download_LSP.m to download and see demo_LSP.m for an example of usage.

Results of ICML 2016 paper

For comparisons, we provide some results of our ICML 2016 paper: results_icml2016.zip [10 Mb] and results_regPath_icml2016.zip [2 Mb]. The plotting scripts are provided here.


This work was partially supported by the MSR-Inria Joint Center and a Google Research Award.

Copyright Notice

The documents contained in these directories are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright.