---
abstract: '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 *anytime* property: it keeps tightening its optimality guarantees the longer it is run. Unfortunately, Structured Procrastination is not *adaptive* to characteristics of the parameterized algorithm: it treats every input like the worst case. Follow-up work (“LeapsAndBounds”) achieves adaptivity but trades away the anytime property. This paper introduces a new algorithm, “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 both that such settings arise frequently in practice and that the anytime property is useful for finding good configurations quickly.'
author:
- |
    Robert Kleinberg\
    Department of Computer Science\
    Cornell University\
    `rdk@cs.cornell.edu` Kevin Leyton-Brown\
    Department of Computer Science\
    University of British Columbia\
    `kevinlb@cs.ubc.ca` Brendan Lucier\
    Microsoft Research\
    `brlucier@microsoft.com` Devon Graham\
    Department of Computer Science\
    University of British Columbia\
    `drgraham@cs.ubc.ca`
bibliography:
- 'main.bib'
title: 'Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration'
---

Introduction
============

Algorithm configuration is the task of searching a space of *configurations* of a given algorithm (typically represented as joint assignments to a set of algorithm parameters) in order to find a single configuration that optimizes a performance objective on a given distribution of inputs. In this paper, we focus exclusively on the objective of minimizing average runtime. Considerable progress has recently been made on solving this problem in practice via general-purpose, heuristic techniques such as ParamILS [@hutter-aaai07a; @hutter-jair09a], GGA [@ansotegui-cp09a; @ansotegui-ijcai15a], irace [@birattari-gecco02a; @lopez-ibanez-tech11a] and SMAC [@hutter-bayesopt11; @hutter-lion11a]. Notably, in the context of this paper, all these methods are *adaptive*: they surpass their worst-case performance when presented with “easier” search problems.

Recently, algorithm configuration has also begun to attract theoretical analysis. While there is a large body of less-closely related work that we survey in Section \[sec:related\], the first nontrivial worst-case performance guarantees for general algorithm configuration with an average runtime minimization objective were achieved by a recently introduced algorithm called *Structured Procrastination (SP)* [@ijcai17]. This work considered a worst-case setting in which an adversary causes every deterministic choice to play out as poorly as possible, but where observations of random variables are unbiased samples. It is straightforward to argue that, in this setting, any fixed, deterministic heuristic for searching the space of configurations can be extremely unhelpful. The work therefore focuses on obtaining candidate configurations via random sampling (rather than, e.g., following gradients or taking the advice of a response surface model). Besides its use of heuristics, SMAC also devotes half its runtime to random sampling. Any method based on random sampling will eventually encounter the optimal configuration; the crucial question is the amount of time that this will take. The key result of @ijcai17 is that SP is guaranteed to find a near-optimal configuration with high probability, with worst-case running time that nearly matches a lower bound on what is possible and that asymptotically dominates that of existing alternatives such as SMAC.

Unfortunately, there is a fly in the ointment: SP turns out to be impractical in many cases, taking an extremely long time to run even on inputs that existing methods find easy. At the root, the issue is that SP treats every instance like the worst case, in which it is necessary to achieve a fine-grained understanding of every configuration’s runtime in order to distinguish between them. For example, if every configuration is very similar but most are not quite ${\varepsilon}$-optimal, subtle performance differences must be identified. SP thus runs every configuration enough times that with high probability the configuration’s runtime can accurately be estimated to within a $1+{\varepsilon}$ factor.

<span style="font-variant:small-caps;">LeapsAndBounds</span> and <span style="font-variant:small-caps;">CapsAndRuns</span> {#sec:beyond}
--------------------------------------------------------------------------------------------------------------------------

@weisz2018leapsandbounds introduced a new algorithm, <span style="font-variant:small-caps;">LeapsAndBounds (LB)</span>, that improves upon Structured Procrastination in several ways. First, LB improves upon SP’s worst-case performance, matching its information-theoretic lower bound on running time by eliminating a log factor. Second, LB does not require the user to specify a runtime cap that they would never be willing to exceed on any run, replacing this term in the analysis with the runtime of the optimal configuration, which is typically much smaller. Third, and most relevant to our work here, LB includes an adaptive mechanism, which takes advantage of the fact that when a configuration exhibits low variance across instances, its performance can be estimated accurately with a smaller number of samples. However, the easiest algorithm configuration problems are probably those in which a few configurations are much faster on average than all other configurations. (Empirically, many algorithm configuration instances exhibit just such non-worst-case behaviour; see our empirical investigation in the Supplementary Materials.) In such cases, it is clearly unnecessary to obtain high-precision estimates of each bad configuration’s runtime; instead, we only need to separate these configurations’ runtimes from that of the best alternative. LB offers no explicit mechanism for doing this. LB also has a key disadvantage when compared to SP: it is not anytime, but instead must be given fixed values of ${\varepsilon}$ and $\delta$. Because LB is adaptive, there is no way for a user to anticipate the amount of time that will be required to prove $({\varepsilon},\delta)$-optimality, forcing a tradeoff between the risks of wasting available compute resources and of having to terminate LB before it returns an answer.

<span style="font-variant:small-caps;">CapsAndRuns (CR)</span> is a refinement of LB that was developed concurrently with the current paper; it has not been formally published, but was presented at an ICML 2018 workshop [@weisz2018capsandruns]. CR maintains all of the benefits of LB, and furthermore introduces a second adaptive mechanism that does exploit variation in configurations’ mean runtimes. Like LB, it is not anytime.

Our Contributions
-----------------

Our main contribution is a refined version of SP that maintains the anytime property while aiming to observe only as many samples as necessary to separate the runtime of each configuration from that of the best alternative. We call it “Structured Procrastination with Confidence” (SPC). SPC differs from SP in that it maintains a novel form of lower confidence bound as an indicator of the quality of a particular configuration, while SP simply uses that configuration’s sample mean. The consequence is that SPC spends much less time running poorly performing configurations, as other configurations quickly appear better and receive more attention. We initialize each lower bound with a trivial value: each configuration’s runtime is bounded below by the fastest possible runtime, $\kappa_0$. SPC then repeatedly evaluates the configuration that has the most promising lower bound.[^1] We perform these runs by “capping” (censoring) runs at progressively doubling multiples of $\kappa_0$. If a run does not complete, SPC “procrastinates”, deferring it until it has exhausted all runs with shorter captimes. Eventually, SPC observes enough completed runs of some configuration to obtain a nontrivial upper bound on its runtime. At this point, it is able to start drawing high-probability conclusions that other configurations are worse.

Our paper is focused on a theoretical analysis of SPC. We show that it identifies an approximately optimal configuration using running time that is nearly the best possible in the worst case; however, so does SP. The key difference, and the subject of our main theorem, is that SPC also exhibits near-minimal runtime beyond the worst case, in the following sense. Define an $({\varepsilon},\delta)$-suboptimal configuration to be one whose average runtime exceeds that of the optimal configuration by a factor of more than $1+{\varepsilon}$, even when the suboptimal configuration’s runs are capped so that a $\delta$ fraction of them fail to finish within the time limit. A straightforward information-theoretic argument shows that in order to verify that a configuration is $({\varepsilon},\delta)$-suboptimal it is sufficient—and may also be necessary, in the worst case—to run it for $O({\varepsilon}^{-2} \cdot \delta^{-1} \cdot {\text{OPT}})$ time. The running time of SPC matches (up to logarithmic factors) the running time of a hypothetical “optimality verification procedure” that knows the identity of the optimal configuration, and for each suboptimal configuration $i$ knows a pair $({\varepsilon}_i,\delta_i)$ such that $i$ is $({\varepsilon}_i,\delta_i)$-suboptimal and the product ${\varepsilon}_i^{-2} \cdot \delta_i^{-1}$ is as small as possible.

SPC is anytime in the sense that it first identifies an $({\varepsilon},\delta)$-optimal configuration for large values of ${\varepsilon}$ and $\delta$ and then continues to refine these values as long as it is allowed to run. This is helpful for users who have difficulty setting these parameters up front, as already discussed. SPC’s strategy for progressing iteratively through smaller and smaller values of ${\varepsilon}$ and $\delta$ also has another advantage: it is actually faster than starting with the “final” values of ${\varepsilon}$ and $\delta$ and applying them to each configuration. This is because extremely weak configurations can be dismissed cheaply based on large $({\varepsilon}, \delta)$ values, instead of taking more samples to estimate their runtimes more finely.

Other Related Work {#sec:related}
------------------

There is a large body of related work in the multi-armed bandits literature, which does not attack quite the same problem but does similarly leverage the “optimism in the face of uncertainty” paradigm and many tools of analysis [@lai1985asymptotically; @auer2002finite; @bubeck2012regret]. We do not survey this work in detail as we have little to add to the extensive discussion by @ijcai17, but we briefly identify some dominant threads in that work. Perhaps the greatest contact between the communities has occurred in the sphere of hyperparameter optimization [@bergstra2011algorithms; @thornton2013auto; @li2016hyperband] and in the literature on bandits with correlated arms that scale to large experimental design settings [@kleinberg2006anytime; @kleinberg2008multi; @chaudhuri2009parameter; @bubeck2011x; @srinivas2012information; @cesa2012combinatorial; @munos2014bandits; @shahriari2016taking]. In most of this literature, all arms have the same, fixed cost; others [@guha2007approximation; @tran2012knapsack; @badanidiyuru2013bandits] consider a model where costs are variable but always paid in full. (Conversely, in algorithm configuration we can stop runs that exceed a captime, yielding a potentially censored sample at bounded cost.) Some influential departures from this paradigm include @kandasamy2016multi, @ganchev2010censored, and most notably @li2016hyperband; reasons why these methods are nevertheless inappropriate for use in the algorithm configuration setting are discussed at length by @ijcai17.

Recent work has examined the learning-theoretic foundations of algorithm configuration, inspired in part by an influential paper of @gupta2017pac that framed algorithm configuration and algorithm selection in terms of learning theory. This vein of work has not aimed at a general-purpose algorithm configuration procedure, as we do here, but has rather sought sample-efficient, special-purpose algorithms for particular classes of problems, including combinatorial partitioning problems (clustering, max-cut, etc) [@balcan2017learning], branching strategies in tree search [@balcan2018learning], and various algorithm selection problems [@Vitercik2018]. Nevertheless, this vein of work takes a perspective similar to our own and demonstrates that algorithm configuration has moved decisively from being solely the province of heuristic methods to being a topic for rigorous theoretical study.

Model
=====

We define an algorithm configuration problem by the 4-tuple $(N, \Gamma, R, \kappa_0)$, where these elements are defined as follows. $N$ is a family of (potentially randomized) algorithms, which we call *configurations* to suggest that a single piece of code instantiates each algorithm under a different parameter setting. We do not assume that different configurations exhibit any sort of performance correlations, and can so capture the case of $n$ distinct algorithms by imagining a “master algorithm” with a single, $n$-valued categorical parameter. Parameters are allowed to take continuous values: $|N|$ can be uncountable. We typically use $i$ to index configurations. $\Gamma$ is a probability distribution over input instances. When the instance distribution is given implicitly by a finite benchmark set, let $\Gamma$ be the uniform distribution over this set. We typically use $j$ to index (input instance, random seed) pairs, to which we will hereafter refer simply as instances. $R(i,j)$ is the execution time when configuration $i \in N$ is run on input instance $j$. Given some value of $\theta > 0$, we define $R(i,j,\theta) = \min\{R(i,j), \theta\}$, the runtime capped at $\theta$. $\kappa_0 > 0$ is a constant such that $R(i,j) \geq \kappa_0$ for all configurations $i$ and inputs $j$.

For any timeout threshold $\theta$, let $R_\theta(i) = {\mathrm{E}}_{j \sim \Gamma}[R(i,j,\theta)]$ denote the average $\theta$-capped running time of configuration $i$, over input distribution $\Gamma$. Fixing some running time $\bar{\kappa} = 2^{\beta} \kappa_0$ that we will never be willing to exceed, the quantity $R_{\bar{\kappa}}(i)$ corresponds to the expected running time of configuration $i$ and will be denoted simply by $R(i)$. We will write $OPT = \min_i R(i)$. Given $\epsilon > 0$, a goal is to find $i^* \in N$ such that $R(i^*) \leq (1+\epsilon) OPT$. We also consider a relaxed objective, where the running time of $i^*$ is [*capped*]{} at some threshold value $\theta$ for some small fraction of (instance, seed) pairs $\delta$.

\[def:eps-delta-opt\] A configuration $i^*$ is *$(\epsilon,\delta)$-optimal* if there exists some threshold $\theta$ such that $R_{\theta}(i^*) \leq
(1+\epsilon) OPT$, and $\Pr_{j \sim \Gamma} \big( R(i^*,j) > \theta \big) \leq \delta$. Otherwise, we say $i^*$ is *$(\epsilon, \delta)$-suboptimal*.

[^1]: While both SPC and CR use confidence bounds to guide search, they take different approaches. Rather than rejecting configurations whose lower bounds get too large, SPC focuses on configurations with small lower bounds. By allocating a greater proportion of total runtime to such promising configurations we both improve the bounds for configurations about which we are more uncertain and allot more resources to configurations with relatively low mean runtimes about which we are more confident.
