  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 gapbased 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.
