Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration

Kevin Leyton-Brown                                                                                                                      University of British Columbia

See the media page for the video of the talk.

Algorithm configuration methods optimize the performance of parameterized heuristic algorithms on given distributions of problem instances; they can be seen as extending classical machine learning to hypothesis spaces consisting of algorithm designs.

This talk will begin by defining the problem and illustrating its promise via some recent practical success stories. It will then turn to a theoretical problem that should interest both the FOGA and COSEAL communities: while existing methods for algorithm configuration achieve good performance in practice, they lack meaningful performance guarantees. Indeed, we show that all widely used algorithm configuration methods have poor asymptotic runtime performance in the worst case. In contrast, a new algorithm configuration approach called Structured Procrastination with Confidence (SPC) achieves approximately optimal runtime. More precisely, with high probability and nearly as quickly as possible in the worst case, SPC finds an algorithm configuration that provably achieves near optimal performance. SPC has two other important properties. First, it is *adaptive*: it dramatically exceeds its worst-case performance when algorithm configurations exhibit high runtime variance. Second, it is *anytime*: it keeps tightening its performance guarantees the longer it is run. Empirically, we show that such high variance settings arise frequently in practice and that the anytime property is useful for finding good configurations quickly.