Maximum Budget setting and elitist version of irace

[melch...@gmail.com]

Good evening,

what follows is a list of few questions I have about the settings and the scheme of irace. 

It is really important to me to understand them in order to make use of this tool in the best way to tune the parameters of an algorithm of mine.

1. Experiments Budget: By now this is the only irace parameter I am tuning by myself and I see it has many implications (the budget for each iteration and the number of candidate configurations for each iteration are derived from it). In my case I was thinking to set the Budget to 1000 having 3 types of parameters to tune with irace, each of them able to take only 3 different values (so the space of total configurations has 27 elements). Accordingly with some irace papers at the first iteration (among 3 expected) the number of candidate configurations would result 55. Is this setting correct? 55 is greater than the total space of 27 combinations. What will irace do in this case? Will it start by executing the first instance 55 times repeating configurations? Will it be more correct to set another value of the Budget (for example 500 or 200) in order to have a set of candidate configurations smaller than/equal to the cardinality of the configuration space?
2. Irace Running time: Is it right that an estimation of the computational time required by a call of irace is given by (Experiments Budget)*(CPU time for each call of the algotihm/target-runner) ? Does the elitist version of irace take more time because of the need of re-evaluating configurations on previous instances? Or is the time always bounded by the iteration budget?
3. Elitist: by default is activated. Do you have suggestions about when it could be better to deactivate it? What is its potential?

Thank you so much for your availability,

A.

[Manuel López-Ibáñez]

On 10/08/17 21:08, melch...@gmail.com wrote:
> what follows is a list of few questions I have about the settings and the
> scheme of irace.
>
> It is really important to me to understand them in order to make use of this
> tool in the best way to tune the parameters of an algorithm of mine.

Dear Anna,

Just to point out that there is a tutorial on irace
(http://iridia.ulb.ac.be/irace/files/irace-comex-tutorial.pdf) for an older
version but describes the main ideas at an introductory level.

The up-to-date user guide also contains a step-by-step tutorial and very
detailed answers:
https://cran.r-project.org/web/packages/irace/vignettes/irace-package.pdf

And the more formal details about the irace algorithms are described in the ORP
journal paper: http://dx.doi.org/10.1016/j.orp.2016.09.002


> 1. *Experiments Budget*: By now this is the only irace parameter I am tuning

> by myself and I see it has many implications (the budget for each iteration
> and the number of candidate configurations for each iteration are derived
> from it). In my case I was thinking to set the Budget to 1000 having 3
> types of parameters to tune with irace, each of them able to take only 3
> different values (so the space of total configurations has 27 elements).
> Accordingly with some irace papers at the first iteration (among 3
> expected) the number of candidate configurations would result 55. Is this
> setting correct? 55 is greater than the total space of 27 combinations.
> What will irace do in this case? Will it start by executing the first
> instance 55 times repeating configurations? Will it be more correct to set
> another value of the Budget (for example 500 or 200) in order to have a set
> of candidate configurations smaller than/equal to the cardinality of the
> configuration space?

Unfortunately, it is really hard to give advice on how much budget you should
use since this depends on the difficulty of the tuning landscape and the
heterogeneity of the instances. Research on this is at its infancy and I'm not
aware of any research on budget estimation / stopping rules for irace. Our
rules of thumbs are very rough. Usual values range from 1000 for small number
of parameters to 100K for very large ones.

Currently, irace does not try to detect whether all possible configurations can
be evaluated for the given budget, thus, the initial random sampling performed
by irace may generate repeated configurations and/or never generate some
configurations, which is not ideal. The ideal approach in such cases is to
provide all configurations explicitly to irace and execute a single
race (nbIterations=1). Hopefully, a future version of irace will automatically
detect this case and switch to basic racing.


> 2. *Irace Running time: *Is it right that an estimation of the computational
> time required by a call of irace is given by/ (Experiments Budget)*(CPU
> time for each call of the algotihm/target-runner/) ? Does the elitist

> version of irace take more time because of the need of re-evaluating
> configurations on previous instances? Or is the time always bounded by the
> iteration budget?

The estimate is roughly correct, however, irace still consumes some extra CPU
time (R is sometimes very slow) and parallel execution may produce slowdowns in
some environments (See --load-balancing). We print the wall-clock time (W time)
that it takes to evaluate configurations on each instance and a time-stamp at
each step of irace. If you notice irace taking more time than expected, we
would like to know the details.

The elitist version never re-runs elite configurations on already seen
instance-seed pairs, however, if the number of instances is small, the same
"instance" may be sampled with a different seed, which irace treats as a new
instance. In short, no, the elitist version should not take more time.

> 3. *Elitist: *by default is activated. Do you have suggestions about when it

> could be better to deactivate it? What is its potential?

We hope the elitist is better most of the time and it fixes some undesirable
behavior of the non-elitist one, this is why we developed it and why it is the
default. The full rationale can be found in the ORP paper. However, we noticed
that in some scenarios it does not make a difference. Moreover, with some
recent artificial benchmarks, it appears to perform worse in some cases if we
also change some other internal parameters of irace, but we need to investigate
exactly what is going on there. As irace is a heuristic method, the elitist
version may be unlucky in some runs while the non-elitist may be lucky in others.

If you have the time to do the experiments, we will be extremely interested in
real-world tuning scenarios where the elitist version consistently performs
worse than the non-elitist. If you notice that, please let us know.

I hope this answers all your questions.

Cheers,

Manuel.