Put CASH on Bandits: A Max K-Armed Problem for Automated Machine Learning

Thanks a lot for the detailed review and the raised points. We particularly appreciate your highlighting the quality of explanation and clarity.

“Could the authors clarify how the tabular datasets used in the empirical distribution analysis were selected? For example, were these chosen to be representative of a specific class of AutoML problems, or were they selected based on convenience or availability?”

We used several well-established and widely used benchmark sets that were developed to compare HPO methods. Each benchmark contained different datasets, tasks, and search spaces, to ensure our empirical distribution analysis was not limited to a single source or problem type.

• For example, TabRepo is one of the largest tabular benchmarks, including 200 classification and regression datasets and evaluating over 1,310 models and configurations. A full evaluation of TabRepo could require up to 4,066,576 CPU hours.

• For TabRepoRaw, where we ran Bayesian optimization directly over TabRepo’s search space, we selected the D244_F3_C1530_30 subset due to cost limitations. This subset includes 30 datasets that were specifically chosen by the TabRepo authors to represent a diverse yet computationally feasible set of tasks. We spent over 10,000 CPU hours to collect this benchmark.

• YaHPOgym is a well-known and widely used surrogate benchmark for HPO in the tabular domain, containing 103 datasets from the OpenML collection.

• We also added the Reshuffling benchmark which includes 10 datasets with and HEBO as the HPO method. We included this task to diversify the HPO methods in our study.

• Furthermore, in Appendix E.5, we used Supernet selection in the Few-Shot Neural Architecture Search benchmark (containing CIFAR-10, CIFAR-100, and ImageNet16-120 datasets) to show that our analysis and algorithm can work beyond CASH tasks.

“While the paper frames MaxUCB as a novel contribution, the core idea using a UCB-style bandit strategy with an exploration bonus adapted to bounded reward distributions can be seen as a relatively straightforward extension of standard UCB principles.”

The main novelty in MaxUCB is a distribution-adapted exploration bonus (which is a distinct approach compared to standard UCB literature). Our main contribution, and what makes the method work ultimately, is to identify a semi-parametric modelling of the distribution of the maxima we aim to optimize.

The main difficulty is getting the details right in the modelling assumptions. There may be alternative, smarter, and more complex algorithmic designs for this problem, but isn’t it remarkable that a simple algorithm achieves such good empirical performance on such a widely studied problem?

Thanks a lot for the detailed positive assessment of our work. We are happy to comment on the pointed-out suggestions for improvement.

“Regarding the near-stationarity assumption,”

As noted in our response to Reviewer 7Zgt, we acknowledge that this simplifying assumption may not strictly hold, but it provides a solid foundation for developing a strong algorithm. In classic bandits, non-stationarity is typically addressed by combining algorithms with i.i.d. assumptions with techniques such as sliding windows, discounting, or change-point detection, which have shown promising results in various applications. Since the max k-armed bandit has a different regret definition, it may require specialized techniques. Designing such techniques is a promising research direction.

“The paper does not provide a lower bound on regret,”

Thanks a lot for raising this point. The notion of optimality for max K-armed bandits is unclear, as Nishihara et al. (2016) [1] pointed out. Namely, as opposed to classical bandit problems, the best arm, and thus, the optimal policy, depends on the time horizon, which is here our compute budget. They argue that the existence of no-regret algorithms fully depends on the distributional assumptions and show impossibility results in the Bernoulli case. A notion of optimality, if it exists, would have to be fully distribution-dependent, but for which distribution family? Our study focuses on CASH and proposes a useful set of assumptions on useful distributions, but we do not claim, nor aim to be optimal, since this notion remains elusive for this problem. Bounded extreme bandits are not extensively studied, potentially because use cases were lacking, but our work may open avenues for more fundamental research questions. We will clarify it in the paper.

References

1. Nishihara et al.: "No regret bound for extreme bandits." Artificial Intelligence and Statistics. PMLR, 2016.

Thanks a lot for the detailed review and the raised points.

“1. The regret definition in Eq. (4) is unusual in the bandit literature.”

We very much appreciate this question and are happy to clarify. Indeed, our regret definition (known as extreme regret [1]) is unusual in the general bandit literature, but it is central in HPO literature.

Jamieson et al. (2015) [2] already state that max-value objectives should be the right ones for HPO, but rightfully state that they are “less well behaved”. Further, Nishihara et al. (2019) [3] stated that the Max K-armed Bandit (Extreme Bandits) should be the valid framework for HPO but also proved that without appropriate assumptions, it may be infeasible (lower bounds). More recently, Hu et al. (2021) [4] mentioned that the classic UCB algorithm is inappropriate for the CASH problem because of the regret definition. These very challenges motivated our study. A similar discussion can be found in lines 40-50, but we will extend it.

“2. Can the proposed method and theoretical guarantees be applied to the scenario when the number of possible hyperparameter choices (arms) is large?”

We apologize, but we are confused by this question. To clarify: In our setup, an arm is an ML model class, and “pulling an arm” corresponds to running HPO on the chosen ML model class (see Figure 1 and lines 82-84). So, arms are not hyperparameter choices.

MaxUCB would not be directly applicable to this different setup where an arm corresponds to a hyperparameter configuration (especially since our regret bound in Corollary 4.3 grows linearly with the number of arms K). Other Bandit methods, like Hyperband, are designed and known to work well for this different setting with only one model class.

“3. But these properties may not always hold in realistic hyperparameter optimization applications.”

Our data analysis covers several benchmarks, with 300+ datasets representing realistic hyperparameter optimization tasks (see response to Reviewer PkJH). Indeed, different problems may exist, but one important contribution of our paper is to consider the broader set of assumptions for the most realistic space of HPO/CASH problems.

We derived theoretical guarantees under quite general semi-parametric assumptions, as stated in Theorem 4.2 and the accompanying discussion. Our assumptions allow for a wide range of reward distributions (we discuss typical distribution types in Appendix C.2). If a problem would have a very small L constant (in contrast to all the CASH problems we studied), then the performance of MaxUCB would be worse, as predicted by our theory.

“4...So the regret bound in Corollary 4.3 may not be achieved by the proposed algorithm.”

Yes, we completely agree. The result of Corollary 4.3 shows how to choose optimal $\alpha$ when these values are known or can be estimated in advance via meta-learning. In the discussion, we also mention that adapting $\alpha$ by estimating these parameters on the fly is possible.

“5..The writing of this paper needs to be improved.”

Thanks a lot for pointing this out. We will unify terminology in the revision:

• $L_i$ refers to the value of $L$ from Lemma 3.3 for arm $i$, and $i^*$ denotes the optimal arm (see lines 224-225).
• We refer to “combined search” as a single-level approach and with “two-level approach” to Bandit-based methods that address the bi-level optimization problem in Eq(2). See also our response to Reviewer 7Zgt.

References

1. Carpentier, Alexandra, and Michal Valko. "Extreme bandits." Advances in Neural Information Processing Systems 27 (2014).
2. Jamieson, Kevin, and Ameet Talwalkar. "Non-stochastic best arm identification and hyperparameter optimization." Artificial intelligence and statistics. PMLR, 2016.
3. Nishihara, Robert, David Lopez-Paz, and Léon Bottou. "No regret bound for extreme bandits." Artificial Intelligence and Statistics. PMLR, 2016.
4. Hu, Yi-Qi, et al. "Cascaded algorithm selection with extreme-region UCB bandit." IEEE Transactions on Pattern Analysis and Machine Intelligence 44.10 (2021): 6782-6794.

Thanks a lot for the detailed review and acknowledging our contributions. We will fix all minor comments in a revised version and address your questions in the following.

“From a purely algorithmic perspective, the originality of the proposed algorithm is somewhat unclear.”

The UCB principle is central to dealing with decision-making under uncertainty. We agree it is not original in this sense. However, as Reviewer Vu3f noted, the regret definition in Eq. (4), which corresponds to the Max K-armed Bandit problem, differs from the common regret used in classical bandit settings. The main challenge lies in getting the details right in the modelling assumptions. Our main contribution, and what makes the method work ultimately, is to identify a semi-parametric model of the distribution of the maxima we aim to optimize. We discuss this in more detail in our response to Reviewer PkJH.

“a) … distinction between "combined algorithm" and "individual search-based algorithm”

With the “combined search” approach, we refer to an optimization method that searches the entire space of all K models’ hyperparameters, while an “individual search-based algorithm” only searches hyperparameters for a single model (and without budget allocation, needs to be conducted K times). The main challenge for “combined search” is efficiently searching the entire high-dimensional and heterogeneous combination of K search spaces. The main challenge for “individual search-based algorithms” is to allocate the budget between the K runs by an additional optimizer.

As you correctly pointed out, the “two-level” and “single-level” terminology corresponds to the “individual” (i.e., decomposed CASH) and “combined search” approaches introduced earlier. We agree that terminology might be confusing, but we wanted to highlight the combined term in CASH; we will revise and unify the terminology.

“b) difference between Eq. (1) and Eq. (2)?...”

Eq.(1) and Eq.(2) are equivalent and describe the same optimization problem (and thus also share the same solution): finding the best-performing configuration of a model. In Eq. (2), we highlight the structure of CASH problems and that we can decompose the problem into a bi-level optimization problem.

“c) agnostic to the inner HPO method ...”

Yes, absolutely. It’s a strength of our method that it would also allow using a different HPO method (e.g., random search or Bayesian optimization) per model class.

“e) … the characteristics of the tasks and datasets used in the empirical analysis in Section 3 ...”

Yes, we agree. Tables D.1, D.2, and D.3 provide detailed information about the tasks, and Figures D.7 and D.8 report performance per task. Each task corresponds to a different dataset. For YaHPOgym, the task is classification, with accuracy as the evaluation metric.

For Reshuffling, the task is binary classification with AUC as the metric. In TabRepo and TabRepoRaw, the tasks include regression, multiclass classification, and binary classification, with RMSE, log loss, and AUC used as the respective metrics (we also discuss this in our response to reviewer PkJH)

In general, linking MaxUCB's performance to task characteristics or using meta-learning to exploit similarities across tasks would be promising future directions. However, here, we first focused on designing and analysing a principled algorithm that works empirically well on average.

“f) choice of alpha?”

Corollary 4.3 theoretically gives the optimal value for $\alpha$ when characteristics of the datasets and the budget are known. We find that a default of $\alpha=0.5$ works empirically well (see Appendix D.4). Indeed, we can not provide a general rule for choosing the optimal alpha as it is a problem-dependent quantity. Similar to our answer to e), meta-learning the optimal alpha based on task characteristics could be an empirical approach to mitigate this issue.

“g) In Assumption 3.2, the random variable is assumed to be i.i.d., but line 86 suggests that the reward process is not i.i.d. Could you clarify?”

You’re correct. In Assumption 3.2, we assume that our random variable is i.i.d. In practice, our rewards are not strictly i.i.d. (unless we use random search), and we know that this assumption might not hold in practice (as stated in line 86). However, our data analysis shows that the distribution shift during HPO is small in most cases (line 146), and our empirical results confirm that we can model this process reasonably well to perform well in practice. This simplifying assumption is key to designing a simple and effective algorithm.