Search papers, labs, and topics across Lattice.
This paper investigates the impact of feature computation budget on per-instance algorithm selection (PIAS) within black-box optimization (BBO). They compare PIAS performance with varying feature computation budgets against the single best algorithm across diverse algorithm selection scenarios, problem sets, dimensionalities, and target budgets. Results show PIAS remains viable even with a substantial feature computation budget (up to 25%), and that optimizing the feature computation budget is crucial for maximizing PIAS benefits.
Spending up to 25% of your black-box optimization budget on feature computation for per-instance algorithm selection can still pay off, but optimizing that budget is key to unlocking PIAS's full potential.
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.
