Extreme Algorithm Selection With Dyadic Feature Representation
This addresses the scalability issue in algorithm selection for combined algorithm and hyperparameter optimization, enabling meta-learning with large candidate sets.
The paper tackles the problem of algorithm selection when the candidate set grows to thousands of algorithms, proposing extreme algorithm selection (XAS) and a dyadic feature representation that improves over state-of-the-art methods in various metrics.
Algorithm selection (AS) deals with selecting an algorithm from a fixed set of candidate algorithms most suitable for a specific instance of an algorithmic problem, e.g., choosing solvers for SAT problems. Benchmark suites for AS usually comprise candidate sets consisting of at most tens of algorithms, whereas in combined algorithm selection and hyperparameter optimization problems the number of candidates becomes intractable, impeding to learn effective meta-models and thus requiring costly online performance evaluations. Therefore, here we propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms, facilitating meta learning. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation in which both problem instances and algorithms are described. We find the latter to improve significantly over the current state of the art in various metrics.