12
$\begingroup$

I have been going through Andrew NG's original data science course on Coursera. I learned the BFGS algorithm at some point in my OR education, but not the Limited Memory version that Andrew NG focuses on.

From a practical point of view, are there some scenarios where it makes sense to use the original BFGS? Usually limited memory means slower computation, but it is not clear to me ML packages even give the user a choice between the two.

$\endgroup$
8
$\begingroup$

If you have enough memory to use the non-limited memory version of BFGS, then, subject to the caveat below that not all BFGS (or LBFGS) implementations are equal, use that in preference to LBFGS (Limited Memory version of BFGS). I.e., a high quality LBFGS implementation may still perform better than a lower quality implementation of BFGS.

Not all BFGS implementations are equal. BFGS specifies only one aspect of the algorithm, and without further elaboration, does not distinguish between, trust region, line search, and unsafeguarded, among many other attributes. Some BFGS implementations require objective function gradient to be provided, while others do not and can use numerical differentiation for the gradient. BGFS implementations vary in what types of constraints they handle. They can markedly vary in the numerical robustness of the algorithm implementation, And they also vary in terms of what, if any, presolve algorithm they employ, which can be very significant if there are complicated and (partially) redundant constraints.

Most machine learning package authors either assume that all nonlinear optimization problems to be solved are so large that LBGS is required in place of BFGS, or they have only ever even heard of LBFGS, so don't know that non-limited memory version of BFGS exists.

Also, BFGS is not the only Quasi-Newton method. SR1 (Symmetric Rank One) is often superior to BFGS on highly non-convex problems. That is because the SR1 Hessian updates do not preserve positive definiteness. Therefore they can better adapt to non-convex and changing curvature, and so provide a better model (approximation) for optimization purposes of the objective function (or more generally, the Lagrangian, if there are nonlinear constraints), which can improve performance of the optimization algorithm.

| improve this answer | |
$\endgroup$
  • $\begingroup$ This answer helps to explain some confusion I had about one of your comments from 2016! For example, with respect to BFGS, I'd see it as simple algorithm that simply lacks stuff like trust regions; not that anyone should use the naked algorithm, but that I'd stop calling it "BFGS" once it's been modified. By contrast, you seem to refer to it as BFGS still, just with implementation-specific variations. $\endgroup$ – Nat Jun 22 '19 at 3:07
  • $\begingroup$ @Nat If BFGS were a car rather than an algorithm, it would be like saying the car has a 4 speed transmission. But of course, that is only one attribute of the car. I stand by all my comments on the thread you linked, although the context for some of them has apparently been lost due to deletion of other comments. $\endgroup$ – Mark L. Stone Jun 22 '19 at 9:19

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.