Limited-memory BFGS

Limited-memory BFGS (L-BFGS or LM-BFGS) is an optimization algorithm in the family 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. The algorithm's target problem is to minimize formula_1 over unconstrained values of the real-vector formula_2 where formula_3 is a differentiable scalar function.
Like the original BFGS, L-BFGS uses an estimate of the inverse Hessian matrix to steer its search through variable space, but where BFGS stores a dense formula_4 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" can be small (often formula_5). These updates are used to implicitly do operations requiring the Hk"-vector product.
Algorithm.
The algorithm starts with an initial estimate of the optimal value, formula_6, and proceeds iteratively to refine that estimate with a sequence of better estimates formula_7. The derivatives of the function formula_8 are used as a key driver of the algorithm to identify the direction of steepest descent, and also to form an estimate of the Hessian matrix (second derivative) of formula_1.
L-BFGS shares many features with other quasi-Newton algorithms, but is very different in how the matrix-vector multiplication formula_10 is carried out, where formula_11 is the approximate Newton's direction, formula_12 is the current gradient, and formula_13 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."
We take as given formula_14, the position at the -th iteration, and formula_15 where formula_3 is the function being minimized, and all vectors are column vectors. We also assume that we have stored the last updates of the form 
We define formula_19, and formula_20 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 we define a sequence of vectors formula_22 as formula_23 and formula_24. Then a recursive algorithm for calculating formula_25 from formula_26 is to define formula_27 and formula_28. We also define another sequence of vectors formula_29 as formula_30. There is another recursive algorithm for calculating these vectors which is to define formula_31 and then recursively define formula_32 and formula_33. The value of formula_34 is then our ascent direction.
Thus we can compute the descent direction as follows:
This formulation gives the search direction for the minimization problem, i.e., formula_36. For maximization problems, one should thus take instead. Note that the initial approximate inverse Hessian formula_20 is chosen as a diagonal matrix or even a multiple of the identity matrix since this is numerically efficient.
The scaling of the initial matrix formula_38 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, but cannot guarantee that the curvature condition formula_39 will be satisfied by the chosen step since a step length greater than formula_40 may be needed to satisfy this condition. Some implementations address this by skipping the BFGS update when formula_41 is negative or too close to zero, but this approach is not generally recommended since the updates may be skipped too often to allow the Hessian approximation formula_13 to capture important curvature information.
This two loop update only works for the inverse Hessian. Approaches to implementing L-BFGS using the direct approximate Hessian formula_43 have also been developed, as have other means of approximating the inverse Hessian.
Applications.
L-BFGS has been called "the algorithm of choice" for fitting log-linear (MaxEnt) models and conditional random fields with formula_44-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 (aka 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 formula_45-regularized models, exploiting the inherent sparsity of such models.
It minimizes functions of the form
where formula_47 is a differentiable convex loss function. The method is an active-set type method: at each iterate, it estimates the sign of each component of the variable, and restricts the subsequent step to have the same sign. Once the sign is fixed, the non-differentiable formula_48 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:
Notable non open source implementations include: