Cascaded Algorithm-Selection and Hyper-Parameter Optimization with Extreme-Region Upper Confidence Bound Bandit

1 Introduction

Algorithm selection and hyper-parameter optimization are core parts of automatic machine learning (AutoML). Previously, AutoML approaches often define the search space as the algorithm selection space [Brazdil et al., 2003; Adankon and Cheriet, 2009; Biem, 2003], hyper-parameter space [Hu et al., 2018; Hu et al., 2019], or the joint of the both spaces (CASH problem) [Feurer et al., 2015; Thornton et al., 2013]. While the joint space allows a more thorough search that could cover potentially better configurations, the huge space is a barrier to effective search in limited time. Moreover, the joint space can be quite redundant when considering only one of the algorithms, since the hyper-parameters of the other algorithms are irrelevant. Therefore, the joint space contains redundancy or even can be misleading.

∗This work is supported by the National Key R&D Program of China (2017YFB1001903), NSFC (61876077), Jiangsu SF (BK20170013), and Collaborative Innovation Center of Novel Software Technology and Industrialization. Yang Yu is the corresponding author.

The cascaded algorithm selection can have levels [Jamieson and Talwalkar, 2016]. The first level is on the hyper-parameter optimization. It only needs to focus on the selected algorithm, but not the hyper-parameters of all algorithms. The second level is on the algorithm selection. However, previous methods in this kind commonly carry out a full hyper-parameter optimization on the candidate algorithms, making the slow and expensive algorithm evaluations.

In this paper, we propose a cascaded algorithm selection approach to avoid a full-space hyper-parameter optimization. The hyper-parameter optimization usually employs some stepping search methods, which can be paused after every search step, and can also be resumed. The selection receives feedback and allocates the next search step to one of the algorithms. Thus, the cascaded algorithm selection is naturally to be modeled as a multi-armed bandit problem [Auer et al., 2002]. However, most of the classical bandits maximize the average feedbacks. In the AutoML, however, only the best feedback matters. A variant of the bandit, the extreme bandit [Carpentier and Valko, 2014], can model this situation, which tries to identify the arm with the maximize (or equivalently minimize) feedback value. However, as the extreme bandit follows the extreme distribution, it is not only unstable but often require to known the distribution type, making the extreme bandit approach unpractical.

In this paper, we propose the extreme-region UCB bandit (ER-UCB), which focuses on the extreme region of the feedback distributions. Unlike the extreme bandit, ER-UCB considers a region instead of the extreme point, which can lead to a better mathematical condition. Moreover, in machine learning where the test data is commonly different from the train data, the extreme region can be more robust for generalization. With K-arms and n trials, our analysis proves that ERUCB has the O(K lnn) regret upper bound, which has the same order with the classical UCB strategy. The experiments on synthetic and real AutoML tasks reveal that the ER-UCB can find the best algorithm precisely, and exploit it with the majority of the trial budget.

The rest sections present background & related works, extreme-region UCB bandit, experiments, and conclusion.

2 Background &RelatedWorks

We consider the algorithm selection and hyper-parameter optimization on classification tasks. Let Dtrain and Dtest denote the training and testing datasets. Let C = {C1, C2, . . . , CK} denote the algorithm set with K candidates. For Ci ∈ C, δi ∈ ∆i denotes a hyper-parameter setting, where ∆i is the hyper-parameter space of Ci. Let f (·) denote a performance criterion for a configuration C δi i , e.g., accuracy, AUC score, etc. The AutoML problem can be formulated as follows:

where Dvalid j ∈ Dtrain and Dtrain j = Dtrain - Dvalid j . It is also concludes the CASH problem formulation [Feurer et al., 2015].

Because of the non-convex, non-continuous and nondifferentiable properties, derivative-free optimization [Yu et al., 2016; Hu et al., 2017] is usually applied to solve it. For example, a tree-structure based Bayesian optimization (SMAC) [Hutter et al., 2011] is employed on AutoWEKA [Thornton et al., 2013] and AutoSKLEARN [Feurer et al., 2015], the popular open-source AutoML tools. Derivative-free optimization explores search space by sampling and evaluating. But the high time-cost restrains the total number of evaluations on AutoML. With the limited trials, the performance of derivative-free optimization is very sensitive to search space. However, in above formulation, the search space ∆ = ∆1 × ∆2, ×, . . . , ×∆K. Obviously, ∆ is redundant, because the best configuration is only relevant to the hyper-parameter space of the best algorithm.

Hence, we consider an easier formulation, i.e., optimizing hyper-parameters of algorithms separately:

The hyper-parameter processes can be seen as arms. The algorithm selection level is a multi-armed bandit problem. The bandit is a classical formulation of the resource allocation problem. In [Fel´ıcio et al., 2017], the authors formulated the cold-start user recommendation as a multi-armed bandit problem, which user information was unavailable at the beginning. The feedbacks of users has to be obtained by trials. In this situation, the bandit concerns more about the average feedback of arms. In [Cicirello and Smith, 2005], the authors proposed the max K-armed bandit, which focused on the maximum feedback of trials. But it assumed that the reward distribution was a Gaussian distribution, and it was designed for the heuristic search, in which more than one arms can be selected at a trial step.

In this paper, we customize the extreme-region UCB (ERUCB) bandit for AutoML problems.

3 Extreme-Region UCB Bandit

In this section, we present details of the ER-UCB: the bandit formulation for AutoML, the deduction of the ER-UCB strategy and the theoretical analysis on the ER-UCB strategy.

3.1 Bandit Formulation for AutoML

In the classical multi-armed bandit, feedbacks of an arm obey an underlying distribution. In this paper, we employ the random search on the hyper-parameter optimization. A trial in a model Ci is uniformly sampling hyper-parameters from ∆i, and its performance is the feedback of this trial. Thus, Xi ∼ Di (µXi , σ2Xi ), where Xi denote a feedback of a trial on Ci, and Di (µXi , σ2Xi ) is the underlying performance distribution of Ci. Because of the random search, Di is fixed. With K algorithm candidates, let D = {D1,D2, . . . ,DK} denote the performance distribution set. The K-armed bandit formulation for AutoML is: at the t-th trial, the CIt is selected from K algorithm candidates, and get a feedback XIt independently from DIt .

3.2 Deduction

In AutoML tasks, the selected algorithm is required to have maximum performances. For this requirement, we present the extreme-region target for the proposed bandit. Then, we show the deduction details of extreme-region UCB strategy.

Extreme-Region Target

The target of the hyper-parameter optimization is to find the hyper-parameters which have the maximum performance. In the bandit, with a fixed ϵ, we want the probability Pr [Xi ≥ µXi + ϵ] as large as possible. With the Chebyshev

In other words, with the same fixed probability upper bound θ, the best arm selection is:

With the given µXi and σXi , the ground-truth selection strategy is (4). But, when facing the unknown distributions, we have to estimate the expectation and variance based on the observations. With the Markov inequality, it is easy to relate the expectation µXi with its estimation. But for variance, it is hard to find the relationship. With the variance definition:

Because E [X2 i ] is the expectation of the random variable X2 i . The Markov inequality can be applied to it easily. And E [X2 i ] can partly represent σ2Xi according to (5). Thus, we try to replace σXi with √E [X2 i ]:

Comparing with (4), (6) magnifies the effect of expectation item on selection strategy. To tackle this issue, we introduce a hyper-parameter β ≥ 0, and construct a new random variable Yi = Xi -β. Furthermore, let µYi = E [Yi], Zi = (Xi - β)2 and µZi = E [Zi]. Thus, the extreme-region target is:

We prove that it can reduce the effect of expectation on algorithm selection by introducing into β:

Proof. According to definitions of Xi, Yi and Zi,

Comparing with (4), because of β ≥ 0, the item of expectation is reduced, but the item of variance stays the same. It concludes the proof.

Extreme-Region UCB Strategy

We apply the upper confidence bound (UCB) strategy on the extreme-region target. In this paper, we assume that the random variables satisfy the following moment condition. There exists a convex function ψ on the reals, for all λ ≤ 0,

If we let X ∈ [0, 1] and ψ (λ) = λ2 8 , (9) is known as Hoeffding's lemma. We apply this assumption to construct an upper bound for the estimated expectations at some fixed confidence level. Let ψ∗ denote the Legendre-Fenchel transform of ψ. With s observations of Xi, let ˆµsYi = 1s ∑st=1 Yi,t and ˆµsZi = 1s ∑st=1 Zi,t denote the estimated expectations of Yi and Zi. Only for Yi with a fixed ϵYi , using the Markov inequality:

The same deduction for Zi, and f (x) = √x is a monotonically increasing function:

Because √a+ b ≤ √a + √b, and let ϵYi = ϵZi = ϵ. With the union bound, we combine Yi and Zi as follows:

Let 2e-sψ∗ (ϵ) = δ. With the probability at least 1 - δ,

Algorithm 1 Extreme-region UCB Bandit

Input:

inp {C1, C2, . . . , CK}: K model candidates;

inp {∆1,∆2, . . . ,∆K}: hyper-parameter spaces of models; inp γ, θ, β: hyper-parameters; inp n: trial budget;

inp Dtrain : train dataset of task;

inp SampleU : uniform sample sub-procedure; inp Evaluate: evaluation sub-procedure.

Procedure:

• 1: for t = 1 to K do
• 2: Xt = Evaluate (Ct, SampleU (∆t) ,Dtrain )
• 3: ˆµYt =Xt -β, ˆµZt = (Xt -β)2 , Tt = 1
• 4: end for
• 5: for t =K +1 to n do
• 6: get index It according to (17)
• 7: XIt = Evaluate (CIt , SampleU (∆It ) ,Dtrain )
• 8: ˆµYIt = TIt (t)ˆµYIt +XIt -β TIt (t)+1
• 9: ˆµZIt = TIt (t)ˆµZIt +(XIt -β)2 TIt (t)+1
• 10: TIt = TIt +1
• 11: end for
• 12: return the hyper-parameters with the best X.

Within total s trials, let Ti (s) = ∑st=1 1It=i denote the number that the i-th arm is selected, and 2δ = tα. (α, ψ)-ER-UCB strategy is:

Ωi and Ψi are the exploitation and exploration items. With Hoeffding's lemma, taking ψ (λ) = λ2 8 , then, ψ∗ (ϵ) = 2ϵ2 . And let α = 4. The exploration can be re-written as:

Thus, the Hoeffding's ER-UCB strategy is:

Because Xi ∈ [0, 1] on AutoML, the exploitation item is often much smaller than the exploration item. To further exploration and exploitation trade-off, we introduce a hyperparameter γ. The practical Hoeffding's ER-UCB strategy is:

The cascaded algorithm selection and hyper-parameter optimization with ER-UCB bandit is presented at Algorithm 1. Line 2 and 7 are the procedures of uniformly sampling hyperparameters for the selected algorithm and obtaining the feedbacks. Line 1 to 4 are the initialization steps. In the main loop (line 5 to 10), the algorithm is selected by the ER-UCB strategy (line 6). Line 7 to 9 are the procedures for updating the exploitation item for the selected algorithm.

We have to discuss the hyper-parameters, i.e., θ, γ and β for the ER-UCB bandit. θ is employed to control the space size of the extreme region. It is usually a small real number, e.g., 0.1 or 0.01. γ is the exploration-and-exploitation tradeoff hyper-parameter. In AutoML tasks, γ is used to magnify the exploitation item. Thus, it is usually a big number such as 10 or 20. β is applied to reduce the impact of expectation item in the selection strategy. It should be tuned according to tasks. In experiments, we will investigate them empirically.

3.3 Theoretical Analysis

We present the analysis of the upper bound for (α, ψ)- ER-UCB strategy (14) and the Hoeffding's ER-UCB strategy (15) on the extreme-region regret. For the arbitrary arm i and a fixed ρ, we define Pr [Xi ≥ ρ] = pi. Thus, p∗ = argmaxi∈{1,2,...,K} pi. According to (7), let i∗ = argmaxi∈{1,2,...,K} µYi + √ 1 θ µZi , thus µ∗Y + √ 1 θ µ∗Z = µYi∗ +√ 1 θ µZi∗ , and Γi = µ∗Y +√ 1 θ µ∗Z -µYi -√ 1 θ µZi . We assume p∗ = pi∗ by choosing an appropriate β. The extremeregion regret is the Definition 1.

Definition 1 (Extreme-region regret). At n-th trial, event A is the number of times that Xi∗ ≥ ρ occurs, and event B is the number of times that XIt ≥ ρ occurs with a given strategy. The extreme-region regret is:

Introducing Ti (s) and Θi = p∗ - pi, The extreme-region regret can be re-written as:

We can prove the following simple upper regret bound for (α, ψ)-ER-UCB strategy:

Theorem 1 (Regret of (α, ψ)-ER-UCB). Assume the feedback distribution of arbitrary arm satisfy (9). With α > 2, (α, ψ)-ER-UCB satisfies:

Due to the limitation of paper length, we present the proof details in our supplementary material. Based on Theorem 1, we can easily prove the extreme-region regret of the Hoeffding's ER-UCB strategy:

Corollary 1 (Regret of Hoeffding's ER-UCB). Assume the feedback distribution of arbitrary arm satisfy (9). With α > 2, Hoeffding's ER-UCB satisfies:

According to the theoretical analysis, the ER-UCB bandit has O (K ln n) upper bound on the extreme-region regret.

4 Experiments

In the experiment section, we empirically investigate the effectiveness of the ER-UCB bandit on some synthetic and realworld AutoML tasks. Some state-of-the-art bandit strategies are selected as the compared methods, including the classical UCB (C-UCB) [Bubeck et al., 2012], ϵ-greedy [Sutton and Barto, 2018], softmax strategy [Tokic and Palm, 2011] and random strategy which allocates the budget by selecting arms randomly. In addition, we apply the random search on the joint hyper-parameter spaces of all algorithms (Joint) to compare with the cascaded hyper-parameter optimization.

4.1 Synthetic Problem

We construct a 7-armed bandit problem in this section. The feedbacks obey Gaussian distributions with different expectations and variances: G1 (0.84, 0.072 ), G2 (0.84, 0.012 ), G3 (0.85, 0.042 ), G4 (0.85, 0.022 ), G5 (0.88, 0.012 ), G6 (0.88, 0.022 ), G7 (0.89, 0.012 )}. The best arm is not only related with the expectation, but also influenced by the variance. Obviously, it is more likely to obtain the best feedback by exploiting in G1, in other words, i∗ = 1. We study on the three hyper-parameters of ER-UCB firstly, and then compare the ER-UCB with other methods.

Hyper-Parameter Study

We investigate the θ, γ and β for the ER-UCB. With fixed two of them, we study another one: with fixed γ = 20, β = 0.85, we study θ ∈ [0.0001, 0.5]; with fixed β = 0.85, θ = 0.01, we study γ ∈ [0, 50]; with fixed θ = 0.01, γ = 20, we study β ∈ [0, 1.5]. For every hyper-parameter, we evenly sample 1000 settings from the setting region. The core problem we care about is how the methods allocate budget to arms. Let Rexi i = Ti(n) n define the exploitation rate for arm i. Large Rexi i means the large number of trials that the arm i is selected. The trial budget is set as 1000. The experiment for every hyperparameter setting is repeated for 3 times independently, and the average results are presented.

Figure 1:a.1, 2 and 3 show the study results of θ, γ and β. The arm 1 is the best selection. Thus, the larger Rexi 1 the better. For θ (Figure 1:a.1), the green line (Rexi 1 ) is approaching 1 when θ nears by 0. In practice, θ should be set as a small value. For γ (Figure 1:a.2), when γ is small, the exploitation rates of arms are similar. And the green line is increasing during γ is increasing. It means that the small γ encourages exploration and the large γ encourages exploitation according to the observations. For β (Figure 1:a.3), the exploitation rates are sensitive to β when β is around the expectations of reward distributions. Thus, β should be carefully tuned according to different tasks.

Investigation with Compared Methods

According to the hyper-parameter study results of the ERUCB, we set θ = 0.01, γ = 20, β = 0.85, and compare it with the C-UCB, ϵ-greedy (ϵ = 0.1), Softmax strategy (τ = 0.1) and random selection strategy. The trial budget is 1000. Every experiment is repeated for 3 times independently. The average performances are presented in Table 1.

Table 1 shows that the ER-UCB outperforms the compared methods. Furthermore, the ER-UCB can find the best arm (arm 1) and allocate most of budget to it (maxRexi i = {1, 1, 1} and average Rexi 1 is 0.9). Because the C-UCB depends only on mean observations to make decisions. It wrongly allocates budget to arm 7 (maxRexi i = {7, 7, 7}). The Rexi 1 of ϵ-greedy is very unstable. It means ϵ-greedy can't find the best arm effectively. In general, the ER-UCB can effectively discover the best-arm and reasonably allocate budget to exploration and exploitation in this synthetic problem.

4.2 Real-World AutoML Tasks

We apply the ER-UCB to solve the real-world classification tasks. We select 10 frequently-used algorithms as the candidates from SKLEARN [Pedregosa et al., 2011], including DecisionTree (DT), AdaBoost (Ada), QuadraticDiscriminantAnalysis (QDA), GaussianNB (GNB), BernoulliNB (BNB), K-Neighbors (KN), ExtraTree (ET), PassiveAggressive (PA), RandomForest (RF) and SGD. And 12 classification datasets from UCI are selected as AutoML tasks. The evaluation criterion of each configuration is the accuracy score. The compared methods are C-UCB, ϵ-greedy (ϵ = 0.1), Softmax strategy (τ = 0.1), random strategy and Joint. The trial budget is 1000. We set θ = 0.01, γ = 20 for the ER-UCB on all datasets. The β is set according to the tasks, and showed in Table 2. For each method and each dataset, we run every experiment 3 times independently, and the average performances of our experiment are presented. In addition, we apply the random search with 1000 trials to explore on every algorithm candidate. According to (2), we can find out the best ground-truth algorithm for the datasets.

The average performances of the compared methods on all 12 datasets are presented in Table 2. From Table 2, we can get the following empirical conclusions:

• "No free lunch" has been proved again in those experiments. The best performance algorithms are different in different datasets. Particularly, tree-based ensemble algorithms, e.g., AdaBoost, RandomForest, etc, show the outstanding performance in most of the datasets. It indicates that the algorithm selection is necessary for making search hyper-parameters easier.
• The cascaded algorithm selection and hyper-parameter optimization are necessary for making the search problem easier to solve. Comparing the random strategy with the Joint, the random strategy beats the Joint on most of the datasets (8/12). It indicates that the large search space provides more difficult for optimization.
• It will mislead the strategy to select wrong algorithms only according to the average performance. In Table 2, the random strategy is not always bad in datasets. The strategies, such as C-UCB, ϵ-greedy and Softmax, which focus on the average performance are easy to select wrong algorithms which average performances are good.
• The proposed ER-UCB bandit strategy can effectively find out the best performance algorithm (B. Alg. is the ground-truth algorithm on 9/12 datasets), and reasonably allocate the trial budget to the best algorithm (ERUCB gets the highest Rexi i∗ on 12/12 datasets).

5 Conclusion

This paper proposes the extreme-region upper confidence bound (ER-UCB) bandit for the cascaded algorithm selection and hyper-parameter optimization. we employ the random search in the hyper-parameter optimization level. The level of algorithm selection is formulated as a multi-armed bandit problem. The bandit strategies are applied to allocate the limited search budget to the hyper-parameter optimization processes on algorithm candidates. However, the algorithm selection focuses on the algorithm with the maximum performance but not the average performance. To tackle this, we propose the extreme-region UCB (ER-UCB) strategy, which selects the arm with the largest extreme region of the underlying distribution. The theoretical study shows that the ER-UCB has O (K ln n) extreme-region regret upper bound, which has the same order with the classical UCB strategy. The experiments on synthetic and real-world AutoML problems empirically verify that the ER-UCB can precisely discover the algorithm with the best performance, and reasonably allocate the trial budget to the algorithm candidates.