Is Algorithm Selection Worth It? Comparing Selecting Single Algorithms and Parallel Execution

Haniye Kashgarani, Lars Kotthoff
AAAI Workshop on Meta-Learning and MetaDL Challenge, PMLR 140:58-64, 2021.

Abstract

For many practical problems, there is more than one algorithm or approach to solve them. Such algorithms often have complementary performance – where one fails, another performs well, and vice versa. Per-instance algorithm selection leverages this by employing portfolios of complementary algorithms to solve sets of difficult problems, choosing the most appropriate algorithm for each problem instance. However, this requires complex models to effect this selection and introduces overhead to compute the data needed for those models. On the other hand, even basic hardware is more than capable of running several algorithms in parallel. We investigate the tradeoff between selecting a single algorithm and running multiple in parallel and incurring a slowdown because of contention for shared resources. Our results indicate that algorithm selection is worth it, especially for large portfolios.

Cite this Paper

BibTeX
@InProceedings{pmlr-v140-kashgarani21a, title = {Is Algorithm Selection Worth It? Comparing Selecting Single Algorithms and Parallel Execution}, author = {Kashgarani, Haniye and Kotthoff, Lars}, booktitle = {AAAI Workshop on Meta-Learning and MetaDL Challenge}, pages = {58--64}, year = {2021}, editor = {Guyon, Isabelle and van Rijn, Jan N. and Treguer, Sébastien and Vanschoren, Joaquin}, volume = {140}, series = {Proceedings of Machine Learning Research}, month = {09 Feb}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v140/kashgarani21a/kashgarani21a.pdf}, url = {https://proceedings.mlr.press/v140/kashgarani21a.html}, abstract = {For many practical problems, there is more than one algorithm or approach to solve them. Such algorithms often have complementary performance – where one fails, another performs well, and vice versa. Per-instance algorithm selection leverages this by employing portfolios of complementary algorithms to solve sets of difficult problems, choosing the most appropriate algorithm for each problem instance. However, this requires complex models to effect this selection and introduces overhead to compute the data needed for those models. On the other hand, even basic hardware is more than capable of running several algorithms in parallel. We investigate the tradeoff between selecting a single algorithm and running multiple in parallel and incurring a slowdown because of contention for shared resources. Our results indicate that algorithm selection is worth it, especially for large portfolios.} }
Endnote
%0 Conference Paper %T Is Algorithm Selection Worth It? Comparing Selecting Single Algorithms and Parallel Execution %A Haniye Kashgarani %A Lars Kotthoff %B AAAI Workshop on Meta-Learning and MetaDL Challenge %C Proceedings of Machine Learning Research %D 2021 %E Isabelle Guyon %E Jan N. van Rijn %E Sébastien Treguer %E Joaquin Vanschoren %F pmlr-v140-kashgarani21a %I PMLR %P 58--64 %U https://proceedings.mlr.press/v140/kashgarani21a.html %V 140 %X For many practical problems, there is more than one algorithm or approach to solve them. Such algorithms often have complementary performance – where one fails, another performs well, and vice versa. Per-instance algorithm selection leverages this by employing portfolios of complementary algorithms to solve sets of difficult problems, choosing the most appropriate algorithm for each problem instance. However, this requires complex models to effect this selection and introduces overhead to compute the data needed for those models. On the other hand, even basic hardware is more than capable of running several algorithms in parallel. We investigate the tradeoff between selecting a single algorithm and running multiple in parallel and incurring a slowdown because of contention for shared resources. Our results indicate that algorithm selection is worth it, especially for large portfolios.
APA
Kashgarani, H. & Kotthoff, L.. (2021). Is Algorithm Selection Worth It? Comparing Selecting Single Algorithms and Parallel Execution. AAAI Workshop on Meta-Learning and MetaDL Challenge, in Proceedings of Machine Learning Research 140:58-64 Available from https://proceedings.mlr.press/v140/kashgarani21a.html.

Related Material