%0 Conference Paper %1 WGySz19 %A Weisz, G. %A György, A. %A Szepesvári, Cs. %B ICML %D 2019 %K algorithm configuration, data heavy tail theory, %P 6707-6715 %T CapsAndRuns: An Improved Method for Approximately Optimal Algorithm Configuration %X We consider the problem of configuring general-purpose solvers to run efficiently on problem instances drawn from an unknown distribution, a problem of major interest in solver autoconfiguration. Following previous work, we focus on designing algorithms that find a configuration with near-optimal expected capped runtime while doing the least amount of work, with the cap chosen in a configuration-specific way so that most instances are solved. In this paper we present a new algorithm, CapsAndRuns, which finds a near-optimal configuration while using time that scales (in a problem dependent way) with the optimal expected capped runtime, significantly strengthening previous results which could only guarantee a bound that scaled with the potentially much larger optimal expected uncapped runtime. The new algorithm is simpler and more intuitive than the previous methods: first it estimates the optimal runtime cap for each configuration, then it uses a Bernstein race to find a near optimal configuration given the caps. Experiments verify that our method can significantly outperform its competitors.

@inproceedings{WGySz19, abstract = {We consider the problem of configuring general-purpose solvers to run efficiently on problem instances drawn from an unknown distribution, a problem of major interest in solver autoconfiguration. Following previous work, we focus on designing algorithms that find a configuration with near-optimal expected capped runtime while doing the least amount of work, with the cap chosen in a configuration-specific way so that most instances are solved. In this paper we present a new algorithm, CapsAndRuns, which finds a near-optimal configuration while using time that scales (in a problem dependent way) with the optimal expected capped runtime, significantly strengthening previous results which could only guarantee a bound that scaled with the potentially much larger optimal expected uncapped runtime. The new algorithm is simpler and more intuitive than the previous methods: first it estimates the optimal runtime cap for each configuration, then it uses a Bernstein race to find a near optimal configuration given the caps. Experiments verify that our method can significantly outperform its competitors.}, added-at = {2020-03-17T03:03:01.000+0100}, author = {Weisz, G. and Gy{\"o}rgy, A. and {Sz}epesv{\'a}ri, {Cs}.}, bdsk-url-1 = {http://proceedings.mlr.press/v54/hanawal17a.html}, biburl = {https://www.bibsonomy.org/bibtex/2a6fb5fe4b044e459814c0913d4b39af3/csaba}, booktitle = {ICML}, date-added = {2019-07-20 13:39:07 -0600}, date-modified = {2019-07-20 13:40:34 -0600}, interhash = {bc06afce3072f296658652eb6271beaa}, intrahash = {a6fb5fe4b044e459814c0913d4b39af3}, keywords = {algorithm configuration, data heavy tail theory,}, month = May, pages = {6707-6715}, pdf = {papers/ICML2019-CapsAndRuns.pdf}, timestamp = {2020-03-17T03:03:01.000+0100}, title = {{CapsAndRuns}: An Improved Method for Approximately Optimal Algorithm Configuration}, year = 2019 }