Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields
Mark Schmidt, Reza Babanezhad, Mohamed Ahmed, Aaron Defazio, Ann Clifton, Anoop Sarkar
Abstract
We apply stochastic average gradient (SAG) algorithms for training conditional random fields (CRFs). We describe a practical implementation that uses structure in the CRF gradient to reduce the memory requirement of this linearly-convergent stochastic gradient method, propose a non-uniform sampling scheme that substantially improves practical performance, and analyze the rate of convergence of the SAGA variant under non-uniform sampling. Our experimental results reveal that our method significantly outperforms existing methods in terms of the training objective, and performs as well or better than optimally-tuned stochastic gradient methods in terms of test error.
BibTeX
@InProceedings{pmlr-v38-schmidt15,
title = {{Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields}},
author = {Schmidt, Mark and Babanezhad, Reza and Ahmed, Mohamed and Defazio, Aaron and Clifton, Ann and Sarkar, Anoop},
booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics},
pages = {819--828},
year = {2015},
editor = {Lebanon, Guy and Vishwanathan, S. V. N.},
volume = {38},
series = {Proceedings of Machine Learning Research},
address = {San Diego, California, USA},
month = {09--12 May},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v38/schmidt15.pdf},
url = {https://proceedings.mlr.press/v38/schmidt15.html},
abstract = {We apply stochastic average gradient (SAG) algorithms for training conditional random fields (CRFs). We describe a practical implementation that uses structure in the CRF gradient to reduce the memory requirement of this linearly-convergent stochastic gradient method, propose a non-uniform sampling scheme that substantially improves practical performance, and analyze the rate of convergence of the SAGA variant under non-uniform sampling. Our experimental results reveal that our method significantly outperforms existing methods in terms of the training objective, and performs as well or better than optimally-tuned stochastic gradient methods in terms of test error.}
}