ImpatientCapsAndRuns: Approximately Optimal Algorithm Configuration from an Infinite Pool
Gellert Weisz, András György, Wei-I Lin, Devon Graham, Kevin Leyton-Brown, Csaba Szepesvari, Brendan Lucier
Abstract
Algorithm configuration procedures optimize parameters of a given algorithm to perform well over a distribution of inputs. Recent theoretical work focused on the case of selecting between a small number of alternatives. In practice, parameter spaces are often very large or infinite, and so successful heuristic procedures discard parameters ``impatiently'', based on very few observations. Inspired by this idea, we introduce ImpatientCapsAndRuns, which quickly discards less promising configurations, significantly speeding up the search procedure compared to previous algorithms with theoretical guarantees, while still achieving optimal runtime up to logarithmic factors under mild assumptions. Experimental results demonstrate a practical improvement.
BibTeX
@inproceedings{NEURIPS2020_ca5520b5,
author = {Weisz, Gellert and Gy\"{o}rgy, Andr\'{a}s and Lin, Wei-I and Graham, Devon and Leyton-Brown, Kevin and Szepesvari, Csaba and Lucier, Brendan},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {17478--17488},
publisher = {Curran Associates, Inc.},
title = {ImpatientCapsAndRuns: Approximately Optimal Algorithm Configuration from an Infinite Pool},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/ca5520b5672ea120b23bde75c46e76c6-Paper.pdf},
volume = {33},
year = {2020}
}