Numerical Optimization: Understanding L-BFGS

Numerical Optimization: Understanding L-BFGS(aria42.com)

34 points by aria 11 years ago | 14 comments

jamessb 11 years ago |

This is a nice introduction, but it looks there is a problem with the formatting: some of the math is not rendered properly (in the source, some expressions are wrapped in dollar-signs rather than script tags).

aria 11 years ago | |

What browser are you in? It just using MathJax and appears to work in WebKit and Firefox.

jamessb 11 years ago | | |

Firefox 33.1.1 on Mac OS 10.10.1. Initially it would get stuck looking like: http://imgur.com/DhXAmI7

After refreshing the page a few times, all the formulae rendered correctly. In Safari things rendered correctly immediately.

howeman 11 years ago |

Gonum has an LBFGS implementation https://github.com/gonum/optimize/blob/master/lbfgs.go

howeman 11 years ago | |

See the "NextDirection" method for the update.

aria 11 years ago |

Author here, happy to answer any questions.

stephencanon 11 years ago | |

I hate to be that guy, but "Raphson", not "Rhapson" (http://en.wikipedia.org/wiki/Joseph_Raphson). It's also worth noting that no one ever actually forms the inverse of H, even if H is dense. At worst you would compute some factorization of H and use that to solve for the update d.

aria 11 years ago | | |

Typo is fixed, thanks!

I think that's explicitly mentioned in the Quasi-Newton section that you only need to implicitly multiply and not form the matrix.

lliiffee 11 years ago | |

Is it typical to interface to Newton's method via a function that computes the inverse Hessian? I've never seen that. Typically, people claim it is numerically unstable to explicitly invert the Hessian, and that it would be better for the interface to take the Hessian itself, and then call a subroutine to do a linear solve.

aria 11 years ago | | |

In practice you only need to do $H^{-1} g$; L-BFGS stores the {s_k} and {y_k} vectors which allow you to do the $H^{-1} g$ directly rather than needing to ever form the hessian or its inverse. There are techniques that aren't BFGS-based which approximate the hessian rather than the inverse and in that case you'd be better off solving.