Help needed to understand Fig. 2 in "Benchmarking the Nelder-Mead..." by Nikolaus Hansen (2009)

[aabbtree77]

I struggle to interpret Fig. 2 in

Benchmarking the Nelder-Mead Downhill Simplex Algorithm
With Many Local Restarts (2019).

Example: In subfigure on F23 Katsuuras I see that Nelder-Mead (NM) reaches the targets delta = 1 and 1e-1 in D=40, but what is fopt? How bad is NM here?

Randomly sampled values of various BBOB-2009 functions are above O(1e3) and often even above O(1e6), while fopt is O(10) or O(100), which would imply such deltas (absolute errors) nearly solve the problem.

So I understand the diffiuclty with relative errors is that if fopt is tiny we get into nonsense, but reporting absolute error for wildly varying cost value also does not tell how well the method is solving the problem. What does an absolute error of unity mean? On F23, F10...

For someone to design a benchmark, would you recommend fixing fopt to some larger value, like CEC-2017 did with f1=100, f2=200, f11 = 1100... so that one can report relative errors?

[nikohansen]

The value of fopt is i) somewhat arbitrarily sampled per instance and ii) irrelevant when we know the target delta. Dividing by fopt to get a relative error is not a meaningful operation here, to all I can see.

What does an absolute error of unity mean? On F23, F10...

What an absolute error means is determined by the function definition. All these functions are "artificial" test functions. There is not really any deeper "meaning". Sometimes, the error is roughly the square of the distance to the optimum, sometimes a Mahalanobis distance.

Characterizing "the meaning" of a sublevel set generally requires either knowledge of the function topography or performance data.

For someone to design a benchmark, would you recommend fixing fopt to some larger value, like CEC-2017 did with f1=100, f2=200, f11 = 1100... so that one can report relative errors?

No. To all I can see, there is no advantage to report relative errors by dividing by fopt. We could set fopt=1. Nothing would change, but we would by definition report relative errors.

A generic way to deal with the lack of semantics of (target) f-values would be to consider their sublevel set volumes, or equivalently, the performance of "pure" uniform random search. Tobias Glasmachers and Olaf Mersmann have, independently, suggested this idea before.

[aabbtree77]

I think you are slightly overcomplicating matters here.

Relative errors work very well, except when fopt is epsilon due to division problems, which we can avoid by design.

For instance on tougher functions like F24 BBOB-2009 a strong algorithm will go below 10%, and the outstanding ones will get below 1%. This is also the case in an entire CEC-2017. The best ones (BIPOP, ARRDE) will go below 10%, but on F20 - F30 nothing goes below 1%, except the ARRDE on F24 which is fascinating.

Relative error is a clear and pragmatic way. Below 10% - we have optimization case, not "Bayesian optimization", 1% - problem solved for all the practical purposes. At least this differentiates extremely well endless algorithms on entire BBOB-2009 and CEC-2017.

Random sampling as a reference is not so good as it will be a million times the optimal value on F10 BBOB-2009 and it will be a thousand times the optimal value on F24 BBOB-2009. I understand that you want to encode real structure and distance to these values ideally, but pragmatically speaking, if the solution is within bounds and the cost is 1% from the optimum, we cover most practical problems on the planet Earth and solve the energy crisis, except may be not in trading/arbitrage where it simply matters who is quicker.

The problem is that when I look at Fig. 2 for Nelder-Mead, it looks like it's still in the game, reaching some targets, but we know it's completely incapable to optimize anything in these Rastrigins and is generally a very weak algorithm like most of what is out there, including entire Powell, MCS, Nomad...

So on CEC-2017, I can quickly communicate something, like hey I got 2500 with BIPOP on F24, and this acts like mnemonics, people understand it is not yet 2400, but decent, 4% rel error, while you provide a lot of details in that Figure 2, but a) very hard to see what absolute error 1 or 1e-1 is giving us (nothing), and b) it's just too much effort for no real gain.

If you give me an algorithm which reaches 1% rel error on F20-F30 CEC-2017, I know it's the 21st century progress. When I test anything I try it first on F24 CEC-2017 and I immediately know where we are standing. ARRDE 1st, BIPOP 2nd. A similar picture on F25 except ARRDE does not get below 1% there. Nothing does, so again I know when an improvement comes some day, it's quick and easy to spot, no need for all this bureaucracy.

Basically if it is a good DFO algorithm, it will be immediately visible on F24 CEC-2017 alone as it should get zero error. If it's weaker, then it should go below 5% like BIPOP, otherwise we are not even in the 21st century.

[nikohansen]

Relative errors work very well, except when fopt is epsilon due to division problems, which we can avoid by design.

You probably don't realize that fopt can also be negative. Also, fopt can be zero. fopt=0 is actually the standard scenario in the optimization literature and indeed preferable from the performance analysis point of view. Then, the f-values are $\Delta f$-values to the optimum. This is one reason why the BBOB assessment subtracts fopt in each instance such that the optimal "normalized" f-value becomes zero. fopt is only nonzero to prevent algorithms from exploiting this f-value property.

On the other hand, it does make some sense to interpret the achieved "target" values relative to the value of $f(0) - f_{\text{opt}}$. Indeed, considering the relative improvement over $x_0$,

$$\frac{f(x_t) - f_{\text{opt}}}{f(x_0) - f_{\text{opt}}}$$

is also an established standard in the optimization literature. Typical targets for this expression are like $10^{-3}$ or $10^{-6}$. For the BBOB problems, using $x_0=0$ seems to make most sense (its typical value is around $f_{\text{opt}} + 100$ but it may be $<f_{\text{opt}} + 1$ or $>f_{\text{opt}} + 10^7$ and can substantially vary between instances of the same function). The relative improvement is limited in that this may somewhat ignore variables with low sensitivity and thereby ignore the inherent nature of some of the problems.

[...] if the solution is within bounds and the cost is 1% from the optimum, we cover most practical problems on the planet Earth

The function value can not be, in general, equated with some actual cost. The value may be more often than not monotonous in some actual cost, but the required monotonous transformation makes all the difference.

When I test anything I try it first on F24 CEC-2017 and I immediately know where we are standing. [...]
Basically if it is a good DFO algorithm, it will be immediately visible on F24 CEC-2017 alone as it should get zero error.

Evaluating an algorithm on a single function is a pretty limited assessment methodology.