Algorithm configuration methods optimize the performance of a parameterized
heuristic algorithm on a given distribution of problem instances. Recent work
introduced an algorithm configuration procedure (‘Structured Procrastination’)
that provably achieves near optimal performance with high probability and with
nearly minimal runtime in the worst case. It also offers an $textit{anytime}$
property: it keeps tightening its optimality guarantees the longer it is run.
Unfortunately, Structured Procrastination is not $textit{adaptive}$ to
characteristics of the parameterized algorithm: it treats every input like the
worst case. Follow-up work (‘Leaps and Bounds’) achieves adaptivity but trades
away the anytime property. This paper introduces a new algorithm configuration
method, ‘Structured Procrastination with Confidence’, that preserves the
near-optimality and anytime properties of Structured Procrastination while
adding adaptivity. In particular, the new algorithm will perform dramatically
faster in settings where many algorithm configurations perform poorly; we show
empirically that such settings arise frequently in practice.

Source link