Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields

2017-12-22 · Rémi Le Priol, Alexandre Piché, Simon Lacoste-Julien

This work investigates the training of conditional random fields (CRFs) via the stochastic dual coordinate ascent (SDCA) algorithm of Shalev-Shwartz and Zhang (2016). SDCA enjoys a linear convergence rate and a strong empirical performance for binary classification problems. However, it has never been used to train CRFs. Yet it benefits from an `exact' line search with a single marginalization oracle call, unlike previous approaches. In this paper, we adapt SDCA to train CRFs, and we enhance it with an adaptive non-uniform sampling strategy based on block duality gaps. We perform experiments on four standard sequence prediction tasks. SDCA demonstrates performances on par with the state of the art, and improves over it on three of the four datasets, which have in common the use of sparse features.

📄 PDF Abstract BibTeX arXiv:1712.08577

Code (0)

등록된 구현이 없습니다.

Tasks

Binary Classification General Classification

Stochastic Dual Coordinate Ascent with Adaptive Probabilities

2015-02-27 · Dominik Csiba, Zheng Qu, Peter Richtárik

This paper introduces AdaSDCA: an adaptive variant of stochastic dual coordinate ascent (SDCA) for solving the regularized empirical risk minimization problems. Our modification consists in allowing the method adaptively…

Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent

2013-12-01 · NeurIPS 2013 12 · Tianbao Yang

We present and study a distributed optimization algorithm by employing a stochastic dual coordinate ascent method. Stochastic dual coordinate ascent methods enjoy strong theoretical guarantees and often have better perf…

Distributed Optimization

Accelerated Mini-Batch Stochastic Dual Coordinate Ascent

2013-05-12 · NeurIPS 2013 12 · Shai Shalev-Shwartz, Tong Zhang

Stochastic dual coordinate ascent (SDCA) is an effective technique for solving regularized loss minimization problems in machine learning. This paper considers an extension of SDCA under the mini-batch setting that is of…

BIG-bench Machine Learning

Online Dual Coordinate Ascent Learning

2016-02-24 · Bicheng Ying, Kun Yuan, Ali H. Sayed

The stochastic dual coordinate-ascent (S-DCA) technique is a useful alternative to the traditional stochastic gradient-descent algorithm for solving large-scale optimization problems due to its scalability to large data …

Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization

2013-09-10 · Shai Shalev-Shwartz, Tong Zhang

We introduce a proximal version of the stochastic dual coordinate ascent method and show how to accelerate the method using an inner-outer iteration procedure. We analyze the runtime of the framework and obtain rates tha…

BIG-bench Machine Learning regression