Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields
This work addresses training efficiency for CRFs, which are used in sequence labeling tasks like NLP, but it is incremental as it builds on existing SAG methods with optimizations.
The authors tackled the problem of efficiently training conditional random fields (CRFs) by applying stochastic average gradient (SAG) algorithms, resulting in a method that often significantly outperforms existing methods in training objective and matches or beats optimally-tuned stochastic gradient methods in test error.
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 often 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.