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

By Anton Osokin, Jean-Baptiste Alayrac, Isabella Lukasewitz, Puneet Kumar Dokania, Simon Lacoste-Julien. 2016

70 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

End-to-End Learning of Visual Representations From Uncurated Instructional Videos (2019, neutral): “Niter do i← sample from distribution proportional to g [26] ∇(i)f(Yt)← 1 N (Y (i) t −XWt) # Block gradient Ymin ← argminx∈Y(i)〈∇(i)f(Yt), x〉F # Linear oracle D ← Ymin − Y (i) gi ← −〈D,∇(i)f(Yt)〉F # Block gap γ ← min(1, gi 1 N 〈D,D−X(i)P D〉F ) # Line-search Wt+1←Wt + γP D # W update”
Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields (2017, methodology): “lmost proportionally to the norm of the dual ascent direction. Yet as the norm is not separable over cliques, this scheme cannot be applied to CRFs. Inspired by the approach followed by Osokin et al. [9] to improve the Block-Coordinate Frank-Wolfe algorithm [6], we propose to bias sampling towards e”
Weakly-Supervised Learning of Visual Relations (2017, methodology): “We optimize the cost in (3) on pairs of objects in the training set using a variant of the Frank-Wolfe al-gorithm [33, 36].”
Learning from Video and Text via Large-Scale Discriminative Clustering (2017, unknown): “Niter do i← sample from distribution proportional to g [27] ∇(i)f(Yt)← 1 N (Y (i) t −XWt) # Block gradient Ymin ← argminx∈Y(i)〈∇(i)f(Yt), x〉F # Linear oracle D ← Ymin − Y (i) gi ← −〈D,∇(i)f(Yt)〉F # Block gap γ ← min(1, gi 1 N 〈D,D−X(i)P (i)D〉F ) # Line-search Wt+1 ←Wt + γP D # W update”
Learning from Narrated Instruction Videos (2015, methodology): “Note that the discriminative clustering algorithm could be further scaled-up to 1000 s of videos using the Block-Coordinate Frank-Wolfe algorithm [20], [31] as has been recently shown in [25].”
Approximate Steepest Coordinate Descent (2017, background): “…in (Shalev-Shwartz & Zhang, 2013; Friedman et al., 2007; 2010; Shalev-Shwartz & Tewari, 2011) uniform sampling (UCD) is used, whereas other papers propose adaptive sampling strategies that change over time (Papa et al., 2015; Csiba et al., 2015; Osokin et al., 2016; Perekrestenko et al., 2017).”
Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets (2018, methodology): “For these reasons, FW optimization has drawn growing interest in recent years, especially in matrix completion, structural SVM, computer vision, sparse PCA, metric learning, and many other settings (Jaggi, Sulovsk, and others 2010; Lacoste-Julien et al. 2013; Osokin et al. 2016; Wang et al. 2016; Ch”
Faster Coordinate Descent via Adaptive Importance Sampling (2017, methodology): “However, our work generalizes the gap-based adaptive criterion of [Osokin et al., 2016] in a nontrivial way to a broader convex optimization template of the following form: where A is the data matrix, f is a smooth convex function, and each g i is a general convex function.”
Lazifying Conditional Gradient Algorithms (2016, methodology): “, 2009)) as well as the Block-Coordinate Frank-Wolfe algorithm in (Shah et al., 2015; Osokin et al., 2016).”
A flexible model for training action localization with varying levels of supervision (2018, methodology): “We use optimal line search and we sample videos according to the block gap values [30] which speeds up convergence in practice.”
A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition (2020, unknown): “, [18], [22], [24], [39] and references therein).”
Dual Decomposed Learning with Factorwise Oracle for Structural SVM of Large Output Domain (2016, methodology): “In practice, a Block-Coordinate Frank-Wolfe (BCFW) method has much faster convergence than Frank-Wolfe method (Algorithm 2) [13, 9], but proving linear convergence for BCFW is also much more difficult [13], which prohibits its use in our analysis.”