Exponentiated Gradient Algorithms for Conditional Random Fields and Max-Margin Markov Networks

By Michael Collins, Amir Globerson, Terry Koo, Xavier Carreras, Peter L. Bartlett. 2008

184 citations recorded by the source corpus.

Subfields: Artificial Intelligence, 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 Optimization & Training

Citations in the corpus

Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields (2017, methodology): “On the other hand, the online exponentiated gradient method (OEG) (Collins et al., 2008) and SAG are both members of a family of algorithms with cheap stochastic updates and linear convergence rates, and they have both been applied to the training of CRFs. They are called variance reduced algorithms”
Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, methodology): “In contrast, other approaches must use more expensive (and potentially intractable) oracles such as computing marginals over labels (Collins et al., 2008; Zhang et al., 2011) or doing a Bregman projection onto the space of structures (Taskar et al., 2006).”
Minimizing finite sums with the stochastic average gradient (2013, background): “Friedlander and Schmidt [2012] give conditions under which this strategy achieves the O(1/k) and O(ρ) convergence rates of FG methods.”
Stochastic dual coordinate ascent methods for regularized loss (2012, neutral): “For example, [2] analyzed an exponentiated gradient dual coordinate ascent algorithm.”
Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields (2015, methodology): “We also included the online exponentiated gradient ( OEG ) method [Collins et al., 2008], and we followed the heuristics in the author’s code.”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, background): “[3] but inmore restricted settings than the general problem considered in this paper.”
FASOLE: Fast Algorithm for Structured Output LEarning (2014, unknown): “We also refer to [9] which provides a thorough comparison showing that the BCFW consistently outperforms approximate on-line methods including the exponentiated gradient [11] and the stochastic sub-gradient method [14] hence these methods are excluded from our comparison.”
Hidden Part Models for Human Action Recognition: Probabilistic versus Max Margin (2011, background): “There is also work [38] showing that the dual optimization has a better convergence rate.”
Large-Scale Personalized Human Activity Recognition Using Online Multitask Learning (2013, background): “A typical convergent choice of learning rate can be found in [32]:”
Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms (2014, background): “, projecting onto the trace norm ball, onto base polytopes Fujishige & Isotani, 2011), and in some cases even computationally intractable (Collins et al., 2008).”
Steps Toward Deep Kernel Methods from Infinite Neural Networks (2015, background): “, with O(log(1/ )) updates to the elements α a dual exponentiated coordinate descent achieves an −optimal dual solution [7].”
Proximal Stochastic Dual Coordinate Ascent (2012, result): “Similar results can also be found in Collins et al. [2008], Le Roux et al. [2012], Shalev-Shwartz and Zhang [2012] but in more restricted settings than the general problem considered in this paper.”
A Sequential Dual Method for Structural SVMs (2011, methodology): “Gradient based online methods like stochastic gradient descent (SGD) and others [4, 20] can be used for solving the primal problem.”
Dual coordinate descent methods for logistic regression and maximum entropy models (2011, methodology): “Note that we follow Collins et al. (2008) to use w(α) in (41). To improve the convergence, Collins et al. (2008) adaptively adjust the learning rate ηi for each instance.”
A dual coordinate descent method for large-scale linear SVM (2008, methodology): “The setting is related to (Crammer & Singer, 2003; Collins et al., 2008).”
A Primal-Dual Message-Passing Algorithm for Approximated Large Scale Structured Prediction (2010, methodology): “The following duality formulation is known for CRFs when = 1 with `(2)2 regularization, and for structured SVM when = 0 with `(2)2 regularization, [11, 21, 1].”
Accelerated training of max-margin Markov networks with kernels (2011, methodology): “Further, we design a kernelized procedure which allows all computations per iteration to be performed at the same cost as the state-of-the-art approaches.”
Recent Advances of Large-Scale Linear Classification (2012, methodology): “[71] proposed an exponential gradient method to solve ME dual.”