On the Influence of the Feature Computation Budget on Per-Instance Algorithm Selection for Black-Box Optimization
For practitioners using algorithm selection in black-box optimization, this work quantifies the trade-off between feature computation cost and selection performance, highlighting the need to account for the feature budget.
This paper investigates the impact of the feature computation budget on per-instance algorithm selection (PIAS) for black-box optimization. It finds that PIAS is viable in most scenarios even when up to 25% of the total budget is spent on feature computation, and that the optimal fraction varies by scenario, with an average of 20% of PIAS loss attributed to the feature budget.
Per-instance algorithm selection (PIAS) takes advantage of complementarity between a set of algorithms by deciding which algorithm to run on a given instance. This decision is based on features of the instances, which, in the context of black-box optimization (BBO), require a part of the optimization budget to be computed. This raises two questions: (a) from which fraction of the budget spent on feature computation does PIAS become worth it for BBO, and (b) which fraction of the budget optimizes the tradeoff between feature accuracy and PIAS performance. To this end, we perform a broad study where PIAS with varying sampling budgets for feature computation is compared to the single best algorithm on a broad range of algorithm selection scenarios. These scenarios consist of two portfolio sizes, three problem sets, 4 dimensionalities, and 10 target budgets. We find that PIAS is viable for the majority of tested scenarios, even when as much as a quarter of the total budget is spent on feature computation. The tradeoff for the fraction of the budget spent on feature computation to maximize the benefit of PIAS is highly dependent on the specific AS scenario. Further, on average 20 percent of PIAS loss to the virtual best solver is explained by the budget spent on feature computation, highlighting the importance of properly accounting for the feature budget.