Efficiency Through Procrastination: Approximately Optimal Algorithm Configuration with Runtime Guarantees

1 Introduction

Algorithm configuration techniques have received considerable study in artificial intelligence over the past decade. General-purpose procedures include ParamILS [Hutter et al., 2007; 2009], GGA [Ans´otegui et al., 2009; 2015], irace [Birattari et al., 2002; L´opez-Ib´a˜nez et al., 2011] and SMAC [Hutter et al., 2011b; 2011a]. All of these methods have demonstrated significant successes in practice. However, they are also all heuristic: they cannot assess how close they have come to finding an optimal algorithm configuration, and offer no theoretical guarantees about the running time they would require to find such a configuration.

We focus on such guarantees, and thus consider the worstcase expected performance of algorithm configuration methods. Specifically, we assume that an adversary causes every deterministic choice to prolong runtime as much as possible, while observations of random variables are unbiased samples from the underlying distribution. Under this analytic framework, gradient-following methods like ParamILS and GGA can perform very poorly: in the worst case, gradients will lead the search astray and optimal configurations will not be surrounded by large basins of attraction. (Of course, such methods can nevertheless perform well in practice, as extensive experimental evidence shows that they often do; our concern in this paper is exclusively with worst-case analysis rather than such empirical investigations.) Similarly, Bayesian optimization methods like SMAC can learn misleading models that will drive the search to investigate unpromising regions of the configuration space. However, as a hedge against a misleading model, SMAC guarantees that it spends half of its time examining randomly sampled configurations. Such

Brendan Lucier

Microsoft Research brlucier@microsoft.com

samples are immune to the manipulations of an adversary. Indeed, SMAC is defined as an extended version of a model-free method, ROAR, that works entirely by such random sampling.

This paper proposes an algorithm configuration method, Structured Procrastination, that is similarly based on random sampling, but that is accompanied by a nontrivial runtime guarantee. All random-sampling-based methods like SMAC and ROAR eventually encounter the optimal configuration; the crucial question, therefore, is how long it takes for a method to do so. We call a method incumbent driven if it only ever sets timeouts for algorithm runs either at a fixed maximum timeout or at a predetermined fraction of the best runtime that some "incumbent" configuration has achieved on any problem instance. (This argument is made more formally in Section 3.) We demonstrate that our approach takes arbitrarily less time to find a configuration close to optimal than any incumbent-driven algorithm configurator, where this arbitrarily large gap depends on the ratio between the running time of any candidate incumbent on its best-case instance and the running time of the optimal configuration averaged across instances. All algorithm configuration methods of which we are aware are incumbent diven (notably, ParamILS, GGA, irace, SMAC, and ROAR); 1 thus, to our knowledge our method provides the best worst-case runtime guarantees.

The literature on multi-armed bandits provides another important source of related work. Indeed, our method is structurally similar to various methods from that literature, leveraging the influential "optimism in the face of uncertainty" paradigm [Auer et al., 2002; Bubeck et al., 2012], and we employ similar analytic tools. Furthermore, there has already

1 However, the public software releases of both SMAC and ParamILS support experimental command-line options, never described in any publication, that produce non-incumbent-driven behavior. In both cases, preliminary experiments did not provide strong evidence that these options yielded substantially improved performance. Nevertheless, we describe them here for completeness. SMAC (and hence ROAR) has an option --init-mode that affects the initialization phase that precedes the subsequent, incumbent-driven search. This option can be used to direct SMAC to iteratively increase captimes until a sufficient fraction of preselected initialization configurations complete. ParamILS has an option -id that causes it to execute in stages of increasing time budgets and doubling captimes, where the incumbent from stage k is used as the initial configuration for stage k + 1. Our subsequent discussion of SMAC, ROAR, and ParamILS focuses only on the algorithms as described in publications.

been considerable contact between the algorithm configuration and bandits communities, largely in the sphere of hyperparameter optimization [Bergstra et al., 2011; Thornton et al., 2013; Li et al., 2016] and in the literature on bandits with correlated arms that are able to scale to large experimental design settings [Kleinberg, 2006; Kleinberg et al., 2008; Chaudhuri et al., 2009; Bubeck et al., 2011; Srinivas et al., 2012; Cesa-Bianchi and Lugosi, 2012; Munos, 2014]; see also the survey by Shahriari et al. [2016]. Nevertheless, the runtime minimization objective of algorithm configuration is crucially different from the more general objective functions targeted in most of the bandits literature. First, our cost of pulling an arm is measured in the same units as the objective function to be minimized; we aim to find the arm with the lowest expected cost (ranging over both instances and random seeds). Second, we have the freedom to set a maximum amount x we are willing to pay in pulling an arm; if the true cost exceeds x, we pay only x but learn only that the true cost was higher. In contrast, in a general bandits setting, pulling arms is an all-or-nothing operation. In most of the literature, all arms simply involve the same, fixed cost. An alternative body of work has variable costs and a fixed overall budget [Guha and Munagala, 2007; Tran-Thanh et al., 2012; Badanidiyuru et al., 2013]; here, however, one always pays the full cost associated with that arm (whether fixed or variable) and observes a sample from the underlying distribution. Because all methods with this property fail to avail themselves of the option to cap long runs before they terminate, these methods are again incumbent driven, and hence our separation theorem applies.

A few methods depart from this paradigm. In some cases, the algorithm can specify a maximum cost to be paid when pulling an arm, but never pays less than that specified budget [Kandasamy et al., 2016]. Our setting is different (a run that does not time out costs less than its runtime budget to evaluate), and in the most natural way of translating such algorithms to our setting, they are again incumbent driven. Work by Ganchev et al. [2010] is similar because it considers bandits where observations are censored if they exceed a given budget. Nevertheless, this setting is different enough that there is no natural way to map its algorithm onto the algorithm configuration domain: Ganchev et al. consider a maximization (rather than minimization) objective; they also choose a vector of "allocations" across many arms at each time step that sum to an exogenously specified amount, rather than choosing only one arm to run for an endogenously specified amount of time.

Finally, the Hyperband algorithm of Li et al. [2016] is perhaps the closest to our work. They reason about a setting in which the quality of a hyperparameter configuration can be approximated with increasing fidelity as more time is devoted to assessing it. They propose an approach in which a large number n of configurations are assessed, each with a time budget B/n; the worst half of configurations are discarded; the remaining configurations are given doubled captimes (B/0.5n); and the process continues until only one configuration remains. This whole process runs inside an outer loop that performs a grid search trading off the number of initial configurations n against the initial captime B/n (i.e., holding B constant). Replacing the term "hyperparameter configuration" with "algorithm configuration", this approach would seem applicable to our setting. Indeed, both Hyperband and our own approach take inspiration from the bandits literature, so this similarity is more than superficial. However, it turns out to be highly nontrivial to fill in the details. First, given the decision to evaluate a configuration for time B/n, how should this time budget be allocated across the infinite stream of available (instance, seed) pairs? Second, after the allocated runs have completed for configuration i, how should the measured runtimes-some of which may represent capped runs-be aggregated to form an estimate of i's expected runtime across (instance, seed) pairs? (Li et al. require simply that these estimates converge to the correct answer as the time allocated to configuration i goes to infinity.) Third, when i is reconsidered with a longer time budget, how should the choices of which runs to preform and which performance estimates to return depend on previous runs? (Li et al. do not explicitly propose such dependence, since they consider arbitrary performance functions that do not decompose across (instance, seed) pairs; however, doing better than restarting from scratch at each iteration is critical in our domain, and indeed our core idea of "procrastination" addresses this issue.) We are not aware of any way to answer these questions within the Hyperband framework without obtaining a worst-case bound that is asymptotically worse than ours, and we suspect that it is not possible to do so. Nevertheless, we see our paper's main technical contribution as the adaptation of existing bandits approaches such as Hyperband to the algorithm configuration setting.

In what follows, we define the problem we address more formally (Section 2) and provide a lower bound on the runtime of incumbent-driven algorithm configuration approaches (Section 3). We then present our own approach, Structured Procrastination. We begin by considering the case of a small set of configurations among which we would like to identify the best (Section 4). We then consider large or continuous spaces of configurations, and aim to identify a configuration with performance in the top 1/γ-quantile across the set of configurations, where γ shrinks as the algorithm runs (Section 5). In both cases, we show that our procedure approximately optimizes the desired objective with high probability. Its runtime is asymptotically better than the lower bound for incumbentdriven procedures developed earlier; in Section 6 we also show that it is optimal up to a logarithmic factor. Section 7 shows how Structured Procrastination can be extended to work with Bayesian optimization approaches such as SMAC and how it can achieve linear speedups when parallelized.

2 Problem Statement

We define an algorithm configuration problem by the 4-tuple (N, Γ,R, κ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. Γ is a probability distribution over input instances. When the instance distribution is given implicitly by a finite benchmark set, let Γ 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 ∈ N is run on input instance j. Given some value of θ > 0, we define R(i, j, θ) = min{R(i, j), θ}, the runtime capped at θ. κ0 > 0 is a constant such that R(i, j) ≥ κ0 for all configurations i and inputs j.

Informally, our goal is to find a configuration from N with the minimum average running time over the input space Γ and over its own random seeds. We are allowed to execute any configuration on any input and adaptively terminate any such execution at any time. More precisely, for any timeout threshold θ, let Rθ(i) = Ej∼Γ[R(i, j, θ)] denote the average running time of configuration i, over distribution Γ of input instances. Fixing some running time ¯κ = 2β κ0 that we will never be willing to exceed, the quantity R¯κ(i) corresponds to the expected running time of configuration i and will be denoted simply by R(i) . Given ϵ > 0, a basic problem is to find i∗ ∈ N such that R(i∗ ) ≤ (1 + ϵ)mini{R(i)}. It will turn out, from the standpoint of worst-case guarantees, that this goal is too ambitious because it is too hard to estimate R(i) when the running-time distribution of i is very heavytailed. If the average running time is driven by a small set of bad inputs that occur very rarely, but induce configuration i to run for an astronomical number of steps when they occur, then the only way to accurately estimate the average running time of configuration i is to run it on enough inputs that we see enough of these "black swans." This pathological scenario leads to worst-case bounds that scale linearly with ¯κ even when mini{R(i)} ≪ ¯κ; see Section 6. To avoid an analysis aimed at such pathologies, we relax our objective by allowing the running time of i∗ to be capped at some threshold value θ for some small fraction of (instance, seed) pairs δ.

Definition 2.1 A configuration i∗ is (ϵ, δ)-optimal if there exists some threshold θ such that Rθ(i∗ ) ≤ (1 + ϵ) mini{R(i)}, and Prj∼Γ (R(i∗ , j) > θ) ≤ δ. Otherwise, we say i∗ is (ϵ, δ)-suboptimal.

Example 2.2 Consider 3 deterministic configurations, N = {C1, C2, C3}, with Γ as the uniform distribution over 1000 input instances. Runtime is measured in ms, with κ0 = 1 and timeout ¯κ = 220 . Configuration C1 has runtime 10 for all instances and hence R(C1) = 10. Configuration C2 has runtime 1000 for 10 out of the 1000 instances and runtime 11 for the remaining instances; i.e., R(C2) = 20.89. Configuration C3 has runtime 1000 for 100 input instances, runtime 100 for 100 input instances, and runtime 5 for the remaining instances; i.e., R(C3) = 114. C1 is optimal. Since R11(C2) = 11 and Pr[R(C2, j) > 11] = 0.01, C2 is (0.1, 0.01)-optimal. Since R5(C3) = 5 ≤ 10 and Pr[R(C3, j) > 5] = 0.2, C3 is (0, 0.2)-optimal. Additionally, R100(C3) = 24 and Pr[R(C3, j) > 100] = 0.1, so C3 is also (1.4, 0.1)-optimal.

3 Runtime of Incumbent-Driven Procedures

In this section we develop a lower bound on the runtime of what we call incumbent-driven approaches, which as discussed above include most widely used algorithm configuration procedures. We describe algorithm configurators' queries of target algorithm runtimes via the subroutine RUN(i, j, θ), which executes configuration i on instance j and caps the run if it does not complete after θ seconds. This subroutine takes time R(i, j, θ), and returns the value R(i, j, θ).

We say that a search procedure is incumbent-driven if, whenever a query RUN(i, j, θ) is made, it must be that either θ = ¯κ or θ ≥ RUN(i′ , j ′ , θ′ ) for some query RUN(i′ , j ′ , θ′ ) that was executed previously. Such procedures can be thought of as either performing unconditional algorithm runs (capping only at the maximum runtime ¯κ) or maintaining an 'incumbent' best algorithm and using previously observed runtimes to bound the amount of time needed to run an alternative 'challenger' algorithm before determining which is preferable (as is done, e.g., by the "adaptive capping" mechanisms in ParamILS, ROAR, and SMAC).

Example 3.1 Consider a discrete set N of n configurations, indexed so that R(1) < R(2) < . . . < R(n). Each configuration's runtime is tightly concentrated around its expectation, so that i has runtime nearly R(i) on every input instance. Moreover, R2/R1 is large, meaning that configuration 1 is significantly faster than the others. Any incumbent-driven search procedure must begin by choosing a configuration and executing it until completion. Since the configurations are initially indistinguishable, the choice of which to execute is essentially random, so this takes time at least R2, with probability at least 1 - 1/n (the probability that algorithm 1 is not chosen).

In comparison to the example above, our search procedure takes time rougly proportional to nR1. If n is smaller than the ratio R2/R1, this can be a significant improvement. The same idea can be formalized to show that any incumbent-driven search procedure can experience arbitrarily poor runtime performance with arbitrarily high probability. Here we handle the more realistic setting of a continuum of candidate configurations, by speaking about the fraction of configurations with favorable runtimes; see Section 5 for details.

Theorem 3.2 For any incumbent-driven search procedure, any γ > 0, and any runtimes R1 < R2, there is an algorithm configuration problem in which a γ fraction of all possible configurations have average runtime no greater than R1, but with probability at least (1 - γ) the search procedure will require time at least R2.

4 The Case of FewConfigurations

We now describe our proposed algorithm configuration method. We begin by considering a case where the family N of configurations is finite and relatively small; we consider the alternative in Section 5. Let |N| = n and write OPT = mini R(i). Algorithm configuration in this case boils down to selecting the configuration with smallest expected runtime from a fixed set of alternatives. This problem may seem straightforward: we could simply run every configuration on every instance (capping at ¯κ). The catch is that we care about how long our procedure takes to run. To speed things up, we could sample instances at random from Γ, run every configuration on the sampled instances, and use Chernoff bounds

Algorithm 1: Structured Procrastination (few configs) require : Set N of n algorithm configurations require :Precision parameter ϵ ∈ (0, 13 ) require : Failure probability parameter ζ ∈ (0, 1) require :Lower and upper runtime bounds, κ0 and ¯κ require :Sequence j1, j2, . . . of (instance, seed) pairs // Initializations 1 β = log2(¯κ/κ0) 2 for i ∈ N do 3 ki := 0 4 ℓi := ⌈12ϵ-2 ln(3βn/ζ)⌉ 5 Qi := empty double-ended queue 6 for ℓ = 1, . . . , ℓi do 7 Riℓ := 0 8 Insert (ℓ, κ0) at tail of Qi // Main loop. Run until interrupted. 9 repeat 10 i := argmini∈N { 1 ki ∑ki ℓ=1 Riℓ} 11 Remove (ℓ, θ) from head of Qi 12 if Riℓ = 0 then // jℓ is a fresh instance 13 ki := ki +1 14 qi := ⌈12ϵ-2 ln(3βn(ki)2 /ζ)⌉ 15 if RUN(i, jℓ, θ) terminates in time t ≤ θ then 16 Riℓ := t 17 else 18 Riℓ = θ 19 Insert (ℓ, 2θ) at tail of Qi 20 while |Qi| < qi do // Replenish queue 21 ℓi := ℓi +1 22 Ri,ℓi := 0 23 Insert (ℓi, θ) at head of Qi 24 until anytime search is interrupted 25 return i∗ = argmaxi∈N {∑ki ℓ=1 Riℓ} , δ = √1+ϵ qi∗ ki∗

to bound the probability that we select an configuration with performance within some given constant factor of optimal. Or we could adopt a racing procedure such as F-Race [Birattari et al., 2002], evaluating configurations round robin and discarding those that statistically sufficient evidence shows are suboptimal (F-Race uses the nonparametric Friedman test). Observe that such racing procedures are incumbent driven.

This work shows that we can do even better, introducing the first algorithm configuration method with worst-case running time guarantees that are superior to all of these procedures. We call our method Structured Procrastination, in homage to the eponymous time management technique due to Stanford philosopher John Perry [1996] (for which he received the 2011 Ig Nobel Prize in Literature [Improbable Research, 2011]). In essence, Perry proposes maintaining a set of daunting and apparently important tasks that one procrastinates to avoid, thereby accomplishing other tasks. Eventually, each daunting task is superseded by a new task that is even more daunting, and is completed in its turn.

Similarly, our approach maintains lists of tasks (for each configuration i, a bounded-length queue Qi of (instance, captime) pairs describing runs that i should perform, initialized with instances constructed by randomly sampling from Γ and randomly sampling a seed, and with aggressive captimes of κ0), and procrastinates when these tasks prove daunting (need to be retried with doubled captimes). We maintain lower bounds on the expected runtime achieved by every configuration i, assigning expected runtime of zero to configurations on which no runs have yet been performed and otherwise averaging observed runtimes, treating capped runs as though they completed at their captimes. We then choose the task that we forecast will be easiest: the (instance, captime) pair at the head of the queue corresponding to the configuration i for which the lower bound on expected runtime is smallest. If the run does not complete within the specified captime, we will double the captime and try again. But doing so is a harder problem, so we procrastinate, adding this task to the tail of queue Qi, and instead choosing the easiest available task. The key way this approach differs from past work-and the reason it is not incumbent based-is its reliance on the idea of procrastination: we only ever spend a long time running a given configuration on a given instance after having failed to find any different instance that could be evaluated more quickly.

To run our method, the user must specify a precision parameter ϵ (how far solutions can be from optimal), a failure probability ζ (the maximum probability with which our guarantees can fail to hold), a maximum amount of time ¯κ that any configuration could ever be run, and a minimum amount of time κ0 below which configuration running times can be considered identical. The failures captured by ζ are due to the unlikely events that sampled instances are atypical; in our proofs below we bound this failure probability with speciallytailored statistical tests based on Chernoff and union bounds. As discussed above, we will identify (ϵ, δ)-optimal configurations; hence, we must specify δ, the fraction of "outlying" instances on which the returned configuration's running time may be capped. Unlike the other parameters, we do not believe that this is one that a user will know how to set in advance. Structured Procrastination thus runs in an anytime manner, gradually reducing δ; when it is stopped, it returns the δ for which its guarantee holds. We note that our algorithm does not return the configuration with the best empirical estimate, as might seemmost intuitive. Observe that our algorithm could spend most of its time testing one configuration, but right before anytime search is interrupted, a few outliers could inflate its estimate beyond that of a second configuration that received little scrutiny. We could not return the latter configuration and maintain strong statistical guarantees. Instead, our approach amounts to choosing the configuration that was most often the empirically best.

In more detail, for each configuration i there is a FIFO queue Qi, containing pairs (ℓ, θ) where ℓ is the index of an element jℓ in an infinite sequence of i.i.d. samples from the input distribution Γ and θ represents twice the timeout threshold that was applied the last time we attempted to run configuration i on instance jℓ. (The same sequence is used for every configuration, producing a blocking design [Dean and Voss, 1999].) When jℓ reaches the head of the queue we will attempt to run it for θ steps. In this way, the timeout threshold of any input instance j progressively doubles until we have successfully completed j. When an input instance j completes, we select the next "fresh" instance from the infinite sequence of random instances and insert it into the back of the queue, matching its timeout threshold with that of the element ahead of it. (Occasionally more than one such element is inserted because the desired queue length, qi, has increased.) In this way, we ensure three invariants. First, at any point in time, when the head of the queue is a pair (ℓ, θ), then all of the elements in the queue have a timeout threshold of either θ or 2θ. Second, each input instance that configuration i has already finished solving was completed in θ or fewer steps. Third, the queue's contents are arranged in non-decreasing order of timeout threshold.

Every instance j that has ever been inserted into Qi is either fresh, completed, or deferred, depending on whether the algorithm has never attempted to run configuration i on instance j, has run i on j until termination, or has attempted run i on j at least once but all such runs have timed out. The variable ki stores the number of completed or deferred instances, whereas ℓi stores the number of fresh, completed, or deferred instances. The value Riℓ stores the amount of time taken by the most recent call to RUN(i, j, θ) for the instance j = jℓ: it equals the capped running time R(i, j, θ) if j is completed or deferred, or 0 if j is fresh. The quantity 1 ki ∑ki ℓ=1 Riℓ therefore represents the average θ-capped running time of all the completed and deferred instances of configuration i, a quantity which we shall denote by Remp θ (i) henceforth. In each iteration of the main loop, the structured procrastination algorithm selects the configuration with the minimum average capped running time and processes the next element in that configuration's queue.

Example 4.1 Consider our algorithm's execution on Example 2.2, say with ϵ = 0.2 and failure probability ζ = 0.1. There are 3 queues, Q1,Q2,Q3, corresponding to configurations C1, C2, and C3. Each queue is initialized with ℓi input instances, which in this example is approximately 2248. Note that this is more than the total number of distinct input instances in our example; while we know that the number of inputs is limited, the search procedure does not know this a priori and its statistical tests suggest a minimum of this many inputs to yield the desired guarantees.

As instances are drawn from the queues (in round-robin fashion, since the configurations appear identical at first), their runtime caps are doubled until we reach threshold 8. At this point, assuming events follow expectations, roughly 80% of instances in Q3 terminate with a runtime of 5 while all other instances time out at 8. This causes C3 to have lower estimated average runtime than C1 or C2, so Algorithm 1 begins testing instances only from Q3. As instances are completed from C3's queue, they are replaced with fresh instances, some of which will also complete with a runtime of 5. Any instance that times out is sent to the back of the queue. If the search procedure is terminated at this point, C3 will be returned, and the corresponding δ will be greater than 0.2.

Eventually, Q3 becomes filled with instances that timed out at θ = 8. These instances must then be executed with higher thresholds, which slowly increases the runtime estimate for C3. This estimate grows and eventually overtakes the estimates for C1 and C2. Algorithm 1 then resumes testing instances from Q1 and Q2. Eventually we evaluate instances from Q1 with timeout θ = 16. At this point, all instances fromQ1 terminate with runtime 10, and eventually the runtime estimate for C1 drops below that of C2 and C3. The search procedure will return C1 if terminated after this point. Note that Algorithm 1 continues to evaluate instances from Q1 until termination. This can be interpreted as searching for outlier instances on which C1 has very poor runtime (which, in this example, do not exist). The longer the search continues, the more rare we conclude such outliers (if any) must be, and correspondingly the value of δ returned becomes smaller and smaller.

To justify this greedy rule of always choosing the configuration with minimum average capped runtime, we will show that, with high probability, we spend only a limited amount of time testing any individual (ϵ, δ)-suboptimal configuration. Consider any configuration i that satisfies R(i) > (1+ϵ)OPT. By Lebesgue's Monotone Convergence Theorem, we know that limθ→∞Rθ(i) = R(i), so let θ(i) be the smallest timeout threshold such that Rθ(i) > (1 + ϵ)OPT and θ(i)/κ0 is a power of 2. We will show that, with high probability, the Structured Procrastination algorithm will never attempt to run configuration i with timeout threshold θ(i). This will, in turn, imply an upper bound on the total running time devoted to experimenting with configuration i. In what follows, given a configuration i we will tend to write θ for the largest value such that each deferred instance in Qi has been executed with a threshold of at least θ.

Definition 4.2 An execution of the Structured Procrastination algorithm is called clean if it satisfies the following properties for every configuration i ∈ N, at all times during its execution.

Lemma 4.3 An execution of the Structured Procrastination algorithm is clean with probability at least 1 - ζ.

Proof Sketch: We use Chernoff bounds to verify that empirical averages of i.i.d. random variables are unlikely to deviate from their expected values by a factor greater than (1+ϵ)±1/2 . We adjust the constants in these bounds to account for the fact that the multiplicative error factor is expressed as (1 + ϵ)±1/2 instead of 1 ± ϵ. For (1) we define the random variables by Xℓ = 1 if R(i, jℓ) > θ and Xℓ = 0 otherwise. For (1) we define the random variables by Xℓ = 1 θ R(i, jℓ, θ).

During a clean execution, if an iteration of the main loop selects configuration i in Line 13, then Lemma 4.3 implies

This implies that θ ≤ θ(i). Consequently, if we let δ(i) denote the fraction of input instances j (under distribution Γ) that satisfy R(i, j) ≥ θ(i), then Prj∼Γ(R(i, j) ≥ θ) ≥ δ(i).

Lemma 4.3 now implies that

The equation implies an upper bound on ki, but it requires a tedious calculation to extract the upper bound because the right side depends on ki. Assuming the failure probability parameter ζ is less than βn/600, this calculation implies

Our next theorem shows that for every δ, there exists a bounded amount of time after which our algorithm outputs an (ϵ, δ)-optimal configuration with high probability.

Theorem 4.4 For any δ > 0, if an execution of the Structured Procrastination algorithm is halted at any time

then it outputs an (ϵ, δ)-optimal configuration with probability at least 1- ζ.

Proof: With probability 1 - ζ the execution is clean. We will show that a clean execution running for T or more steps can never output an (ϵ, δ)-suboptimal configuration. If i is (ϵ, δ)- suboptimal then δ(i) ≥ δ. Above we have argued that over the entire course of a clean execution, ki satisfies the upper bound in (4). The total running time invested in configuration i up to time T is ∑ki ℓ=1 Riℓ, which is at most 3kiRemp θ , where θ denotes the largest value such that each deferred instance in Qi has been executed with a threshold of at least θ. Owing to the greedy rule that was used to select configuration i at that time, we know that the inequality Remp θ (i) ≤ Remp θ (iopt ) held at that time, and hence Remp θ (i) < (1 + ϵ)1/2OPT by Lemma 4.3. Multiplying this inequality by (4), and using the fact that ϵ < 13 , we find that the total time spent running configuration i is bounded by

leveraging our assumption that ϵ < 1 3 .

Let N(ϵ, δ) = {all (ϵ, δ)-suboptimal configurations}. Subtracting the right side of (5) for each i ∈ N(ϵ, δ) from T , the remainder is at least |N\N(ϵ, δ)| · 104 δϵ2 ln ( 3βn ζδϵ2 ) OPT. By the pigeonhole principle, at least one of the |N \N(ϵ, δ)| configurations that is (ϵ, δ)-optimal has run for at least 104 δϵ2 ln ( 3βn ζδϵ2 ) time steps before time T. This is greater than the amount of time that has been invested in running any of the (ϵ, δ)- suboptimal configurations, by (5) and the fact that δ(i) > δ for every (ϵ, δ)-suboptimal configuration i. Therefore, when the Structured Procrastination algorithm is stopped at time T and it outputs the i∗ which has run for the greatest total amount of time thus far, if the execution is clean then it will choose an (ϵ, δ)-optimal configuration.

5 The Case of Many Configurations

Our method of choosing among a relatively small set of configurations, while interesting (and useful for what follows), is far from a general algorithm configuration method. The catch is that our runtime guarantee is linear in n, the number of configurations. This is unavoidable when each configuration must be considered explicitly, since if a configuration is not tried there is no way of being sure that it is not dramatically faster than all others. This is not too high a price to pay when n is small. In a general algorithm configuration application, however, it is common for parameters to number in the dozens or even hundreds, and furthermore for some parameters to have continuous domains. Thus, an approach based on explicitly testing each configuration cannot work.

We must therefore relax the requirement that we identify a configuration with performance close to that of the very best one-this best configuration could be arbitrarily better than others, and hidden by an adversary in the last part of the search space that we check, making it a 'needle in a haystack' that is effectively impossible to find. Instead, our relaxed objective will be to find a configuration with performance in the top ⌊1/γ⌋-quantile. (Alternately, we will seek a configuration with performance close to the best one that remains after we exclude the γ fraction of fastest configurations from N, treating rare but exceptionally good configurations as outliers.) Our approach to achieving this relaxed goal is to use a variant of Algorithm 1 to find the (approximately) best configuration from among a set of configurations sampled from the population. This random sample serves as a net with which we search the configuration space. Our search procedure will incrementally tighten this net by sampling additional configurations as necessary. While the Structured Procrastination method from Section 4 improves (i.e., reduces) the parameter δ over time, our modified algorithm will gradually reduce both δ and the fraction γ of configurations treated as outliers.

Our procedure, given as Algorithm 2, builds on Algorithm 1. It runs in phases, with additional configurations sampled at the end of each phase. Each phase runs approximately twice as long as the last. Np is the set of configurations being tested in phase p ≥ 1. When the search procedure is terminated, it returns the configuration that had the longest total execution time in the most recently completed phase. It is parameterized by ω > 0, which controls the rate at which δ is improved relative to the number of configurations searched: the algorithm will return a configuration that is (ϵ, 1/nω )-optimal with respect to the best configuration in a sample of size n, where n grows over time.

We are now ready to state the performance guarantee of this modified Structured Procrastination method. Given a set N ′ of configurations, write OPT(N ′ ) = mini∈N ′ R(i).

Theorem 5.1 For any n ≥ n0 there exists some n′ ≥ n such that if Algorithm 2 is halted at any time

where N ′ = {i1, . . . , in′} (from Algorithm 2), then it outputs a configuration that is (ϵ, n-ω )-optimal with respect to N ′ with probability at least 1 - ζ.

require :Minimum number of configurations n0 require : Tradeoff parameter ω > 0 require :Precision parameter ϵ ∈ (0, 13 ) require : Failure probability parameter ζ ∈ (0, 1) require :Lower and upper runtime bounds, κ0 and ¯κ require :Sequence i1, i2, . . . of configurations require :Sequence j1, j2, . . . of (instance, seed) pairs // Initializations 1 Define function T (n) := 40n1+ω ϵ-2 ln(3n1+ω /ζ 2 ϵ2 ) 2 n := n0, N0 := ∅, T:=0, β := log2(¯κ/κ0) // Main loop. Run until interrupted. 3 for p = 1, 2, 3, . . . do // Ensure that we have n initialized queues 4 Np := {i1, . . . , in}, Tip := 0 for all i = 1, . . . , n 5 for i ∈ Np\Np-1 do 6 ki := 0 7 ℓi := ⌈12ϵ-2 ln(3βn/ζ)⌉ 8 Qi := empty double-ended queue 9 for ℓ = 1, . . . , ℓi do 10 Riℓ := 0 11 Insert (ℓ, κ0) at tail of Qi 12 repeat 13 i := argmini∈N { 1 ki ∑ki ℓ=1 Riℓ} 14 Remove (ℓ, θ) from head of Qi 15 if Riℓ = 0 then // jℓ is a fresh instance 16 ki := ki +1 17 qi := ⌈12ϵ-2 ln(3βn(ki)2 /ζ)⌉ 18 if RUN(i, jℓ, θ) terminates in time t ≤ θ then 19 Riℓ := t 20 else 21 Riℓ := θ 22 Insert (ℓ, 2θ) at tail of Qi 23 T := T +Riℓ // Total execution time 24 Ti,p := Ti,p +Riℓ // T , restricted to i and p 25 while |Qi| < qi do // Replenish queue 26 ℓi := ℓi +1 27 Ri,ℓi := 0 28 Insert (ℓi, θ) at head of Qi 29 until T > T (n) 30 n := 21/(1+ω)n // Increase n for next phase 31 p∗ := p-1 // Return config that was run most last phase 32 return i∗ = argmaxi∈Np∗ {Ti,p∗} , δ = √1+ϵ qi∗ ki∗

Proof: With probability 1 - ζ the execution is clean, as described in Definition 4.2. We claim that in a clean execution, after the most recently-completed phase p prior to termination at time T , we have |Np| ≥ n and the configuration returned by the procedure is (ϵ, 1/nω )-optimal with respect to the set Np. The argument closely follows the proof of Theorem 4.4. The main difference is to consider only execution steps taken in phase p, when at least n configurations were under consideration. As in Theorem 4.4 one can bound the number of steps taken by any (ϵ, 1/nω )-suboptimal configuration in phase p, and thereby argue that the configuration that executes for the most steps in phase p must be (ϵ, 1/nω )-optimal.

We can interpret the sample of configurations as a net that searches for potentially rare configurations with good performance. To that end, define Nγ to be all configurations except the γ fraction of fastest ones, and write OPTγ = OPT(Nγ) for the runtime of the best configuration in Nγ.

Corollary 5.2 For any n ≥ n0 and any γ ∈ (0, 1), if the Structured Procrastination algorithm is run using a random sequence of configurations, and it is halted at any time

then with probability at least 1 - ζ - e-γn it outputs a configuration that is (ϵ, n-ω )-optimal with respect to Nγ

Proof: We apply Theorem 5.1 and note that the probability that none of the γ-fraction of fastest configurations appear in a uniform sample of n configurations is at most e-nγ .

6 Near-Optimality of Runtime

In this section, we show that the worst-case guarantees for Structured Procrastination, Theorem 4.4 and Corollary 5.2, are optimal up to logarithmic factors.

Theorem 6.1 Suppose an algorithm configuration procedure is guaranteed to select an (ϵ, δ)-optimal configuration with probability at least 12 . In the setting with a finite number n = |N| of configurations, the worst-case expected running time of the procedure must be at least Ω( n δϵ2OPT). In the setting with many configurations, letting δ = n-ω and γ = ln 2 n (so that 1 - e-γn = 12 ), the worst-case expected running time of the procedure must be at least Ω( n1+ω ϵ2 OPTγ ).

Proof: Suppose every time an algorithm solves an input instance, it is either a "safe run" that deterministically takes time κ or a "risky run" that either takes κ or κ/δ, depending on the configuration's random seed. For all configurations, the probability of a risky run is 4δ. The probability that R(i, j) = κ/δ, conditional on the run being risky, is 12 for most configurations (the "standard" configurations), but for a 1n fraction of configurations (the "special" configurations), this conditional probability is 12 - ϵ. The special configurations will then be the only ones that are (ϵ, δ)-optimal. We will show that in expectation, the search procedure executes at least Ω( n δϵ2 ) operations of the form RUN(i, j, θ) where θ > κ. Since each such operation takes time at least κ, and OPT = O(κ), this will imply the stated lower bound for n configurations. The extension to many configurations follows by supposing we have n1+ω configurations in total, and nω of them are special, so that with constant probability there is exactly one special configuration among the n sampled ones.

Before embarking on the proof that the expected number of calls to RUN(i, j, θ) with θ > κ is Ω( n δϵ2 ), let us justify this bound in intuitive terms. Selecting an (ϵ, δ)-optimal configuration requires (a) searching through enough configurations to find a special one (which explains the factor of n in the lower bound), (b) running each of the configurations enough times to observe some slow runs (which explains the 1/δ), and (c) observing enough slow runs to estimate their occurrence probability to within a 1-2ϵ factor (which explains the 1/ϵ2 ).

To formalize this reasoning, we define the history of an execution of the procedure to consist of the sequence of RUN(i, j, θ) operations the procedure invoked, along with the running times of those operations. The length-t initial history consists of the first t elements in this sequence. Fixing a search procedure, let Q0 (resp., Qt0 ) denote the distribution over histories (resp., length-t initial histories) in a "null model" where all configurations are standard. Now for 1 ≤ i ≤ n consider a model in which all configurations are standard except for configuration i, which is special. Let Qi and Qti denote the induced distributions over histories and length-t initial histories, respectively.

For each configuration i let pi denote the probability under distribution Q0 that the search procedure selects configuration i. Since p1 + · · · + pn = 1, if n > 2 then there must be at least one configuration i such that pi ≤ 13 . Under distribution Qi, configuration i is the only one that is (ϵ, δ)-optimal, so the search procedure must select it with probability at least 12 . Hence the total variation distance between Q0 and Qi must be at least 16 . By Pinsker's Inequality, their KL-divergence is at least 1 18 . Using the fact that the sequence DKL(Qt0 ‖Qti ) converges monotonically to DKL(Q0‖Qi) as t → ∞, we obtain ∑∞t=1 DKL(Qt0 ‖Qti ) - DKL(Qt-1 0 ‖Qt-1 i ) ≥ 1 18 . By the chain rule for KL-divergence, DKL(Qt0 ‖Qti ) - DKL(Qt-1 0 ‖Qt-1 i ) is simply equal to the conditional KLdivergence of the tth -step of the history, given the first t - 1 steps. If step t runs configuration i′ ̸= i, or if it is a safe run of configuration i, then the running time distribution in step t is the same under distributions Qt0 and Qti . Thus, the conditional KL-divergence equals the conditional probability (under Q0) of a risky run of configuration i in step t, times the conditional KL-divergence of the running times in case of a risky run, which is 12 ln( 1 1-2ϵ )+ 12 ln( 1 1+2ϵ ) < 4ϵ2 . Summing over t ≥ 1, we find that the expected number of risky runs of configuration i, under distribution Q0, must be at least 1 72 ϵ-2 . Summing over configurations, the expected total number of risky runs is at least n 72 ϵ-2 . Since a run is only risky if the timeout threshold exceeds κ, and then it is only risky with probability 2δ, the expected number of times any configuration is run with timeout threshold greater than κ must be at least n 144δϵ2 , which completes the proof.

7 Extensions for Practical Performance

To this point, we have limited ourselves to (uniform) random sampling of the parameter space. While even incumbentdriven random sampling has shown surprising success for algorithm configuration-and, hence, our approach is likely to work even better-considerable evidence in the literature (e.g., contrasting SMAC and ROAR) indicates that it is a good idea in practice to combine sampling with Bayesian optimization (as in SMAC). There are straightforward ways that our approach could be extended to do this. For example, in the Structured Procrastination method described in Section 5, whenever configurations are added to the pool of samples, one could draw half uniformly and generate the other half using an arbitrary model fit using all previous samples. This does not help in the worst case, of course, but nor does it degrade our worst-case bounds by very much. In effect, we pay no statistical cost for the fact that our model is conditioned on previous observations and obtain a bound as though the random samples were the only configurations considered.

Theorem 7.1 Suppose that half of the algorithms sampled in Structured Procrastination are generated according to an arbitrary structural model, which in turn depends on previous observations. Then Theorem 5.1 continues to hold with n replaced by 2n in the upper bound on T .

A second practical extension is from sequential to parallel processing. Structured Procrastination is inherently parallelizable: themain loop repeatedly draws and executes a simulation from a queue. Using the queues as a shared data structure, each parallel processor could repeatedly draw an instance from the queue for a configuration with minimal empirical runtime estimate-locking that (configuration, instance) pair to prevent other processors from considering it in the meantime-and then update that estimate once the execution completes. This can result in a suboptimal configuration being queried more than necessary due to stale empirical runtime estimates. However, this can only result in each element of a configuration's queue being executed one more time than necessary, which at most doubles the total time spent processing any given configuration. This intuition can be leveraged to show that using p processors results in a linear speedup, as long as the procedure runs for long enough that there are more input instances enqueued than there are processors.

Theorem 7.2 Suppose that Structured Procrastination is executed by p processors running in parallel. Then for n sufficiently large and n/n0 a power of 2, there is a random sample N0 of n configurations such that if the elapsed wall clock time is at least T ≥ 160n1+ω pϵ2 ln ( 3n1+ω ζ 2 ϵ2 ) OPT(N0) then it outputs a configuration that is (ϵ, n-ω )-optimal with respect to N0 with probability at least 1 - ζ.

8 Conclusions

We have introduced Structured Procrastination, a new method for automated algorithm configuration. Crucially, it depends on the idea of procrastinating in the face of potentially hard inputs, rather than solving them to completion when first encountered. Our method is guaranteed to find an approximately optimal algorithm configuration in time that worst-case dominates that of any existing algorithm configuration technique.

Our approach in this paper has been focused purely on the worst case. This is justified by the fact that we obtain a positive result. However, the strong performance of heuristic methods suggests that realistic algorithm configuration settings are not as adversarial as our analysis has assumed. A critical direction for future work is empirically evaluating our techniques and comparing them to existing algorithm configuration methods.