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  over unconstrained values of the real-vector  where  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  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 ). 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, , and proceeds iteratively to refine that estimate with a sequence of better estimates . The derivatives of the function  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 .

L-BFGS shares many features with other quasi-Newton algorithms, but is very different in how the matrix-vector multiplication  is carried out, where  is the approximate Newton's direction,   is the current gradient, and  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 , the position at the -th iteration, and  where  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 , and  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  as  and . Then a recursive algorithm for calculating  from  is to define  and . We also define another sequence of vectors  as . There is another recursive algorithm for calculating these vectors which is to define  and then recursively define  and . The value of  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., . For maximization problems, one should thus take  instead. Note that the initial approximate inverse Hessian  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  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  will be satisfied by the chosen step since a step length greater than  may be needed to satisfy this condition. Some implementations address this by skipping the BFGS update when  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  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  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 -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 -regularized models, exploiting the inherent sparsity of such models.
It minimizes functions of the form

where  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  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.

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.

Works cited

Further reading

Optimization algorithms and methods
L-BFGS (혹은 Limited-memory BFGS, LM-BFGS) 준-뉴턴 방식 (quasi-Newton methods)의 최적화 알고리즘이다. 제한된 컴퓨터 메모리를 이용하여 기존 BFGS (Broyden–Fletcher–Goldfarb–Shanno algorithm) 알고리즘을 속도면에서 개선한 알고리즘이다. (결과는 근사값). 본 알고리즘은 Adam과 함께 머신 러닝에 있어서 널리 사용되는 파라메터 추정 알고리즘이다. 본 알고리즘의 목적함수는 의 최소값을 찾는 것이며, 여기서, 는 unconstrained value의 real-vector이고, 는 미분가능한 스칼라 함수이다.

원래의 BFGS와 같이, L-BFGS 알고리즘은 variable space의 검색을 조정하는 추정된 inverse Hessian matrix를 이용한다. 하지만 BFGS는 inverse Hessian에서 추정된 전체  을 이용하고, L-BFGS는 단지 몇개의 벡터만을 저장한다. 비록 일부의 벡터이지만 이런 일부의 벡터 역시 암시적으로 대표성을 지니고 있다. (주로 홀수개의 벡터를 지정하고 10 이하. 문헌에서 봤는데 이유는 기억이 가물가물.. ) 여기서 n은 문제에서 변수의 갯수를 의미한다. 선형 메모리의 요구사항으로 인해, L-BFGS는 많은 변수를 가진 최적화 문제에 적합하다고 알려져 있다. inverse Hessian Hk  대신에 L-BFGS는 과거 m update의 기록과 gradient ∇f(x) 이용한다. 일반적으로 과거 기록인 m 의 크기는 주로 10 이하를 선정한다.

(문서는 Wikipedia의 영어판에 게재된 Limited-memory BFGS 문서의 한국어 번역이며, 필자의 판단으로 일부 내용은 의역하였음.)

알고리즘 (Algorithm) 
알고리즘은 최적 변수의 초기 추정값, ,과 함께 시작하고, 반복적으로 더 나은 추정값 을 평가하는 과정으로 진행된다. 목적 함수의 미분, , steepest descent의 방향을 정하고, 이차 미분 함수인 Hessian 메트릭스의 추정를 구성하는데 아주 중요한 요소이다.

L-BFGS는 다른 quasi-Newton 알고리즘과 많은 특징을 공유하지만, 메트릭스-벡터의 곱, , 이 수행되는 방식에서 매우 다르다. 여기서, 는 대략적인 뉴튼의 방향이고,  는 현재의 gradient, 는 Hessian 메트릭스의 역행렬이다. 이러한 방향 벡터를 정하기 위한 업데이트의 기록을 이용하는 많은 접근방식이 있으며, 여기서는 소위 "two loop recursion"이라고 불리는 일반적인 접근법 (알고리즘)을 소개한다.

k번째 iteration에서의 위치와 gradient를 , 라 하자. 여기서 는 최소화되어야 함수이고, 모든 벡터들은 컬럼 벡터이다. 마지막  업데이트는 저장했다고 가정하자.

,
.

 이고,  는 inverse Hessian의 초기 가정이라고 하자. BFGS를 기반으로 inverse Hessian은 아래와 같다.

하나의 고정된 에서 벡터의 시퀀스를  as  와  로 정의하자. 그때, 로부터 를 계산하는 번복 알고리즘은  로 정의하고, 다음과 같이 를 정한다.

또 하나의 벡터의 시퀀스 는 로 정한다. , , 를 결정하는 또하나의 recursive 알고리즘이 있다.  의 값은 이제 오르막 방향이며, 다음과 같이 내리막 방향을 계산할 수 있다.
 

상기의 공식은 최소화 문제 를 위한 방향 검색을 제공한다. 최대화 문제에 대해서는, 의 부호를 변경해야 한다. 초기 inverse Hessian  근사값은 대각 행렬값이나, 효율적인 계산 방식인 identity 메트릭스의 배수로 선택한다.

초기 메트릭스 의 스케일은 방향 검색이 잘 되도록 배율되어야 하고, 단위 스텝의 길이가 대부분의 iteration에서 적용가능하여야 한다. Wolfe line search는 curvature조건을 만족하고, BFGS의 업데이트를 안정시키기 위해 사용된다.

어떤 소프트웨어에서는 backtracking line search를 이용하지만, 이것은 선택된 스텝에 의해 curvature 조건  만족되어 져야 함을 보증하지 못한다. 어떤 알고리즘 구현에서는 가 음수이거나, zero (영)에 가까우면 건너 뛰는 방식을 취하지만, 이런 접근법은 일반적으로 권장하지는 않는다. 왜냐하면 너무 자주 건너 뛰므로써 중요한 곡면 정보를 파악하기 힘들고, 적절한 Hessian 추정을 못할 수 있기 때문이다.

이러한 two loop update는 단지 inverse Hessian 잘 작동한다. 다른 방식으로 inverse Hessian 추정하는 직접 근사 Hessian 를 이용하는 방식도 개발되어 있다.

변형된 알고리즘들 (Variants) 
BFGS와 L-BFGS는 구속조건들 없이 Smooth 함수를 최적화하도록 설계되었기 때문에, L-BFGS 알고리즘은 미분이 되지 않은 함수나 구속들을 포함하는 함수에 적용하기 위해서는 수정이 필요하다. 가장 인기있는 변형된 알고리즘은 active-set방식이라 불린다. 이 아이디어는 현재 iterate의 작은 근사값으로 구속했을 때, 함수와 구속을 단순화 할 수 있다는 것이다.

L-BFGS-B 
L-BFGS-B 알고리즘은 simple box 구속들을 다루기 위해서 확장된 방식이다. 단순화된 구속은 하한과 상한 경계가 있는  형식이며, 각 를 위해, 양 방향 혹은 한쪽 방향의 경계는 제거되어 질 수도 있다 . 이 방법은 (단순 gradient 방식을 이용하는) 각 스텝에서 고정과 자유 변수들을 결정하고, 높은 정확도을 얻기 위해서 자유 변수에 L-BFGS를 이용하고, 과정을 반복함으로써 동작한다.

OWL-QN 
Orthant-wise limited-memory quasi-Newton (OWL-QN)는 -regularized 모델을 피팅하고, inherent sparsity 모델을 이용하기 위해 변형된 L-BFGS알고리즘이다. 아래의 형태의 함수를 최소화 (최적화)한다.
 

여기서 는 미분가능한 convex 손실 함수이다. 이 방식은 하나의 active-set 방식이며, 변수들의 각 요소의 부호를 평가(추정, 예측)하고, 같은 부호를 가지기 위해 서브 시퀀스 스텝을 제약한다. 일단 부호가 고정되면, 미분이 가능하지 않은  term은 하나의 smooth linear term 이 된다. 이런 smooth linear term은 L-BFGS에 의해 이용될 수 있다. 하나의 L-BFGS스텝 이후, 이 방식은 부호를 변경하기 위한 일부 변수들을 허용하고, 과정을 반복한다.

O-LBFGS 
Schraudolph 둥은 BFGS와 L-BFGS에 대한 온라인 근사법을 제안했다. Stochastic gradient descent (SGD)와 유사하게, 이 방법은 에러 함수와 각 iteration에서의 전체 데이터 셋에 대한 randomly drawn subset의 gradient를 평가함으로써, 계산의 복잡성을 감소시키기 위해 사용될 수 있다. BFGS 혹은 O-BFGS의 온라인 근사법은 반드시 수렴하지는 않지만, O-LBFGS는 거의 글로벌하게 수렴함을 보여준다.

참고 문헌

읽을거리 
 
 
 

최적화 알고리즘