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

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

arXiv commentAppears in Proceedings of the 33rd International Conference on Machine Learning (ICML 2016). 31 pages

References in corpus (2)

• Piecewise linear regularized solution paths
• Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functions

Cited by in corpus (13)

• Randomized Block Frank-Wolfe for Convergent Large-Scale Learning
• Frank-Wolfe Algorithms for Saddle Point Problems
• Weakly-supervised learning of visual relations
• Curvature of Feasible Sets in Offline and Online Optimization
• Adaptive Sketch-and-Project Methods for Solving Linear Systems
• Trusting SVM for Piecewise Linear CNNs
• Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem
• Lazifying Conditional Gradient Algorithms
• Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity
• Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport
• One-sided Frank-Wolfe algorithms for saddle problems
• Marginal Weighted Maximum Log-likelihood for Efficient Learning of Perturb-and-Map models
• Safe Adaptive Importance Sampling