On the Broyden-Fletcher-Goldfarb-Shanno Method, by D.F. Shanno, . In Journal of Optimization Theory and Applications, 1985.
The L-BFGS algorithm is an optimization method that falls under the group of techniques known as "quasi-Newton" optimization methods. The "L" stands for "Limited" (in the limited memory sense, not that the method is necessarily limited), and BFGS are the individuals who came up with the original (non-limited memory variant) algorithm: Broyden, Fletcher, Goldfarb, and Shanno. Here is a picture of all of them:
In general, whereas optimization methods like the cutting planes algorithm, which are in the category of "bundle methods", essentially lower bound the objective function using linear gradients, quasi-Newton algorithms use the gradients to estimate the Hessian (the square matrix of the second-order partial derivatives, think of it as the vector generalization of a second derivative). With the gradient and an approximated Hessian, we can build a quadratic approximation of the objective function.
The standard BFGS approximates the objective function with a locally quadratic optimization: where is the objective function, is the gradient, and is the Hessian.
We update parameters with the weight that minimizes the quadratic approximation:
In Quasi-Newton methods, we use a Newton update to update the weight, in other words we use the Hessian and the gradient to come up with a direction in which to update: , where is the step size, which is usually found/tuned by a line search. The line search needs to match the Wolfe Conditions, which intuitively make sure there is a sufficient decrease in objective function while respecting the curvature condition (of convexity).
The exact Hessian is very expensive to calculate, and the full exact Hessian is very expensive to invert. We wish to come up with an iterative approximation to the inverse Hessian, let us call it . Then, , where is the gradient difference between iterations, and is the parameter difference between iterations. After a bit of math, this results in the following update ( is the identity matrix):
The above explains the BFGS method. L-BFGS is essentially the same, except we use a low-rank approximation to B.
For non-smooth optimization functions, there are a few modifications we need to make. Firstly, our local quadratic approximation is no longer well defined. Second, note that since not every subgradient is a descent direction, the descent direction (which we formulated as is also not well defined. We adjust our quadratic approximation as: . We deal with this supremum by shifting a term from the objective function to a constraint and creating a constrained optimization problem for the weight update:
such that . Notice that we sample k subgradients from the set of subgradients (which is a convex set by the way).
There are a lot of papers that use this method. Here are some examples: