Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields

By Mark W. Schmidt, Reza Babanezhad, Mohamed Osama Ahmed, Aaron Defazio, Ann Clifton, Anoop Sarkar. 2015

83 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Optimization & Training

Citations in the corpus

Structured Convolutional Kernel Networks for Airline Crew Scheduling (2021, methodology): “Since the CRF optimizers (SAG-NUS, SAG-NUS* (Schmidt et al., 2015), SDCA, SDCA-GAP (Le Priol et al.”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “Moreover, VR makes setting the learning rate easier and there has been work exploring the use of line-search techniques for automatically setting the step-size for these methods [74, 73, 83, 78].”
Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields (2017, methodology): “Both OEG and SAG-NUS use a line search where they call an oracle on each step.”
Minimizing finite sums with the stochastic average gradient (2013, methodology): “Indeed, we provide here an argument to justify a non-uniform sampling strategy based on the Lipschitz constants of the individual gradients f ′ i and we note that in subsequent works this intuition has proved correct for related algorithms [53,64].”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “This methods has been recently extended for use in Conditional Random Fields [84].”
Stochastic Variance Reduction Methods for Saddle-Point Problems (2016, methodology): “For the bound above to be valid for non-uniform sampling, like for convex minimization [25], we need to resa mplem operators after we make the iterate update.”
Coupling Adaptive Batch Sizes with Learning Rates (2016, background): “We note that another recent line of work on non-uniform sampling of training samples with the goal of variance reduction (including, but not limited to, [18, 27, 24, 4]) is orthogonal to our work, since it is concerned with the composition of batches rather than their size.”
Online Batch Selection for Faster Training of Neural Networks (2015, methodology): “They often consist of i) biasing the sampling towards the Lipschitz constants of the gradients, so that gradients that change quickly get sampled more often and gradients that change slowly get sampled less often (Schmidt et al., 2015), and ii) re-weighting the obtained gradients by inverses of thei”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “This methods has been recently extended for use in Conditional Random Fields [157].”
Stochastic Learning on Imbalanced Data: Determinantal Point Processes for Mini-batch Diversification (2017, background): “A second class of methods relies on non-uniform sampling of minibatches [8, 11, 32, 38, 47, 48].”
Safe Adaptive Importance Sampling (2017, background): “In contrast, adaptive importance sampling strategies constantly re-evaluate the relative importance of each data point during training and thereby often surpass the performance of static algorithms [22, 5, 26, 10, 21, 23].”
Stochastic quasi-gradient methods: variance reduction via Jacobian sketching (2018, methodology): “[30] about the rate of SAGA with importance sampling in the affirmative.”
Balanced Mini-batch Sampling for SGD Using Determinantal Point Processes (2017, background): “A second class of methods relies on non-uniform sampling of minibatches [8, 11, 33, 39, 48, 49].”