Frugal Algorithm Selection
<|reference_start|>Frugal Algorithm Selection: When solving decision and optimisation problems, many competing algorithms (model and solver choices) have complementary strengths. Typically, there is no single algorithm that works well for all instances of a problem. Automated algorithm selection has been shown to work very well for choosing a suitable algorithm for a given instance. However, the cost of training can be prohibitively large due to running candidate algorithms on a representative set of training instances. In this work, we explore reducing this cost by choosing a subset of the training instances on which to train. We approach this problem in three ways: using active learning to decide based on prediction uncertainty, augmenting the algorithm predictors with a timeout predictor, and collecting training data using a progressively increasing timeout. We evaluate combinations of these approaches on six datasets from ASLib and present the reduction in labelling cost achieved by each option.<|reference_end|>
@article{kuş2024frugal,
    title={Frugal Algorithm Selection},
    author={Erdem Kuc{s}, "Ozg"ur Akg"un, Nguyen Dang, Ian Miguel},
    journal={arXiv preprint arXiv:2405.11059},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.11059},
    primaryClass={cs.LG}
}