Similarity-based Portfolio Construction for Black-box Optimization
For practitioners in black-box optimization, this work provides a practical method to construct algorithm portfolios that reduce risk and improve performance over single-algorithm selection.
The paper tackles the problem of algorithm selection in black-box optimization by proposing a similarity-based portfolio construction method. The proposed k-nearest-neighbor-based finetuning approach outperforms the virtual best solver baseline, demonstrating the effectiveness of portfolio selection in fixed-budget settings.
In black-box optimization, a central question is which algorithm to use to solve a given, previously unseen, problem. Selecting a single algorithm, however, entails inherent risks: inaccuracies in the selector may lead to poor choices, and even well-performing algorithms with high variance can yield unsatisfactory results in a single run. A natural remedy is to split the evaluation budget across multiple runs of potentially different algorithms. Such sequential algorithm portfolios benefit from variance reduction and complementarities between algorithms, often outperforming approaches that allocate the entire budget to a single solver. While effective portfolios can be constructed post-hoc, transferring this idea to the algorithm selection setting is non-trivial. We show that a naive portfolio constructed over the full training set already outperforms the strongest traditional baseline, the virtual best solver. We then propose a simple yet effective k-nearest-neighbor-based finetuning approach to construct portfolios tailored to unseen instances, yielding further improvements and highlighting the effectiveness of portfolio selection in fixed-budget black-box optimization.