Orthant-wise limited-memory quasi-Newton

Orthant-wise limited-memory quasi-Newton (OWL-QN) is a numerical optimization algorithm that belongs to the class of quasi-Newton methods, and is specifically designed to serve in the training/fitting algorithm of log-linear (MaxEnt) models with $\ell_1$-regularization. It minimizes functions of the form

$f(\vec x) = g(\vec x) + C \|\vec x\|_1$

where g is a differentiable convex loss function.

OWL-QN's design is based on limited-memory BFGS (L-BFGS) but extended to exploit the sparsity of $\ell_1$-regularized models.^[1]

Implementations

• C++ implementation by the designers of OWL-QN, includes the original ICML paper on the algorithm^[1]
• Python implementation by Michael Subotin, intended for use with SciPy
• The CRF toolkit Wapiti includes a C implementation of OWL-QN

References

1. ^ ^{a b} Andrew, Galen; Gao, Jianfeng (2007). "Scalable Training of L₁-Regularized Log-Linear Models". ICML.