Utilitarian Algorithm Configuration for Infinite Parameter Spaces

"The impact of the extension to continuous space is unclear. I would suggest to compare COUP with OUP + fixed discretization of continuous space."

• We see the benefit of the extension to continuous space as being the seamless applicability, in an anytime fashion, of the procedure to continuous and infinite parameter spaces, which is the reality for most algorithms. The alternative would be to sample a finite set of configurations and run OUP on this set. But how big should this set be? And what do we do if OUP finishes and we decide this set was not big enough? The only option would be to sample more configurations and then rerun OUP or, better yet, have OUP pick up where it left off, adjusting the probabilistic bounds accordingly, which is precisely what COUP does. So the real benefit of COUP over OUP is that it does this sampling internally and, importantly, does it in an anytime fashion, meaning it samples more and more configurations as time goes on. An investigation of the effect of discretization/sampling might be interesting but is not possible with our current pre-computed datasets.

"The continuous structure (similarities among neighbor parameters) is not utilized in COUP. So, C in COUP does not describe its nature accurately."

• We definitely don't want our procedure's name to be misleading. In response to your review we had a long discussion about this issue and about other candidate names. In the end, we couldn't think of a better alternative, particularly given our desire to use a name that reflects the tight connection with OUP. It seems to us that the "C" for "Continuous" does make sense because COUP can handle parameters with continuous domains (i.e., continuous in the sense of "continuous random variable") by taking an unbounded number of samples from these domains. In contrast, OUP (and UP, etc.) cannot: the set of samples they consider must be chosen in advance. We have revised the paper to make this justification for the name clearer and to forestall any potential misunderstanding.

"In Lemma 2, don’t you need 'with probability 1 - delta'"?

• Lemma 1 says that an execution is "clean" with probability $1 - \delta$, and Lemma 2 says that if the execution is clean, then the bounds hold.

Why not using log scale for the vertical axes of Figure 1?

• The updated pdf now shows total time on a log scale.

We thank the reviewer for their time and effort.

"The presentation of Section 3 could be improved slightly; introducing the notation before presenting Algorithm 1..."

• We have adjusted the layout in the updated pdf so that definitions come before the algorithm description.

"Anonymous repo link seems to be missing?"

• Our intention was to release the code at time of publication; the "anonymous repo link" was just a placeholder, but we can release the code anonymously beforehand if reviewers find it important.

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

• This just means that at around 700 CPU days OUP was able to prove a much better epsilon (.1) than it was able to prove before (e.g., epsilon of about .2 at 500 CPU days). This may be because OUP started seeing more instances that where more representative or it could be the result of a captime doubling event revealing something about the runtime CDFs that was not observed before.

"... it’s unclear to me that COUP/OUP actually outperforms [Hyperband]. Is there a reason to expect COUP/OUP would perform better, or is there something I might be overlooking?"

• We think Hyperband is generally a good algorithm and indeed it does beat OUP/COUP on some datasets with some parameter settings. But on others it is consistently worse (e.g., the minisat dataset). Hyperband is not anytime, so once we've committed to running it and we get an answer we cannot work to improve that answer without completely re-running it with more refined parameters. OUP/COUP work continually to improve the answer they give, until the user is satisfied, and in all cases they eventually find a configuration that is at least as good as the one found by Hyperband. Additionally, OUP/COUP make guarantees about the near-optimality of the returned configuration, which Hyperband is unable to do.

"... 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."

• Stronger guarantees could indeed be made with stronger assumptions about the space of configurations. Generally in algorithm configuration, we have little idea of what structure this space has. We do not, in general, expect it to be Lipschitz continuous. Often we find that small changes to a parameter within a given range have little or no effect on performance, but if the value is pushed just outside of this range, performance changes drastically. There is a body of work showing that the parameter space is often divided into regions where performance is relatively stable, separated from each other by large jumps in performance (see, e.g., Balcan et al., (2021)), and for certain problems where this structure is known, it can indeed be taken advantage of.

"I think, it would have reasonable to test the algorithm against algorithms that minimize the running time..."

• We have now added this comparison to Figure 5 (second row) of the updated pdf. The utility function used coincides with (capped) average runtime.

"The start of the paper is a bit of a slog. It would have been nice to get to the point faster."

• We have tried to tighten up the first two sections and we'll give particular attention to these when making our final pass.

"notation for Algorithm 1 is introduced after the algorithm is explained"

• We have now adjusted the layout so that definitions come before the algorithm and its description.

"i is shadowed..."

• Fixed, thanks.

"brown/purple/green combination..."

• We have changed Figure 1 significantly in the updated pdf. The procedures should now be more easily distinguishable based on their color and marker types.

"In Figure 3, the green line for OUP goes backwards..."

• This is to be expected sometimes and essentially has to do with the order in which the configurations are sampled. At the end of each phase COUP has proved epsilon-optimality with respect to a particular set of configurations. We give these to OUP and ask it to prove optimality for the same epsilon. What has happened here is that a good configuration was sampled in phase 5 by COUP. When we then give this set of configurations to OUP and ask it to prove epsilon-optimality, it is able to do so more quickly than it did in phase 4 because of the presence of this good configuration. We have added an explanation of this in the updated pdf.

"The symbols in Figure 5..."

• We have changed Figure 5 significantly in the updated pdf.

"COUP samples new configurations at random... Is there no way of sampling configurations that might actually be good while maintaining guarantees?..."

• Indeed, we do believe this is a very promising direction for future work. To make the theoretical guarantee we do requires independent randomly-sampled configurations. However, in addition to this, some configurations may be sampled according to a predictive model. This is the approach taken by some existing heuristic algorithm configuration procedures (e.g. SMAC). For example, half of the configurations may come from random sampling and half from the predictions of a random forest which is trained along the way. The random forest will tend to focus in on good areas of the space, and the quantile guarantee can still be made, while the total runtime increases by at most a factor of 2.

"The presentation of this paper is very hard to follow."

• We hope that the changes we have made help with the overall presentation.

"What is delta in OUP?..."

• Delta is the failure probability. We have specified this more clearly in OUP's inputs now.