Schmidt, MarkBabanezhad, RezaAhemd, M. OsamaDefazio, AaronClifton, AnnSarkar, Anoop2025-12-172025-12-171532-4435https://hdl.handle.net/1885/733795945We 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.10enPublisher Copyright: Copyright 2015 by the authors.201584954318065