10
$\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
$\endgroup$
9
  • $\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
    Commented Feb 27, 2017 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
    Commented Feb 27, 2017 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
    Commented Feb 27, 2017 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
    Commented Feb 27, 2017 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
    Commented Feb 27, 2017 at 21:49

2 Answers 2

4
$\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.

$\endgroup$
4
  • $\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
    Commented Feb 27, 2017 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
    Commented Feb 27, 2017 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
    Commented Feb 27, 2017 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.
    Commented Feb 27, 2017 at 23:06
1
$\begingroup$

Think of them as follows (look here for the BFGS update):

BGFS: starting from an initialization $H_0$ (usually a multiple of the identity) a positive definite approximation of the inverse Hessian $H_k$ is constructed at iteration $k$, using the BFGS rank-2 update rule, which then gives the descent direction $-H_k\nabla f(x_k)$.

L-BFGS: given a fixed positive integer $m$, construct the BFGS approximation using the same rules as if the optimization algorithm started at $x_{k-m}$. This requires to keep in memory only information for the past $m$ iterations. Moreover, the inverse Hessian is never constructed as a matrix. The product of a matrix of rank 1 and a vector is computed via a simple scalar product.

Therefore, the two algorithms are basically the same, just that LBFGS is in some sense an approximation of BFGS which uses less memory.

Nevertheless you should expect L-BFGS to work better:

  • BFGS quickly fills up the memory, since either you store a full matrix or you store all gradients starting from the beginning of the optimization.

  • L-BFGS uses O(mn) memory where $m$ is relatively small $m\in [5,20]$ gives good results. Moreover, increasing $m$ too much will not generally help.

This brings us to the main reason why L-BFGS outperforms BFGS: the main point is to approximate the inverse Hessian close to the current iterate, to have second order information which will accelerate the convergence locally.

BFGS keeps the whole optimization history in $H_k$. Information around the initialization $x_0$ is meaningless after a few iterations, but BFGS keeps it nonetheless. L-BFGS will only approximate the inverse Hessian close to the working point and that is exactly what is needed to accelerate the convergence.

Therefore L-BFGS wins in both aspects: memory and inverse Hessian approximation!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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