# On the Influence of the Feature Computation Budget on Per-Instance Algorithm Selection for Black-Box Optimization

arXiv: https://arxiv.org/abs/2605.04954 · HTML: https://mlsanity.com/paper/2605.04954/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 39 references that are in the map.
- First posted on arXiv 6 May 2026.

## Builds on (most cited first, 18 of 18)

- [COCO: A Platform for Comparing Continuous Optimizers in a Black-Box Setting](https://mlsanity.com/paper/1603.08785/) (2016)
- [Automated Algorithm Selection: Survey and Perspectives](https://mlsanity.com/paper/1811.11597/) (2018)
- [Automated Algorithm Selection on Continuous Black-Box Problems By Combining Exploratory Landscape Analysis and Machine Learning](https://mlsanity.com/paper/1711.08921/) (2017)
- [IOHexperimenter: Benchmarking Platform for Iterative Optimization Heuristics](https://mlsanity.com/paper/2111.04077/) (2021)
- [Per-run Algorithm Selection with Warm-starting using Trajectory-based Features](https://mlsanity.com/paper/2204.09483/) (2022)
- [Towards Feature-Based Performance Regression Using Trajectory Data](https://mlsanity.com/paper/2102.05370/) (2021)
- [Towards Explainable Exploratory Landscape Analysis: Extreme Feature Selection for Classifying BBOB Functions](https://mlsanity.com/paper/2102.00736/) (2021)
- [Automated Algorithm Selection: from Feature-Based to Feature-Free Approaches](https://mlsanity.com/paper/2203.13392/) (2022)
- [MA-BBOB: A Problem Generator for Black-Box Optimization Using Affine Combinations and Shifts](https://mlsanity.com/paper/2312.11083/) (2023)
- [Comparing Algorithm Selection Approaches on Black-Box Optimization Problems](https://mlsanity.com/paper/2306.17585/) (2023)
- [Deep-ELA: Deep Exploratory Landscape Analysis with Self-Supervised Pretrained Transformers for Single- and Multi-Objective Continuous Optimization Problems](https://mlsanity.com/paper/2401.01192/) (2024)
- [On the Utility of Probing Trajectories for Algorithm-Selection](https://mlsanity.com/paper/2401.12745/) (2024)
- [Landscape Features in Single-Objective Continuous Optimization: Have We Hit a Wall in Algorithm Selection Generalization?](https://mlsanity.com/paper/2501.17663/) (2025)
- [Using the Empirical Attainment Function for Analyzing Single-objective Black-box Optimization Algorithms](https://mlsanity.com/paper/2404.02031/) (2024)
- [PS-AAS: Portfolio Selection for Automated Algorithm Selection in Black-Box Optimization](https://mlsanity.com/paper/2310.10685/) (2023)
- [A Survey of Features Used for Representing Black-box Single-objective Continuous Optimization](https://mlsanity.com/paper/2406.06629/) (2024)
- [MO-IOHinspector: Anytime Benchmarking of Multi-Objective Algorithms using IOHprofiler](https://mlsanity.com/paper/2412.07444/) (2024)
- [Benchmarking that Matters: Rethinking Benchmarking for Practical Impact](https://mlsanity.com/paper/2511.12264/) (2025)

## Abstract (arXiv)

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.