L-BFGS

Summary

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.

Details

The standard BFGS approximates the objective function with a locally quadratic optimization: $m_{t}(w)J(w_{t})+\langle \nabla J(w_{t}),w-w_{t}\rangle +{\frac {1}{2}}(w-w_{t})^{T}H_{t}(w-w_{t})$ where $J(w_{t})$ is the objective function, $\nabla J(w_{t})$ is the gradient, and $H_{t}$ is the Hessian.

We update parameters with the weight that minimizes the quadratic approximation: Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. TeX parse error: Double subscripts: use braces to clarify"): {\displaystyle w_{t+1}=\arg \min _{w}J(w_{t})+\langle \nabla J(w_{t}),w_{w}_{t}/rangle+{\frac {1}{2}}(w-w_{t})^{T}H_{t}(w-w_{t})}

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: $w_{t+1}=w_{t}-H_{t}^{-1}\nabla J(w_{t})$