Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields

Rémi Le Priol, Alexandre Piché, Simon Lacoste-Julien
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:814-823, 2018.

Abstract

This work investigates the training of condi- tional random fields (CRFs) via the stochas- tic 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 ex- periments 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-le-priol18a, title = {Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields}, author = {Le Priol, R{\'e}mi and Pich{\'e}, Alexandre and Lacoste-Julien, Simon}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {814--823}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/le-priol18a/le-priol18a.pdf}, url = {https://proceedings.mlr.press/r16/le-priol18a.html}, abstract = {This work investigates the training of condi- tional random fields (CRFs) via the stochas- tic 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 ex- periments 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields %A Rémi Le Priol %A Alexandre Piché %A Simon Lacoste-Julien %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-le-priol18a %I PMLR %P 814--823 %U https://proceedings.mlr.press/r16/le-priol18a.html %V R16 %X This work investigates the training of condi- tional random fields (CRFs) via the stochas- tic 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 ex- periments 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. %Z Reissued by PMLR on 04 October 2026.
APA
Le Priol, R., Piché, A. & Lacoste-Julien, S.. (2018). Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:814-823 Available from https://proceedings.mlr.press/r16/le-priol18a.html. Reissued by PMLR on 04 October 2026.

Related Material