Non-uniform stochastic average gradient method for training conditional random fields

We apply stochastic average gradient (SAG) algorithms for training conditional random fields (CRFs). We describe a practical im-plementation that uses structure in the CRF gradient to reduce the memory requirement of this linearly-convergent stochastic gradi-ent method, propose a non-uniform sampling scheme that substantially improves practical performance, and analyze the rate of con-vergence of the SAGA variant under non-uniform sampling. Our experimental results reveal that our method significantly outper-forms existing methods in terms of the training objective, and performs as well or bet-ter than optimally-tuned stochastic gradient methods in terms of test error.