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. The algorithm's target problem is to minimize f ( x ) {\displaystyle f(\mathbf {x} )} over unconstrained values of the real-vector x {\displaystyle \mathbf {x} } where f {\displaystyle f} 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 n × n {\displaystyle n\times n} 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 m < 10 {\displaystyle m<10} ). 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, x 0 {\displaystyle \mathbf {x} _{0}} , and proceeds iteratively to refine that estimate with a sequence of better estimates x 1 , x 2 , … {\displaystyle \mathbf {x} _{1},\mathbf {x} _{2},\ldots } . The derivatives of the function g k := ∇ f ( x k ) {\displaystyle g_{k}:=\nabla f(\mathbf {x} _{k})} 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 f ( x ) {\displaystyle f(\mathbf {x} )} . L-BFGS shares many features with other quasi-Newton algorithms, but is very different in how the matrix-vector multiplication d k = − H k g k {\displaystyle d_{k}=-H_{k}g_{k}} is carried out, where d k {\displaystyle d_{k}} is the approximate Newton's direction, g k {\displaystyle g_{k}} is the current gradient, and H k {\displaystyle H_{k}} 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 x k {\displaystyle x_{k}} , the position at the k-th iteration, and g k ≡ ∇ f ( x k ) {\displaystyle g_{k}\equiv \nabla f(x_{k})} where f {\displaystyle f} is the function being minimized, and all vectors are column vectors. We also assume that we have stored the last m updates of the form
s k = x k + 1 − x k {\displaystyle s_{k}=x_{k+1}-x_{k}}
y k = g k + 1 − g k {\displaystyle y_{k}=g_{k+1}-g_{k}} . We define ρ k = 1 y k ⊤ s k {\displaystyle \rho _{k}={\frac {1}{y_{k}^{\top }s_{k}}}} , and H k 0 {\displaystyle H_{k}^{0}} will be the 'initial' approximate of the inverse Hessian that our estimate at iteration k begins with. The algorithm is based on the BFGS recursion for the inverse Hessian as
… excerpt ends here. Continue reading the full article.
