Utilitarian Algorithm Configuration
Authors: Devon R. Graham
Kevin Leyton-Brown
Tim Roughgarden
Venue: NeurIPS 2023 poster (2023)
Keywords: algorithm configuration
algorithm selection
data-driven algorithm design
utility of runtime
TL;DR: A theoretically-grounded utilitarian approach to algorithm configuration

Abstract: We present the first nontrivial procedure for configuring heuristic algorithms to maximize the utility provided to their end users while also offering theoretical guarantees about performance. Existing procedures seek configurations that minimize expected runtime. However, very recent theoretical work argues that expected runtime minimization fails to capture algorithm designers' preferences. Here we show that the utilitarian objective also confers significant algorithmic benefits. Intuitively, this is because mean runtime is dominated by extremely long runs even when they are incredibly rare; indeed, even when an algorithm never gives rise to such long runs, configuration procedures that provably minimize mean runtime must perform a huge number of experiments to demonstrate this fact. In contrast, utility is bounded and monotonically decreasing in runtime, allowing for meaningful empirical bounds on a configuration's performance. This paper builds on this idea to describe effective and theoretically sound configuration procedures. We prove upper bounds on the runtime of these procedures that are similar to theoretical lower bounds, while also demonstrating their performance empirically.

Utilitarian Algorithm Configuration
Devon R. Graham
Kevin Leyton-Brown Department Computer Science
Department of Computer Science University of British Columbia Vancouver, BC drgraham@cs cs. ubc.
University of British Columbia
Vancouver, BC kevinlbecs.ubce ubc.ca
Tim Roughgarden
Columbia University & al6z crypto New York, NY
tim. rom.roughggardd@@mmall... com
Abstract
We present the first nontrivial procedure for configuring heuristic algorithms maximize the utility provided to their end users while also offering theoretical guarantees about performance. Existing procedures seek configurations that mini- mize expected runtime. However, very recent theoretical work argues that expected runtime minimization fails to capture algorithm designers' preferences. Here we show that the utilitarian objective also confers significant algorithmic benefits. Intuitively, this because mean runtime dominated by extremely long runs even when they are incredibly rare; indeed, even when an algorithm never gives rise to such long runs, configuration procedures that provably minimize mean runtime must perform huge number of experiments to demonstrate this fact. In contrast, utility is bounded and monotonically decreasing runtime, allowing for meaningful empirical bounds on configuration's 's performance. This paper builds on this idea to describe effective and theoretically sound configuration procedures. We prove upper bounds the runtime of these procedures that are similar theoretical lower bounds, while also demonstrating their performance empirically.
Introduction
Heuristic algorithms are surprisingly effective at solving hard computational problems. However, no single set of heuristics works well on all problems; the design choices must be tuned to distribution of problem instances in the same way that the parameters of machine learning model are tuned to dataset. This black-box optimization problem is called algorithm configuration. Roughly speaking, the literature on algorithm configuration divided into two camps. The older and larger camp designs heuristic procedures that aim to find good configurations as quickly as possible (Birattari et al. 2002 al. 2016). second, more recent line of work aims to provably identify approximately optimal configurations and to offer guarantees about the runtime required to do so (Kleinberg et al. 2017: Weisz al.. 2018 Kleinberg et al.) 2019)
Hutter et al. 2009 [011 Ansótegui et al. 2009 López-
Weisz et af., 2019 2020). Virtually all of the work in both camps has focused on minimizing some version of capped average runtime, although one exception which we are aware is Tornede et al. (2020), which explores objectives like higher-order polynomials of runtime that might better capture a user's level of risk-aversion.
Very recently, theoretical argument has been made that minimizing expected runtime is inconsistent with plausible set of axioms about algorithm designers' preferences (Graham et al. 2023). Runtime is an economic good and, like other economic goods, the value an individual assigns to it is not
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

necessarily proportional to the value of the good itself nor should it be. We can characterize a set of bounded and monotonically decreasing utility functions that are implied by certain axioms. These are essentially the von Neumann-Morgenseen classical decision theory, plus two novel runtime-specifie axioms that assert a (weak) preference for faster runs over slower ones, and (strict) preference for algorithm runs that complete over ones that time out, Preferences that follow these axioms are described by a utility function that is monotonically decreasing in runtime from I to O. This utility function can incorporate factors like the benefit an end user attains from completing a run, the cost they pay for cloud computing resources, and any uncertainty they may have about when an answer will stop being useful to them. This utilitarian perspective opens a new and exciting direction for algorithm configuration.
axioms (Von Neumann and Morgenstern 1944) from
While it is reassuring to know that optimizing utility instead of runtime is the right thing to do, it also offers significant algorithmic benefits. Because utilities are bounded and monotonically decreasing, exceedingly long runs contribute negligibly to estimates of an algorithm's is expected utility. This means that there will always be some captime that allows us to accurately estimate true expected utility from capped samples. We can use tools from the multi-armed bandit literature for best arm identification, and the algorithms we describe will draw on the elimination and racing algorithms described in Mannor and Tsitsiklis (2004); [Even-Dar et al. (2006) and elsewhere. In contrast, runtime- based configuration procedures like Structured Procrastination (Kleinberg et al.. 2017). Structured Procrastination with Confidence (Kleinberg al.] 2019), LodundndBounds (Weisz et al.] 2018), CapsAndRuns (Weisz et al. 2019), and ImpatientCapssAddRue (Weisz et al. (020) need to do many runs at large captimes in order to make theoretical guarantees. Furthermore. in order to be able to make any provable guarantees at all, they have to introduce an additional parameter specifying how much of the runtime CDF can be ignored; even if algorithm has always finished very quickly on every instance seen so far, it could always take so long on the next instance that its expected runtime arbitrarily large. In this setting, no optimality guarantees can be made without broadening the definition of optimality.
Other iieoretically-motivvteed motivated methods such as Gupta and Roughgarden (2017); Balcan et al. 2017 202T) offer performance guarantees based on different measures of complexity and guarantee notions of PAC optimality akin to those present here. These papers do not focus runtime, instead studying traditional sample complexity, with each sample (i.c., algorithm run) contributing the same "sampling cost." In our algorithm configuration setting, the cost of sample is the amount of (capped) runtime spent acquiring it, with longer captimes potentially leading to more expensive (but also more informative) samples. Because of this difference, these two lines of work propose quite different types of learning algorithms. However, Balcan et al. (202T) do assume the existence of a bounded utility function which measures algorithm performance, and others (Hoos and Stützle, 2004) have argued that utility functions of this form are better objectives to optimize than runtime when choosing algorithms. Some methods have been specifically designed exploit the parallel nature of the algorithm configuration problem; AC- Band (Brandt et al. 2023) is bandit-basse procedure inspired by the Hyperband algorithm (Li al.) 2017) that runs multiple configurations simultaneously while ruling out poor-perti wor-perforring ones along the way and offering theoretical guarantees with respect to the set of configurations considered.
Inspired by the mantra of procrastination that has found success in previous work, and by the benefits that come with the use of utility functions, this paper presents procedure we dub Utilitarian Procrastination (UP), so-named because it performs as many low-captime runs as possible before proceeding to higher-captime runs. We offer theoretical guarantees about its performance, showing that it will return a good configuration and proving that its worst-case upper bound is similar to the theoretical lower bound that any procedure must require. We also present experimental results showing how this procedure performs in practice and how it compares to a more naive baseline.
2 Setup
We assume there is a monotonically decreasing runtime utility function R20 + [0. 1] with u(O) 1 and lim u(!) = 0. The existence of u follows from simple axioms (Graham et al., 2.23). h. The value u(l) describes the (expected) well-being of an individual who uses an algorithm to solve a problem instance (e.g., an integer program). During the configuration process, the goal will be to choose an algorithm that maximizes u(t), in expectation over t.
2

---

Given a set of algorithms indexed by i 1...., our goal is to find an approximately optimal algorithm using capped runtime samples. We assume we have access to stream of imput instances indexed by j = 2, 2,... drawn from some distribution Dy. We will use 4ij to denote the true uncapped runtime of algorithm on input j. and (1)(*)) = min(leg x) to be the x-capped runtime of i on j- When we do run, we observe fiy (K), not lig. Of course these coincide for any run that completes. The instance distribution Dj, along with any randomness of the algorithm or execution environment will together induce a runtime distribution for each algorithm i. We will use D, to denote this runtime distribution, and F, to denote its CDE. For each algorithm i, the true uncapped expected utility is
U
IF twD.
[u(t]]
The capped expected utility is
U((K)= [u(minu (miin(t, k))].
tnD;
And given any capped runtime samples tu (z), tsm (K), the capped empirical average utility is U (1:) = 1 Eu(tts(n)
m j=1
Definition (e-optimal). An algorithm i" called c-optimal if 2 max; -c
Our goal will be to find e-optimal algorithms with probability at least 1 - ō, and to do so as quickly as possible. Our first lemma deterministically bounds an algorithm's uncapped expected utility in terms of its capped expected utility and CDF.
Lemma 1. For any i and K we deterministically have U.(K) - u(x)(1 F.())) s U, S (K)).
Proof. This follows from the law of total expectation and the fact that u is non-increasing, and so u(k) 2 u(t) for all 2 K.
Intuitively, Lemma D is true because the capped expected utility counts runs that cap as having just completed at the captime, when really they would have taken longer if given the chance. This makes the capped expected utility look more favourable than the uncapped expected utility. Our second lemma shows that if we do runs at captime K, then we can accurately estimate the algorithm's 's runtime CDF at K.
Lemma 2.
For any i, m, Ks and 6, let (1)) be the fraction of the m runs that A completes within
captime Then (r)((s) / [n(1/8) < F((k) S Fimm
[I[118] with probability at least 1 - 28.
2m
Proof. For each j. let X, 1 if t.y and X, 0 otherwise. The proof then follows from straightforward application of Hoeffding's inequality.
simply says that if we take enough samples at captime the fraction of those runs that complete will be close to the true likelihood of a run completing before k. Our third lemma shows that expected capped utility can be estimated accurately using capped runtime samples.
Lemma 2
Lemma 3. For any i, m, K and 8 we have Ü.. (K) (1 u(k)) V
Im(1/5] < U,(K) (x)+
(1 (1-u(x)) V
In(1/5) with probability least 28.
2m
Proof. Since u (())(N)) E [n(x),1] for all j. the proof follows immediately from Hoeffding's inequality.
Lemma simply says that if we take enough samples, then the empirical capped average utility will be close the true expected capped utility. Together, these lemmas imply empirical confidence bounds on the true expected utility. Define the upper and lower confidence bounds
In in(4n/8)
UCB (1:) = (0m((r)) + (1 11-11umm (xx)) V
2m
1n(4n/8)
LCB (R:) = -.sm(r)) -V
u(x)(( Fsm (x)).
2m
3

---

The next lemma shows that these are good confidence bounds if both the captime & and the number of samples m are sufficienlly large. With probability at least - 6, each algorithm' 's true expected utility will fall within these confidence bounds, and the width of each confidence range will not be too large.
Lemma 4. If we do m runs of each algorithu at captime H, then with probability at least 5 we will have
LC SUSUUC 19.SUC SUCBim
and
In(4n/0)
UCB
LCB S 12
+ u(k)(1 F(()))
2m
for all i simultaneously.
See Appendix for a full proof. The idea is that the definition of the bounds together with Lemmas 3 mean the confidence bounds hold and are accurate.
We can see in Lemma 4 that the error in our estimate of an algorithm's expected utility comes from
In(4n/6)
represents the error due to sampling, while the term u(x) (1- (x)) represents the error due to capping. To make good guarantees,
two sources: sampling and capping. The term 2/
2m
configuration procedures will need to ensure that both of these terms are sufficiently small.
3 Configuration Procedures
We first describe two hypothetical procedures that give us lower bounds on the number of samples and the captime that any configuration procedure will need to use. The bound on the number of samples (Section 3.1 is classic result. In Section 3.2 we use a novel "prover-skeptic" argument to show the lower bound on captime. We then describe in Section 3.3 simple usable procedure that returns an 6-optimal algorithm with probability at least 8, but which suffers from two major drawbacks. First, requires that we specify an accuracy parameter and a captime as input ahead of time. Making poor choices for these parameters time (see Section 4 for an illustration). Indeed, many choices of e, and are mutually incompatible, giving rise to meaningless bounds. To avoid this, we hope design procedures that anytime: they continue to improve the accuracy guarantees they can make as they spend more time running. By taking gradually more and more samples, and by gradually taking them at higher and higher captimes, an anytime procedure continues to shrink the that it can guarantee, rather than trying to target a fixed it given input. Second, the naive procedure is not input-adaptive in any way. It does the same number of samples at the same captime for every algorithm. Both of these drawbacks are fixed by UP procedure in Section 3.4 UP is an anytime procedure, meaning it requires neither
have large impact total configuration
a x as input, but instead gradually reduces the it can guarantee by increasing both the number of samples and the captime.
3.1 Hypothetical Runtime Oracle Procedure
The unique characteristic of our setting is the fact that observe capped rather than true runtime samples, and that the cost we pay for each sample equal to the time we spend collecting it. If this were not the case, then our problem would already be solved. If we had some oracle that could simply query for the true runtime of an algorithm run on a given instance, then all we would need to do is collect sufficiently many samples from each algorithm. In this case, the optimal procedure simply takes an increasing number samples of each algorithm and rules out each suboptimal one was soon as it can. The Runtime Oracle Procedure (Algorithm) I an instantiation of the Successive Elimination algorithm Even-Dar et al. (2006) (their Algorithm 3). With probability at least ô will eventually eliminate all algorithms except the optimal one.
Theorem 1.
With probability at least 1 the Runtime Oracle procedure will eventually return the optimal algorithm, and it will return an e-optimal algorithm if it is run until m is large enough that
lnf lu(Amm2/8 (8) < e. At that point it will have taken m uncapped samples of each e-optimal algorithm, 2m
2

---

Algorithm Runtime Oracle Procedure
Inputs: Algorithms = 1,, ni stream of instance j = 1, 2, ...; utility function w; parameter 8;
runtime oracle R.
< {I,....11} [1 for m 1,2,3,.... do
D candidate algorithms
for i E I do
fi obtain i's runtime from R. on m-th instance m Σ== u(t)))
Umm end for
1 f- arg max 0am
In(4nm²
2m do
for
i
if 0 km Upmm
20 then 1+1
is suboptimal D remove i
end if end for I = or execution interrupted then
return 1"
end if end for
In /8) 2m,
and m, S uncapped samples of each e-suboptimal algorithm where 2 where A the difference between the expected utility of an optimal algoritim and of algorithm i.
< A; and
See Even-Dar et al. (206)) Theorem and Remark 9 for proofs and details. The Runtime Oracle procedure has two desirable qualities that would like to preserve in the configuration procedures we design. Firstly, we do not need to supply the parameter ahead time. Instead, the procedure maintains an internal that it can guarantee, continually shrinking this toward O. Secondly, the number of samples needed to eliminate e-suboptimal algorithms grows with square of the suboptimality gap A max; Uy U, rather than the square of c. Theorem [ gives input-dependent guarantee for the Runtime Oracle procedure that we would like to preserve in the usable procedures we design. If some algorithm i is very suboptimal, with A, > then we will be able eliminate it with many fewer samples than an algorithm that is almost coppiimll.
The Runtime Oracle procedure gives us baseline against which to compare. Its sample complexity guarantee is essentially optimal in the following data-dependent sense.
Theorem 2 (Theorem 5 of Mannor and Tsitsiklis (2004)). There exists some set of input distributions for which every oracle procedure that returns an e-optimal algorithum with probability least 1 must take Q( 2l(e)l log } + EiEN(e) A7 algorithms.
1 log }) samples, where ((e) is the set of e-suboptimal
3.2 Hypothetical Captime Verification Procedure
We now consider lower bound the captime we will be required to use, even world where we do not need to take samples. We imagine there are prover and skeptic. The prover has access to the runtime CDF of each algorithm The skeptic will get see each runtime CDF only up some N; that the prover will choose. The prover then recommends an algorithm i" and the skeptic should be convinced that i" e-optimal, based only on the truncated CDFs. As the K; 's tend infinity, the skeptic will see more and more of the true CDFs and therefore eventually be convinced of the prover's s claim (assuming it is true). The goal convince the skeptic that i* is e-optimal using Ky that are as small as possible. The skeptic will be able to compute the following deterministic bounds

---

Algorithm 2 Captime Verification Procedure
Inputs: Algorithms i i= I ni stream of instances j = 1, ... utility function u; parameter runtime CDFs F1, Pu..
for i = 1,..... do
U,= So (t))
I> expected utility
end for gops
<- arg max; U,
optimal algorithm
for i = 1, ..... ni do
A U punt Uj
K; f inf (K= u(x) (1(()) SA, + +
end
i" arg max; LB;
if LB,- 2 UB; - for 1,.., .....'' then
D skeptic's check
return 1"
else
return "failed"
end
on an algorithm's 's expected utility
UB: J/" u(t)dF((()+ + (1 P((ks))
LB, ' u(t)dF((t).
The skeptic knows that LB, S U. S U;, but also that the runtime distributions could such as to make U, fall anywhere in this range. So whatever algorithm i" the prover returns to the skeptic, the skeptic will be convinced that is e-optimal if, and only if, they observe LB;- 2 UB; e for all i 7 it. The following lemma justifies this condition.
Lemma 5. If LB;- 2 UB: for all i + i', then i is e-optimal. If there exists an i + i with LB,- B; e, then regardless of the values of the CDFs F. up the captimes Ki, there are some impul distributions for which i" is not e-optimal.
The proof works by constructing counter-example CDFs, but takes the CDFs given up Kg so does not rely on specifying any information available to the skeptic No matter what the CDF of each i looks like up to Ki; there will be some inputs with LB₃- U B; for which i" e-optimal.
Lemma 6. The skeptic will be convinced that both popt and i* arg max; LB, are c-optimal if the captimes Kg are large enough that (1,,))(1 F.(()) < A + for all algorithms
Algorithm describes the prover- skeptic interaction. The next lemma shows that using these captimes is essentially optimal. gives us a baseline minimum captime against which to compare.
Lemma 7. There are some inputs for which any verification procedure must use captimes K; large enough that u(R;) (1-F.(s.) S A; + e for all algorithms i, the skeplic will not be convinced that the returned algorithm e-optimal.
The proof simply constructs counterexample for which doing runs at smaller captime will lead any configuration procedure to make a wrong conclusion.
3.3 Naive Procedure
We now turn to the setting we are actually interested in, where runs cost time and long ones must eventually terminated. The simplest thing we could do is just pick captime perhaps we somehow "know" the right captime) and do the necessary number of runs. With a fixed captime, the scenario is not much different from the runtime oracle scenario above. The main difference is that the "resolution" at which we can understand an algorithm's 's expected utility will be limited by the size of the captime we use take our samples. We will never know what the runtime CDF looks like beyond the captime, matter how many samples take. Given any the confidence bounds described in

---

Algorithm 3 Naive Procedure
Inputs: Algorithms = I,..., ni stream of instances j = 1, 2.... utility function u; parameters e, 8, captime satisfying u(x)) <.
2ln(2n/8)
(c (c-u(x))²
for i = 1,..., do
L1 (K) ,..,, Lim (1) run on m instances using captime
Ü im (K)
m u (x)(
empirical average utility
end for
i" < arg max; (k)
return
Section 2 tell us could simply choose the smallest satisfying 2 runs of each algorithm at captime k, then return the one with largest empirical average utility. We can think of 2
In(2n/5) + u(K) S do m
In(2n/62
as the error due to sampling, and ((t)) as the error due to capping. This is the 2m
Naive procedure.
Theorem 3. With probability at least ô the Naive procedure returns an e-optimal algorithm. It
takes enough k-capped runtime samples of each algorithm to ensure that 2v
[u(2n/8)
+ u(K) S.
2m
The proof of this and of subsequent theorems are deferred Appendix A] Each essentially follows from the fact that the upper and lower confidence bounds are specified satisfy Hoeffding's inequality and the union bound. Comparing Theorem 3 to Theorem I we can see the reason for the increased number of samples required when observe capped instead of uncapped runs: if u(x) is relatively
/I((2//6) enough to satisfy the inequality in 2m
large, will take much larger m shrink the term 2 Theorem
The Naive procedure has some undesirable qualities. Choosing the right may not be easy and in Section 4 we will show what difference this choice can make for the total runtime of the Naive procedure. We are also required to specify an c beforehand; it may hard to know the "right" c, and the best m and K for one e may be quite different from the best for slightly different e. What's ss more, this procedure ignores information about an algorithm's runtime distribution that could be learned by observing runs along the way; it essentially assumes that every algorithm always times out given captime. As result, it takes more samples of e-suboptimal algorithms than is necessary. The UP procedure corrects these defects.
3.4 Utilitarian Procrastination
Our Utilitarian Procrastination (UP) procedure starts by doing runs at the smallest captime possible, trying to rule out whatever configurations can, and only starts doing runs larger captime when necessary.
Theorem 4. With probability at least 1 - 8 UP eventually returns the optimal algo- rithm and returns an e-optimal algorithm if is run until m is large enough that 2 [n(1imm2
oop + u(Kspp)) Froms (Riortt )) I c. For any suboptimal i, if
2m
m. Kipps are ever large enough that 2 u(x))( - F((r))) + u(Keegg)) (1 (1- Frops (Kepp))) S A then i will be eliminated.
In(12nm (logg. (108),+1)//0 2m
+2 In(11nm 2 (log ont +1)2/8)
2m
In Theorem we can clearly see the analog of both Theorem | and Theorem 3 UP input dependent in two senses. The condition for ruling out suboptimal i depends on A; and also on the runtime CDFs F; and F, Just in the pure sample complexity case of Theorem D if is very suboptimal and A, is large, it will be easier to satisfy the condition in Theorem E and thus rule out. Additionally, the condition will be easier to satisfy if the inputs are such that either or jopt is able to complete lot of runs at their respective captimes, so that their CDFs are close to 1. Theorem 4 also implies the following theorem and corollary, which together constitute our main theoretical result.
7

---

Algorithm 4 Utilitarian Procrastination
Inputs: Algorithms i = 1, 1,.., n; stream of instances 1, 1, 2...i utility function u:; parameter < [I,... ] Ki - for all E
candidate algorithms
for m 1,2.3,... do
for i E do
ta (K:)), tim (N:) f run on m instances using captime Ki
Fim f 1 (1,())))))
>> fraction of runs that completed empirical average utility
Ümm( (14))
E== (Kt) m
In(11nm (aaaaimmmilloooooo N.
aim
2m
UCB Umm(mi + u(ki))
LC + Üa (mo) a'm u(n;)(1 Fim (ki)
end for 8" for i arg maxiel LCBin do if UCBB LCB then
i is suboptimal b remove
I+ {i}
end if
if 200mm
I <u(ks)(1 (x:)) then
D. captime doubling condition
Ri 2kg
end if end for
if [
1 or execution is interrupted then
return 1"
end if end for
Theorem For any m, let 6 == =3v c-optimal algorithm once it takes m samples. At that point, if K2 is the largest captime algorithm i has been run with then x² < 2nf {n u(x) (.))))
[a( Then with probability at least - 6, UP returns an 2m
3
The proof follows from Theorem 4 and from UP's specific choice of captime doubling condition. We note that there is room for improvement, but that this captime bound is comparable to the worst-case lower bound captime needed by any configuration procedure presented Section 3.2 The smallest captime that satisfies u(x)(1 (x())) <
3v2 needs to be larger than the smallest captime that
< A, + c, which is the best we can hope to do. satisfies (1=))(1-F((())
Corollary With probability at least ò, UP returns an e-optimal algorithm after taking a number of samples that at most a logarithmic factor more than is optimally required by any procedure, and at a captime that is a constant larger than inf {R (1):)(( - F,(K:) < 3
Proof. The number of samples follows immediately from the definition e in Theorem 5 Because the captimes are always doubled, the total time spent by UP on any single instance is at most constant times larger than the time spent running that instance the final time it was run. Since the captime at that point at most xt; the total time spent running any instance is at most a constant times inf {K u(k) (x)))) < 3/2)
4 Experiments
We now illustrate the runtime costs of utilitarian algorithm configuration and the impacts of the adaptive improvements offered by UP over Naive. We would have liked to go further, and particular to offer comparisons against baselines other than Naive. However, we saw no straightforward way of doing so: there is simply no previous work on offering algorithm configuration the utility- maximizing setting. Our paper focuses algorithm configuration with theoretical guarantees. There

---

minisat
oplex FCW
cplex region
30.00
20000
3a burtiee 20H0 daysa
2000
30
Figure 1: Runtime of the Naive procedure for different values of input captime k. on three datasets using a Log-Laplace utility function. Choosing a bad captime can have a large effect on total configuration time, especially for smaller values.
do exist many methods with guarantees in the runtime minimizing setting; we could have run existing procedures like Structured Procrastination, LedpuundBounds, or CapsAndRuns and then evaluated them in terms of utilitarian objective. However, such an apples-to-oranges comparison would likely have yielded very poor performance and regardless would have dispensed with the guarantees that motivate these methods. Second, we could have compared to heuristic methods like SMAC, ParamILS and GGA. Again, however, they optimize a different objective function. It is possible to imagine modifying one of these algorithms to optimize utility, but doing so would require fundamental algorithmic changes (e.g., to their so-called adaptive capping heuristics) and nontrivial software con-controversial way, comparing comparison. Perhaps for these reasons, we note that no paper of which we are aware has yet compared any heuristic algorithm configuration method to any offering theoretical guarantees. We do intend to pursue such an investigation ourselves in future work, but anticipate that a careful study of this question will require an entire research paper.
engineering effort. Even if we could have made such changes heuristic methods to methods offering guarantees would again be an apples-to-orang
Experimental Setup. We leverage three datasets from Weisz et al. (2020). The first is set of runtimes for the minisat SAT solver on data generated by the CNFuzzdd instance generator. The others are sets of runtimes for the CPLEX integer program solver the combinatorial auction winner determination instances (regions) and on woodpecker conservation problems (rew); see Appendix D of Weisz et al. (2020) for details. We only used the first seed for the CPLEX datasets !
Choosing the Right Captime Matters. In Fig. D we plot the total configuration time of the Naive procedure with different input captimes x on three datasets from Weisz et al. (2020) using a log-
Laplace utility function from Graham et al. (2023): u(() ur.r. (4; 60, 1) = 2 60 if < 60 and u(t) 2 60 otherwise. We used values of 0.1, 0.15 and 0.2 and set 8 = 0.1. The first observation we make is that choosing a bad captime can have a large effect on total configuration time, especially for smaller values. The second observation is that, for any fixed k. different values of can also have huge effects on total runtime of the configuration procedure. Both of these points help to emphasize the need for a procedure like UP that starts out with small K, only increasing it as needed, and refines the e it can guarantee "on the fly"", based on the runs it has observed.
Anytime Speedups Matter. In Fig. 2 we plot the total configuration time of UP and Naive as function of We used the same log-Laplace utility function as above and set 8 0.1 (within reasonable ranges, the value of has relatively little effect on total runtime). UP can drastically outperform Naive, especially for smaller values c.
Unsurprisingly, being anytime x helps most when we do not know how to provide a good ii as input beforehand. If we somehow guess or know the right captime to use, then it can be hard to beat Naive. But if we use the wrong captime. UP can be much faster than Naive. In Fig. 3 we use a uniform utility function from Graham et al. 2023 with u(t) Muni (t: 60) = 1 and 0 otherwise. In the top row, we have used a captime of k = 60 for Naive, which is appropriate for this utility function since it is linear up to that point and then O thereafter. In the bottom row, we have set the captime poorly at x = 600, meaning that we are not terminating some runs even though
for t < 60
'Code reproduce all plots can be found http:://gthhub..ooodddg///ttttit

---

minisat
cplex rCW
cplex region
Figure 2: Runtime of the different configuration procedures for different values of on three different datasets using a log-Lapllace utility function. UP easily outperforms Naive.
minisat
cpi IXX region
Tote Nartime (CPL Maga) (App))
1000
400-
To
613
530
024
620
43x
413
532
004
414
6.1
4:24
0.22
minisal
cplex nCW
cplex region
2030
31000
1540
Totul
331
511 872
61c
Figure 3: Runtime of the different configuration procedures for different values of on three different datasets using a uniform utility function. The top row shows a scenario where the Naive procedure has been given an appropriate captime, the bottom row shows a scenario where it has not.
they are so long they give us utility. We can see that if we get the captime right, then Naive will perform quite well. But if we get it wrong, Naive can drastically underperform compared to UP.
5 Conclusion
We have presented Utilitarian Procrastination (UP), a utility- approach to automated algorithm configuration. This is the first procedure that we know of to incorporate utility functions into the algorithm configuration framework. UP is anytime, meaning it requires minimal input from the user and continues to refine its guarantees it is run. In simple experiments, we show that by freeing the user from having to provide either an accuracy parameter e or a captime x UP can help avoid the excessively long runtimes that come when these inputs are chosen poorly. Of course we would have liked to have shown that UP never uses a captime larger than Ky < 2 inf (N u(n)(11 - Fx(x:) <
As + } matching the hypothetical procedure. The bound we do show is a result of the condition UP checks when deciding whether to double the the captime Ng. UP uses a simple condition that balances the error due to sampling with the error due to capping. Other, more intelligent choices may be possible, but improving this will have to wait for future work.
10

---

6 Acknowledgements
Graham and Leyton- Browwn funded by NSERC Discovery Grant, DND/NSERC Discovery Grant Supplement, a CIFAR Canada AI Research Chair (Alberta Machine Intelligence Institute), a Compute Canada RAC Allocation, and DARPA award FA8750- 19-2-0222, CFDA #12.910 (Air Force Research Laboratory). Roughgarden's research at Columbia University is supported in part by NSF awards CCF-2006737 and CNS-2212745.
References
Ansótegui, C., Sellmann, M., and Tierney, K. (2009). A gender-based genetic algorithm for the automatic configuration of algorithms. International Conference on Principles and Practice of Constraint Programming, pages 142-157. Springer.
Balcan, M.-F., DeBlasio, D., Dick, T., Kingsford, C., Sandholm, T., and Vitercik, E. (2021). How much data is sufficient to learn high-performing algorithms? generalization guarantees for data- driven algorithm design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 932-932.
Balcan, M.-F., Nagarajan, V., Vitercik, E., and White, C. (2017). Learning- foundations of algorithm configuration for combinatorial partitioning problems. In Conference on Learning Theory, pages 213-274. PMLR.
Birattari, M., Stützle, T., Paquete, L., and Varrentrapp. K. (2002). racing algorithm for configuring metaheuristics. In Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computattion, page 1 11-18. Morgan Kaufmann Publishers Inc.
Brandt, J., Schede, E.,, Haddenhorst, B., Bengs, V., Hüllermeier, E., and Tiemey, K. (2023). Ac-band: A combinatorial bandit- based approach to algorithm configuration. Proceedings of the AAAI Conference Artificial Intelligence, 37(10):
Even-Dar, E., Mannor, S., Mansour, Y., and Mahadevan, S. (2006). Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6).
Graham, D. R., runtime distributions. In International Conference on Machine Learning, pages 1669-11682.
K., and Roughgarden, T. (2023). Formalizing preferences over
PMLR.
Gupta, R. and Roughgarden, T. (2017). A pac approach to application-specific algorithm selection.
SIAM Journal on Computing, 46(3):992-1017.
Hoos, H. H. and Stützle, T. (2004). Stochastic local search: Foundations and applications. Elsevier.
Hutter, F., H. Hoos, H., and Leyton-Brown, K. (2011). Sequential model-based optimization for general algorithm configuration. In International Conference on Learning and Intelligent Optimization, pages 507-523. Springer.
Hutter, F., Hoos, H. H., Leyton-Brown, K., and Stützle, T. (2009). Paramils: an automatic algorithm configuration framework. Journal of Artificial Intelligence Research, 36:267-306.
Kleinberg, R., Beyton--rowwe K., and Lucier, B. (2017). Efficiency through procrastination: Approx- imately optimal algorithm configuration with runtime guarantees. In IJCAI, volume 3, page 1.
Kleinberg, R., -roown, K., Lucier, B., and Graham, D. (2019). Procrastinating with confidence:
Near-optimal, anytime, adaptive algorithm configuration. arXiv preprini 102.54.90..0544.
Li, L., Jamicson, K., DeSalvo, G., Rostamizadch, A., and Talwalkar, A. (2017). Hyperband: A novel bandit-based approach to hyperparameter optimization. The journal of machine learning research, 18(1):6765-688 6816.
López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M., and Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43-58.

---

Mannor, S. and Tsitsiklis. J. N. (2004). The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5(Jun):623-6488
Tornede, A., Wever, M., Werner, S., Mohr, F,, and Hüllermeier, E. (2020). Run2survive: decision-
theoretic approach algorithm selection based survival analysis. In Asian Conference Machine Learning, pages 737-752. PMLR.
Von Neumann, J. and Morgenstern, O. (1944). Theory of games and economic behavior. Princeton university press.
Weisz, G., György, A., Lin, W.-I., Graham, D., Leyton-Brown, K., Szepesvari, C., and Lucier, B. (2020). Impatientcapsandnuns: Approximately optimal algorithm configuration from an infinite pool. Advances in Neural Information Processing Systems, 33:17478-17488.
Weisz, G., Gyorgy, A., and Szepesvári, C. (2018). Leapsandhounds: A method for approximately optimal algorithm configuration. In International Conference on Machine Learning, pages 5257- 5265. PMLR.
Weisz, G., Gyorgy, A., and Szepesvári, C. (2019). Capsandruns: An improved method for approxi- mately optimal algorithm configuration. In International Conference Machine Learning, pages 6707-6715 15. PMLR.
12


Reviews:
[{"review_id": "Epe7vccf4D", "reviewer": "Reviewer_Qzq9", "summary": "The paper introduces a setting and an algorithm for algorithm configuration based on utility of the algorithm's running time. Theoretical guarantees are provided and upper and lower bounds are compared against. The algorithm is evaluated on case studies.", "questions": "Is this the net or the intrinsic utility?", "limitations": "The limitations are addressed adequately.", "rating": 2, "confidence": 5, "soundness": 1, "presentation": 4, "contribution": 1, "strengths": "Utility-based decision making approach is applied to algorithm configuration. The proposed approach is theoretically analyzed and empirically evaluated. ", "weaknesses": "## Literature\n\nOn time (or resource in general) constrained utility based decision making, start with this seminal work by Stuart Russell and his PhD student Eric Wefald: https://mitpress.mit.edu/9780262513821/do-the-right-thing/\n\nFor a   more updated recent account on bounded rationality (that is, on making utility based decisions under computational resource constraints) look at this work (UAI 2012): https://arxiv.org/abs/1207.5879\n\nEric Horvitz is the 'father' of resource-bounded decision making.  Citations on bounded rationality are here: http://erichorvitz.com/computational_rationality_readings.htm. A good collection of articles coedited by Eric Horvitz and Shlomo Zilberstein is in this special issue of AIJ: https://www.sciencedirect.com/journal/artificial-intelligence/vol/126/issue/1\n\n## Problem with the submission under discussion\n\nAn algorithm is selected based on its expected net utility. The net utility consists of two terms, the intrinsic utility and the deliberation cost. Relevant work on algorithm configuration assumes that all algorithms have the same intrinsic utility (solve the problem 'exactly' or with solutions of indistinguishable quality), and their total utility depends on deliberation cost --- which is in many settings just the running time. \n\nIntuitively, the intrinsic utility is what you get and the deliberation cost is what you pay. The theory of utility to which the authors refer applies to the intrinsic utility.  The computation/time cost is an additive negative term in the total utility, which conforms to different laws, see the citations above for detailed discussion. \n\nThe authors confuse the intrinsic utility and the time cost, and apply non-linear bounding transformation to the running time instead of to a parameter of the solution quality. They then come up with an algorithm that allows to select algorithms more efficiently than the baseline based on the time cost. However, due to inherent inconsistency in applying bounding transformation to the time cost, the authors' approach results in a selection/configuration scheme that may prefer an algorithm that does not always terminate to an algorithm that terminates, even within reasonable time limits. This is just an extreme example.\n\nAs another intuition, assume there are two luxury car models, one costs USD1 million, the other USD2 million. The authors argue that USD1 million is such a huge sum that USD1 million or USD2 million do not differ much, and if you have USD1000000 but want the USD2000000 car, you **can just add some pocket change** to buy it. However, this will most probably not work. To get a USD2000000 car you still need twice amount of money you would pay for USD1000000 car, the amount of money you can buy **2 USD1000000 cars**.  However, the value you get from a USD2000000 car, whether for vanity or practicality, is not twice the value of USD1000000 car, it is likely to be the same or just a little bit higher (unless there is a club of USD2000000 car owners you want badly to be accepted to). \nHere, the car price is the cost (deliberation cost, time cost in algorithm selection) and the value is the intrinsic utility (how good the algorithm solution is). \n\nThe problem in the submission is in improper use of utility-based decision making to select computations. The theory is detailed in the works cited above. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time, unfortunately we have had a hard time understanding their objections. We have tried our best to address each of their concerns below. \n\n\"The approach is based on a notion of utility that is not consistent neither with the common practice of utility functions, nor with utility based decision making theory, nor with the notion of rationality.\" - The existence of the utility function we use was proved in Graham, et al. (2022), peer reviewed and published work. This utility function is based on the Von Neumann-Morgenstern (1947) axiomatization, which is an extremely well-established notion of \"rationality\" and has been a cornerstone of expected utility-based decision theory for three quarters of a century. We accept that there are other functions called \"utility functions\" (e.g., quasilinear) but these are not the functions we are considering. The axioms of Graham, et al. (2022) imply a certain class of utility function, and we assume a function of this form. Whether one finds those axioms to be consistent with their idea of \"rationality\" is a personal choice, but it is one that is very commonly made in other works and certainly leads to a sensible and consistent notion of utility.\n\n\"For decision making the utility must be bounded above, but it does not have to be bounded from below...\" - VNM utility functions are bounded from above and from below. \n\n\"The proposed notion of probability bounded between 0 and 1 is not just 'impractical', it leads to contradictions in rational decision making...\" - Probabilities, of course, are bounded between 0 and 1 by definition, so we are not sure what is meant by this comment. \n\n\"If, however, the notion of utility is made consistent with the decision theory, the proposed approach cannot be constructed, as far as I understand.\" - Given that our notion of utility *is* consistent with VNM-based decision theory, as shown in Graham et al. (2022), and that we *have* constructed the proposed approach, UP, we would suggest that the reviewer has indeed misunderstood something. We hope that the above explanations have helped to clarify this. \n\n\"Is this the net or the total utility?\" - The function $u(t)$ represents the utility gained from a single run that takes $t$ seconds to complete. \n"}, {"review_id": "Q73l7Ajdkc", "reviewer": "Reviewer_Sepd", "summary": "Theoretical guarantees for algorithm configuration (AC) when using a utilitarian objective function are proposed. This work differs from previous work in several ways, the first being that it focuses on the \"utilitarian\" objective function, which differs from the objective functions used in essentially all previous work. Second, the algorithm proposed provides anytime theoretical guarantees, meaning key parameters from previous approaches need not be input. A short experimental evaluation is performed on some well-known datasets for examining theoretical AC approaches to further drive home the results from the theorems.", "questions": "1. Relating to weakness #5, would it not be possible to craft a utility function close to, say, PAR10 or mean runtime for comparison purposes?\n\n2. In AC, mean runtime and PAR10 have become standard functions because (1) they are easy to compute and (2) they relatively closely reflect what algorithm users actually want. Long runtimes are indeed reduced by PAR10, even if the 10 is very arbitrary. If I do not have many timeouts, is the utility function still \"better\"? Are there some clear use cases that can be described?", "limitations": "The limitations are adequately discussed within the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The paper is well-organized and clearly written.\n\n2. The introduction of an anytime approach for AC with theoretical guarantees is a rather significant result. One of the key drawbacks of previous work is that the decision maker must choose values like epsilon and kappa that have little to no meaning to a non-expert. Integrating these values into the approach itself is a very welcome advancement that will have an impact on future work in this area.\n\n3. I am not sure whether the use of the utilitarian objective function is a strength or weakness, it has both aspects to it, so I include it here. On the one hand, the paper bases all of its work on the utilitarian objective function, which has not caught on with the empirical side of AC yet. Perhaps it will. At any rate, while it offers a way forward in terms of the proofs that was potentially unavailable before, it also somewhat strands this work away from the rest of the AC literature, making comparisons difficult and it somewhat hard to assess exactly where this work stands. I think overall the utilitarian objective function is a net positive, hence I place this comment under strengths.", "weaknesses": "1. I found the proofs both in the paper and in the supplementary material (although I admit I have not fully checked the supplementary material) somewhat... let's call it almost arrogant? I am sorry to use that word, but for less mathematically inclined readers, I think they will come away from this paper feeling rather stupid. I know I did.\n\n2. Regarding lemma 1, and potentially putting myself in the category of stupid reviewers, I do not understand how U_i <= U_i(kappa). I just do not understand how the uncapped expected utility could possibly be less than the capped utility. Clearly, they can in some cases be equal. But is this a typo? This is an example where an actual proof would lead to better understanding.\n\n3. I am including the dataset used as a weakness, because a better dataset is sorely needed for comparing theoretical approaches. I do note that the dataset used is better than nothing, and this point does not influence my score, as the authors practically have no choice other than to expend significant computational resources.\n\n4. I would have appreciated a more detailed explanation of utilitarian AC. The reader really cannot be expected to know about or have read the previous paper in detail to evaluate this one. In the future, this would serve as a refresher for those who have read the utilitarian paper and need to be reminded.\n\n5. The authors provide overall a good justification for not comparing to previous techniques, I do wonder, though, what the performance would be like if one modeled a utility function after the functions usually used -- would this not be possible?\n\n6. The authors left out the most recent theoretical approach, AC-Band, in the related work, but this is not important for my evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and address each of their concerns below. \n\nWeaknesses: \n\n1. We plead ignorance not arrogance. Being so familiar with the work it becomes hard to see it from the perspective of someone who is not, and easy to forget that what seems obvious now was not always so. We will endeavor to make explanations of the proofs more straightforward and clear. \n\n2. See 1. above. The capped expected utility $U_i(\\kappa)$ could be greater than the uncapped expected utility if there is any chance of a run exceeding the captime $\\kappa$. This is because the utility function $u$ is monotonically decreasing, and so if runtime exceeds $\\kappa$ we will have $u(\\kappa) \\ge u(runtime)$. Intuitively, the capped expected utility counts capped runs as having just completed at the captime, when really they would have taken longer if given the chance. Since we prefer short runs, this means that the capped expected utility looks better than the uncapped. Again, we will make this explanation more clear in the paper. \n\n3. We note only that there are actually three datasets (albeit from a single source) and that we are working on much more extensive experiments. \n\n4. We will include more explanation of utilitarian AC. Specifically, we can better explain what motivates the use of utility functions, what assumptions are needed to ensure the existence of utility functions, and what is implied about the form of those functions. \n\n5. Graham et al. (2022) have argued that many scoring functions used in practice are not consistent with a certain form of rational decision making. Some functions (such as PAR10) could be expressed as functions of this form if a consistent capping strategy is included. For example, if we cap all runs at 100 seconds and use a PAR10 scoring function then this is equivalent to what Graham et al. (2022) have called a linear utility function. It is linear from 0 to 100 seconds, with $u(0) = 1$ and  $u(100) = 1 - 100/1000$, and $u(t) = 0$ for $t$ greater than 100 seconds. (To derive this we apply a linear transformation to the PAR10 score: multiply the PAR10 score by -1 and add 1000, then divide this by 1000.) Certainly utility functions of this sort could be used. \n\n6. We will include an explanation of AC-Band. \n\nQuestions: \n\n1. See response to Weakness 5 above. Graham et al (2002) include discussion of the mean runtime objective, arguing that it is a poor formalization of algorithm users' preferences for various reasons. We do not repeat that full argument here, but some of the reasons include that it essentially assumes that we obtain no increase in happiness for solving our problem and that it doesn't coincide with actual behavior. If practitioners did care about average runtime, they would be unable to compare algorithms that occasionally fail to complete, since both averages would be infinite. \n\n2. We think of the utility function as something that exists *a priori* and reflects the user's preferences, rather than something that can be used to improve optimization performance (although it is nice that this can also be the case). As discussed in the response to Weakness 5 above, there are ways in which PAR10 (or more generally PARk) scoring functions are directly equivalent to some utility function $u(t)$ of the form we have assumed. But the converse is not always true. The idea behind using more general utility functions is that they can more accurately express the true preferences of users. As pointed out, the 10 is arbitrary. What's more, the point at which we choose to apply the x10 penalty (i.e., the captime) is also somewhat arbitrary. Referring back to the response to Weakness 5 above, maybe we want a x10 penalty at captime 100 seconds, but also a x2 penalty at captime 50 seconds. There is a $u(t)$ that can reflect this preference. With this interpretation, there is no sense in which one utility function is \"better\" than another, they simply reflect preferences.  "}, {"review_id": "4jSBzKifqe", "reviewer": "Reviewer_3kwZ", "summary": "The paper presents the first nontrivial procedure for configuring heuristic algorithms to  maximize the utility provided to their end users while also offering theoretical guarantees about performance. The paper shows how to avoid extremely long runs with low probability by putting limits on the runtime, assuming a bounded utility that is monotonically decreasing in runtime. The paper compares several ideas\n(1) the idea behind the runtime Oracle Procedure that eliminates algorithms progressively;\n(2) the idea of using a time limit whose value doubles until the optimal algorithm is identified (this idea is also used in restart procedures)\n(3) estimations of the mean time and the fraction of the distribution that has been explored\n\nThe results shows that the proposed procedure returns an optimal algorithm with a certain probability with a number of samples. It also characterizes the upper bound on the threshold. The results are with a logarithmic factor of optimality for the samples and provide a constant bound for the time limit. ", "questions": "no question", "limitations": "yes, the authors mention that the bounds are not tight yet.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- novel algorithms with performance guarantees\n- well-written and intuitive paper\n- automatic tuning of the time limit\n", "weaknesses": "- experimental results could be stronger and use a lot more problems", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time. We note only that we are looking at much more extensive experiments in future work. "}, {"review_id": "ZwL3WLMuDf", "reviewer": "Reviewer_Azei", "summary": "This paper studies the algorithm configuration problem with a monotone (invertible) utility function. We are given a set of $n$ algorithms, and instances are drawn from a distribution, $\\mathcal{D}$. We can observe samples of running times of $i\\in [n]$ on $j\\sim\\mathcal{D}$ capped by $\\kappa>0$, and we aim to find an $\\epsilon$-optimal algorithm from $[n]$. The characteristic of the setting studied in this paper is that the cost paid for each sample depends on the time we spent collecting it and that only capped runtime can be observed. \n\nThe authors first discuss lower bounds on the number of samples and captime required for identifying an $\\epsilon$-optimal algorithm (Sections 3.1 and 3.2). The result on captime was constructively proved via a prover--skeptic procedure. The authors then give a naive configuration method (Naive), which requires specifying $\\epsilon$. This requirement is impractical since a slight change in $\\epsilon$ may largely affect appropriate $m$ and $\\kappa$ values (this is also confirmed empirically in Section 4). Section 3.4 addresses this problem and presents the Utilitarian Procrastination method (UP), an anytime algorithm that starts from the smallest captime and increases it if necessary. Experiments in Section 4 demonstrate the advantage of UP over Naive. ", "questions": "1. Although algorithm configuration with bounded utility functions is new, I have not felt it is technically very different from the previous setting (Kleinberg et al. 2017, 2019), particularly because monotone and invertible utility functions could simplify technical treatment. I would appreciate it if the authors could describe the main technical novelty in the utilitarian setting. \n2. Are there natural examples of utility functions used in practice?\n3. While $u$ is assumed to be invertible in Section 2, the function used in Section 4 (i.e., $u(t) = 10/t$ for $t>10$ and $u(t) = 0$ o.w.) is not on $\\\\{t: u(t)=0 \\\\}$. Is it possible to relax the assumption to deal with such non-invertible functions? (As far as I see, the invertibility on $\\\\{t: u(t)>0\\\\}$ seems sufficient). ", "limitations": "While not explicitly discussed, the range to which the results apply appears to be clear.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. The paper studies an interesting direction of algorithm configuration based on the utility-theoretic approach of (Graham et al. 2022).\n2. The setup and algorithms are well described. \n3. The technical motivation of UP is described clearly. The results are fairly strong, considering the lower bounds. ", "weaknesses": "1. The technical novelty appears to be somewhat marginal, given that the idea of procrastination is already developed.\n2. The utilitarian setting, albeit interesting, looks somewhat artificial. It is not easy to imagine realistic utility functions that naturally appear in practice. \n3. The lower bound in Section 3.2 seems to be considering too pessimistic inputs, which in turn makes it easier to obtain nearly tight upper bounds in the subsequent sections (although similar tightness results are often appreciated). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and address each of their concerns below. \n\nWeaknesses:\n\n1. We see the strength of our procedure (UP) as being in its anytime-ness rather than in its use of procrastination. In our context, \"procrastination\" really just means capping runs at small captimes before trying again later with larger ones. This is essentially necessary to make any theoretical guarantees, since the alternative would be to let some runs run for an unbounded amount of time. See Question 1 below for more discussion on technical novelty. \n\n2. See our response to Question 2 below. \n\n3. We wanted to state a result that parallels the classic sample complexity result described in Section 3.1. Considering only sample complexity, the worst-case number of samples required grows with $1/\\epsilon^2$, but the tighter \"input-dependent\" bound allows a number of samples that grows with $1/\\Delta^2$ for suboptimal algorithms, where $\\Delta$ is the sub-optimality gap. When algorithms are very suboptimal, and $\\Delta \\gg \\epsilon$, these bounds will be very different. Our result in Section 3.2 is also \"input-dependent\" in that it scales with $\\Delta$ as well, but also with $F(t)$, the algorithm's runtime CDF. If $\\Delta$ is very large, the captime $\\kappa$ required to satisfy Lemma 7 will be smaller, since the inequality will be easier to satisfy. Similarly, for runtime distributions that are likely to complete before the captime $\\kappa$, the term $1-F(\\kappa)$ will be very small and will tend to be less than $\\Delta + \\epsilon$ no matter how small $\\Delta$ is. In this way, the captime bound described in Section 3.2 is analogous to the well-established sample-complexity bound described in Section 3.1. \n\n\n\nQuestions: \n\n1. We see our novel technical contributions as including the following:\n\n    (1). We present a configuration procedure (UP) with performance guarantees that is anytime in the optimality guarantee it makes with respect to both the number of samples $m$ and the captime $\\kappa$. Growing $m$ and $\\kappa$ simultaneously in a way that does not cause the configuration procedure to incur a large runtime cost is not straightforward. UP balances the growth of these in a way that ensures it will eventually find the optimal algorithm by gradually ruling out all suboptimal ones, a guarantee that existing procedures like those in Kleinberg et al. (2017, 2019) do not (can not) make. \n\n    (2). We show an input-dependent lower bound on the captime required by any configuration procedure (Lemma 7, Section 3.2). To our knowledge this has not been shown elsewhere and is a useful contribution as it provides a non-trivial performance target for actual configuration procedures and a benchmark against which to compare them. While the basic idea behind the proof of Lemma 7 is simple (we do not know what things will look like beyond the captime $\\kappa_i$; the algorithm could finish immediately after, or it could run forever), the proof relies on the construction of a counterexample that is non-obvious in a subtle way: it holds for any value of $F_i(\\kappa_i)$ and so it does not rely on the skeptic being fooled only after having seen a particular value of $F_i(\\kappa_i)$ (i.e., it holds no matter how many uncapped runs the skeptic sees).\n\n    (3). We use a cleaner and more intuitive notion of optimality than runtime-based works such as Kleinberg et al. (2017, 2019). The theoretical guarantees of Kleinberg et al. (2017, 2019) and other similar procedures need to be defined with respect to an additional parameter, which our work is able to eliminate. The guarantee we make is of the form \"here is an algorithm whose performance is within $\\epsilon$ of the optimal algorithm\", while the guarantee made in previous works is of the form \"here is an algorithm whose performance is within $\\epsilon$ of the optimal algorithm *if we ignore the $\\delta$-fraction of each algorithm's longest runs*\". \n\n\n2. Graham et al. (2022) give some concrete examples of utility functions that could be used in practice and give arguments about how practitioners might go about identifying utility functions that describe their own preferences. If we have clear costs of compute, we know something about how much time we will have to run the algorithm, and we can specify a value we obtain from solutions that the algorithm provides, then we can specify a definite utility function. This will essentially be a linear transformation of the expected profit that we earn. Another natural utility function used in practice is the fraction of runs completed before a certain captime. Beyond this, while utility functions are not yet commonly seen in the AC/algorithmics community, they are a ubiquitous feature in economics and decision theory. It is well accepted that individuals prefer financial outcomes according to their utility, not their raw monetary value, and Graham et al. (2022) have argued that the same should be so of algorithms and their runtimes. Though specifying them in practice may sometimes be challenging, we believe it is clear that optimizing utility functions rather than raw runtimes is the right thing to do in a fundamental way. \n\n\n3. The function $u(t)$ does not really need to be invertible anywhere. Defining $u^{-1}(x) = \\inf ( t : u(t) \\le x ) $ is really what is needed. Since $u(t)$ must be monotonically decreasing this intuitively just means that $u^{-1}(x)$ is the first (i.e., smallest) runtime where our utility falls below a given level $x$. We will change this in the paper.\n"}]

Author rebuttal:

Meta-review: Discounting the score of Reviewer Qzq9 (whose remarks were largely inconsistent with prior established work across fields), the other reviewers all liked this work and felt it was a valuable contribution to the field of algorithmic configuration.
Decision: Accept (poster)