# Sampling Effects on Algorithm Selection for Continuous Black-Box Optimization
## 4 Selector Implementation  
To implement the selector, our first step is to choose representative subsets for the problem, \(\mathcal{F}\), and algorithm, \(\mathcal{A}\), spaces. We use the MATLAB implementation of the Comparing Continuous Optimizers (COCO) noiseless benchmarks v13.09 [33] as representative of \(\mathcal{F}\). The motivation for this choice of benchmark problems revolves around practical advantages. For example, there is a wealth of data collected about the performance of a large set of search algorithms, and there are established conventions on the number of dimensions and the limits on the function evaluation budget. The software implementation of COCO generates instances by translating and rotating the function in the input and output spaces. For example, let \(f(\mathbf{x})=\left\|\mathbf{R}(\mathbf{x}-\mathbf{x}_{o})\right\|^{2}+y_{o}\) be a functions in COCO, where \(\mathbf{R}\) is an orthogonal rotation matrix, \(\mathbf{x}_{o}\) and \(y_{o}\) cause translational shifts on the input and output space respectively. A function instance is generated by providing values for \(\mathbf{R}\), \(\mathbf{x}_{o}\), and \(y_{o}\). To allow replicable experiments, the software uniquely identifies each instance using an index. For each function at each dimension, we analyze instances \([1,\dots,15]\) at \(D=\{2,5,10,20\}\), giving us a total of 1440 problem instances for analysis. As a representative subset of the algorithm space, \(\mathbf{A}\subset\mathcal{A}\), we have used a subset of algorithms from the Black-Box Optimization Benchmarking (BBOB) sessions, composed of \((1+2)^{m}_{s}\)CMA-ES, BIPOP-CMA-ES, LStep and Nelder-Mead with Resize and Half-Runs. Corresponding results are publicly available at the benchmark website ([[http://coco.gforge.inria.fr/doku.php](http://coco.gforge.inria.fr/doku.php)]([http://coco.gforge.inria.fr/doku.php](http://coco.gforge.inria.fr/doku.php))). The subset was selected using ICARUS (Identification of Complementary algoRithms by Uncovered Sets), a heuristic method to construct portfolios based on uncovered sets, a concept derived from voting systems theory [41]. As a comparison algorithm we use a portfolio composed of the BFGS, BIPOP-CMA-ES, LSfminbnd, and LSstep algorithms (BBLL) [2]. In contrast to our automatically selected portfolios, the algorithms in this portfolio were manually selected to minimize \(\overline{T}\) over all the benchmark functions within a target of \(10^{-3}\). The descriptions of all algorithms employed are presented in Table 2.  
As our next step, we calculate the ELA features. Ideally, if the features are to be used for algorithm selection, their additional computational cost should be a fraction of the cost associated with a single search algorithm, which is usually bounded at \(10^{4}\times D\) function evaluations [33]. [PERSON] et al. [47] and [PERSON] et al. [15] use sample sizes of \(30\times D\) and \(50\times D\) respectively, which are close to the population size of an evolutionary algorithm. However, [PERSON] et al. [47] establishes that \(30\times D\) produces poor approximations of the feature values, although they can be improved by training and resampling a surrogate model. Nevertheless, their experiments also demonstrate that most features for the COCO benchmark set level-off between \(10^{2}\times D\) and \(10^{3}\times D\). These results are supported by [PERSON] et al. [13], who determined that for \(D=2\) a sample size of at least \(200\times D\) was necessary to guarantee convergence. Given this evidence, and to balance the cost of our computations, we set the lower bound for the sample size at \(10^{2}\times D\), corresponding to \(1\%\) of the budget, and the upper bound at \(10^{3}\times D\), corresponding to \(10\%\) of the budget, which we consider to be reasonable sample sizes. We divided the range between \(10^{2}\times D\) and \(10^{3}\times D\) into five equally sized intervals in base-10 logarithmic scale, aiming to produce a geometric progression analogous to the progression in \(D\).