# BFGS vs L-BFGS — how different are they really?

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

• 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. – Discrete lizard Feb 27 '17 at 19:51
• @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? – ap21 Feb 27 '17 at 21:17
• 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. – Discrete lizard Feb 27 '17 at 21:29
• 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. – Discrete lizard Feb 27 '17 at 21:37
• 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. – Discrete lizard Feb 27 '17 at 21:49

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).