Utilitarian Algorithm Configuration for Infinite Parameter Spaces

## Abstract

Abstract Utilitarian algorithm configuration is a general-purpose technique for automatically searching the parameter space of a given algorithm to optimize its performance, as measured by a given utility function, on a given set of inputs. Recently introduced utilitarian configuration procedures offer optimality guarantees about the returned parameterization while provably adapting to the hardness of the underlying problem. However, the applicability of these approaches is severely limited by the fact that they only search a finite, relatively small set of parameters. They cannot effectively search the configuration space of algorithms with continuous or uncountable parameters. In this paper we introduce a new procedure, which we dub COUP (Continuous, Optimistic Utilitarian Procrastination). COUP is designed to search infinite parameter spaces efficiently to find good configurations quickly. Furthermore, COUP maintains the theoretical benefits of previous utilitarian configuration procedures when applied to finite parameter spaces but is significantly faster, both provably and experimentally.

## 1 Introduction

*Algorithm configuration* is a general-purpose technique for optimizing the performance of algorithms by automatically searching over the space of their input parameters. Given a set of possible parameter assignments (i.e., a set of “configurations”) our objective is to find one that makes the algorithm perform well on average, over a set of inputs of interest. Recently, attention has begun to shift from procedures that define performance in terms of average runtime toward procedures that define performance in terms of more general utility functions over runtime. introduced Utilitarian Procrastination (UP), the first non-trivial algorithm configuration procedure that maximizes utility achieved instead of minimizing runtime. Unlike more naive approaches, UP can adapt to the hardness of the problem it faces, requiring provably less time to guarantee optimality when many of the configurations it considers are suboptimal. However, UP requires that this set of candidate configurations be discrete and relatively small. This is a major limitation; e.g., many algorithms have at least one continuous parameter. UP cannot effectively search over continuous spaces.

In this paper we present COUP (Continuous, Optimistic Utilitarian Procrastination), which is designed to handle infinite (e.g., continuous) configuration spaces. Like UP, COUP is utilitarian and takes inspiration from the world of multi-armed bandits. However, COUP is based on a different bandit procedure that is guided by the principle of “optimism in the face of uncertainty” and is more readily adapted to handle large configuration spaces. What’s more, COUP is also significantly better than UP on finite sets of configurations because COUP does not try to explicitly rule bad configurations out, but instead simply ignores them once they no longer appear as promising as other alternative configurations.

[Section 2](#S2) discusses relevant background material. [Section 3](#S3) introduces the finite-configuration-space version of COUP and shows that this version finds an approximately optimal configuration in strictly less total time than UP. We simply call this version OUP since it, like UP, does not actually search over a continuous parameter space. [Section 4](#S4) introduces COUP, leveraging our understanding of the finite case into a general-purpose procedure. We discuss empirical evaluations in [Section 5](#S5) and conclude with [Section 6](#S6).

## 2 Background

Given a parameterizable algorithm and a set of possible parameter assignments, the goal of *algorithm configuration* is to find a parameter assignment that makes the algorithm perform well across a set of given inputs. If we also require that a procedure gives a *guarantee* about the near-optimality of its returned configuration, algorithm configuration can be seen as a multi-armed bandit problem (see e.g., Lattimore and Szepesvári, ()) called *approximate best-arm identification*: finding an arm whose mean reward is close to the reward of the best arm available. In this case, it is not the regret of the procedure that concerns us, but the number of samples needed to guarantee the near-optimality of the returned arm. Even-Dar et al., () observe that if we want to find an arm whose value is within $\epsilon$ of the best with good probability, we could just take $\tilde{O}(\epsilon^{-2})$ samples of each arm and apply Hoeffding’s inequality (Hoeffding,, ) to obtain upper and lower confidence bounds on the mean reward of each arm that are sufficient to identify an approximately optimal one (i.e., one within an $\epsilon$ additive factor of optimal). However, this will be more samples than necessary in all but the worst case; any arm that is significantly worse than the best arm can be ruled out using fewer samples than are required by naively applying Hoeffding’s inequality. The Successive Elimination (SE) procedure (Even-Dar et al.,, ) is able to identify an approximately optimal arm with only $\tilde{O}(\min\{\Delta_{i}^{-2},\epsilon^{-2}\})$ samples of each arm, where $\Delta_{i}$ is the suboptimality gap for arm $i$. This can be a significant reduction when many arms are far from optimal. SE achieves this improved, *adaptive* bound by being *anytime*: it does not take an $\epsilon$ as input. It starts by taking only a few samples of each arm, guaranteeing a relatively large $\epsilon$, and then improves this over time. This allows it to stop sampling bad arms and rule them out before it is finished. Up to logarithmic factors, taking $m=\min\{\Delta_{i}^{-2},\epsilon^{-2}\}$ samples of arm $i$ is not only sufficient, but also necessary for general inputs (Mannor and Tsitsiklis,, ).

SE is a simple and intuitive procedure with approximately optimal sample complexity, but it can tend to over-investigate bad arms, sampling them repeatedly until it can expressly rule them out. The Upper Confidence Bound (UCB) procedure (Lai,, ) is an alternative to SE that focuses on arms that look promising and/or about which little is known. By repeatedly pulling the arm with largest upper confidence bound, UCB attempts to maximize the information it gains with each pull. For more discussion on the difference between SE and UCB and on their relative performance see the survey of Jamieson and Nowak, ().

There are two key differences between algorithm configuration and most other bandit problems. First, each arm pull imposes a stochastic cost arising from the amount of time it takes for the algorithm run to complete. Second, we have the option of bounding these costs by “capping” algorithm runs at any fixed time of our choice, but when we do so we obtain only censored information about the arm pull (we learn that the run would have taken more than the captime but not how much more). Overall, it is not the total number of samples that we want to control, but the total amount of time spent searching.

Most existing algorithm configuration procedures that offer theoretical guarantees aim to minimize average runtime. These can broadly be seen as implementing either SE or UCB. These procedures either run all existing configurations simultaneously (i.e., round-robin or in parallel), ruling out the ones that can be proved to be suboptimal after each step Weisz et al., (, , ); Brandt et al., (), or they iteratively select a particular configuration according to a confidence-bound index, and run only this configuration Kleinberg et al., (, ). In either case, these procedures are significantly complicated by the fact that runtimes are potentially unbounded, and the very notion of optimality that they target requires adjustment to compensate for this. Other theoretically-motivated approaches offer performance guarantees based on measures of complexity and guarantee notions of PAC optimality akin to those we present here (Gupta and Roughgarden,, ; Balcan et al.,, , ). The focus there is not on the time consumed by the configuration process, but on the number of samples required to find a sufficiently good configuration.

*Utilitarian* algorithm configuration procedures do not try to minimize expected runtime, but instead try to maximize expected utility, as measured by a user-specified utility function that captures the value associated with solving an input instance as a (weakly decreasing, but not necessarily linear) function of the amount of time spent solving it.
For example, if we face daily scheduling problems, then getting a solution after waiting 100 days is not 100 times worse than getting it after one day; both are too long to wait. If one algorithm solves most inputs very quickly but occasionally takes an astronomical amount of time, while another algorithm takes a moderate amount of time on every input, determining which algorithm is “better” will likewise depend on our particular setting: How much time do we have? How much better is it to get an answer quickly?
generalize such intuitions, offering a detailed argument from first principles that utility maximization is a more appropriate objective (e.g., for algorithm configuration) than runtime minimization and showing that such utility functions are guaranteed to exist if our preferences for algorithm runtime distributions follow a certain reasonable structure based on the axioms of Von Neumann and Morgenstern, ().

UP () is a utilitarian configuration procedure that can be seen as SE coupled with a doubling mechanism for discovering sufficiently large captimes. UP has several desirable qualities that we would like to incorporate into our own configuration procedure. First, UP maximizes utility instead of minimizing runtime. Second, unlike many runtime-optimizing procedures UP can make simple theoretical guarantees about the near-optimality of the configuration it returns. Third, UP is *anytime*, meaning that it provides a better guarantee the longer it is run, and so requires minimal initial input from the user, who can simply observe the procedure’s execution and terminate it when they are satisfied with the guarantee being made. Finally, UP’s guaranteed performance is *adaptive* to the inputs it receives; it provably performs better on non-worst-case inputs (i.e., the associated theoretical guarantees are *input-dependent*).

However, UP can only be applied to a finite (and relatively small) set of configurations since it cycles through these one by one and runs each of them in turn. This is a prohibitive limitation we would like to overcome. A natural idea would be to sample a finite set from the infinite configuration space and simply run UP on this set. The optimality guarantee offered by UP would then be made with respect to the best configuration in this subset, and if enough configurations are sampled, we can guarantee that our subset will be likely to contain at least one of the top, say, $\gamma$-fraction of all configurations. This strategy will work, but since the choice of $\gamma$ potentially limits the quality of the configuration we are likely to find, we would like to make our procedure anytime in $\gamma$ as well; we would like our procedure to start with a relatively small set of configurations (i.e., a relatively large $\gamma$) and grow this set as time goes on, shrinking the $\gamma$ it can guarantee. Of course we still wish to be anytime with respect to the accuracy parameter $\epsilon$, and here we run into a problem with UP. Since UP loops over all remaining configurations, at any point during its execution it will have run all of these configurations on effectively the same number of instances (at most the difference is one). What should we do when we want to expand the set of configurations we are considering? Any newly added configuration will have a large upper confidence bound, since we know little or nothing about it yet. This will severely limit the anytime $\epsilon$ we can guarantee because it remains possible that the new configuration is much better than all the existing ones. So new configurations would need to be “caught up” when they are added. How should we do this?

One extreme strategy would be to completely “catch up” new configurations by running them on all existing instances. This will be unnecessarily costly because it fails to leverage what has already been learned about promising configurations. At the other extreme, we could not “catch up” new configurations at all and just add them to the existing pool, forever estimating them with fewer samples and thus lower accuracy. This will effectively limit the $\epsilon$ we can guarantee to the lower accuracy of these newly introduced configurations. Is there a way to balance these two extremes and integrate new configurations into the estimation process smoothly? This leads us to the UCB procedure. In terms of the runtime cost we incur, we would prefer to take the second extreme approach above and not do anything special with new configurations. However, this leads to configurations with relatively large upper confidence bounds, which limits the optimality guarantee we can make. If we choose to focus on configurations that have large upper bounds, as UCB does, we will explore new configurations just up to the point where something else looks better, and then stop.

Thus, whereas UP was built around the SE procedure, COUP is built around the UCB procedure. Like UP, COUP is utilitarian, adaptive, and anytime with respect to the optimality parameter $\epsilon$. At the same time, COUP can also be applied to infinitely-large sets of configurations, and is also anytime with respect to $\gamma$, the fraction of unexplored configurations. COUP initially makes guarantees for a small set of configurations, then expands this set while simultaneously improving the optimality guarantee that it can make with respect to this (growing) set.

What’s more, COUP also beats UP at its own game: COUP is significantly faster than UP when the input actually is a fixed, finite set of configurations. Because it is built on the SE algorithm, UP runs all suboptimal configurations until they can explicitly be eliminated. For some sets of inputs this can be necessary but in many cases it is more efficient to rule out poor-performing configurations by learning more about (i.e., by narrowing the confidence bounds of) other, better-performing configurations. COUP provably stops running sub-optimal configurations well before they would be eliminated by UP. Additionally, we re-evaluate a key component of UP—the condition it checks before doubling a configuration’s captime—and propose an improvement. UP attempts to balance the estimation error due to sampling with the error due to capping. We argue that this is better achieved with a different doubling condition that emerges from a more careful analysis of the confidence bounds.

## 3 The Case of Few Configurations: OUP

We begin by presenting and analyzing the finite-configuration-space version of COUP, which we call OUP ([Algorithm 1](#alg1)) to indicate that it does not search over continuous spaces like COUP does. OUP can most easily be understood as a UCB procedure for finding configurations with good *capped* mean utility, along with a periodic doubling scheme that allows larger and larger captimes to be considered. Like UP, it is adaptive and anytime in the optimality parameter $\epsilon$.

Figure: Algorithm 1 OUP

Let us now establish notation. We are given a set of configurations, indexed by $i$, and a set of instances, indexed by $j$. We will use $t_{ij}$ to denote the true uncapped runtime of configuration $i$ on input $j$, and $t_{ij}(\kappa)\operatorname{{\vcentcolon=}}\min(t_{ij},\kappa)$ to be the $\kappa$-capped runtime of $i$ on $j$. When we do a run, we observe $t_{ij}(\kappa)$ rather than $t_{ij}$; these coincide for any run that completes. The instance distribution $\mathcal{D}_{J}$, along with any randomness of the algorithm or execution environment will together induce a runtime distribution for each configuration $i$. We will use $\mathcal{D}_{i}$ to denote this runtime distribution, and $F_{i}$ to denote its CDF. For each configuration $i$, the true uncapped expected utility is $U_{i}\operatorname{{\vcentcolon=}}\mathop{\mathbb{E}}_{t\sim\mathcal{D}_{i}}\big{[}u(t)\big{]}$. The cumulative distribution function is $F_{i}(\kappa)\operatorname{{\vcentcolon=}}\Pr_{t\sim\mathcal{D}_{i}}\big{(}t\leq\kappa\big{)}$. The capped expected utility is $U_{i}(\kappa)\operatorname{{\vcentcolon=}}\mathop{\mathbb{E}}_{t\sim D_{i}}\big{[}u\big{(}\min(t,\kappa)\big{)}\big{]}$. Finally, the optimality gaps $\Delta_{i}\operatorname{{\vcentcolon=}}\max_{i^{\prime}}U_{i^{\prime}}-U_{i}$ partially determine the hardness of the problem; if a configuration $i$ has large optimality gap $\Delta_{i}$, then it will be easier to rule out. The notion of optimality that we target is given by the following definition.

###### Definition 1 ( $\epsilon$ -optimal) .

A configuration $i$ is *$\epsilon$-optimal* if $\Delta_{i}\leq\epsilon$.

The error associated with $m$ runtime samples at captime $\kappa$ is $\alpha(m,\kappa)\operatorname{{\vcentcolon=}}\sqrt{\frac{\ln(11nm^{2}(\log\kappa+1)^{2}/\delta)}{2m}}$, chosen to satisfy Hoeffding’s inequality and the necessary union bounds. An execution of OUP will be called *clean* if at all times during its execution we have $\big{|}\widehat{F}_{i}-F_{i}(\kappa_{i})\big{|}\leq\alpha(m_{i},\kappa_{i})$ and $\big{|}\widehat{U}_{i}-U_{i}(\kappa_{i})\big{|}\leq\big{(}1-u(\kappa_{i})\big{)}\cdot\alpha(m_{i},\kappa_{i})$ for all configurations $i$. So during a clean execution, empirical capped average utilities are close to true capped average and empirical CDF values are close to true CDF values at the captime $\kappa_{i}$.

###### Lemma 1 .

An execution of OUP is clean with probability at least $1-\delta$.

All proofs are deferred to the appendices. The idea behind [Lemma 1](#Thmlemma1) is that the bounds that define a clean run hold initially, they do not change in any round where $i$ is not selected, and by Hoeffding’s inequality they are unlikely not to hold in any round where $i$ is selected. The next lemma shows that during a clean execution, the confidence bounds will be valid, and also not too far apart.

###### Lemma 2 .

For all $i$ at all points during a clean execution, we have $LCB_{i}\leq U_{i}\leq UCB_{i}$ and $UCB_{i}-LCB_{i}\leq 2\alpha(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}$.

We can now state the main theorem of this section.

###### Theorem 1 .

With probability at least $1-\delta$, OUP eventually returns an optimal configuration and it returns an $\epsilon$-optimal configuration if it is run until $2\alpha_{i^{opt}}+{u(\kappa_{{i^{opt}}})\big{(}1-F_{{i^{opt}}}(\kappa_{{i^{opt}}})\big{)}}\leq\epsilon$. Furthermore, for any suboptimal configuration $i$, if $m_{i}$ and $\kappa_{i}$ ever become large enough that

$$ $\displaystyle 2\alpha(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}<\Delta_{i}$ (1) $$

then $i$ will never be run again, and $i$ will be outright eliminated once $m_{i},\kappa_{i},m_{i^{opt}}$ and $\kappa_{i^{opt}}$ are large enough that

$$ $\displaystyle 2\alpha(m_{i},\kappa_{i})+2\alpha(m_{i^{opt}},\kappa_{i^{opt}})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}+{u(\kappa_{{i^{opt}}})\big{(}1-F_{{i^{opt}}}(\kappa_{{i^{opt}}})\big{)}}<\Delta_{i}.$ (2) $$

If OUP keeps selecting and running $i$, then the term $2\alpha(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}$ will continue to shrink. So we will eventually have $2\alpha(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}<\Delta_{i}$ as long as we keep running $i$. In either case, we will eventually stop running any suboptimal $i$. This puts a hard limit on the amount of time we will ever dedicate to any suboptimal configuration, and this limit is better than the corresponding guarantee made by UP: compare our [Theorem 1](#Thmtheorem1) to Theorem 4 in . UP guarantees that $i$ will be eliminated once the bound in [Equation 2](#S3.E2) is satisfied. The bound in [Equation 1](#S3.E1) guaranteed by OUP is a necessary condition for this. OUP does not keep running suboptimal configurations until they can be eliminated, as UP does. Instead, it simply stops running them, while continuing to tighten the bounds of better configurations instead.

[Algorithm 1](#alg1) is stated using the old doubling condition introduced in UP. We propose an alternative based on examining the confidence width $UCB_{i}-LCB_{i}=2\big{(}1-u(\kappa_{i})\big{)}\cdot\alpha(m_{i},\kappa_{i})+u(\kappa_{i})\big{(}1-\widehat{F}_{i}+\alpha(m_{i},\kappa_{i})\big{)}$. The first term is the error from runs below $\kappa_{i}$ and the second term is the error from runs above $\kappa_{i}$. Our new doubling condition attempts to balance these two terms. Due to space constraints we discuss this more in the appendices, but ultimately Line 9 of [Algorithm 1](#alg1) becomes

$$ $\displaystyle\text{{\small 9${}^{\prime}$:} }\textbf{ if }2\big{(}1-u(\kappa_{i})\big{)}\cdot\alpha(m_{i},\kappa_{i})\leq u(\kappa_{i})\big{(}1-\widehat{F}_{i}+\alpha(m_{i},\kappa_{i})\big{)}\textbf{ then}$ $\triangleright$ captime doubling condition $$

The change to the continuous-space version COUP is analogous (Line 18 of [Algorithm 2](#alg2)). Implementing this refined doubling condition improves the performance of both UP and (C)OUP.

###### Definition 1 ( ϵ italic-ϵ \epsilon -optimal) .

###### Lemma 1 .

###### Lemma 2 .

###### Theorem 1 .

## 4 The Case of Many Configurations: COUP

We now assume we have a very large, possibly uncountably infinite, set of configurations $\mathcal{A}$, along with an associated distribution $\mathcal{D}_{\mathcal{A}}$ over configurations $a\in\mathcal{A}$ from which we sample. It is no longer feasible to target the configuration with maximum utility $OPT=\max_{a\in\mathcal{A}}U_{a}$. It may be arbitrarily unlikely that we ever sample this configuration and, in fact, such a maximum may not even exist. So we must relax our objective. For any $\gamma\in(0,1)$, let $OPT^{\gamma}=\sup\big{\{}\mu\;:\;\Pr_{a\sim\mathcal{D}_{\mathcal{A}}}[U_{a}\leq\mu]\leq 1-\gamma\big{\}}$. The quantity $OPT^{\gamma}$ marks the top $\lfloor 1/\gamma\rfloor$-quantile of expected utilities. That is, $OPT^{\gamma}$ is the utility of the best configuration that remains after we have excluded the top $\gamma$-fraction of configurations. The notion of optimality that we will target is given by the following definition.

###### Definition 2 ( $(\epsilon,\gamma)$ -optimal) .

A configuration $a\in\mathcal{A}$ is $(\epsilon,\gamma)$-optimal if $U_{a}\geq OPT^{\gamma}-\epsilon$.

Figure: Algorithm 2 COUP

We present the general version of COUP in [Algorithm 2](#alg2). The procedure runs in successive phases. Each phase is essentially an execution of the few-configuration version, OUP, with the bounds being chosen carefully so that runs can be shared across phases. Each phase $p$ of COUP is characterized by two parameters: $\gamma_{p}\in(0,1)$ determines the tail quantile being targeted in this phase, and $\epsilon_{p}\in(0,1)$ determines the level of optimality being targeted. If $\gamma_{p}$ is relatively small and $\epsilon_{p}$ is relatively large, then COUP will sample a large number of configurations in phase $p$, but not work too hard to prove that any of them is approximately optimal. On the other hand, if $\gamma_{p}$ is relatively large and $\epsilon_{p}$ is relatively small, then COUP will sample only a few configurations and work very hard to prove one of them is nearly optimal (with respect to this set). Since we are interested in procedures that are anytime in both $\epsilon$ and $\gamma$, we will be interested in sequences of parameters for which $\epsilon_{p}\to 0$ and $\gamma_{p}\to 0$ as $p\to\infty$. We can think of $\epsilon_{p}$ as controlling the rate at which we explore new instances, and $\gamma_{p}$ as controlling the rate at which we explore new configurations. They are dissimilar in what they quantify though: $\epsilon_{p}$ is in “units” of utility, while $\gamma_{p}$ is in “units” of probability.

COUP never eliminates configurations because it needs them in later phases to make statistical guarantees about relative optimality, but we know it will stop running them well before we will be able to consider them for elimination anyway. Define $\alpha_{p}(m,\kappa)\operatorname{{\vcentcolon=}}\sqrt{\frac{\ln(36p^{2}n_{p}m^{2}(\log\kappa+1)^{2}/\delta)}{2m}}$ to be the confidence width, chosen to satisfy Hoeffding’s inequality and the necessary union bounds. The $p$-th phase of an execution of COUP will be called *clean* if $\big{|}\widehat{F}_{i}-F_{i}(\kappa_{i})\big{|}\leq\alpha_{p}(m_{i},\kappa_{i})$ and $\big{|}\widehat{U}_{i}-U_{i}(\kappa_{i})\big{|}\leq(1-u(\kappa_{i}))\cdot\alpha_{p}(m_{i},\kappa_{i})$ for all $m_{i}$ and $\kappa_{i}$ for all configurations $i\in\mathcal{A}_{p}$.

###### Lemma 3 .

An execution of COUP is clean for all phases with probability at least $1-\frac{\delta}{2}$.

###### Lemma 4 .

During a clean execution of COUP we have $LCB_{i}\leq U_{i}\leq UCB_{i}$ and $UCB_{i}-LCB_{i}\leq 2\alpha_{p}(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}$ for all configurations $i\in\mathcal{A}_{p}$ in all phases $p$.

The $p$-th phase of an execution of COUP will be called *characteristic* if there exists some $i_{p}\in\mathcal{A}_{p}$ with $U_{i_{p}}\geq OPT^{\gamma_{p}}$.

###### Lemma 5 .

An execution of COUP is characteristic for all phases with probability at least $1-\frac{\delta}{2}$.

Finally, we can state our main theorem about COUP’s performance.

###### Theorem 2 .

If COUP is run with parameters $(\epsilon_{1},\epsilon_{2},...)$ and $(\gamma_{1},\gamma_{2},...)$ then with with probability at least $1-\delta$ it returns an $(\epsilon_{p},\gamma_{p})$-optimal configuration at the end of every phase $p=1,2,...$.

###### Definition 2 ( ( ϵ , γ ) italic-ϵ 𝛾 (\epsilon,\gamma) -optimal) .

###### Lemma 3 .

###### Lemma 4 .

###### Lemma 5 .

###### Theorem 2 .

## 5 Empirical Evaluation

We first compare the performance of OUP with the performance of UP ([Section 5.1](#S5.SS1)), and with a naive procedure also described by that simply takes enough runtime samples to satisfy Hoeffding’s inequality for each configuration, and takes them at a high enough captime that it can still make its guarantee whether they complete or not. We then explore the effects on performance when we expand our search to an infinitely-large set of configurations ([Section 5.2](#S5.SS2)). We show that the search of the configuration space does not cost COUP too much in terms of runtime, and we demonstrate COUP’s flexibility in the way it performs its search. We perform our experiments on three existing datasets from the algorithm configuration literature. The minisat dataset represents the measured execution times of the SAT solver by that name on a generated set of instances (see Weisz et al., () for details). The cplex_rcw and cplex_region datasets represent the predicted solve times of the CPLEX integer program solver on wildlife conservation and combinatorial auction problems, respectively (see Weisz et al., () for details). We focus on the two utility functions considered previously by . The “log-Laplace” utility function is defined as $u_{LL}(t)=1-\frac{1}{2}\big{(}\frac{t}{\kappa_{0}}\big{)}^{\alpha}$ if $t<\kappa_{0}$ and $u_{LL}(t)=\frac{1}{2}\big{(}\frac{\kappa_{0}}{t}\big{)}^{\alpha}$ otherwise. The “uniform” utility function is defined as $u_{unif}(t)=1-\frac{t}{\kappa_{0}}$ if $t<\kappa_{0}$ and $u_{unif}(t)=0$ otherwise. The parameter $\kappa_{0}$ is set to 60 in both cases, and the parameter $\alpha$ is set to 1. To facilitate the comparison with UP we use the original doubling condition when recreating the experiments of (i.e., [Figures 1](#S5.F1) and [2](#S5.F2)). For other experiments we use the improved doubling condition. Code to reproduce all experiments can be found at anonymous-repo-link.

### 5.1 The Case of Few Configurations

We first compare the performance of OUP with that of UP by recreating the experiments from . [Figure 1](#S5.F1) shows that OUP consistently proves a meaningful $\epsilon$ in much less time than UP. OUP is faster by an order of magnitude or more (compare the top row of [Figure 1](#S5.F1) to Figure 2 in ). Furthermore, a very simple naive approach based on Hoeffding’s inequality can be faster than UP in some scenarios (i.e. for relatively small values of $\epsilon$) when the captime parameter is chosen appropriately for the given utility function. However, OUP is consistently faster than both UP and this naive approach, regardless of the chosen captime parameter. In [Section 3](#S3) we argued that OUP will spend less time running bad configurations than UP because it can stop devoting attention to them and focus on more promising ones instead. UP, on the other hand, continues to run suboptimal configurations until they are eliminated. [Figure 2](#S5.F2) shows that OUP does indeed spend considerably less time on suboptimal configurations.

Figure: Figure 1: Total runtime required to prove a given $\epsilon$. The plots are from Figures 2 and 3 of , with OUP included for comparison. OUP consistently outperforms both UP and the naive baseline procedure, often by an order of magnitude. The naive procedure can be better than UP when its parameter is chosen appropriately (middle row), but even in these scenarios COUP is generally superior. Results are for the log-Laplace utility function (top row), and the uniform utility function (middle and bottom rows).
Refer to caption: /html/2405.18246/assets/x1.png

Figure: Figure 2: Total time spent by OUP on each configuration (log-Laplace utility function). Configurations are sorted according to average utility. OUP spends less time on all but the very best configurations.
Refer to caption: /html/2405.18246/assets/x10.png

### 5.2 The Case of Many Configurations

We now compare the performance of COUP with that of OUP to show that COUP’s exploration of the configuration space does not cost too much. The results for the log-Laplace utility function are shown in [Figure 3](#S5.F3). We set $\delta=0.01$ throughout. For each phase $p$ we set $\epsilon_{p}=e^{-p/6}$ and $\gamma_{p}=e^{-p/3}$. This schedule allows COUP to sample a large fraction of the configurations and the instances in the datasets we consider. When it is finished each phase, it can make an $\epsilon_{p}$-optimality guarantee with respect to the set $\mathcal{A}_{p}$ of $n_{p}$ configurations. We compare the total configuration time of COUP at the end of each phase to the time OUP takes to prove $\epsilon_{p}$-optimality when applied directly to this set of $n_{p}$ configurations. [Figure 3](#S5.F3) shows that the total configuration time required by COUP is not much different from the time required by OUP, indicating that COUP was efficient at exploring the configuration space.

Figure: Figure 3: Performance of COUP compared to OUP, using the log-Laplace utility function. COUP is anytime, but takes only a small factor more time than OUP. The bottom row shows the final times.
Refer to caption: /html/2405.18246/assets/x13.png

COUP is extremely flexible in the way it explores new configurations relative to exploring new instances. The parameter sequences $\gamma_{1},\gamma_{2},...$ and $\epsilon_{1},\epsilon_{2},...$ control the relative rates at which this exploration takes place. We demonstrate this flexibility in [Figure 4](#S5.F4). Some different exploration strategies are presented. The “$\gamma$ focus” strategy sets $\epsilon_{p}=e^{-p/30}$ and $\gamma_{p}=e^{-p/3}$, and so works to explore many configurations, making relatively weak guarantees about their optimality. The “$\epsilon$ focus” strategy sets sets $\epsilon_{p}=e^{-p/3}$ and $\gamma_{p}=e^{-p/30}$, and so explores relatively few configurations, but makes strong optimality guarantees with respect to these. The “balanced” strategy sets $\epsilon_{p}=\gamma_{p}=e^{-p/5}$. In general, it is not wise to focus on $\epsilon$ too intently until later in the search process. Once we have found a good configuration (i.e., one with a relatively large upper confidence bound), new configurations can be ruled out relatively cheaply, because they quickly look worse than the good one. So it is helpful to find a good configuration quickly, and then later work on proving that it is good. The “$\gamma$ then $\epsilon$” strategy achieves this by setting $\epsilon_{p}=e^{-p^{3}/300}$ and $\gamma_{p}=e^{-p^{2}/30}$.

Figure: Figure 4: Different schedules for exploring new configurations (refining $\gamma$) vs. exploring existing configurations (refining $\epsilon$) when running COUP. Results are for the log-Laplace utility function and the cplex_rcw dataset. Other combinations show a similar pattern.
Refer to caption: /html/2405.18246/assets/x19.png

## 6 Conclusion

We have presented COUP, an improved method for utilitarian algorithm configuration. COUP shares the positive qualities of its predecessors, but is truly general-purpose, in that it can search over infinite configuration spaces effectively. COUP is also shown to be superior when applied to finite configuration spaces. For the sake of continuity with previous work we have made comparisons on the datasets and utility functions that have been used before. However, this comparison is somewhat limited; a more comprehensive investigation would be a valuable direction for future work. Moreover, while we are convinced that optimizing utility functions is better than optimizing runtime, we recognize that coming up with the right utility function is not always easy for end users; establishing a tool or guide for doing this is another important future direction. Our work is about improving the performance of algorithms, and unfortunately this cannot preclude algorithms with potentially negative societal effects (though our work could just as easily be used to improve *countermeasures* to such algorithms). The marginal risk posed by our work, however, is extremely small.

## Appendix A Improved Captime Doubling Condition

We discuss the change in doubling condition as applied to OUP, but the same argument holds for COUP more generally on a per-phase basis, as well as for UP. Line 9 of [Algorithm 1](#alg1) shows the doubling condition introduced by UP:

$$ $\displaystyle\text{{\small 9: }}\textbf{ if }2\alpha(m_{i},\kappa_{i})\leq u(\kappa_{i})(1-\widehat{F}_{i})\textbf{ then}$ $\triangleright$ captime doubling condition $$

The term $2\alpha(m_{i},\kappa_{i})$ can be interpreted as the error incurred due to sampling because this is the term that comes from taking samples and applying the statistical bound of Hoeffding’s inequality. The term $u(\kappa_{i})(1-\widehat{F}_{i})$ can be interpreted as the error incurred due to capping because runs longer than $\kappa_{i}$ can have a utility of at most $u(\kappa_{i})$, and there will only be (approximately) $1-\widehat{F}_{i}$ of these. Balancing these two terms seems like a sensible approach, but a more careful analysis suggest something slightly different.

To emphasize that our uncertainty is the result of both sampling and capping, we re-write the upper and lower confidence bounds without cancelling terms as

$$ $\displaystyle UCB_{i}$ $\displaystyle=\widehat{U}_{i}+\big{(}1-u(\kappa_{i})\big{)}\cdot\alpha(m_{i},\kappa_{i})+0,$ $\displaystyle LCB_{i}$ $\displaystyle=\widehat{U}_{i}-\big{(}1-u(\kappa_{i})\big{)}\cdot\alpha(m_{i},\kappa_{i})-u(\kappa_{i})\big{(}1-\widehat{F}_{i}+\alpha(m_{i},\kappa_{i})\big{)}.$ $$

It can now be seen more clearly that the confidence width decomposes into a sum of two terms. The first represents uncertainty about runs from below the captime $\kappa_{i}$, and the second represents uncertainty about runs from above $\kappa_{i}$:

$$ $\displaystyle UCB_{i}-LCB_{i}$ $\displaystyle=\underbrace{2\big{(}1-u(\kappa_{i})\big{)}\cdot\alpha(m_{i},\kappa_{i})}_{\text{error from runs below }\kappa_{i}}+\underbrace{u(\kappa_{i})\big{(}1-\widehat{F}_{i}+\alpha(m_{i},\kappa_{i})\big{)}}_{\text{error from runs above }\kappa_{i}}.$ $$

Because $i$ was chosen at line 7 to have maximum $UCB$, we have $UCB_{i}-LCB_{i}\geq UCB_{{i^{opt}}}-LCB_{i}\geq\Delta_{i}$, so shrinking the confidence width $UCB_{i}-LCB_{i}$ is necessary to prove a better optimality guarantee for configuration $i$. But because the confidence width is a sum of two terms, shrinking it toward zero requires shrinking both terms toward zero; the confidence width is dominated by the largest term. The new captime doubling condition we propose shrinks these two terms in a balanced way:

$$ $\displaystyle\text{{\small 9${}^{\prime}$:} }\textbf{ if }2\big{(}1-u(\kappa_{i})\big{)}\cdot\alpha(m_{i},\kappa_{i})\leq u(\kappa_{i})\big{(}1-\widehat{F}_{i}+\alpha(m_{i},\kappa_{i})\big{)}\textbf{ then}$ $\triangleright$ captime doubling condition $$

Empirically, this is generally an improvement over the old doubling condition and sometimes a large improvement. We set $\epsilon=\delta=.1$ and run both OUP and UP using both the old and new doubling conditions. [Figure 5](#A1.F5) clearly shows the improvement to both procedures in terms of the optimality guarantee being made and the time spent per configuration.

Figure: Figure 5: Improvement of the new doubling condition on UP and OUP, using the log-Laplace utility function. Other utility functions show similar improvement.
Refer to caption: /html/2405.18246/assets/x22.png

## Appendix B Deferred Proofs

#### Lemma 1 :

An execution of OUP is clean with probability at least $1-\delta$.

###### Proof.

For any configuration $i$ and any round $r$, let $m_{i}(r)$ and $\kappa_{i}(r)$ be the number of samples taken by $i$ and the captime they were taken with, respectively, in round $r$. Let $\widehat{F}_{i}(m_{i},\kappa_{i})$ and $\widehat{U}_{i}(m_{i},\kappa_{i})$ be OUP’s internal variables $\widehat{F}_{i}$ and $\widehat{U}_{i}$ after taking $m_{i}$ samples at captime $\kappa_{i}$. Define the good events:

$$ $\displaystyle\mathcal{G}_{i,m_{i},\kappa_{i}}^{(F)}$ $\displaystyle=\big{\{}\big{|}\widehat{F}_{i}(m_{i},\kappa_{i})-F_{i}(\kappa_{i})\big{|}\leq\alpha(m_{i},\kappa_{i})\big{\}}$ $\displaystyle\mathcal{G}_{i,m_{i},\kappa_{i}}^{(U)}$ $\displaystyle=\big{\{}\big{|}\widehat{U}_{i}(m_{i},\kappa_{i})-U_{i}(\kappa_{i})\big{|}\leq(1-u(\kappa_{i}))\alpha(m_{i},\kappa_{i})\big{\}}$ $\displaystyle\mathcal{G}_{i,m_{i},\kappa_{i}}$ $\displaystyle=\mathcal{G}_{i,m_{i},\kappa_{i}}^{(F)}\cap\mathcal{G}_{i,m_{i},\kappa_{i}}^{(U)}$ $\displaystyle\mathcal{G}_{i,r}$ $\displaystyle=\mathcal{G}_{i,m_{i}(r),\kappa_{i}(r)}$ $\displaystyle\mathcal{G}_{i}$ $\displaystyle=\bigcap_{r=1}^{\infty}\mathcal{G}_{i,r}$ $\displaystyle\mathcal{G}$ $\displaystyle=\mathcal{G}_{1}\cap\cdots\cap\mathcal{G}_{n}.$ $$

By definition, an execution is clean if and only if $\mathcal{G}$ holds. Due to the captime doubling condition, and because $i$ might eventually be eliminated (though it might not be), if $R_{i}$ is the set of rounds in which $i$ was selected, we have

$$ $\displaystyle\bigcap_{m_{i}=1}^{\infty}\bigcap_{l_{i}=1}^{\infty}\mathcal{G}_{i,m_{i},2^{l_{i}-1}}\subseteq\bigcap_{r\in R_{i}}\mathcal{G}_{i,m_{i}(r),\kappa_{i}(r)}.$ (3) $$

For any round $r$, let $\rho_{i}(r)\leq r$ be the last round in which configuration $i$ was selected (i.e., up to and including round $r$). Since $i$ was not selected in any rounds between $\rho_{i}(r)$ and $r$, the values of $i$’s internal variables in round $r$ are the same as they were in round $\rho_{i}(r)$. So the clean bounds hold in round $r$ if and only if they hold in round $\rho_{i}(r)$, and so they hold in all rounds if and only if they hold in all rounds where $i$ is selected. In other words

$$ $\displaystyle\bigcap_{r=1}^{\infty}\mathcal{G}_{i,r}=\bigcap_{r\in R_{i}}\mathcal{G}_{i,r}.$ (4) $$

We can now bound the probability that an execution is not clean:

$$ $\displaystyle\Pr(\overline{\mathcal{G}})$ $\displaystyle=\Pr(\overline{\mathcal{G}_{1}}\cup\cdots\cup\overline{\mathcal{G}_{n}})$ (de Morgan’s law) $\displaystyle\leq\sum_{i=1}^{n}\Pr(\overline{\mathcal{G}_{i}})$ (union bound) $\displaystyle=\sum_{i=1}^{n}\Pr\bigg{(}\overline{\bigcap_{r=1}^{\infty}\mathcal{G}_{i,r}}\bigg{)}$ (definition) $\displaystyle=\sum_{i=1}^{n}\Pr\bigg{(}\overline{\bigcap_{r\in R_{i}}\mathcal{G}_{i,r}}\bigg{)}$ ( Equation 4 ) $\displaystyle=\sum_{i=1}^{n}\Pr\bigg{(}\overline{\bigcap_{r\in R_{i}}\mathcal{G}_{i,m_{i}(r),\kappa_{i}(r)}}\bigg{)}$ (definition) $\displaystyle\leq\sum_{i=1}^{n}\Pr\bigg{(}\overline{\bigcap_{m_{i}=1}^{\infty}\bigcap_{l_{i}=1}^{\infty}\mathcal{G}_{i,m_{i},2^{l_{i}-1}}}\bigg{)}$ ( Equation 3 ) $\displaystyle=\sum_{i=1}^{n}\Pr\bigg{(}\bigcup_{m_{i}=1}^{\infty}\bigcup_{l_{i}=1}^{\infty}\overline{\mathcal{G}_{i,m_{i},2^{l_{i}-1}}}\bigg{)}$ (de Morgan’s law) $\displaystyle\leq\sum_{i=1}^{n}\sum_{m_{i}=1}^{\infty}\sum_{l_{i}=1}^{\infty}\Pr\big{(}\overline{\mathcal{G}_{i,m_{i},2^{l_{i}-1}}}\big{)}$ (union bound) $\displaystyle\leq\sum_{i=1}^{n}\sum_{m_{i}=1}^{\infty}\sum_{l_{i}=1}^{\infty}\bigg{(}\Pr\Big{(}\overline{\mathcal{G}_{i,m_{i},\kappa_{i}}^{(F)}}\Big{)}+\Pr\Big{(}\overline{\mathcal{G}_{i,m_{i},\kappa_{i}}^{(U)}}\Big{)}\bigg{)}$ (union bound) $\displaystyle\leq\sum_{i=1}^{n}\sum_{m_{i}=1}^{\infty}\sum_{l_{i}=1}^{\infty}\frac{4\delta}{11nm_{i}^{2}l_{i}^{2}}$ (Hoeffding’s inequality) $\displaystyle\leq\delta$ $\displaystyle\text{(Basel problem)}.$ $$

∎

###### Proof.

#### Lemma 2 :

For all $i$ at all points during a clean execution, we have

$$ $\displaystyle LCB_{i}\leq U_{i}\leq UCB_{i},$ $$

and

$$ $\displaystyle UCB_{i}-LCB_{i}\leq 2\alpha(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}.$ $$

###### Proof.

We will use the fact that $U_{i}(\kappa)-{u({\kappa})\big{(}1-F_{i}({\kappa})\big{)}}\leq U_{i}$ for any $\kappa$ by the law of total expectation, and that $U_{i}\leq U_{i}(\kappa)$ by the monotonicity of $u$. We have

$$ $\displaystyle LCB_{i}$ $\displaystyle=\widehat{U}_{i}-\alpha(m_{i},\kappa_{i})-u(\kappa_{i})(1-\widehat{F}_{i})$ (definition) $\displaystyle\leq U_{i}(\kappa_{i})-u(\kappa_{i})\cdot\alpha(m_{i},\kappa_{i})-u(\kappa_{i})(1-\widehat{F}_{i})$ (clean) $\displaystyle\leq U_{i}(\kappa_{i})-{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}$ (clean) $\displaystyle\leq U_{i}$ (law of total expectation) $\displaystyle\leq U_{i}(\kappa_{i})$ (monotonic utility) $\displaystyle\leq\widehat{U}_{i}+(1-u(\kappa_{i}))\cdot\alpha(m_{i},\kappa_{i})$ (clean) $\displaystyle=UCB_{i}$ $\displaystyle\text{(definition)}.$ $$

And

$$ $\displaystyle UCB_{i}-LCB_{i}$ $\displaystyle=(2-u(\kappa_{i}))\cdot\alpha(m_{i},\kappa_{i})+u(\kappa_{i})\big{(}1-\widehat{F}_{i}\big{)}$ (definition) $\displaystyle\leq 2\alpha(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}$ $\displaystyle\text{(clean)}.$ $$

∎

###### Proof.

#### Theorem 1 :

With probability at least $1-\delta$, OUP eventually returns an optimal configuration and it returns an $\epsilon$-optimal configuration if it is run until $2\alpha_{i^{opt}}+{u(\kappa_{{i^{opt}}})\big{(}1-F_{{i^{opt}}}(\kappa_{{i^{opt}}})\big{)}}\leq\epsilon$. Furthermore, for any suboptimal configuration $i$, if $m_{i}$ and $\kappa_{i}$ ever become large enough that

$$ $\displaystyle 2\alpha(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}<\Delta_{i}$ $$

then $i$ will never be run again, and $i$ will be outright eliminated once $m_{i},\kappa_{i},m_{i^{opt}}$ and $\kappa_{i^{opt}}$ are large enough that

$$ $\displaystyle 2\alpha(m_{i},\kappa_{i})+2\alpha(m_{i^{opt}},\kappa_{i^{opt}})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}+{u(\kappa_{{i^{opt}}})\big{(}1-F_{{i^{opt}}}(\kappa_{{i^{opt}}})\big{)}}<\Delta_{i}.$ $$

###### Proof.

By [Lemma 1](#Thmlemma1), the execution is clean with probability at least $1-\delta$. Suppose the execution is clean, so the bounds in [Lemma 2](#Thmlemma2) hold. For any configuration $i$ in any round $r$, suppose that $m_{i}$ and $\kappa_{i}$ are large enough that $2\alpha(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}<\Delta_{i}$ at the beginning of round $r$ (i.e., before any runs are performed). We have

$$ $\displaystyle UCB_{i}$ $\displaystyle\leq LCB_{i}+2\alpha(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}$ ( Lemma 2 ) $\displaystyle\leq U_{i}+2\alpha(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}$ ( Lemma 2 ) $\displaystyle<U_{i}+\Delta_{i}$ (assumption) $\displaystyle\leq U_{i^{opt}}$ (definition) $\displaystyle\leq UCB_{i^{opt}}$ ( Lemma 2 ) $$

so $i$ will not be selected in round $r$. And since $2\alpha(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}$ does not change in any round that $i$ is not selected, $i$ will never be selected again. So if $2\alpha(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}<\Delta_{i}$, then $i$ will never be run again.

Now, if OUP keeps selecting and running $i$, then we will have $2\alpha(m_{i},\kappa_{i})\to 0$ and ${u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}\to 0$, so there will come a time where $2\alpha(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}<\Delta_{i}$. In either case there will be some final round $r_{i}$ after which $i$ is never run again. Let $m_{i}$ and $\kappa_{i}$ be the procedure’s internal parameters at the end of this round. Only the optimal configuration(s) will be run after round $\max_{i\text{ suboptimal}}r_{i}$. Define $\gamma_{i}=\Delta_{i}-2\alpha(m_{i},\kappa_{i})-{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}$ and note that $\gamma_{i}>0$. As $m_{i^{opt}}\to\infty$ and $\kappa_{i^{opt}}\to\infty$, there will eventually come a time where $2\alpha(m_{i^{opt}},\kappa_{i^{opt}})+{u(\kappa_{{i^{opt}}})\big{(}1-F_{{i^{opt}}}(\kappa_{{i^{opt}}})\big{)}}<\gamma_{i}$ for any $i$. At this point we will have

$$ $\displaystyle UCB_{i}$ $\displaystyle\leq LCB_{i}+2\alpha(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}$ ( Lemma 2 ) $\displaystyle=U_{{i^{opt}}}-\Delta_{i}+2\alpha(m_{i},\kappa_{i})+{u(\kappa_{i})\big{(}1-F_{i}(\kappa_{i})\big{)}}$ (definition) $\displaystyle=U_{{i^{opt}}}-\gamma_{i}$ (definition) $\displaystyle\leq UCB_{{i^{opt}}}-\gamma_{i}$ ( Lemma 2 ) $\displaystyle\leq LCB_{{i^{opt}}}+2\alpha(m_{i^{opt}},\kappa_{i^{opt}})+{u(\kappa_{{i^{opt}}})\big{(}1-F_{{i^{opt}}}(\kappa_{{i^{opt}}})\big{)}}-\gamma_{i}$ ( Lemma 2 ) $\displaystyle<LCB_{{i^{opt}}}$ (time reached) $\displaystyle\leq LCB_{i^{*}}$ (choice of $i^{*}$ ) $$

and so $i$ will be eliminated outright.

Now, let $i^{*}_{r}$ be the configuration with highest $LCB$ at the end of round $r$, chosen at Line [19](#alg1.l19), and let ${i^{opt}}$ be an optimal configuration. During a clean execution we will have

$$ $\displaystyle UCB_{{i^{opt}}}$ $\displaystyle\geq U_{i^{opt}}$ ( Lemma 2 ) $\displaystyle\geq U_{i^{*}_{r}}$ ( ${i^{opt}}$ is optimal) $\displaystyle\geq LCB_{i^{*}_{r}}$ ( Lemma 2 ) $$

so ${i^{opt}}$ will not be eliminated. On the other hand, by the above, any suboptimal configuration $i$ will eventually be eliminated, so eventually only the optimal configuration(s) will remain.

Finally, suppose that a clean execution of OUP is run until $2\alpha_{i^{opt}}+{u(\kappa_{{i^{opt}}})\big{(}1-F_{{i^{opt}}}(\kappa_{{i^{opt}}})\big{)}}\leq\epsilon$. Then we will have

$$ $\displaystyle U_{i^{opt}}-U_{i^{*}}$ $\displaystyle\leq UCB_{i^{opt}}-LCB_{i^{*}}$ ( Lemma 2 ) $\displaystyle\leq UCB_{i^{opt}}-LCB_{i^{opt}}$ (choice of $i^{*}$ ) $\displaystyle\leq 2\alpha_{i^{opt}}+{u(\kappa_{{i^{opt}}})\big{(}1-F_{{i^{opt}}}(\kappa_{{i^{opt}}})\big{)}}$ ( Lemma 2 ) $\displaystyle\leq\epsilon$ (assumption) $$

so the returned configuration $i^{*}$ is $\epsilon$-optimal.
∎

###### Proof.

#### Lemma 3 :

An execution of COUP is clean for all phases with probability at least $1-\frac{\delta}{2}$.

###### Proof.

For any $p,i,m_{i},\kappa_{i}$, define the good events:

$$ $\displaystyle\mathcal{G}_{p,i,m_{i},\kappa_{i}}^{(U)}$ $\displaystyle=\big{\{}\big{|}U_{i}(\kappa_{i})-\widehat{U}_{i}(m_{i},\kappa_{i})\big{|}\leq(1-u(\kappa_{i}))\cdot\alpha_{p}(m_{i},\kappa_{i})\big{\}}$ $\displaystyle\mathcal{G}_{p,i,m_{i},\kappa_{i}}^{(F)}$ $\displaystyle=\big{\{}\big{|}F_{i}(\kappa_{i})-\widehat{F}_{i}(m_{i},\kappa_{i})\big{|}\leq\alpha_{p}(m_{i},\kappa_{i})\big{\}}$ $\displaystyle\mathcal{G}_{p,i,m_{i},\kappa_{i}}$ $\displaystyle=\mathcal{G}_{p,i,m_{i},\kappa_{i}}^{(U)}\cap\mathcal{G}_{p,i,m_{i},\kappa_{i}}^{(F)}$ $\displaystyle\mathcal{G}_{p,i}$ $\displaystyle=\bigcap_{m_{i}=1}^{\infty}\bigcap_{l_{i}=1}^{\infty}\mathcal{G}_{p,i,m_{i},2^{l_{i}-1}}$ $\displaystyle\mathcal{G}_{p}$ $\displaystyle=\mathcal{G}_{p,1}\cap\cdots\cap\mathcal{G}_{p,n_{p}}.$ $$

An execution is clean in phase $p$ if $\mathcal{G}_{p}$ holds. The probability that an execution is not clean in any phase is

$$ $\displaystyle\Pr\bigg{(}\bigcup_{p=1}^{\infty}\overline{\mathcal{G}_{p}}\bigg{)}$ $\displaystyle\leq\sum_{p=1}^{\infty}\sum_{i=1}^{n_{p}}\sum_{m_{i}=1}^{\infty}\sum_{l_{i}=1}^{\infty}\bigg{(}\Pr(\overline{\mathcal{G}_{p,i,m_{i},2^{l_{i}-1}}^{(F)}})+\Pr(\overline{\mathcal{G}_{p,i,m_{i},2^{l_{i}-1}}^{(U)}})\bigg{)}$ (union bound) $\displaystyle\leq\sum_{p=1}^{\infty}\sum_{i=1}^{n_{p}}\sum_{m_{i}=1}^{\infty}\sum_{l_{i}=1}^{\infty}\frac{4\delta}{36p^{2}n_{p}m_{i}^{2}l_{i}^{2}}$ (Hoeffding’s inequality) $\displaystyle\leq\frac{\delta}{2}$ $\displaystyle\text{(Basel problem)}.$ $$

∎

###### Proof.

#### Lemma 4 :

The proof is completely analogous to that of [Lemma 2](#Thmlemma2) and is omitted.

#### Lemma 5 :

An execution of COUP is characteristic for all phases with probability at least $1-\frac{\delta}{2}$.

###### Proof.

For any $p$, and for any $i\in\mathcal{A}_{p}$, from the definition of $OPT^{\gamma_{p}}$, the probability that $U_{i}\leq OPT^{\gamma_{p}}$ is at most $1-\gamma_{p}$. So the probability that all $n_{p}$ configurations have $U_{i}\leq OPT^{\gamma_{p}}$ is at most $(1-\gamma_{p})^{n_{p}}$, which is at most $(e^{-\gamma_{p}})^{n_{p}}=e^{-n_{p}\gamma_{p}}\leq\frac{3\delta}{\pi^{2}p^{2}}$. Summing over $p=1,2,...$, the probability that in any phase $p$ all $n_{p}$ configurations have $U_{i}\leq OPT^{\gamma_{p}}$ is at most $\frac{\delta}{2}$.
∎

###### Proof.

#### Theorem 2 :

If COUP is run with parameters $(\epsilon_{1},\epsilon_{2},...)$ and $(\gamma_{1},\gamma_{2},...)$ then with with probability at least $1-\delta$ it returns an $(\epsilon_{p},\gamma_{p})$-optimal configuration at the end of every phase $p=1,2,...$.

###### Proof.

By [Lemmas 3](#Thmlemma3) and [5](#Thmlemma5) an execution is both clean and characteristic with probability at least $1-\delta$. Because it is characteristic, there is some $i_{p}$ with $U_{i_{p}}\geq OPT^{\gamma_{p}}$. Let $i^{*}$ be the configuration returned at the end of phase $p$ during a clean and characteristic execution. We will have

$$ $\displaystyle U_{i^{*}}$ $\displaystyle\geq LCB_{i^{*}}$ ( Lemma 4 ) $\displaystyle\geq\max_{i\in\mathcal{A}_{p}}UCB_{i}-\epsilon_{p}$ (phase termination condition) $\displaystyle\geq UCB_{i_{p}}-\epsilon_{p}$ (maximum) $\displaystyle\geq U_{i_{p}}-\epsilon_{p}$ ( Lemma 4 ) $\displaystyle\geq OPT^{\gamma_{p}}-\epsilon_{p}$ $\displaystyle\text{(characteristic)}.$ $$

∎

###### Proof.

## Appendix C More Detailed Plots

[Figure 6](#A3.F6) shows a more detailed comparison of OUP with UP and the naive procedure. These plots show the same thing as [Figure 1](#S5.F1), but with higher resolution.

Figure: Figure 6: The $\epsilon$ guaranteed by each procedure as a function of total runtime using the log-Laplace utility function (top row) and uniform utility function (bottom row). OUP consistently outperforms both UP and the naive procedure for reasonable values of $\epsilon$, often by an order of magnitude and even when the the parameter of the naive procedure has been well-chosen.
Refer to caption: /html/2405.18246/assets/x28.png

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 5
presentation: 2
questions: What is delta in OUP? I don't see it being referenced in the description of OUP. Is it only used in one of the subroutines?
soundness: 3
strengths: The proposed method is general and there are extensive experiments demonstrating its performance.
summary: This paper studies utilitarian algorithm configuration, which is about automatically searching the parameter space of a given algorithm to optimise for its performance.

The first proposed algorithm is OUP.  It is a UCB style algorithm for finding configurations with good capped mean utility, with the addition of a scheme for periodically doubling the cap time.

The main algorithm is COUP. It builds on a new notion of optimisation goal called (epsilon, gamma) optimal. Epsilon is about being close to optimality and gamma controls how many configurations to sample. For fixed epsilon and gamma, the inner algorithm is for the most part just OUP. The novelty of the proposed algorithm is that it allows the sharing of trials over different epsilon and gamma.
weaknesses: The presentation of this paper is very hard to follow.

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 3
questions: 1. See issues with experiments above.
2. On line 6 of algorithm 2, COUP samples new configurations at random, which is basically how all of the theoretical approaches to AC work. Is there no way of sampling configurations that might actually be good while maintaining guarantees? It feels like these approaches are all poking around in the dark rather than actually optimizing. (future work, I suppose)
soundness: 4
strengths: 1. The paper moves the theoretical results for algorithm configuration in a very important direction, namely one step closer to real-world settings.
2. The paper is generally understandable at various levels of detail -- one need not delve into the math to understand the what and why of the paper. The math is clean and well-written, but I note that I could not completely evaluate all of the proofs.
3. The experimental results are quite good, especially in an area where the gains have been mostly small or just on different areas of the Pareto front of time vs quality. This approach is very competitive.
summary: An approach for algorithm configuration is presented based on a maximizing the utility of the target algorithm. The approach follows a line of work on "utilitarian procrastination (UP)", extending the previous work to function in continuous (infinite) spaces. An interesting aspect of the work is that this extension does not come at the cost of hurting performance on the finite-space case, in fact the performance improves. The resulting method, COUP, has bounds proven indicating essentially how good the configurations it finds are.
weaknesses: 1. There are a few minor clarity issues:
	1. The start of the paper is a bit of a slog. It would have been nice to get to the point faster.
	2. I do not understand why the notation for Algorithm 1 is introduced after the algorithm is explained. I needed the notation before reading the explanation, so I ended up just being confused until I found the notation, then had to go back and read it again. 
	3. In Algorithm 1, i is shadowed on line 7. Very minor, but it just seems weird (the same goes for Alg. 2).
2. I found the visuals in the experiments sometimes hard to read, and was confused by some aspects.
	1. Particularly the brown/purple/green combination has very similar shadings on some monitors/printers, another color scheme might be better. 
	2. In Figure 3, the green line for OUP goes backwards between total time 10^0 and 10^1. Something must be wrong there.
	3. The symbols in Figure 5 do not match the legend, and in all honesty I can barely figure out what is going on here. The figures are just too small with too many points crowded in the same spots. 

Overall, I have found no major issues with the paper, but I acknowledge that I am not an expert in the math of this paper and could have overlooked something. I am also not convinced of the superiority of the utilitarian approach of AC versus runtime configuration. However, the authors identify valid limitations and I find the use of utilitarian AC plausible for certain users, thus I do not view my disagreement on this point as something to hold against this paper.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: The questions for me are centered around the relation with metric space bandits, and the use of additional baselines.
soundness: 3
strengths: The problem considered is important, and the proposed algorithms are sound.

The theoretical guarantees are valuable.

The paper is well written.
summary: The paper considers the problem of algorithm configuration. There are two key elements that are not handled in combination by previous approaches: (1) infinite (potentially continuous) parameter spaces, and (2) utilitarian reward (which is a function of the running time).

A new algorithm is proposed, COUP, which is based on UCB, using doubling trick for extending cap on the running time, and sampling increasing numbers of arms to deal with the infinite arm's space. A simplified version for finite number of arms, OUP, is also considered. The algorithms are shown to achieve close to optimal configuration. 

The proposed algorithm is compared to another utilitarian algorithm UP, achieving faster convergence for the finite case. The COUP algorithm  seems to perform well empirically for the many configurations case as well.
weaknesses: The infinite parametric space problem seems related to me to the bandit problems in continuous/metric spaces. For those problems, the performance of the bandit algorithm is compared to the optimal solution, which is facilitated by Lipschitz or stronger conditions on the reward function. In this work only the top percentile is considered (which is simpler with sampling), but I assume similar conditions on the utility could be considered here as well.

The experiments use a very limited set of baselines (UP). I think, it would have reasonable to test the algorithm against algorithms that minimize the running time (with the utility coinciding with the running time, or just using the running time as surrogate measure for those algorithms). Testing non-bandit based algorithm configuration approaches would also make sense.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: 1) Anonymous repo link seems to be missing?

2) In Figure 1 - second row - third graph - there is a sudden drop in the total runtime (for OUP) around $\epsilon \approx 0.19$. Is this due to some specific structure of the problem/algorithm being analyzed?

3) The authors mention that Hyperband also performs well in the percentage-gap metric, but from Figure 5, it’s unclear to me that COUP/OUP actually outperforms it. Is there a reason to expect COUP/OUP would perform better, or is there something I might be overlooking?
soundness: 4
strengths: 1) The finite version (OUP) procedure improves over the previous (UP) procedure using ideas from UCB algorithm in bandit literature.

2) Extensions to the infinite parameter space algorithms.

3) Maintaining the theoretical guarantees provided by the UP procedure.
summary: The paper introduces COUP (Continuous, Optimistic Utilitarian Procrastination) procedure, which explores the parameter space - possibly uncountably infinite - of a given algorithm to optimize its performance on a specified set of inputs, with performance measured through a utility function. The finite (parameter space) verison of the procedure, known as OUP, improves upon the UP (Graham et al., 2023b) by incorporating ideas from the UCB algorithm in bandit literature. Additionally, COUP generalizes the procedure to possibly uncountably infinite parameter space. While doing so, COUP retains the theoretical guarantees of the UP algorithm while being significantly faster, as demonstrated by both theoretical guarantees and empirical results.
weaknesses: 1) The presentation of Section 3 could be improved slightly; introducing the notation before presenting Algorithm 1 might enhance readability.

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
questions: na
soundness: 3
strengths: The paper appears organized and well-written. The authors effectively emphasized the big picture in Sections 1 and 2, providing a clear understanding of this new and improved algorithm.

The algorithm is general enough to be applied to many optimization problems. It includes theoretical properties; however, we did not check the appendix for the validity of the proof.
summary: The authors introduced a new procedure, COUP, which claims that 1) it can run on continuous space and 2) it is faster than UP in the case of discrete space. Later experiments confirmed their claims.
weaknesses: na

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 4
questions: Can you address the points I raised in Weakness?
soundness: 3
strengths: - It is well-motivated, well-executed and well-written.
- The theoretical analysis looks intuitive and right.
summary: The authors study the problem of utilitarian algorithm configuration with inifinite number of parameters.
The key idea is i) to adopt the UCB (upper confidence bound) method rather than the SE (sequential elimination) method in balancing exploration and confirmation of the best parameter to reach the same guarantee with shorter run time, and ii) to relax the reference point of the guarantee from the best to quantiles.
weaknesses: - The impact of the extension to continuous space is unclear. I would suggest to compare COUP with OUP + fixed discretization of continuous space.
- The continuous structure (similarities among neighbor parameters) is not utilized in COUP. So, C in COUP does not describe its nature accurately.  

Minor:
- In Lemma 2, don’t you need “with probability 1- \delta”?
- Why not using log scale for the vertical axes of Figure 1?

Meta-review: Core technical content is bleeding onto the 11th page, for which current guidance is desk rejection. Moreover, none of the reviewers have thoroughly evaluated the main theoretical claims in terms of best arm identification with respect to the state of the art, and are overly positive while lacking any confidence about their assessments.

------

This is a revised meta-review by PCs, as the original meta-review contained a factual error which led to the reject decision.

PCs reviewed the reviews and discussions, and also consulted the manuscript. PCs concur with some of the strengths and weaknesses pointed by the reviewers. PCs recognize the interestingness of the conceptual generalization. PCs also took note of the mixed empirical success and the desiderata of having more systematic comparisons to related algorithms for this problem. Finally, PCs weigh in the factors of reviewers' confidence level in making their assessments.

The overall conclusion is that the paper is recommended to be accepted as a poster.

Decision: Accept (Poster)