What’s the run length measured in? Function evaluations or wall clock time?
1 Like
Number of function evaluations. In the original benchmark they go up to 1e7, but this takes already took like 20 minutes to run.
That’s very interesting. Could you please share the benchmarking code?
Did you use the fastpowers branch of IntervalArithmetic.jl? That should give a huge speedup.
My script is here (need master, my PR of IntervalOptimisation and a couple of other packages, like BlackBoxOptim.jl).
I just tried the fastpowers branch but I’m getting this :
julia> minf, minx = minimise( x->sum(abs2.(x)), IntervalBox(-5.5..5.5, 3) )
ERROR: MethodError: no method matching +(::Interval{Float64}, ::RoundingMode{:Down})
Closest candidates are:
+(::Any, ::Any, ::Any, ::Any...) at operators.jl:502
+(::PyObject, ::Any) at /Users/jbieler/.julia/packages/PyCall/ttONZ/src/pyoperators.jl:13
+(::Interval) at /Users/jbieler/.julia/packages/IntervalArithmetic/19YeJ/src/intervals/arithmetic.jl:65
...
Stacktrace:
[1] +(::Interval{Float64}, ::Interval{Float64}, ::RoundingMode{:Down}) at ./operators.jl:502
[2] +(::Interval{Interval{Float64}}, ::Interval{Interval{Float64}}) at /Users/jbieler/.julia/packages/IntervalArithmetic/19YeJ/src/intervals/arithmetic.jl:85
[3] macro expansion at /Users/jbieler/.julia/packages/StaticArrays/1g9bq/src/mapreduce.jl:103 [inlined]
[4] _mapreduce at /Users/jbieler/.julia/packages/StaticArrays/1g9bq/src/mapreduce.jl:95 [inlined]
[5] _reduce at /Users/jbieler/.julia/packages/StaticArrays/1g9bq/src/mapreduce.jl:204 [inlined] (repeats 2 times)
[6] #sum#275 at /Users/jbieler/.julia/packages/StaticArrays/1g9bq/src/mapreduce.jl:229 [inlined]
[7] sum(::StaticArrays.SArray{Tuple{3},Interval{Interval{Float64}},1,3}) at /Users/jbieler/.julia/packages/StaticArrays/1g9bq/src/mapreduce.jl:229
[8] (::getfield(Main, Symbol("##21#22")))(::StaticArrays.SArray{Tuple{3},Interval{Float64},1,3}) at ./REPL[9]:1
[9] #minimise#1(::Type, ::Float64, ::Float64, ::Function, ::getfield(Main, Symbol("##21#22")), ::IntervalBox{3,Float64}) at /Users/jbieler/.julia/dev/IntervalOptimisation/src/optimise.jl:41
[10] minimise(::Function, ::IntervalBox{3,Float64}) at /Users/jbieler/.julia/dev/IntervalOptimisation/src/optimise.jl:22
[11] top-level scope at none:0
1 Like
Sorry, make that the nonrecursive_powers branch then.
That branch is almost 10x faster indeed. I went a bit further with the number of iterations and IntervalOptimisation does very well.
1 Like
Wall-clock time would arguably be more interesting than number of function evaluations for the end user?
1 Like
Wall-clock time depends on the error function (here they are very fast compare to real world cases), so it’s better to count the number of function evaluation and to measure the overhead of the algorithm separately.
For the methodology I’m mostly following : https://coco.gforge.inria.fr/COCOdoc/bbo_experiment.html
3 Likes
Yeah, but isn’t this case a bit different since the function itself takes longer to evaluate due to the intervals? For most other optimization algorithms the function evaluation takes a fixed amount of times, but called with intervals, this is not true.
To be fair, the number oräf arithmetic operations required to propagate intervals through the function compared to a simple floating point value should be reflected in the results somehow.
4 Likes
I agree, the reason why you usually report f-calls is because it’s assumed to be the same. It’s not exactly the same, but it would be like comparing accuracy of a Float64 and Bigfloat run and only counting number of calls. I’m still impressed by the quality of the interval method, but it could potentially be much more expensive (especially in higher dimensions I think?)
2 Likes
It’s higher dimensions, and the expense scale with the condition of the method. The more ill-conditioned the f is, the more divides it needs to do, until it needs to start using BigFloats due to the blow up speed. I think it might be safe to say though that if intervals work on someone’s problem, it should be preferred though.
I agree it’s an awesome technique, but if you look at that plot, then time per f does matter. They appear to be “equally expensive”, but it’s not clear that that is true. Look at D: 6, 1:14 for example. They seem to be equally good for a high value of run length, but it’s not clear to me if 1e4 for BBO is equivalent to 1e3 for IO or if it’s 1e2? If it’s the latter, then BBO seems to take the lead. That’s why wall time would be a nice supplement.
Also, is it possible that IO is better without NelderMead?
It does pretty badly if I don’t chain it into NelderMead ; it gets close to the global minimum but final convergence doesn’t seem very good. That said that depend on the metric you use to measure performance.
For the runtime I noticed that it increases non-linearly with the number of iterations, which means that indeed it will become an issue at some point :
julia> f = BBOB.F15
Rastrigin Function
plot(
y = [@elapsed minimise(f, IntervalBox(-5.5..5.5, 6), f_calls_limit = calls ) for calls in 10:1000:10_000],
Geom.line, Guide.ylabel("Runtime [s]")
)
What do you mean by “chain it into melder mead”?
I agree that interval evaluations are more expensive - maybe 10 times more expensive than standard floating point to evaluate a given f (though that of course depends what f looks like and it would be good to benchmark that carefully).
At the end of the optimization I run a NelderMead starting from the minimum and using a % of the function evaluation budget. That allows algorithms that have good global properties but poor final convergence to have decent performance in the benchmark.
3 Likes
That should hopefully be fixable using the “mean-value form”.
Basically interval optimization suffers from a “cluster effect”, where you start producing more and more small boxes near the minimum.
If the function is differentiable then using a 1st-order Taylor approximation fixes this problem.
Which test function did you use?
1 Like
In the plots above I’ve used 14 test functions from the BBOB set. To check the final convergence one should plot the function value in function of the number of iterations, some algorithms do good initially but then slow down and reach a plateau while other continue to decrease at a faster pace.
This might inform somewhat. For example, is SHGO in Julia yet?
You can always call the Scipy version via PyCall. Unless you are optimizing an extremely cheap function, the inter-language call overhead is probably irrelevant.
1 Like