# Sampling Effects on Algorithm Selection for Continuous Black-Box Optimization
## 5 Selector Validation  
Given the data-driven nature of the ELA features, the randomness and size of the input sample used to calculate may also affect accuracy. Therefore, through the validation process we aim to answer the following questions:  
* Does the selector's accuracy increases with the size of the sample used to calculate the ELA features? * What is the effect of the sample randomness on the selector performance? The validation process is based on the Hold-One-Instance-Out (HOIO) and Hold-One-Problem-Out (HOPO) approaches proposed by [PERSON] et al. [2]. For HOIO, the data from one instance of each problem at all dimensions is removed from the training set. For HOPO, all the instances for one problem at all dimensions are removed from the training set. HOIO measures the performance for instances of problems previously observed; whereas HOPO measures the performance for instances of unobserved problems. To answer **Q1**, we train 30 different models for each validation approach, and average the performance over them. We use a cost-sensitive Random Forest (RF) classification model with 100 binary trees, which weighted each observation according to the difference in performance between algorithms [48] as BCs. The performance is measured for each value of \(n\) in terms of the success, best and worst-case selection, and total failure rates. The Success Rate (\(SR\)) is the percentage of solved problems by the selector; the Best Case Selection Rate (\(BCSR\)) is the percentage of problems for which the best algorithm was selected; the Worst-Case Selection Rate (\(WCSR\)) is the percentage of problems for which the worst algorithm was selected; and the Total Failure Rate (\(TFR\)) is the percentage of unsolved problems due to selecting the worst performing algorithm. To summarize the efficiency and accuracy results of the selector, we define a normalized performance score, \(\rho_{a_{T}}\), as follows:  
\[\rho_{a_{T}}(F,\alpha,e_{t})=\frac{\overline{T}(F,\alpha_{T},e_{t})}{SR(F, \alpha_{T},e_{t})}\cdot\frac{SR(F,\alpha,e_{t})}{\overline{T}(F,\alpha,e_{t})} \tag{5}\]  
Figure 4: Instance evaluation procedure. An input sample \(\textbf{X}\in\mathcal{X}\) is evaluated in all the problem instances \(f_{i,j},i=1,\dots,24,j=1,\dots,15\), where \(i\) is the function index, and \(j\) the instance index. The result is an output sample \(\textbf{Y}_{j,j}\in\mathcal{Y}\). The procedure guarantees that the differences among measures only depend on the output sample. where \(\alpha_{T}\) is a baseline algorithm for which \(\rho_{\alpha_{T}}=1\). For our cases, the baseline algorithm will be the BBLL portfolio with random selection, \(\rho_{\text{RB}}\). Once we have verified that the architecture of the selector produces satisfactory results, we address **Q2**. To do this, we estimate the empirical probability distribution of each feature, \(\widehat{pr}(c_{k})\). There are multiple approaches to this problem. For example, to take multiple, independent trial sets per function [17], which guarantees the most accurate estimator of \(\widehat{pr}(c_{k})\), although with the substantial computational of cost collecting the function responses and calculating the features, particularly as \(n\) and \(D\) increase. Another approach is to train a surrogate model with a small sample, and then resample from the model [47], which provides a low computational cost estimate of \(\widehat{pr}(c_{k})\), although the resample also includes assumptions generated by the surrogate which may not correspond to the actual function. Moreover, parametric assumptions cannot be made, and there is no guarantee of fulfilling asymptotic convergence. Therefore, we use _bootstrapping_[49] to estimate \(\widehat{pr}(c_{k})\), which allows us to use one, potentially small sample, hence it can be applied on expensive problems, without adding assumptions to the methodology.