pith. machine review for the scientific record. sign in

arxiv: 2605.04954 · v1 · submitted 2026-05-06 · 💻 cs.NE · cs.LG

Recognition: unknown

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

Authors on Pith no claims yet

Pith reviewed 2026-05-08 16:23 UTC · model grok-4.3

classification 💻 cs.NE cs.LG
keywords per-instance algorithm selectionblack-box optimizationfeature computation budgetalgorithm portfoliosbudget allocationinstance features
0
0 comments X

The pith

PIAS in black-box optimization remains effective even when a quarter of the budget is spent on features.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper examines how much of the total optimization budget can be spent computing instance features before per-instance algorithm selection loses its advantage over simply using the single best algorithm. Experiments compare PIAS with varying sampling budgets for features against the single best solver across two portfolio sizes, three problem sets, four dimensionalities, and ten target budgets. The results indicate that PIAS stays better in most scenarios even when feature computation takes up to 25 percent of the budget. The fraction that maximizes the benefit varies strongly with the specific scenario, and feature costs account for about 20 percent of the average gap to the virtual best solver.

Core claim

Per-instance algorithm selection based on features computed via sampling from the optimization budget outperforms the single best algorithm in the majority of tested black-box optimization scenarios, even when as much as a quarter of the total budget is allocated to feature computation, with the optimal feature budget fraction depending on the particular algorithm selection scenario and with feature computation explaining on average 20 percent of the performance loss relative to the virtual best solver.

What carries the argument

Per-instance algorithm selection (PIAS) that chooses an algorithm for each instance based on features sampled from the black-box function using a fraction of the evaluation budget.

If this is right

  • A substantial share of the optimization budget can be used for features without eliminating the advantage of PIAS over the single best solver.
  • The best fraction of budget for feature computation must be selected according to the specific portfolio and problem characteristics.
  • Feature computation costs explain a measurable portion of why PIAS does not reach virtual best solver performance.
  • PIAS can be considered for black-box problems where the total number of evaluations is strictly limited.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • More efficient or accurate feature computation techniques could reduce the remaining gap to the virtual best solver.
  • Allowing the algorithm selector to adjust the feature budget dynamically during optimization might improve results further.
  • The observed viability suggests PIAS could be embedded in practical optimization libraries with automatic budget allocation rules.

Load-bearing premise

That sampling-based feature computation yields features accurate enough for reliable algorithm selection decisions on the tested problem sets.

What would settle it

Finding a set of scenarios where any positive fraction of budget spent on feature computation causes PIAS performance to fall below that of the single best algorithm.

Figures

Figures reproduced from arXiv: 2605.04954 by Diederick Vermetten, Koen van der Blom.

Figure 1
Figure 1. Figure 1: Schematic visualization showing how the budget is split into feature com view at source ↗
Figure 2
Figure 2. Figure 2: PIAS performance when trained with different ELA budget factors, com view at source ↗
Figure 3
Figure 3. Figure 3: Fraction of the SBS-VBS gap closed by PIAS for different total budgets, view at source ↗
Figure 4
Figure 4. Figure 4: Fraction of the SBS-VBS gap closed by PIAS for different total budgets, view at source ↗
Figure 5
Figure 5. Figure 5: Performance of PIAS with different feature computation budgets com view at source ↗
Figure 6
Figure 6. Figure 6: Comparison of SBSfull (y-axis) and PIASperf (x-axis) results over all set￾tings, for BBOB (left) and MA-BBOB (right) respectively. Color indicates the fraction of budget used for feature calculation. Each dot corresponds to one AS scenario: budget, feature budget, dimensionality. Both portfolio sizes are in￾cluded. Dots below the diagonal indicate cases where PIAS is beneficial. To identify when spending a… view at source ↗
Figure 7
Figure 7. Figure 7: Decomposition of the PIASperf loss into the loss that is occurring based on the selection procedure itself (VBSopt − PIASperf, y-axis), and the loss resulting from the budget needed for feature calculation (VBSfull − VBSopt, x-axis). Both the full portfolio and the one with 4 algorithms are included. Each dot represents a single algorithm selection scenario. Left: BBOB. Right: MA-BBOB. MA-BBOB setting. We … view at source ↗
Figure 8
Figure 8. Figure 8: Average and 95% confidence interval of relative budget loss SS view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper examines how the fraction of the black-box optimization budget allocated to sampling-based instance feature computation affects the performance of per-instance algorithm selection (PIAS) relative to the single best solver. Across experiments with two portfolio sizes, three problem sets, four dimensionalities, and ten target budgets, it reports that PIAS remains viable in the majority of scenarios even at up to 25% feature budget, that the optimal feature-budget fraction is scenario-dependent, and that on average 20% of PIAS loss to the virtual best solver is explained by feature computation cost.

Significance. If robust, the results offer concrete practical guidance on budget allocation when deploying PIAS for black-box optimization, an area where feature costs are often overlooked. The multi-factor experimental design is a strength and supports broader applicability than single-scenario studies. However, the central claims rest on the unverified assumption that low-budget sampling yields sufficiently stable and informative features; without direct fidelity checks this limits the reliability and impact of the viability and loss-attribution findings.

major comments (2)
  1. [Experimental design / results sections] Experimental design / results sections: No direct validation of sampling-based feature fidelity is reported (e.g., intra-sample variance, correlation with full-budget features, or selector sensitivity to feature perturbation). This is load-bearing for the headline claims, because high variance or bias in low-budget features could cause suboptimal selections, confounding both the reported viability at 25% feature budget and the 20% loss attribution to feature cost.
  2. [Results presentation] Results presentation: The claims that PIAS is 'viable for the majority of tested scenarios' and that 'on average 20 percent of PIAS loss ... is explained by the budget' are stated without accompanying error bars, statistical significance tests, or per-scenario breakdowns that would allow assessment of consistency across the 2×3×4×10 design.
minor comments (1)
  1. [Abstract] The abstract and introduction would benefit from an explicit definition of 'viable' (e.g., PIAS outperforming the single best solver by a stated margin on a stated fraction of instances).

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed feedback. The comments identify key areas where additional validation and clearer presentation would strengthen the manuscript. We respond to each major comment below and indicate the revisions we will make.

read point-by-point responses
  1. Referee: [Experimental design / results sections] Experimental design / results sections: No direct validation of sampling-based feature fidelity is reported (e.g., intra-sample variance, correlation with full-budget features, or selector sensitivity to feature perturbation). This is load-bearing for the headline claims, because high variance or bias in low-budget features could cause suboptimal selections, confounding both the reported viability at 25% feature budget and the 20% loss attribution to feature cost.

    Authors: We agree that explicit checks on feature fidelity at reduced sampling budgets would improve interpretability of the results. The original experiments emphasize end-to-end PIAS performance across budgets, which provides indirect support for feature utility, but do not include direct fidelity metrics. In the revised manuscript we will add (i) intra-sample variance estimates for the computed features and (ii) correlation analyses between low-budget and full-budget feature vectors on a representative subset of instances. A limited selector-sensitivity analysis under feature perturbation will also be included for selected scenarios. These additions will be reported in a new subsection of the results and will help isolate the contribution of feature noise to the observed performance gaps. revision: partial

  2. Referee: [Results presentation] Results presentation: The claims that PIAS is 'viable for the majority of tested scenarios' and that 'on average 20 percent of PIAS loss ... is explained by the budget' are stated without accompanying error bars, statistical significance tests, or per-scenario breakdowns that would allow assessment of consistency across the 2×3×4×10 design.

    Authors: We accept that the current presentation lacks the statistical detail needed to evaluate consistency across the full experimental grid. In the revision we will (i) add error bars (standard deviation across independent runs) to all key performance plots and tables, (ii) include per-scenario breakdowns (by portfolio size, problem set, dimensionality, and target budget) either in the main text or as supplementary tables, and (iii) report Wilcoxon signed-rank tests comparing PIAS against the single-best solver, with Holm correction for multiple comparisons. These changes will allow readers to assess both the magnitude and statistical reliability of the reported viability and loss-attribution figures. revision: yes

Circularity Check

0 steps flagged

No circularity: purely empirical comparison with no derivations or self-referential predictions

full rationale

The paper conducts a broad experimental study comparing PIAS performance under varying feature computation budgets against the single best solver across multiple scenarios (portfolios, problem sets, dimensionalities, target budgets). All reported findings, including viability at up to 25% feature budget and the 20% average loss attribution, are direct outputs of these experiments rather than any mathematical derivation, fitted model, or prediction that reduces to the inputs by construction. No equations, ansatzes, uniqueness theorems, or self-citations are invoked as load-bearing steps in a derivation chain. The analysis is self-contained against the performed runs and does not rename known results or smuggle assumptions via prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest entirely on empirical observations from a designed experiment rather than new theoretical axioms or postulated entities.

axioms (1)
  • domain assumption The algorithms within each portfolio exhibit complementary performance across different problem instances.
    This is required for PIAS to have any advantage over the single best algorithm.

pith-pipeline@v0.9.0 · 5543 in / 1336 out tokens · 43995 ms · 2026-05-08T16:23:59.578305+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 26 canonical work pages

  1. [1]

    Journal of Heuristics29, 1–38 (2023).https://doi

    Alissa, M., Sim, K., Hart, E.: Automated algorithm selection: from feature-based to feature-free approaches. Journal of Heuristics29, 1–38 (2023).https://doi. org/10.1007/s10732-022-09505-4

  2. [2]

    Swarm and Evolution- ary Computation100, 102246 (2026).https://doi.org/10.1016/j.swevo.2025

    Andova, A., Cork, J.N., Tuˇ sar, T., Filipiˇ c, B.: A methodology for multi-label algo- rithm selection in constrained multiobjective optimization. Swarm and Evolution- ary Computation100, 102246 (2026).https://doi.org/10.1016/j.swevo.2025. 102246

  3. [3]

    In: Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation

    Bischl, B., Mersmann, O., Trautmann, H., Preuß, M.: Algorithm selection based on exploratory landscape analysis and cost-sensitive learning. In: Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation. p. 313–320. GECCO ’12, Association for Computing Machinery, New York, NY, USA (2012). https://doi.org/10.1145/2330163.2330209

  4. [4]

    Van der Blom, K., Vermetten, D.: On the influence of the feature computation bud- get on per-instance algorithm selection for black-box optimisation - Reproducibility files (Apr 2026).https://doi.org/10.5281/zenodo.19604700

  5. [5]

    Swarm and Evolutionary Computation101, 102288 (2026)

    Cenikj, G., Nikolikj, A., Petelin, G., Van Stein, N., Doerr, C., Eftimov, T.: A survey of features used for representing black-box single-objective continu- ous optimization. Swarm and Evolutionary Computation101, 102288 (2026). https://doi.org/10.1016/j.swevo.2026.102288

  6. [6]

    Cenikj, G., Petelin, G., Seiler, M., Cenikj, N., Eftimov, T.: Landscape features in single-objective continuous optimization: Have we hit a wall in algorithm selection generalization? Swarm and Evolutionary Computation94, 101894 (2025).https: //doi.org/10.1016/j.swevo.2025.101894

  7. [7]

    In: Rudolph, G., Kononova, A.V., Aguirre, H., Ker- schke, P., Ochoa, G., Tuˇ sar, T

    Dietrich, K., Mersmann, O.: Increasing the diversity of benchmark function sets through affine recombination. In: Rudolph, G., Kononova, A.V., Aguirre, H., Ker- schke, P., Ochoa, G., Tuˇ sar, T. (eds.) Parallel Problem Solving from Nature – PPSN XVII. pp. 590–602. Springer International Publishing, Cham (2022). https://doi.org/10.1007/978-3-031-14714-2_41

  8. [8]

    Research Report RR-6829, INRIA (2009),https://inria.hal.science/inria-00362633 On the Influence of the Feature Computation Budget on PIAS for BBO 15

    Hansen, N., Finck, S., Ros, R., Auger, A.: Real-Parameter Black-Box Optimization Benchmarking 2009: Noiseless Functions Definitions. Research Report RR-6829, INRIA (2009),https://inria.hal.science/inria-00362633 On the Influence of the Feature Computation Budget on PIAS for BBO 15

  9. [9]

    In: Castillo, P.A., Jim´ enez Laredo, J.L

    Jankovic, A., Eftimov, T., Doerr, C.: Towards feature-based performance regression using trajectory data. In: Castillo, P.A., Jim´ enez Laredo, J.L. (eds.) Applications of Evolutionary Computation. pp. 601–617. Springer International Publishing, Cham (2021).https://doi.org/10.1007/978-3-030-72699-7_38

  10. [10]

    Evolutionary Computation27, 3–45 (2019)

    Kerschke, P., Hoos, H.H., Neumann, F., Trautmann, H.: Automated algorithm selection: Survey and perspectives. Evolutionary Computation27, 3–45 (2019). https://doi.org/10.1162/evco_a_00242

  11. [11]

    Evolutionary Computation27(1), 99–127 (03 2019).https://doi.org/10.1162/ evco_a_00236

    Kerschke, P., Trautmann, H.: Automated algorithm selection on continuous black- box problems by combining exploratory landscape analysis and machine learning. Evolutionary Computation27(1), 99–127 (03 2019).https://doi.org/10.1162/ evco_a_00236

  12. [12]

    arXiv preprint arXiv:2511.12264 (2025).https://doi.org/10.48550/arXiv.2511.12264

    Kononova, A.V., van Stein, N., Mersmann, O., B¨ ack, T., Bartz-Beielstein, T., Glasmachers, T., Hellwig, M., Krey, S., Kudela, J., Naujoks, B., et al.: Benchmark- ing that matters: Rethinking benchmarking for practical impact. arXiv preprint arXiv:2511.12264 (2025).https://doi.org/10.48550/arXiv.2511.12264

  13. [13]

    In: Faust, A., Garnett, R., White, C., Hutter, F., Gardner, J.R

    Kostovska, A., Cenikj, G., Vermetten, D., Jankovic, A., Nikolikj, A., Skvorc, U., Korosec, P., Doerr, C., Eftimov, T.: PS-AAS: Portfolio selection for automated algorithm selection in black-box optimization. In: Faust, A., Garnett, R., White, C., Hutter, F., Gardner, J.R. (eds.) Proceedings of the Second International Con- ference on Automated Machine Lea...

  14. [14]

    In: Rudolph, G., Kononova, A.V., Aguirre, H., Kerschke, P., Ochoa, G., Tuˇ sar, T

    Kostovska, A., Jankovic, A., Vermetten, D., de Nobel, J., Wang, H., Eftimov, T., Doerr, C.: Per-run algorithm selection with warm-starting using trajectory- based features. In: Rudolph, G., Kononova, A.V., Aguirre, H., Kerschke, P., Ochoa, G., Tuˇ sar, T. (eds.) Parallel Problem Solving from Nature – PPSN XVII. LNCS, vol. 13398, pp. 46–60. Springer Intern...

  15. [15]

    IEEE Transactions on Evolutionary Computation29(5), 1774–1782 (2025).https: //doi.org/10.1109/TEVC.2024.3462758

    L´ opez-Ib´ a˜ nez, M., Vermetten, D., Dreo, J., Doerr, C.: Using the empirical attain- ment function for analyzing single-objective black-box optimization algorithms. IEEE Transactions on Evolutionary Computation29(5), 1774–1782 (2025).https: //doi.org/10.1109/TEVC.2024.3462758

  16. [16]

    In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation

    Mersmann, O., Bischl, B., Trautmann, H., Preuss, M., Weihs, C., Rudolph, G.: Exploratory landscape analysis. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. pp. 829–836. GECCO ’11, Association for Computing Machinery, New York, NY, USA (2011).https://doi.org/10.1145/ 2001576.2001690

  17. [17]

    Mu˜ noz, M.A., Sun, Y., Kirley, M., Halgamuge, S.K.: Algorithm selection for black- box continuous optimization problems: A survey on methods and challenges. Inf. Sci.317, 224–245 (2015).https://doi.org/10.1016/J.INS.2015.05.010

  18. [18]

    Evolutionary Computation32(3), 205–210 (09 2024).https://doi.org/10.1162/evco_a_00342

    de Nobel, J., Ye, F., Vermetten, D., Wang, H., Doerr, C., B¨ ack, T.: IOHexperi- menter: Benchmarking platform for iterative optimization heuristics. Evolutionary Computation32(3), 205–210 (09 2024).https://doi.org/10.1162/evco_a_00342

  19. [19]

    Journal of Machine Learning Research12, 2825–2830 (2011)

    Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., Duchesnay, E.: Scikit-learn: Machine learning in Python. Journal of Machine Learning Research12, 2825–2830 (2011)

  20. [20]

    In: Correia, J., Smith, S., Qaddoura, R

    Prager, R.P., Trautmann, H.: Nullifying the inherent bias of non-invariant ex- ploratory landscape analysis features. In: Correia, J., Smith, S., Qaddoura, R. (eds.) Applications of Evolutionary Computation. pp. 411–425. Springer Nature Switzerland, Cham (2023).https://doi.org/10.1007/978-3-031-30229-9_27 16 Koen van der Blom and Diederick Vermetten

  21. [21]

    Evolutionary Computation 32(3), 211–216 (09 2024).https://doi.org/10.1162/evco_a_00341

    Prager, R.P., Trautmann, H.: Pflacco: Feature-based landscape analysis of continu- ous and constrained optimization problems in Python. Evolutionary Computation 32(3), 211–216 (09 2024).https://doi.org/10.1162/evco_a_00341

  22. [22]

    Rapin, J., Teytaud, O.: Nevergrad - A gradient-free optimization platform.https: //GitHub.com/FacebookResearch/Nevergrad(2018)

  23. [23]

    In: Proceedings of the Genetic and Evolutionary Computation Conference Companion

    Renau, Q., Dreo, J., Doerr, C., Doerr, B.: Expressiveness and robustness of land- scape features. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion. pp. 2048–2051. GECCO ’19, Association for Comput- ing Machinery, New York, NY, USA (2019).https://doi.org/10.1145/3319619. 3326913

  24. [24]

    In: Castillo, P.A., Jim´ enez Laredo, J.L

    Renau, Q., Dr´ eo, J., Doerr, C., Doerr, B.: Towards explainable exploratory land- scape analysis: Extreme feature selection for classifying BBOB functions. In: Castillo, P.A., Jim´ enez Laredo, J.L. (eds.) Applications of Evolutionary Com- putation. pp. 17–33. Springer International Publishing, Cham (2021).https: //doi.org/10.1007/978-3-030-72699-7_2

  25. [25]

    In: Smith, S., Correia, J., Cintrano, C

    Renau, Q., Hart, E.: On the utility of probing trajectories for algorithm-selection. In: Smith, S., Correia, J., Cintrano, C. (eds.) Applications of Evolutionary Com- putation. pp. 98–114. Springer Nature Switzerland, Cham (2024).https://doi. org/10.1007/978-3-031-56852-7_7

  26. [26]

    In: Advances in computers, vol

    Rice, J.R.: The algorithm selection problem. In: Advances in computers, vol. 15, pp. 65–118. Elsevier (1976).https://doi.org/10.1016/S0065-2458(08)60520-3

  27. [27]

    Evolutionary Computation pp

    Seiler, M.V., Kerschke, P., Trautmann, H.: Deep-ELA: Deep exploratory landscape analysis with self-supervised pretrained transformers for single- and multi-objective continuous optimization problems. Evolutionary Computation pp. 1–27 (02 2025). https://doi.org/10.1162/evco_a_00367

  28. [28]

    In: Proceedings of the Genetic and Evolutionary Compu- tation Conference

    Seiler, M.V., Preuß, O.L., Trautmann, H.: RandOptGen: A unified random prob- lem generator for single- and multi-objective optimization problems with mixed- variable input spaces. In: Proceedings of the Genetic and Evolutionary Compu- tation Conference. p. 76–84. GECCO ’25, Association for Computing Machinery, New York, NY, USA (2025).https://doi.org/10.1...

  29. [29]

    In: In Contributions to the Theory of Games, volume II, pp

    Shapley, L.S.: A value for n-person games. In: In Contributions to the Theory of Games, volume II, pp. 307–317. Princeton University Press. (1953)

  30. [30]

    In: Singh, H., Ray, T., Knowles, J., Li, X., Branke, J., Wang, B., Oyama, A

    Vermetten, D., Rook, J., Preuß, O.L., de Nobel, J., Doerr, C., L´ opez-Iba˜ nez, M., Trautmann, H., B¨ ack, T.: MO-IOHinspector: Anytime benchmarking of multi- objective algorithms using IOHprofiler. In: Singh, H., Ray, T., Knowles, J., Li, X., Branke, J., Wang, B., Oyama, A. (eds.) Evolutionary Multi-Criterion Op- timization. pp. 242–256. Springer Nature...

  31. [31]

    ACM Trans

    Vermetten, D., Ye, F., B¨ ack, T., Doerr, C.: MA-BBOB: A problem generator for black-box optimization using affine combinations and shifts. ACM Trans. Evol. Learn. Optim.5(1) (Mar 2025).https://doi.org/10.1145/3673908

  32. [32]

    University of British Columbia,, Tech

    Xu, L., Hutter, F., Hoos, H., Leyton-Brown, K.: Features for SAT. University of British Columbia,, Tech. Rep (2012)

  33. [33]

    Journal of Artificial Intelligence Research32, 565–606 (2008).https://doi.org/10.1613/jair.2490

    Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: SATzilla: Portfolio-based al- gorithm selection for SAT. Journal of Artificial Intelligence Research32, 565–606 (2008).https://doi.org/10.1613/jair.2490

  34. [34]

    In: Proceedings of the 18th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA 2011)

    Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: Hydra-MIP: Automated algo- rithm configuration and selection for mixed integer programming. In: Proceedings of the 18th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA 2011). pp. 16–30 (2011)