11
$\begingroup$

The purpose of the paper was to optimize some parameters by maximizing the regularized log-likelihood. Then they calculate Partial derivatives. And then authors mention that they optimize the equation using L-BFGS, a standard quasi-Newton procedure to optimize smooth functions of many variables (no more details).

How does it work ?

$\endgroup$
  • 3
    $\begingroup$ What paper? Put in link to paper Needs a context. Put in links to acronyms, e.g. L-BFGS AND spell them out: L-BFGS = Limited-memory Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm $\endgroup$ – Carl Jun 11 '17 at 4:04
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Limited-memory_BFGS There are many variations, which can differ greatly in capability and performance. $\endgroup$ – Mark L. Stone Jun 11 '17 at 11:25
  • $\begingroup$ hi , thanks mr Mark :) i'll take a look. The paper is cs.stanford.edu/people/jure/pubs/circles-tkdd14.pdf ( equation 6 optimization) $\endgroup$ – Abir Jun 11 '17 at 12:39
  • $\begingroup$ Basically think of L-BFGS as a way of finding a (local) minimum of an objective function, making use of objective function values and the gradient of the objective function. That level of description covers many optimization methods in addition to L-BFGS though. You can read more about it in section 7.2 of springer.com/us/book/9780387303031 . $\endgroup$ – Mark L. Stone Jun 11 '17 at 13:12
  • 1
    $\begingroup$ BFGS is a way to try to get a first order method to mimic a second order method (newton) via the secant method $\endgroup$ – user795305 Jun 11 '17 at 13:26
26
$\begingroup$

Basically think of L-BFGS as a way of finding a (local) minimum of an objective function, making use of objective function values and the gradient of the objective function. That level of description covers many optimization methods in addition to L-BFGS though. You can read more about it in section 7.2 of Nocedal and Wright "Numerical Optimization, 2nd edition" http://www.springer.com/us/book/9780387303031 . A very cursory discussion of L-BFGS is provided at https://en.wikipedia.org/wiki/Limited-memory_BFGS .

First order method means gradients (first derivatives) (and maybe objective function values) are used, but not Hessian (second derivatives). Think of, for instance, gradient descent and steepest descent, among many others.

Second order method means gradients and Hessian are used (and maybe objective function values). Second order methods can be either based on

  1. "Exact" Hessian matrix (or finite differences of gradients), in which case they are known as Newton methods or

  2. Quasi-Newton methods, which approximate the Hessian based on differences of gradients over several iterations, by imposing a "secant" (Quasi-Newton) condition. There are many different Quasi-Newton methods, which estimate the Hessian in different ways. One of the most popular is BFGS. The BFGS Hessian approximation can either be based on the full history of gradients, in which case it is referred to as BFGS, or it can be based only on the most recent m gradients, in which case it is known as limited memory BFGS, abbreviated as L-BFGS. The advantage of L-BFGS is that is requires only retaining the most recent m gradients, where m is usually around 10 to 20, which is a much smaller storage requirement than n*(n+1)/2 elements required to store the full (triangle) of a Hessian estimate, as is required with BFGS, where n is the problem dimension. Unlike (full) BFGS, the estimate of the Hessian is never explicitly formed or stored in L-BFGS (although some implementations of BFGS only form and update the Choelsky factor of the Hessian approximation, rather than the Hessian approximation itself); rather, the calculations which would be required with the estimate of the Hessian are accomplished without explicitly forming it. L-BFGS is used instead of BFGS for very large problems (when n is very large), but might not perform as well as BFGS. Therefore, BFGS is preferred over L-BFGS when the memory requirements of BFGS can be met. On the other hand, L-BFGS may not be much worse in performance than BFGS.

Even at this level of description, there are many variants. For instance, the methods can be totally unsafeguarded, in which case anything goes, and they may not converge to anything, even on convex problems. Or they can be safeguarded. Safeguarded methods are usually based on trust regions or line search, and are meant to ensure convergence to something. Very importantly, just knowing that a method is L-BFGS does not by itself tell you what type of safeguarding, if any, is used. It's kind of like saying that a car is a 4-door sedan - but of course not all 4-door sedans are the same in performance or reliability. It is just one attribute of an optimization algorithm.

$\endgroup$
  • 1
    $\begingroup$ Hi mark, i need your help again , could you tell me briefly the difference between newton and quazi newton methods ?? thanks $\endgroup$ – Abir Jun 18 '17 at 23:17
  • 3
    $\begingroup$ Newton methods calculate the Hessian matrix, "by scratch", at each iteration of the algorithm, either exactly, or by finite-differences of the gradient at that iteration.. Quasi-Newton methods build up an approximation of the Hessian matrix by using the gradient differences across iterations. There are many different ways of doing this, giving rise to a variety of different Quasi-Newton methods, such as BFGS, DFP, SR1, and others. Usually Newton methods require a large amount of compjuting at each iteration to calculate the Hessian, much more computing per iteration than Quasi-Newton methods. $\endgroup$ – Mark L. Stone Jun 18 '17 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.