LeapsAndBounds: A Method for Approximately Optimal Algorithm Configuration

Gellert Weisz, Andras Gyorgy, Csaba Szepesvari
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:5257-5265, 2018.

Abstract

We consider the problem of configuring general-purpose solvers to run efficiently on problem instances drawn from an unknown distribution. The goal of the configurator is to find a configuration that runs fast on average on most instances, and do so with the least amount of total work. It can run a chosen solver on a random instance until the solver finishes or a timeout is reached. We propose LeapsAndBounds, an algorithm that tests configurations on randomly selected problem instances for longer and longer time. We prove that the capped expected runtime of the configuration returned by LeapsAndBounds is close to the optimal expected runtime, while our algorithm’s running time is near-optimal. Our results show that LeapsAndBounds is more efficient than the recent algorithm of Kleinberg et al. (2017), which, to our knowledge, is the only other algorithm configuration method with non-trivial theoretical guarantees. Experimental results on configuring a public SAT solver on a new benchmark dataset also stand witness to the superiority of our method.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-weisz18a, title = {{L}eaps{A}nd{B}ounds: A Method for Approximately Optimal Algorithm Configuration}, author = {Weisz, Gellert and Gyorgy, Andras and Szepesvari, Csaba}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {5257--5265}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/weisz18a/weisz18a.pdf}, url = {https://proceedings.mlr.press/v80/weisz18a.html}, abstract = {We consider the problem of configuring general-purpose solvers to run efficiently on problem instances drawn from an unknown distribution. The goal of the configurator is to find a configuration that runs fast on average on most instances, and do so with the least amount of total work. It can run a chosen solver on a random instance until the solver finishes or a timeout is reached. We propose LeapsAndBounds, an algorithm that tests configurations on randomly selected problem instances for longer and longer time. We prove that the capped expected runtime of the configuration returned by LeapsAndBounds is close to the optimal expected runtime, while our algorithm’s running time is near-optimal. Our results show that LeapsAndBounds is more efficient than the recent algorithm of Kleinberg et al. (2017), which, to our knowledge, is the only other algorithm configuration method with non-trivial theoretical guarantees. Experimental results on configuring a public SAT solver on a new benchmark dataset also stand witness to the superiority of our method.} }
Endnote
%0 Conference Paper %T LeapsAndBounds: A Method for Approximately Optimal Algorithm Configuration %A Gellert Weisz %A Andras Gyorgy %A Csaba Szepesvari %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-weisz18a %I PMLR %P 5257--5265 %U https://proceedings.mlr.press/v80/weisz18a.html %V 80 %X We consider the problem of configuring general-purpose solvers to run efficiently on problem instances drawn from an unknown distribution. The goal of the configurator is to find a configuration that runs fast on average on most instances, and do so with the least amount of total work. It can run a chosen solver on a random instance until the solver finishes or a timeout is reached. We propose LeapsAndBounds, an algorithm that tests configurations on randomly selected problem instances for longer and longer time. We prove that the capped expected runtime of the configuration returned by LeapsAndBounds is close to the optimal expected runtime, while our algorithm’s running time is near-optimal. Our results show that LeapsAndBounds is more efficient than the recent algorithm of Kleinberg et al. (2017), which, to our knowledge, is the only other algorithm configuration method with non-trivial theoretical guarantees. Experimental results on configuring a public SAT solver on a new benchmark dataset also stand witness to the superiority of our method.
APA
Weisz, G., Gyorgy, A. & Szepesvari, C.. (2018). LeapsAndBounds: A Method for Approximately Optimal Algorithm Configuration. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:5257-5265 Available from https://proceedings.mlr.press/v80/weisz18a.html.

Related Material