Block-Coordinate Frank-Wolfe Optimization for Structural SVMs

By Simon Lacoste-Julien, Martin Jaggi, Mark W. Schmidt, Patrick A. Pletscher. 2012

387 citations recorded by the source corpus.

Reference EPFL-ARTICLE-229252 URL: http://arxiv.org/abs/1207.4747 Record created on 2017-06-21, modified on 2017-06-21

Subfields: Artificial Intelligence, Computational Mechanics, 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 Computational Mechanics

In Optimization & Training

Citations in the corpus

End-to-End Learning of Visual Representations From Uncurated Instructional Videos (2019, methodology): “Our solution builds on the Block-Coordinate FrankWolfe (BCFW) [21] algorithm and extends it with a smart block-dependent update procedure as described next.”
Structured Convolutional Kernel Networks for Airline Crew Scheduling (2021, methodology): “To train CRFs, we either use a Structured SVM solver using BCFW algorithm (Lacoste-Julien et al., 2013), or a stochastic optimization algorithm using SDCA (Le Priol et al., 2018).”
Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, methodology): “Moreover, for some highly structured polytopes such as those appearing in alignment constraints (Alayrac et al., 2016) or Structured SVM (Lacoste-Julien et al., 2013), there exists a fast and elegant dynamic programming algorithm to compute the LMO , while there is no known practical algorithm to…”
Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields (2017, methodology): “Our proposed gap sampling strategy is similar to the one from Osokin et al. (2016) in the context of SDCA applied to the structured SVM objec-tive, which reduces to the block-coordinate Frank-Wolfe (BCFW) algorithm (Lacoste-Julien et al., 2013).”
Frank-Wolfe Algorithms for Saddle Point Problems (2016, methodology): “As some of the algorithms only work on the primal and to make our result comparable to Lacoste-Julien et al. (2013), we choose to plot the primal suboptimality error p ( w t ) − p ∗ for the diﬀerent algorithms in Figure 1e and 1f (the α t iterates for the SP approaches are thus ignored in this…”
Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs (2016, methodology): “In what follows, we use the modified induction technique of (Lacoste-Julien et al., 2013, Proof of Theorem C.1).”
Barrier Frank-Wolfe for Marginal Inference (2015, methodology): “This is a generalization of the technique used in Teo et al. (2007) (also used in the context of Frank-Wolfe in the proof of Theorem C.4 in Lacoste-Julien et al. (2013)).”
Minimizing finite sums with the stochastic average gradient (2013, background): “Related results also appear in [11,29] showing the advantage of stochastic optimization strategies over deterministic optimization strategies in the context of certain dual optimization problems.”
Introduction to Online Convex Optimization (2016, methodology): “Due to the applicability of the FW algorithm to large-scale constrained problems, it has been a method of choice in recent machine learning applications, to name a few: [61, 69, 60, 39, 50, 58, 98, 16, 104, 46, 47, 18].”
On the Global Linear Convergence of Frank-Wolfe Optimization Variants (2015, background): “Optimization over the marginal polytope appears for example in structured SVM learning [21] and variational inference [18].”
Stochastic Optimization with Importance Sampling for Regularized Loss Minimization (2014, methodology): “Similarly for prox-SDCA, the traditional approach such as Stochastic Dual Coordinate Ascent (SDCA) (Shalev-Shwartz & Zhang, 2013) picks a coordinate to update by sampling the training data uniformly at random (Luo & Tseng, 1992; Mangasarian & Musicant, 1999; Hsieh et al., 2008; Shalev-Shwartz & Tewa”
Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields (2015, methodology): “2 The scheme for SAG proposed by Schmidt et al. [2013, Section 5.5] uses a fairly complicated adaptive NUS scheme and step-size, but the key ingredient is estimating each constant L i using Algorithm 2.”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, methodology): “Recently, [11] derived a stochastic coordinate ascent for structural SVM based on the FrankWolfe algorithm.”
A novel Frank-Wolfe algorithm. Analysis and applications to large-scale SVM training (2013, methodology): “In [39] the authors adapted the FW method to train SVMs with structured outputs like graphs and other combinatorial objects [60, 3], obtaining an algorithm which outperforms competing structural SVM solvers4.”
FASOLE: Fast Algorithm for Structured Output LEarning (2014, positive): “Unlike the SGD which optimizes the primal objective, the recently proposed Sequential Dual Method for Structural SVMs (SDM) [1] and the Block-Coordinate Frank-Wolfe (BCFW) [9] are on-line solvers maximizing the Lagrange dual of the SOSVM problem.”
Learning from Video and Text via Large-Scale Discriminative Clustering (2017, methodology): “In the following, we explain how to convert such form of weak supervision into a set of constraints on latent Algorithm 1 BCFW for Discriminative Clustering [2] Initiate Y 0 , P : + γD # Block update end for variables corresponding to the names and actions of people.”