Scalable training of L1-regularized log-linear models

By Galen Andrew, Jianfeng Gao. 2007

665 citations recorded by the source corpus.

The L-BFGS limited-memory quasi-Newton method is the algorithm of choice for optimizing the parameters of large-scale log-linear models with L2 regularization, but it cannot be used for an L1-regularized loss due to its non-differentiability whenever some parameter is zero. Efficient algorithms have been proposed for this task, but they are impractical when the number of parameters is very large. We present an algorithm Orthant-Wise Limited-memory Quasi-Newton (OWL-QN), based on L-BFGS, that can efficiently optimize the L1-regularized log-likelihood of log-linear models with millions of parameters. In our experiments on a parse reranking task, our algorithm was several orders of magnitude faster than an alternative algorithm, and substantially faster than L-BFGS on the analogous L2-regularized problem. We also present a proof that OWL-QN is guaranteed to converge to a globally optimal parameter vector.

Subfields: Artificial Intelligence, Computational Mechanics

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

Citations in the corpus

CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “In Section 6, we include experimental comparisons with ADMM, gradient descent, and L-BFGS variants, including orthant-wise limited memory quasi-Newton (OWL-QN) for the L 1 setting (Andrew and Gao, 2007).”
Regularization Paths for Generalized Linear Models via Coordinate Descent (2010, positive): “OWL-QN : Orthant-Wise Limited-memory Quasi-Newton Optimizer for (cid:96) 1 -regularized Objectives (Andrew and Gao 2007a,b).”
Learning Continuous Phrase Representations for Translation Modeling (2014, methodology): “In our experiments we train the parameters of the CPTM, 𝛉 , using the L-BFGS optimizer described in Andrew and Gao (2007), together with the loss function described in (5).”
Modeling Latent-Dynamic in Shallow Parsing: A Latent Conditional Model with Improved Inference (2008, methodology): “We implemented an L-BFGS optimizer in C++ by modifying the OWLQN package (Andrew & Gao 2007) developed by Galen Andrew.”
Combining Heterogeneous Models for Measuring Relational Similarity (2013, methodology): “Instead of employing explicit feature selection methods, we used an efficient L1 regularized log-linear model learner (Andrew and Gao, 2007) and chose the hyper-parameters based on model performance on the training data.”
Understanding Natural Language Commands for Robotic Navigation and Mobile Manipulation (2011, methodology): “In order to learn the parameters µk that maximize the likelihood of the training dataset, we compute the gradient, and use the Mallet toolkit (McCallum, 2002) to optimize the parameters of the model via gradient descent with L-BFGS (Andrew and Gao, 2007).”
Optimizing Costly Functions with Simple Constraints: A Limited-Memory Projected Quasi-Newton Algorithm (2009, neutral): “Also, one of the most eﬀective solvers for (non-diﬀerentiable) (cid:96) 1 -regularized optimization problems is also an extension of the L-BFGS method, known as orthant-wise descent (OWD) (Andrew and Gao, 2007).”
Practical Very Large Scale CRFs (2010, methodology): “We study and compare three different ways to implement `1 penalty for CRFs that have been introduced recently: orthantwise Quasi Newton (Andrew and Gao, 2007), stochastic gradient descent (Tsuruoka et al., 2009) and coordinate descent (Sokolovska et al., 2010), concluding that these methods have…”
Learning Semantic Representations for the Phrase Translation Model (2013, positive): “�)𝑃(�|��)𝜆�+1𝑁(�,�;�) (�,𝐴)∈��(��) (14) where U(𝛉,�)=sBleu(��,�)−xBleu(𝛉). 5.2 The Training Algorithm In our experiments we train the parameters of the SPTM 𝛉 using the L-BFGS optimizer described in [1], together with the loss function described in (5). The gradient is computed as described ”
Elements of style (2015, methodology): “There are several techniques that have been developed in the context of L1-norm regularized optimization which are applicable to our problem (see [Schmidt et al. 2007; Andrew and Gao 2007] for related reviews and references).”
A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization (2016, methodology): “We compare Acc-DADM to CoCoA+ and OWL-QN (Andrew and Gao, 2007), as they have already been shown to be superior to other related algorithms in (Yang, 2013; Jaggi et al., 2014; Ma et al., 2017; Andrew and Gao, 2007).”
Pedestrian detection aided by deep learning semantic tasks (2014, methodology): “maini ) + xTbx+ yTby. Combining all the above deﬁnitions, Eqn.(10) is an unconstrained optimization problem, where the importance coefﬁcients can be efﬁciently updated by using the L-BFGS algorithm [1]. 4. Experiments The proposed TA-CNN is evaluated on the CaltechTest [11] and ETH datasets [12]. W”
Structured Embedding via Pairwise Relations and Long-Range Interactions in Knowledge Base (2015, background): “…is no longer than 4 (L = 4) and the maximum number of long-range interactions for each pairwise relation is K = 10; (v) minibatched Limited-memory BFGS (L-BFGS) (Malouf 2002; Andrew and Gao 2007) is used for optimizing non-convex object function and the number of training iterations is set to 500.”
L1-Regularized Distributed Optimization: A Communication-Efficient Primal-Dual Framework (2015, background): “This case delivers the fastest convergence rates in the distributed setting, which in particular don’t degrade as the number of machines K grows and n remains fixed.”
Learning the Structure of Sum-Product Networks (2013, methodology): “L1 structure was learned using the OWL-QN package (Andrew & Gao, 2007) for L1 logistic regression.”