## 3 Literature Review and Related Work
### Learning Approaches for Parameter Tuning
#### 3.2.1 Racing  
[PERSON] [4] argued that a brute-force approach is clearly not the best solution for solving the parameters tuning problem. A more refined and efficient way to perform metaheuristics tuning can be achieved by streamlining the evaluation of candidates and releasing those who appear to be less promising during the evaluation process. This statement summarizes the racing approaches applied to the parameters tuning of combinatorial optimization techniques (Figure 2). The information that follows is based on [4; 39]. In the 1990s, [PERSON] and [PERSON] [54] proposed the Hoeffding race method, in order to speed up the selection of models in supervised learning problems. Hoeffding race adopted a statistical test based on the formula of Hoeffding [55], concerning the confidence in the empirical average of \(k\) positive numbers, whose sample is used independently from the same distribution. However, the Hoeffding race adopts a non-parametric test, even if the adopted test needs knowledge of a limit on the observed error, and this aspect reduces significantly the range of applications of the method. Despite this fact, the idea behind racing approaches is very appealing. [PERSON] and [PERSON] [56] proposed some algorithms based on different statistical tests. Among them, BRACE is based on Bayesian statistics and implements a statistical technique known as blocking [44; 57; 58]. A block plan is an experimental definition that is possibly adopted when two or more candidates have to be compared. Blocks improve that comparison accuracy. A block is a set of relatively homogeneous experimental conditions under which all the candidates are tested. In the best candidate selection context, the adoption of block plans is particularly natural and simple: each survivor candidate is tested in the same examples, and each instance is therefore a block in the considered plan. The statistical test adopted in BRACE is equivalent to the paired \(t\)-test [59] performed between each pair of survivor candidates. Contrary to the test adopted in Hoeffding race, the \(t\)-test is a parametric process and therefore is based on some assumptions concerning stochastic variables. BRACE proved to be very effective and is reported as capable of achieving better results than the Hoeffding race [54; 56]. The F-race method [27] is a racing approach that integrates into a single algorithm the best features of Hoeffding race and BRACE. As already mentioned, Hoeffding race adopts a non-parametric approach but does not consider blocking. On the other hand, BRACE adopts blocking but discards the non-parametric definition by a Bayesian approach. F-race is based on the Friedman test (Friedman two-way analysis of variance by ranks) that implements a block plan in an extremely natural manner and is, at the same time, a non-parametric test [44]. To give a description of Friedman test, let us assume that F-race reached step \(k\), where there are still \(k-1\) configurations in the run. The [PERSON] test assumes that the observed costs for the candidates still in the race are \(k\) mutually independent random variables, called blocks. Each block corresponds to the computational results in an instance for each configuration still in the race at step \(k\). Figure 2: Graphical representation of the computational effort by racing vs. brute force approaches executing a number of instances over a number of candidates [4]. The dashed line represents the computational effort of brute force approaches. The gray curve represents the computational effort of racing approaches. [PERSON] [4] described that, in addition to the [PERSON] test, the Wilcoxon test (Wilcoxon matched-pairs, signed-ranks) can be used [44] when there are only two candidates in the run, since it has proven to be more robust and efficient. In F-race, ranking plays an important dual role. First, it is connected with the non-parametric nature of the ranking based test.