SDCA-Powered Inexact Dual Augmented Lagrangian Method for Fast CRF Learning

Xu Hu, Guillaume Obozinski
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:988-997, 2018.

Abstract

We propose an efficient dual augmented Lagrangian formulation to learn conditional random fields (CRF). Our algorithm, which can be interpreted as an inexact gradient descent algorithm on the multipliers, does not require to perform global inference iteratively and requires only a fixed number of stochastic clique-wise updates at each epoch to obtain a sufficiently good estimate of the gradient w.r.t. the Lagrange multipliers. We prove that the proposed algorithm enjoys global linear convergence for both the primal and the dual objectives. Our experiments show that the proposed algorithm outperforms state-of-the-art baselines in terms of the speed of convergence.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-hu18a, title = {SDCA-Powered Inexact Dual Augmented Lagrangian Method for Fast CRF Learning}, author = {Hu, Xu and Obozinski, Guillaume}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {988--997}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/hu18a/hu18a.pdf}, url = {https://proceedings.mlr.press/v84/hu18a.html}, abstract = {We propose an efficient dual augmented Lagrangian formulation to learn conditional random fields (CRF). Our algorithm, which can be interpreted as an inexact gradient descent algorithm on the multipliers, does not require to perform global inference iteratively and requires only a fixed number of stochastic clique-wise updates at each epoch to obtain a sufficiently good estimate of the gradient w.r.t. the Lagrange multipliers. We prove that the proposed algorithm enjoys global linear convergence for both the primal and the dual objectives. Our experiments show that the proposed algorithm outperforms state-of-the-art baselines in terms of the speed of convergence.} }
Endnote
%0 Conference Paper %T SDCA-Powered Inexact Dual Augmented Lagrangian Method for Fast CRF Learning %A Xu Hu %A Guillaume Obozinski %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-hu18a %I PMLR %P 988--997 %U https://proceedings.mlr.press/v84/hu18a.html %V 84 %X We propose an efficient dual augmented Lagrangian formulation to learn conditional random fields (CRF). Our algorithm, which can be interpreted as an inexact gradient descent algorithm on the multipliers, does not require to perform global inference iteratively and requires only a fixed number of stochastic clique-wise updates at each epoch to obtain a sufficiently good estimate of the gradient w.r.t. the Lagrange multipliers. We prove that the proposed algorithm enjoys global linear convergence for both the primal and the dual objectives. Our experiments show that the proposed algorithm outperforms state-of-the-art baselines in terms of the speed of convergence.
APA
Hu, X. & Obozinski, G.. (2018). SDCA-Powered Inexact Dual Augmented Lagrangian Method for Fast CRF Learning. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:988-997 Available from https://proceedings.mlr.press/v84/hu18a.html.

Related Material