# How does the number of function calls in BFGS scale with the dimensionality of space?

## Question

Is there any estimate for the scaling of the number of function calls in BFGS-optimization with the dimensionality of the search space? Specifically I am assuming a (free) expression for the gradient is supplied by the user so that no function calls are made in its evaluation.

Note the gradient is only available for free if the function at that point has already been computed. This is due to an analytical trick. I am also not interested in any of the scaling of the manipulations that are done in the BFGS algorithm. Again I consider those free compared to the function calls.

Are there theorems that, given some conditions, guarantee a certain space complexity? Is there experimental data on this for some examples? What would be search terms to look for to find this kind of data?

All scaling seems to focus on the computational steps in the optimization algorithm and not on the scaling of the number of function calls. In my case a single function call is orders of magnitude more expensive than any and all other manipulations in a full optimization run added together.

## Details

I am looking to find a local minimum, it does not have to be the global minimum. I am interested in continuous functions that are also (twice) differentiable. (At least generically, at worst they might be piece-wise linear at some points. But I am of course also interested in examples in better behaved fully differentiable functions.)

• The conditioning of the problem is a critical factor that needs to be taken into account. Apr 12, 2021 at 17:56
• I would say that your question is too general and a complete answer cannot be given without further information regarding your objective function. The examples given in the answer of @Infinity77 are really nice, but keep in mind that Rosenbrock's function becomes more ill conditioned as the dimension increases. As the previous comment says, the conditioning of the problem is critical. Theoretically, if the condition number of the Hessian does not deteriorate when the dimension increases, the number of iterations should not increase too much. Taking a look at the quadratic case might help. Apr 14, 2021 at 21:06
• @Beni, I disagree a bit. The question is explicitly about whether there is some kind of generic estimate and I think that kind of question is extremely important to have on this stackexchange. For my problem I don't have a specific function in mind but a class of (very complicated and expensive so I cannot give an example) functions. If the answer really is that no prediction of any use can be made than that is a very useful answer as well. Based on the answer by Infinity77 I do not think this is the case. It seems that generically the scaling is not terrible. cont'd ... Apr 15, 2021 at 7:56
• @Beni, if you have a counter example to this scaling that would be much appreciated as well. I understand that the conditioning number has to do with how much the function changes under a small change. I don't know whether there is an easy or useful answer for this. BFGS should be scale invariant after a sufficient number of steps so what does small even mean exactly, I guess with respect to the space I actually want the BFGS to explore. Anyway I am happy to add more data on the type of functions I have in mind if requested. I saw I did not add any information on continuity so I will add that. Apr 15, 2021 at 8:00
• @Beni, Also what do you mean about the Rosenbrock's function becoming more ill-conditioned. Does that not give additional evidence in favor of the scaling behaviour being generic. The Rosenbrock function shows linear scaling for a large range of dimensions. You also say it is both well-conditioned (for a low dimensionality) and ill-conditioned (for a large dimensionality). Both show linear scaling so it seems that the ill-conditioning itself is not that much of a problem then. Do you agree? Apr 15, 2021 at 8:02

That very much depends on your objective function. If you know that your objective function is highly multi-modal and complex, then BFGS is only going to give you a local minimum. If that is enough for you, then all is good. Otherwise - if you need a global optimum or simply an extremely good local minimum/maximum, then the problem becomes much more intractable as you're looking at using global optimization algorithms. Depending on the size of your problem - in terms of number of variables - it can range from relatively simple to almost impossible to locate a global optimum. On the other hand, convex objective functions shouldn't pose any difficulty on BFGS (or other algorithms) in any dimension.

That said, if we consider the BFGS method against a relatively common test function (the Rosenbrock or "Banana" function), we can take a look at this code:

import numpy as np
import scipy.optimize as optimize
import matplotlib.pyplot as plt

def rosen(x):
global fun_calls
fun_calls += 1
return np.sum(100.0*(x[1:] - x[:-1]**2.0)**2.0 + (1 - x[:-1])**2.0)

xm = x[1:-1]
xm_m1 = x[:-2]
xm_p1 = x[2:]
der = np.zeros_like(x)
der[1:-1] = 200*(xm-xm_m1**2) - 400*(xm_p1 - xm**2)*xm - 2*(1-xm)
der = -400*x*(x-x**2) - 2*(1-x)
der[-1] = 200*(x[-1]-x[-2]**2)
return der

def main():

global fun_calls
nvars = np.arange(2, 101)
nfuns = []

for n in nvars:

x0 = -3.14159265*np.ones((n, ))
lb = -5.0*np.ones_like(x0)
ub = 10.0*np.ones_like(x0)
bounds = zip(lb, ub)
fun_calls = 0
out = optimize.fmin_l_bfgs_b(rosen, x0, fprime=rosen_gradient, maxfun=10000)
nfuns.append(fun_calls)

m, q = np.polyfit(nvars, nfuns, 1)
fig = plt.figure()
ax.plot(nvars, nfuns, 'b.', ms=13, zorder=1, label='Function Calls')
ax.plot(nvars, nvars*m+q, 'r-', lw=2, zorder=2, label=r'Fit: $$y = %0.2f\cdot x + %0.2f$$'%(m, q))

ax.grid()
ax.set_xlabel('Problem Dimension', fontsize=16, fontweight='bold')
ax.set_ylabel('Function Calls', fontsize=16, fontweight='bold')
ax.set_title('Rosenbrock Function', fontsize=18, fontweight='bold')
plt.show()

if __name__ == '__main__':
main()



This code will produce this picture (at least for me): Note that I have provided also the gradient of the objective function. This picture will of course vary depending on the function itself. There are also test objective functions in the literature for which the global optimum becomes exponentially more difficult to find as the dimension increases. That said, the curse of dimensionality is almost unavoidable in nonlinear optimization.

EDIT

I have done some more tests, just for fun, with other test functions. I don't have analytical gradients for those but I used the Python package autograd (https://github.com/HIPS/autograd) to get them (and carefully counting which objective evaluations come from L-BFGS-B and which ones from autograd).

Surprise surprise: there is not that much of a pattern: 2D representation of the test functions from my work on Global Optimization:

Wavy

Alpine

Brown

DixonPrice

Griewank

Enjoy :-)

• Thank you! This is the kind of thing I was looking for! I understand that it is function dependent but I would like to get a generic idea of an estimate for which I think this is an appropriate test function. (And I am satisfied with finding a local minimum. I will add that to the question.) The fact that this scales linearly is really promising! Apr 13, 2021 at 12:44
• You're welcome :-) . Please keep in mind that I have only tested this with one objective function (Rosenbrock), so I'd be careful to generalize to all problems and say that BFGS "scales linearly". It may well be the case, but I am not aware of any literature regarding this (but I am sure it exists) and the experimental data I provided is extremely limited... Apr 13, 2021 at 13:09
• Thank you for adding more examples. To me there does seem to be a pattern. All examples look like they scale linearly at worst (or at least definitely less than quadratically). It is funny that finding a minimum becomes easier in the Griewank function, but perhaps there are simply more minima so that there is one closer to the initial point. (The functions I am interested in minimizing look more like the Rosenbrock, Brown and DixonPrice functions.) Apr 14, 2021 at 9:44