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

Source: arXiv - 2605.04954v1

Overview

This paper investigates a practical dilemma that many developers face when using per‑instance algorithm selection (PIAS) for black‑box optimization (BBO): how much of the total runtime budget should be spent on computing instance features before deciding which optimizer to run? The authors conduct a large‑scale empirical study to pinpoint the sweet spot where the overhead of feature computation pays off, showing that PIAS can be beneficial even when a sizable chunk of the budget is devoted to feature extraction.

Key Contributions

• Systematic budget analysis: Quantifies the minimum fraction of the total optimization budget that must be allocated to feature computation for PIAS to outperform the single best algorithm.
• Extensive experimental matrix: Evaluates 2 portfolio sizes across 3 benchmark problem sets, 4 dimensionalities, and 10 target budgets (total ≈ 240 scenario variations).
• Trade‑off characterization: Demonstrates that the optimal feature‑budget fraction is highly scenario‑dependent, but PIAS remains viable in most cases—even with up to 25 % of the budget spent on features.
• Loss decomposition: Shows that, on average, ≈ 20 % of the performance gap between PIAS and the virtual best solver (VBS) can be attributed directly to the feature‑budget overhead.
• Practical guidelines: Provides actionable recommendations for practitioners on budgeting feature computation in real‑world BBO pipelines.

Methodology

1. Portfolio Construction – Two algorithm portfolios were built: a small set (3–4 optimizers) and a large set (≈ 10 optimizers), covering a range of evolutionary and surrogate‑based methods.
2. Feature Extraction Budgeting – For each instance, a configurable fraction of the total optimization budget (ranging from 0 % to 40 %) was reserved for sampling the objective function and computing statistical, landscape, and exploratory features.
3. Selection Model – A standard machine‑learning classifier (random forest) was trained on the extracted features to predict the best algorithm for a given instance.
4. Evaluation Protocol – The study spanned three benchmark suites (e.g., BBOB, COCO, synthetic combinatorial problems), four problem dimensions (2, 5, 10, 20), and ten target budgets (from 10⁴ to 10⁶ function evaluations). Each configuration was repeated across many random seeds to ensure statistical robustness.
5. Metrics – Performance was measured as the expected runtime to reach a target objective value, comparing PIAS (with its feature‑budget) against the single best algorithm (SBA) and the virtual best solver (VBS) that magically picks the optimal algorithm per instance.

Results & Findings

Practical Implications

• Production pipelines: When integrating PIAS into automated hyper‑parameter tuning or meta‑optimization services, allocate ~10 % of the total evaluation budget to feature sampling as a safe default; adjust upward for high‑dimensional or highly multimodal problems.
• Cost‑aware selection: The study provides a quantitative framework to budget feature computation, enabling developers to predict whether the selection overhead will be justified for a given SLA (e.g., time‑to‑solution constraints).
• Tooling: Existing PIAS libraries (e.g., ASLib, AutoML‑Zero) can expose a “feature‑budget” knob, allowing users to tune it per workload rather than relying on a one‑size‑fits‑all setting.
• Portfolio design: Adding diverse algorithms (especially those that excel on different landscape characteristics) amplifies the benefit of PIAS, but the added selection cost must be accounted for—particularly in cloud‑cost‑sensitive environments.
• Real‑world use‑cases: Industries that run expensive simulations (engineering design, finance, drug discovery) can reap immediate gains by spending a modest portion of their simulation budget on cheap exploratory runs to inform algorithm choice, thereby reducing overall compute spend.

Limitations & Future Work

• Feature set fixed: The study uses a predefined collection of landscape features; exploring adaptive or learned feature representations could shift the optimal budget.
• Static budgets: The fraction of budget dedicated to features is fixed a priori; dynamic budgeting (e.g., stop sampling early if confidence is high) was not examined.
• Algorithm pool: Only two portfolio sizes were tested; scaling to very large portfolios (dozens of optimizers) may exhibit different trade‑offs.
• Domain specificity: Benchmarks are synthetic or standard BBO testbeds; real‑world black‑box problems with noisy, expensive evaluations might behave differently.
• Selection model: A random‑forest classifier was used; investigating more sophisticated meta‑learners (e.g., neural surrogates) could affect both accuracy and computational overhead.

Bottom line: By explicitly accounting for the cost of feature computation, developers can make informed decisions about when and how to deploy per‑instance algorithm selection in black‑box optimization, unlocking performance gains without blowing the budget.

Authors

• Koen van der Blom
• Diederick Vermetten

Paper Information

• arXiv ID: 2605.04954v1
• Categories: cs.NE, cs.LG
• Published: May 6, 2026
• PDF: Download PDF