Limited-memory BFGS on arvau

Wikipedia / Limited-memory BFGS

Limited-memory BFGS (L-BFGS or LM-BFGS) is an optimization algorithm in the collection of quasi-Newton methods that approximates the Broyden–Fletcher–Goldfarb–Shanno algorithm (BFGS) using a limited amount of computer memory. It is a popular algorithm for parameter estimation in machine learning. is a differentiable scalar function.

Like the original BFGS, L-BFGS uses an estimate of the inverse Hessian matrix approximation to the inverse Hessian (n being the number of variables in the problem), L-BFGS stores only a few vectors that represent the approximation implicitly. Due to its resulting linear memory requirement, the L-BFGS method is particularly well suited for optimization problems with many variables. Instead of the inverse Hessian Hk, L-BFGS maintains a history of the past m updates of the position x and gradient ∇f(x), where generally the history size m). These updates are used to implicitly do operations requiring the Hk-vector product.

Algorithm

is the inverse of the Hessian matrix. There are multiple published approaches using a history of updates to form this direction vector. Here, we give a common approach, the so-called "two loop recursion."

, the position at the is the function being minimized, and all vectors are column vectors. We also assume that we have stored the last updates of the form

will be the 'initial' approximate of the inverse Hessian that our estimate at iteration begins with.

The algorithm is based on the BFGS recursion for the inverse Hessian as

For a fixed is then our ascent direction.

Thus we can compute the descent direction as follows:

. For maximization problems, one should thus take is chosen as a diagonal matrix or even a multiple of the identity matrix since this is numerically efficient.

ensures that the search direction is well scaled and therefore the unit step length is accepted in most iterations. A Wolfe line search is used to ensure that the curvature condition is satisfied and the BFGS updating is stable. Note that some software implementations use an Armijo backtracking line search in order to satisfy the curvature condition.

The two-loop recursion formula is widely used by unconstrained optimizers due to its efficiency in multiplying by the inverse Hessian. However, it does not allow for the explicit formation of either the direct or inverse Hessian and is incompatible with non-box constraints. An alternative approach is the compact representation, which involves a low-rank representation for the direct and/or inverse Hessian. This represents the Hessian as a sum of a diagonal matrix and a low-rank update. Such a representation enables the use of L-BFGS in constrained settings, for example, as part of the SQP method.

Applications

L-BFGS has been called "the algorithm of choice" for fitting log-linear (MaxEnt) models and conditional random fields with \ell_2-regularization.

Variants

Since BFGS (and hence L-BFGS) is designed to minimize smooth functions without constraints, the L-BFGS algorithm must be modified to handle functions that include non-differentiable components or constraints. A popular class of modifications are called active-set methods, based on the concept of the active set. The idea is that when restricted to a small neighborhood of the current iterate, the function and constraints can be simplified.

L-BFGS-B

The L-BFGS-B algorithm extends L-BFGS to handle simple box constraints ( bound constraints) on variables; that is, constraints of the form where and are per-variable constant lower and upper bounds, respectively (for each , either or both bounds may be omitted). The method works by identifying fixed and free variables at every step (using a simple gradient method), and then using the L-BFGS method on the free variables only to get higher accuracy, and then repeating the process.

OWL-QN

Orthant-wise limited-memory quasi-Newton (OWL-QN) is an L-BFGS variant for fitting \ell_1-regularized models, exploiting the inherent sparsity of such models. It minimizes functions of the form

is a differentiable convex loss function. The method is an active-set type method: at each iterate, it estimates the sign term becomes a smooth linear term which can be handled by L-BFGS. After an L-BFGS step, the method allows some variables to change sign, and repeats the process.

O-LBFGS

Schraudolph et al. present an online approximation to both BFGS and L-BFGS. Similar to stochastic gradient descent, this can be used to reduce the computational complexity by evaluating the error function and gradient on a randomly drawn subset of the overall dataset in each iteration. It has been shown that O-LBFGS has a global almost sure convergence while the online approximation of BFGS (O-BFGS) is not necessarily convergent.

Implementation of variants

Notable open source implementations include:

ALGLIB implements L-BFGS in C++ and C# as well as a separate box/linearly constrained version, BLEIC.
R's optim general-purpose optimizer routine uses the L-BFGS-B method.
SciPy's optimization module's minimize method also includes an option to use L-BFGS-B.
Julia's Optim.jl also implements the L-BFGS and L-BFGS-B algorithm.
Stan implements L-BFGS together with automatic differentiation as an option to solve maximum likelihood estimation and maximum a posteriori estimation problems.

Notable non open source implementations include:

The L-BFGS-B variant also exists as ACM TOMS algorithm 778. In February 2011, some of the authors of the original L-BFGS-B code posted a major update (version 3.0).
A reference implementation in Fortran 77 (and with a Fortran 90 interface). This version, as well as older versions, has been converted to many other languages.
An OWL-QN C++ implementation by its designers.