Online) Subgradient Methods for Structured Prediction

By Nathan D. Ratliff, J. Bagnell, Martin A. Zinkevich. 2007

179 citations recorded by the source corpus.

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs (2016, methodology): “In the literature, multiple optimization methods have been applied to tackle this problem, including cutting-plane methods (Tsochantaridis et al., 2005; Joachims et al., 2009) and stochastic subgradient methods (Ratliff et al., 2007), among others.”
Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, methodology): “call to the so-called maximization oracle on each iteration, basic stochastic subgradient methods are still widely used for training structural SVMs (Ratliff et al., 2007; Shalev-Shwartz et al., 2010a).”
A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning (2010, methodology): “The k output binary variable ŷk = I(w k x + bk > 0), where wk, bk optimizes the SVM objective with regularizer λ = 10−4 using stochastic gradient descent (Ratliff et al., 2007; Bottou, 2009).”
Jointly Learning to Parse and Perceive: Connecting Natural Language to the Physical World (2013, methodology): “We optimize this objective using the stochastic subgradient method (Ratliff et al., 2006).”
Fastfood: Approximate Kernel Expansions in Loglinear Time (2014, methodology): “Specifically, whenever the kernels are invariant under the action of a symmetry group, we can use the eigenfunctions of its representation to diagonalize the kernel.”
Learning-Based Single-Document Summarization with Compression and Anaphoricity Constraints (2016, methodology): “Our system and models are publicly available at http://nlp.cs.berkeley.edu”
Slow Learners are Fast (2009, background): “This occurs, for instance, in the case of conditional random fields [15, 18], in planning [14], and in ranking [19].”
A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method (2012, background): “Our main motivating example is the support vector machine (SVM) and its structured prediction extensions [5, 6, 7], where the pairs (xt, yt) for t > 1 are independent and identically distributed and f(w) = E`(y, w>x) + μ2‖w‖ 2, where `(y, u) is a Lipschitz-continuous convex loss function (with respe”
Imitation learning for locomotion and manipulation (2007, methodology): “In [5], a simple but effective subgradient method was developed for optimizing the upper bound given in Eqn.”
CHOMP: Gradient optimization techniques for efficient motion planning (2009, background): “We first note that under these conditions, the overall CHOMP objective function is strongly convex [22]– that is, it can be lower-bounded over the entire region by a quadratic with curvature A.”
Better Word Representations with Recursive Neural Networks for Morphology (2013, methodology): “(3) is not differentiable, we use the subgradient method (Ratliff et al., 2007) to estimate the objective gradient as:”
Contextual classification with functional Max-Margin Markov Networks (2009, methodology): “[19] provided an unconstrained formulation of the max-margin criteria described by Taskar et al.”
Strong supervision from weak annotation: Interactive training of deformable part models (2011, methodology): “The index vp encodes the view/aspect of a part and is implemented using a mixture model, with different appearance templates and spatial parameters for each vp [28].”
Learning to search: Functional gradient techniques for imitation learning (2009, methodology): “…from the behavior we desire (and is agnostic as to whether the demonstrating agent is truly trying to minimize a reward function in an MDP), provides approximation and regret (Ratliff et al., 2007a) guarantees on the resulting solutions, and admits a particular class of non-linear loss functions.”
A multi-plane block-coordinate frank-wolfe algorithm for training structural SVMs with a costly max-oracle (2014, background): “Computing the value of Hi(w), or the label that realizes this value, requires solving an optimization problem over the label set.”
A Sequential Dual Method for Structural SVMs (2011, methodology): “Comparison of SDM with the cutting-plane method and the SGD method will then be presented.”
Cutting-plane training of structural SVMs (2009, methodology): “Recently, subgradient methods and their online variants ( Ratliff et al, 2007 ) have also been proposed to solve the optimization problem in maxmargin structured prediction.”
Parsing with Compositional Vector Grammars (2013, methodology): “This max-margin, structureprediction objective (Taskar et al., 2004; Ratliff et al., 2007; Socher et al., 2011b) trains the CVG so that the highest scoring tree will be the correct tree: gθ(xi) = yi and its score will be larger up to a margin to other possible trees ŷ ∈ Y(xi):”
Recursive deep learning for natural language processing and computer vision (2014, methodology): “Therefore, I generalize gradient ascent via the subgradient method (Ratliff et al., 2007) which computes a gradient-like direction.”