Sparse Online Learning via Truncated Gradient

By J. Langford, Lihong Li, Tong Zhang. Neural Information Processing Systems, 2008

502 citations recorded by the source corpus.

We propose a general method called truncated gradient to induce sparsity in the weights of online-learning algorithms with convex loss. This method has several essential properties. First, the degree of sparsity is continuous—a parameter controls the rate of sparsification from no sparsification to total sparsification. Second, the approach is theoretically motivated, and an instance of it can be regarded as an online counterpart of the popular L1-regularization method in the batch setting. We prove small rates of sparsification result in only small additional regret with respect to typical online-learning guarantees. Finally, the approach works well empirically. We apply it to several datasets and find for datasets with large numbers of features, substantial sparsity is discoverable.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/2dd670072f86003702669b4f5298d72172b6ef0b

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 Computational Mechanics

In Management Science and Operations Research

Citations in the corpus

Parallel Coordinate Descent Newton Method for Efficient $\ell_1$-Regularized Minimization (2013, unknown): “Several algorithms perform parallelization over samples (Langford et al., 2009; Zinkevich et al., 2009, 2010; Niu et al., 2011) although usually there are much more features than samples in 1 -regularized problems.”
Building Predictive Models via Feature Synthesis (2015, background): “Vowpal Wabbit (VW): Vowpal Wabbit [14] is a fast outof-core online learning algorithm based on sparse gradient descent.”
Memory, Communication, and Statistical Queries (2016, background): “One more modest and practically relevant goal would be to provide an efficient memory-bounded algorithm for sparse regression without assumptions on the covariance structure.”
Parallel Coordinate Descent for L1-Regularized Loss Minimization (2011, methodology): “For example, it achieves better runtime bounds w.r.t. d than stochastic gradient methods such as SMIDAS (Shalev-Shwartz & Tewari, 2009) and truncated gradient (Langford et al., 2009a).”
Online Convex Optimization in Dynamic Environments (2015, result): “We may compare the DMD approach with classical online learning methods [11]–[13], [22] and more recent regularized formulations [26]–[28].”
Large-Scale Learning with Less RAM via Randomization (2013, methodology): “Smaller Models A classic approach to reducing memory usage is to encourage sparsity, for example via the Lasso (Tibshirani, 1996) variant of least-squares regression, and the more general application of L 1 reg-ularizers (Duchi et al., 2008; Langford et al., 2009; Xiao, 2009; McMahan, 2011).”
Sparse Q-learning with Mirror Descent (2012, methodology): “Different values of p yield an interpolation between the truncated gradient method [LLZ09] and SMI-DAS [SsT09].”
CatBoost: unbiased boosting with categorical features (2017, methodology): “, for the task of click prediction [1, 16]), numerous training examples become available sequentially in time, and the model is updated on the basis of each new example without reconsideration of the previous ones.”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, background): “Several variants of SGD, that leads to sparser intermediate solutions, have been proposed (e.g. [14, 21, 27, 8, 10]).”
Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization (2013, methodology): “Some previous works are closely related to this scheme: the online EM algorithm for latent data models [5,21] and the online matrix factorization technique of [19] involve for instance surrogate functions updated in a similar fashion.”
Dynamic Regret of Strongly Adaptive Methods (2017, background): “Static Regret The majority of studies in online learning are focused on static regret (Shalev-Shwartz & Singer, 2007; Langford et al., 2009; Shalev-Shwartz, 2011; Zhang et al., 2013).”
Towards Optimal One Pass Large Scale Learning with Averaged Stochastic Gradient Descent (2011, background): “On the other hand, stochastic gradient descent (SGD) has been shown to have great promise for large scale learning (Zhang, 2004; Hazan et al., 2006; Shalev-Shwartz et al., 2007; Bottou and Bousquet, 2008; Shalev-Shwartz and Tewari, 2009; Langford et al., 2009).”
DSD: Dense-Sparse-Dense Training for Deep Neural Networks (2016, background): “Sparsity Regularization and Hard Thresholding: the truncation-based sparse network has been theoretically analyzed for learning a broad range of statistical models in high dimensions (Langford et al. (2009); Yuan & Zhang (2013); Wang et al. (2014)).”
Towards a unified architecture for in-RDBMS analytics (2012, background): “optimal runtime performance compared to approaches that exploit shared-memory parallelism [29, 37].”
Structured Sparsity in Structured Prediction (2011, methodology): “…and scalable algorithms having been proposed for training L 1 -regularized CRFs, based on quasi-Newton optimization (Andrew and Gao, 2007), coordinate descent (Sokolovska et al., 2010; Lavergne et al., 2010), and stochastic gradients (Carpenter, 2008; Langford et al., 2009; Tsuruoka et al., 2009).”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, background): “Remark: Upon completion of the paper, we learned that similar ideas of lazy updates were proposed in [40] and [41] for online learning and multinomial logistic regression, respectively.”
Online Machine Learning in Big Data Streams (2018, background): “ise, the gradient for w is xyˆ, and the update rule for learning rate h is w w+hxyˆ if yyˆ <1: (4) The online gradient descent algorithm simply applies the above step to training examples in order [147]. By contrast, the batch gradient descent algorithm reads the input multiple times and usually ”
Online Learning: A Comprehensive Survey (2018, methodology): “Motivated by addressing the above limitation, the Truncated Gradient Descent (TGD) method [68] explores a less aggressive version of the truncation function:”
Exploiting sparseness in deep neural networks for large vocabulary speech recognition (2012, methodology): “To enforce a sparse solution, one often truncates the solutions after each K steps by forcing parameters with magnitude smaller than a threshold θ to zero [11].”