7
$\begingroup$

I am trying to implement an optimization procedure in Python using BFGS and L-BFGS in Python, and I am getting surprisingly different results in the two cases. L-BFGS converges to the proper minimum super fast, whereas BFGS converges very slowly, and that too to a nonsensical minimum.

QUESTION: From my readings, it seems to me that BFGS and L-BFGS are basically the algorithm (quasi-Newton methods), except that the latter uses less memory, and hence is faster. Is that true? Otherwise, if they are more different, then how so?

Ultimately, I want to figure out if the difference in performance is due to some differences in the actual algorithms, or due to their implementation in the python SciPy modules.

EDIT: I am adding some data to support my claims of divergent behaviour from the two algorithms.

 RUNNING THE L-BFGS-B CODE

       * * *

Machine precision = 2.220D-16
N =          147     M =           10
This problem is unconstrained.

At X0         0 variables are exactly at the bounds
At iterate    0    f=  2.56421D+04    |proj g|=  1.19078D+03
At iterate    1    f=  2.12904D+04    |proj g|=  1.04402D+03
At iterate    2    f=  1.49651D+03    |proj g|=  2.13394D+02
At iterate    3    f=  6.08288D+02    |proj g|=  9.85720D+01
At iterate    4    f=  2.91810D+02    |proj g|=  6.23062D+01
...
At iterate  142    f=  3.27609D+00    |proj g|=  8.80170D-04
Time taken for minimisation: 36.3749790192


*** BFGS code ***

At iterate    1,  f= 21249.561722 
At iterate    2,  f= 15710.435098 
At iterate    3,  f= 15443.836262 
At iterate    4,  f= 15386.035398 
At iterate    5,  f= 15311.242917 
At iterate    6,  f= 15211.986938 
At iterate    7,  f= 15022.632266
...
At iterate  524,  f= 67.898495
...
Warning: Desired error not necessarily achieved due to precision loss.
Iterations: 1239
Time taken: 340.728140116
|cite|improve this question
$\endgroup$
  • $\begingroup$ L-BFGS is quite literally an approximation of BFGS that uses less memory, so you may expect that it converges slower. However, as both are approximations in a sense, it is possible that L-BFGS is 'lucky' for your particular input. Another option is your machine has a severe memory bottleneck when running BFGS, but not for L-BFGS. So if none of the algorithms have any strange behaviour independent of each-other, you simply lack data to make a claim that one particular implementation performs poorer than the other. $\endgroup$ – Discrete lizard♦ Feb 27 '17 at 19:51
  • $\begingroup$ @Discretelizard, I have shared some data that shows how BFGS and LBFGS progress for my function starting from some initial condition. Notice how the function value decreases by order of magnitude for LBFGS within a few iterations, but has dropped only slightly for BFGS. My question is basically about why there could/should be such a large discrepancy in search behaviour? $\endgroup$ – ap21 Feb 27 '17 at 21:17
  • $\begingroup$ Well, both approximate the 'best path' to find an optimum, so their performance could differ in a large amount of data-sets. To get a precise answer, you could check if/why the method from L-BFGS yields a much better gradient descent step for this particular function. I think a visualisation of the solution space showing the 'path' from both methods would be useful to get an idea what is going on. $\endgroup$ – Discrete lizard♦ Feb 27 '17 at 21:29
  • 1
    $\begingroup$ Consider using a lower dimensional solution space. If you're really interested in the behaviour of these algorithms in your specific function, you really have to use the details of the function (e.g. is the function convex, polynomial, linear, discontinuous, etc. ) and the solution space (Is it $\mathbb{R}^n$, a convex set, a polyhedron, etc.), as I doubt an generic condition about the relative quality of these methods on arbitrary functions exists. $\endgroup$ – Discrete lizard♦ Feb 27 '17 at 21:37
  • 2
    $\begingroup$ No, that is the opposite what I'm saying. BFGS and LBFGS can theoretically converge to completely different solutions (if there are multiple local minima) with different convergence speeds, depending on how you choose the function and solution space. So, if you want to make the claim that the implementation has limitations, you should test a large amount of different functions and solution spaces. $\endgroup$ – Discrete lizard♦ Feb 27 '17 at 21:49
2
$\begingroup$

No, they're not the same. In some sense, L-BFGS is an approximation to BFGS, one which requires a lot less memory. BFGS and L-BFGS are explained in great detail in many standard resources.

Very crudely, you can think of the difference like this. BFGS computes and stores the full Hessian $H$ at each step; this requires $\Theta(n^2)$ space, where $n$ counts the number of variables (dimensions) that you're optimizing over. L-BFGS computes and stores an approximation to the Hessian, chosen so that the approximation can be stored in $\Theta(n)$ space. Effectively, L-BFGS uses the approximation $H \approx M^\top M$ for some $k \times n$ matrix $M$ (I think).

Each step of L-BFGS is an attempt at approximating/guessing what the corresponding step of BFGS would do. However, a single step of L-BFGS takes a lot less space and time than a single step of BFGS. Consequently, you can do many more steps of L-BFGS within a particular time bound than BFGS. Therefore, you might find that L-BFGS converges faster, because it can do so many more iterations within a given amount of time than BFGS can.

I don't know what a nonsensical minimum means, or why BFGS would converge to something worse than L-BFGS if both were allowed to run for an unbounded amount of time.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Please look at the following links. The nonsensical minimum given by BFGS -- plot.ly/~apal90/162 -- and the good minimum (a cylinder) given by LBFGS -- plot.ly/~apal90/160. $\endgroup$ – ap21 Feb 27 '17 at 21:28
  • $\begingroup$ What you are saying is that BFGS and LBFGS should theoretically converge to the same solution, time being no barrier, right? Then we are really looking at limitations of the implementation of algorithm in SciPy, right? $\endgroup$ – ap21 Feb 27 '17 at 21:36
  • $\begingroup$ L-BFGS works better on this instance, even with the same amount of iterations. So L-BFGS having faster iterations does not explain the difference here. $\endgroup$ – Discrete lizard♦ Feb 27 '17 at 21:43
  • 1
    $\begingroup$ @Discretelizard, you are quite right. The detailed information about the two runs wasn't available when I wrote my answer, so I was guessing -- and it looks like my guess wasn't correct. I don't know why ap21 is seeing the behavior listed in the question. Hopefully someone else will be able to provide a better answer. $\endgroup$ – D.W.♦ Feb 27 '17 at 23:06

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.