LEAPSANDBOUNDS: A Method for Approximately Optimal Algorithm Configuration

By Gellért Weisz, András György, Csaba Szepesvari. 2018

37 citations recorded by the source corpus.

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Marc-André Zöller
2. Marco F. Huber
3. Maryam Ashoori
4. Yufan Jiang
5. Li Yang
6. Xin He
7. Tien-Dung Nguyen

Citations in the corpus

• Benchmark and Survey of Automated Machine Learning Frameworks (2019, background): “By evaluating multiple problem instances in parallel, long running instances can be discarded early (Weisz et al., 2018; Li et al., 2020).”
• Survey on Automated Machine Learning (2019, background): “By evaluating multiple problem instances in parallel, a dynamic runtime threshold can be computed to abort long running instances while still preserving the theoretical quality guarantees (Weisz et al., 2018).”