Identifying Easy Instances to Improve Efficiency of ML Pipelines for Algorithm-Selection

Renau, Quentin; Hart, Emma

Abstract

Algorithm-selection (AS) methods are essential in order to obtain the best performance from a portfolio of solvers over large sets of instances. However, many AS methods rely on an analysis phase, e.g. where features are computed by sampling solutions and used as input in a machine-learning model. For AS to be efficient, it is therefore important that this analysis phase is not computationally expensive. We propose a method for identifying easy instances which can be solved quickly using a generalist solver without any need for algorithm-selection. This saves computational budget associated with feature-computation which can then be used elsewhere in an AS pipeline, e.g., enabling additional function evaluations on hard problems. Experiments on the BBOB dataset in two settings (batch and streaming) show that identifying easy instances results in substantial savings in function evaluations. Re-allocating the saved budget to hard problems provides gains in performance compared to both the virtual best solver (VBS) computed with the original budget, the single best solver (SBS) and a trained algorithm-selector.

Citation

Renau, Q., & Hart, E. (2024, September). Identifying Easy Instances to Improve Efficiency of ML Pipelines for Algorithm-Selection. Presented at 18th International Conference, PPSN 2024, Hagenberg, Austria

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 18th International Conference, PPSN 2024
• Start Date: Sep 14, 2024
• End Date: Sep 18, 2024
• Online Publication Date: Sep 7, 2024
• Publication Date: 2024
• Deposit Date: Sep 15, 2024
• Publicly Available Date: Sep 8, 2025
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Pages: 70-86
• Series Title: Lecture Notes in Computer Science
• Series Number: 15149
• Series ISSN: 0302-9743
• Book Title: Parallel Problem Solving from Nature – PPSN XVIII
• ISBN: 9783031700675
• DOI: https://doi.org/10.1007/978-3-031-70068-2_5