Learning search spaces for Bayesian optimization: Another view of hyperparameter transfer learning
Valerio Perrone Huibin Shen Matthias Seeger Cedric Archambeau Rodolphe Jenatton


A dense, solar metallicity ISM in the z=4.2 dusty star-forming galaxy SPT 0418-47
    Carlos De Breuck1
          Axel Weiß2
          Matthieu Béthermin 3
          Daniel Cunningham 4,5
          Yordanka Apostolovski 6,7
          Manuel Aravena 8
          Melanie Archipley 9
          Scott Chapman 4,5,10,11
          Chian-Chou Chen 1
          Jianyang Fu 9
          Sreevani Jarugula 9
          Matt Malkan 12
          Amelia C. Mangian 9
          Kedar A. Phadke 9
          Cassie A. Reuter 9
          Gordon Stacey 13
          Maria Strandet 2
          Joaquin Vieira 9
          Amit Vishwas 13
   
    Received 2019 June 24; accepted 2019 September 26
=========================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




Bayesian optimization (BO) is a successful methodology to optimize black-box functions that are expensive to evaluate. While traditional methods optimize each black-box function in isolation, there has been recent interest in speeding up BO by transferring knowledge across multiple related black-box functions. In this work, we introduce a method to automatically design the BO search space by relying on evaluations of previous black-box functions. We depart from the common practice of defining a set of arbitrary search ranges a priori 
by considering search space geometries that are learned from historical data. This simple, yet effective strategy can be used to endow many existing BO methods with transfer learning properties. Despite its simplicity, we show that our approach considerably boosts BO by reducing the size of the search space, thus accelerating the optimization of a variety of black-box optimization problems. In particular, the proposed approach combined with random search results in a parameter-free, easy-to-implement, robust hyperparameter optimization strategy. We hope it will constitute a natural baseline for further research attempting to warm-start BO.




§ INTRODUCTION


Tuning the hyperparameters (HPs) of machine leaning (ML) models and in particular deep neural networks is critical to achieve good predictive performance. Unfortunately, the mapping of the HPs to the prediction error is in general a black-box in the sense that neither its analytical form nor its gradients are available. Moreover, every (noisy) evaluation of this black-box is time-consuming as it requires retraining the model from scratch. Bayesian optimization (BO) provides a principled approach to this problem: an acquisition function, which takes as input a cheap probabilistic surrogate model of the target black-box function, repeatedly scores promising HP configurations by performing an explore-exploit trade-off <cit.>. The surrogate model is built from the set of black-box function evaluations observed so far. For example, a popular approach is to impose a Gaussian process (GP) prior on the unobserved target black-box function f(). Based on a set of evaluations {f(^i)}_i=1^n, possibly perturbed by Gaussian noise, one can compute the posterior GP, characterized by a posterior mean and a posterior (co)variance function. The next query points are selected by optimizing an acquisition function, such as the expected improvement <cit.>, which is analytically tractable given these two quantities. While BO takes the human out of the loop in ML by automating HP optimization (HPO), it still requires the user to define a suitable search space a priori. Defining a default search space for a particular ML problem is difficult and left to human experts.

In this work, we automatically design the BO search space, which is a critical input to any BO procedure applied to HPO, based on historical data. The proposed approach relies on the observation that HPO problems occurring in  ML are often related (for example, tuning the HPs of an ML model trained on different data sets <cit.>). Moreover, our method learns a suitable search space in a universal fashion: it can endow any BO algorithm with transfer learning capabilities. For instance, we demonstrate this feature with three widely used HPO algorithms – random search <cit.>, SMAC <cit.> and hyperband <cit.>. 
Further, we investigate the use of novel geometrical representations of the search spaces, departing from the traditional 
rectangular boxes.
In particular, we show that an ellipsoidal representation is not only simple to compute and manipulate, but leads to faster black-box optimization, especially as the dimension of the search space increases.

 

§ RELATED WORK AND CONTRIBUTIONS

 
Previous work has implemented BO transfer learning in many different ways. For instance, the problem can be framed as a multi-task learning problem, where each run of BO corresponds to a task. Tasks can be modelled jointly or as being conditionally independent with a multi-output GP <cit.>, a Bayesian neural network <cit.>, a multi-layer perceptron with Bayesian linear regression heads <cit.>, possibly together with some embedding <cit.>, or a weighted combination of GPs <cit.>. Alternatively, several authors attempted to rely on manually defined meta-features 
in order to measure the similarity between BO problems <cit.>. If these problems further come in a specific ordering (e.g., because of successive releases of an ML model), the successive surrogate models can be fit to the residuals relative to predictions of the previous learned surrogate model <cit.>. In particular, if GP surrogates are used, the new GP is centered around the predictive mean of the previously learned GP surrogate. Finally, rather than fitting a surrogate model to all past data, some transfer can be achieved by warm-starting BO with the solutions to the previous BO problems <cit.>. 

The work most closely related to ours is <cit.>, where the search space is pruned during BO, removing unpromising regions based on information from related BO problems. Similarity scores between BO problems are computed from data set meta-features. While we also aim to restrict the BO search space, our
approach is different in many ways. First, we do not require meta-features, which in practice can be hard to obtain and need careful manual design. Second, our procedure works completely offline, as a preprocessing step, and does not require feedback from the black-box function
 being optimized. Third, it is parameter-free and model-free. By contrast, <cit.> rely on a GP model and have to select a radius
 and the fraction of the space to prune. 
Finally, <cit.>  use a discretization step to prune the search space, which may not scale 
well as its dimension increases. 
The generality of our approach is such that <cit.> could be used on top of our proposed method (while the converse is not true).

Another line of research has developed search space expansion strategies for BO.
Those approaches are less dependent on the initial search space provided by the users, incrementally expanding it during BO <cit.>. None of this research has considered transfer learning.
A related idea to learn hyperparameter importance has been explored in <cit.>, where a post-hoc functional ANOVA analysis is used to learn priors over the hyperparameter space. Again, such techniques could be used together with our approach, which would define the initial search space in a data driven manner. 



Our contributions are: (1) We introduce a simple and generic class of methods that design compact search spaces from historical data, making it possible to endow any BO method with transfer learning properties, (2) we explore and demonstrate the value of new geometrical representations of search spaces beyond the rectangular boxes traditionally employed, and (3) we show over a broad set of transfer learning experiments that our approach consistently boosts the performance of the optimizers it is paired with. When combined with random search, the resulting simple and parameter-free optimization strategy constitutes a strong baseline, which we hope will be adopted in future research.



§ BLACK-BOX FUNCTION OPTIMIZATION ON A REDUCED SEARCH SPACE


Consider T+1 black-box functions {f_t(·)}_t=0^T, defined on a common search space ⊆^p. The functions are expensive-to-evaluate, possibly non-convex, and accessible only through their values,
without gradient information.
In loose terms, the functions {f_t(·)}_t=0^T are assumed related, corresponding for instance to the evaluations of a given ML model over T+1 data sets (in which case  is the set of feasible HPs of this model).
Our goal is to minimize f_0:

    min_∈ f_0().

However, for t ≥ 1, we have access to n_t noisy evaluations of the function f_t, which we denote by _t ={ (_i,t, y_i,t)}_i=1^n_t.
In this work, we consider methods that take the previous evaluations {_t }_t=1^T as inputs, and output a search space ⊆, so that we solve the following problem instead of (<ref>):

    min_∈ f_0().

The local minima of (<ref>) are a subset of the local minima of (<ref>).
Since  is more compact (formally defined later), BO methods will find those minima faster, i.e., with fewer function evaluations.
Hence, we aim to design  such that it contains a “good” set of local minima, close to the global ones of .



§ DATA-DRIVEN SEARCH SPACE DESIGN VIA TRANSFER LEARNING





  
Notations and preliminaries.We define (_t^⋆, y_t^⋆) as the element in _t that reaches the smallest (i.e., best) evaluation for the black-box t, i.e.,  (_t^⋆, y_t^⋆) = _(_t,y_t) ∈_t y_t. For any two vectors  and  in ^p, ≤ stands for the element-wise inequalities u_j ≤ w_j for j ∈{1,…, p}. We also denote by || the vector with entries |u_j| for j ∈{1,…, p}.  For a collection {_t}_t=1^T of T vectors in ^p, we denote by min{_t}_t=1^T, respectively max{_t}_t=1^T, the p-dimensional vector resulting from the element-wise minimum, respectively maximum, over the T vectors.
Finally, for any symmetric matrix ∈^p× p, ≻ indicates that  is positive definite. 

We assume that the original search space  is defined by axis-aligned ranges that can be thought of as a bounding box: = {∈^p | _0 ≤≤_0} where _0 and _0 are the initial vectors of lower and upper bounds. Search spaces represented as boxes are commonly used in popular BO packages such as  <cit.>,  <cit.>,  <cit.> ,  <cit.> and  <cit.>.

The methodology we develop applies to numerical parameters (either integer or continuous). If the problems under consideration exhibit categorical parameters (we have such examples in our experiments, Section <ref>), we let =_cat×_num. Our methodology then applies to _num only, keeping _cat unchanged. Hence, in the remainder the dimension p refers to the dimension of _num.



 §.§ Search space estimation as an optimization problem


The reduced search space  we would like to learn is defined by a parameter vector ∈^k. To estimate , we consider the following constrained optimization problem:

    min_∈^k
    ()
      such that for  t ≥ 1, _t^⋆∈(),

where () is some measure of volume of (); concrete examples are given in Sections <ref> and <ref>. In solving (<ref>), we find a search space () that contains all solutions {_t^⋆}_t=1^T to previously solved black-box optimization problems, while at the same time minimizing (). Note that () can only get larger (as measured by ()) as more related black-box optimization problems are considered. 
Moreover, formulation (<ref>) does not explicitly use the y_t^⋆'s and never compares them across tasks. As a result, unlike previous work such as <cit.>, we need not normalize the tasks (e.g., whitening).



 §.§ Search space as a low-volume bounding box


The first instantiation of (<ref>) is a search space defined by a bounding box (or hyperrectangle), which is parameterized by the lower and upper bounds  and . More formally, () = {∈^p | ≤≤} and = (, ), with k=2 p. A tight bounding box containing all {_t^⋆}_t=1^T can be obtained as the solution to the following constrained minimization problem:

    min_∈^p, ∈^p
    1/2 - _2^2
      such that for  t ≥ 1, ≤_t^⋆≤

where the compactness of the search space is enforced by a squared ℓ_2 term that penalizes large ranges in each dimension. This problem has a simple closed-form solution ^*_b = (^*, ^*), where

    ^* = min{_t^⋆}_t=1^T   and  ^* = max{_t^⋆}_t=1^T.

These solutions are simple and intuitive: while the initial lower and upper bounds _0 and _0 may define overly wide ranges, the new ranges of (^*_b) are the smallest ranges containing all the related solutions {_t^⋆}_t=1^T. The resulting search space (^*_b) defines a new, tight bounding box that can directly be used with any optimizer operating on the original . Despite the simplicity of the definition of (^*_b), we show in Section <ref> that this approach constitutes a surprisingly strong baseline, even when combined with random search only. We will generalize the optimization problem (<ref>) in Section <ref> to obtain solutions that account for outliers contained {_t^⋆}_t=1^T and, as a result, produce an even tighter search space. 



 §.§ Search space as a low-volume ellipsoid


The second instantiation of (<ref>) is a search space defined by a hyperellipsoid (i.e., affine transformations of a unit ℓ_2 ball), which is parameterized by a symmetric positive definite matrix ∈^p× p and an offset vector ∈^p. More formally, () = {∈^p |  + _2 ≤ 1} and = (, ), with k = p (p+3)/2. 
Using the classical Löwner-John formulation <cit.>, the lowest volume ellipsoid covering all points {_t^⋆}_t=1^T is  the solution to the following problem (see Section 8.4 in <cit.>):

    min_∈^p × p, ≻, ∈^p
     log( ^-1)
      such that for  t ≥ 1, _t^⋆ + _2 ≤ 1,

where the T norm constraints enforce _t^⋆∈(), while the minimized objective is a strictly increasing function of the volume of the ellipsoid ∝ 1/√(( )) <cit.>. This problem is convex, admits a unique solution ^*_e = (^*,^*), and can be solved efficiently by interior-points algorithms <cit.>. In our experiments, we use  <cit.>.

Intuitively, an ellipsoid should be more suitable than a hyperrectangle when the points {_t^⋆}_t=1^T we want to cover do not cluster in the corners of the box. In Section <ref>, a variety of real-world ML problems suggest that the distribution of the solutions {_t^⋆}_t=1^T 
supports this hypothesis. We will also generalize the optimization problem (<ref>) in Section <ref> to obtain solutions that account for outliers contained in {_t^⋆}_t=1^T.



 §.§ Optimizing over ellipsoidal search spaces


We cannot directly plug ellipsoidal search spaces into standard HPO procedures. Algorithm <ref> details how to adapt random search, and as a consequence also methods like hyperband <cit.>, to an ellipsoidal search space. In a nutshell, we use rejection sampling to guarantee uniform sampling in ∩(^*_e): we first sample uniformly in the p-dimensional ball, then apply the inverse mapping of the ellipsoid <cit.>, and finally check whether the sample belongs to . The last step is important as not all points in the ellipsoid may be valid points in . For example, a HP might be restricted to only take positive values. However, after fitting the ellipsoid, some small amount of its volume might include negative values. 
Finally, ellipsoidal search spaces cannot directly be used with more complex, model-based BO engines, such as GPs. They would require resorting to constrained BO modelling <cit.>, e.g., to optimize the acquisition function over the ellipsoid, which would add significant complexity to the procedure. Hence, we defer this investigation to future work.




§ HANDLING OUTLIERS IN THE HISTORICAL DATA


The search space chosen by our method is the smallest hyperrectangle or hyperellipsoid enclosing a set of solutions {_t^⋆}_t=1^T found by optimizing related black-box optimization problems. 
In order to exploit as much information as possible,
 a large number of related problems may be considered. However, the learned search space volume might increase as a result, which will make black-box optimization algorithms, such as BO, less effective. For example, if some of these problems depart significantly from the other black-box optimization problems, their contribution to the volume increase might be disproportionate and discarding them will be beneficial. In this section, we extend of our methodology to exclude such outliers automatically.

We allow for some _t^⋆ to violate feasibility, but penalize such violations by way of slack variables. To exclude outliers from the hyperrectangle,  problem (<ref>) is modified as follows:

    min_∈^p, ∈^p, ξ_t^- ≥ 0, ξ_t^+ ≥ 0
    for t ≥ 1,  -ξ_t^- |_0| ≤_t^⋆≤ + ξ_t^+ |_0|
    λ_b/2 - _2^2 + 1/2T∑_t=1^T (ξ_t^- + ξ_t^+) ,

where λ_b ≥ 0 is a regularization parameter, and {ξ_t^-}_t=1^T and {ξ_t^+}_t=1^T the slack variables associated respectively to  and , which we make scale-free by using |_0| and |_0|. Slack variables can also be used to exclude outliers from an ellipsoidal search region <cit.> by rewriting (<ref>) as follows:

    min_∈^p × p, ≻, ∈^p, ξ_t ≥ 0
    for t ≥ 1, _t^⋆ + _2 ≤ 1 + ξ_t
    λ_e log( ^-1) + 1/T∑_t=1^T ξ_t.

where λ_e ≥ 0 is a regularization parameter and {ξ_t}_t=1^T the slack variables . Note that the original formulations (<ref>) and (<ref>) are recovered when λ_b or λ_e tend to zero, as the optimal solution is then found when all the slack variables are equal to zero. By contrast, when λ_b or λ_e get larger, more solutions in the set {_t^⋆}_t=1^T are ignored, leading to a tighter search space.

To set λ_b and λ_e, we proceed in two steps. First, we compute the optimal solution (θ^*) of the original problem, namely (<ref>) and (<ref>) for the bounding box and ellipsoid, respectively. (θ^*) captures the scale of the problem at hand. Then, we look at λ = s / (θ^*) for s in a small, scale-free, grid of values and select the smallest value of λ that leads to no more than (1-ν) × T solutions from {_t^⋆}_t=1^T (by checking the number of active, i.e., strictly positive, slack variables in (<ref>) and (<ref>)). We therefore turn the selection of the abstract regularization parameter λ to the more interpretable choice of ν as a fraction of outliers. In our experiments, we purely determined those values on the toy SGD synthetic setting (Section <ref>), and then applied it as a default to the real-world problems with no extra tuning (this led to ν_b =0.5 and ν_e=0.1).







§ EXPERIMENTS


Our experiments are guided by three key messages. First, our method can be combined with a large number of HPO algorithms. Hence, we obtain a modular design for HPO (and BO) which is convenient when building ML systems. Second, 
by introducing parametric assumptions (with the box and the ellipsoid),  
we show empirically that our approach is more robust to low-data regimes compared to model-based approaches. Third, our simple method
induces transfer learning
 by reducing the search space of BO. The method compares favorably to more complex alternative models for transfer learning proposed in the literature, thus setting a competitive baseline for future research.

In the experiments, we consider combinations of search space definitions and HPO algorithms.  and  refer to learned hyperrectangular (Section <ref>) and hyperellipsoidal search spaces (Section <ref>). When none of these prefixes are used, we defined the search space using manually specified bounding boxes (see Subsections <ref>–<ref> for the specifics). We further consider a diverse set of HPO algorithms: random search, Hyperband <cit.>, GP-based BO, GP-based BO with input warping <cit.>, random forest-based BO <cit.>, and adaptive bayesian linear regression-based BO <cit.>, which are denoted respectively by , , , , , and . We assessed the transfer learning capabilities in a leave-one-task-out fashion, meaning that we leave out one of the black-box optimization problems and then aggregate the results. Each curve and shaded area in the plots respectively corresponds to the mean metric and standard error obtained over 10 independent replications times the number of leave-one-task-out runs. To report the results and ease comparisons of tasks, we normalize the performance curves of each model by the best value obtained by random search, inspired by <cit.>. Consequently, each random search performance curve ends up at 1 (or 0 when the metric is log transformed).





 §.§ Tuning SGD for ridge regression
 

We consider the problem of tuning the parameters of stochastic gradient descent (SGD) when optimizing a set of 30 synthetic ridge regression problems with 81 input dimensions and 81 observations. The setting is inspired by <cit.> and is described in the Supplement. The HPO problem consists in tuning 3 HPs: learning rate in the range of (0.001, 1.0), momentum in the range of (0.3, 0.999) and regularization parameter in the range of (0.001, 10.0). Figure <ref> shows that the convergence to a good local minimum of conventional BO algorithms, such as , , and , is significantly boosted when the search space is learned () from related problems. It is also interesting to note that all perform similarly once the search space is learned. The results for  combined with  are also similar, where the   improves over  but not as much as in the  case due to significant performance gain with warping. We show the results in Supplement <ref>.







The transfer learning methodology can be combined with resource-based BO algorithms, such as Hyperband <cit.>. We defined a unit of resource as three SGD updates (following <cit.>). By design, the more resources, the better the performance. Figure <ref> shows that both the  and -based transfer benefit . Furthermore,  with transfer is competitive with all other conventional BO algorithms, including model-based ones when comparing the RMSE across Figure <ref> and Figure <ref>.

We then studied the impact of introducing the slack variables to exclude outliers. One example of a learned  search space found for the 3 HPs of SGD on one of the ridge regression tasks is illustrated in Figure <ref>, together with its slack counterpart. The slack extension provides a more compact search space by discarding the outlier with learning rate value ≈ 0.06. A similar result was obtained with the -based learned search space (see Supplement <ref>).







 §.§ Tuning binary classifiers over multiple OpenML data sets
 

We consider HPO for three popular binary classification algorithms: random forest (RF; 5 HPs), support vector machine (SVM; 4 HPs), and extreme gradient boosting (XGBoost; 10 HPs). Here, each problem consists of tuning one of these algorithms on a different data set. We leveraged OpenML <cit.>, which provides evaluation data for many ML algorithm and data set pairs. Following <cit.>, we selected the 30 most-evaluated data sets for each algorithm. 
The default search ranges were defined by the minimum and maximum hyperparameter value used by each algorithm when trained on any of the data sets. Results are shown in Figure <ref>. The  variants consistently outperform their non-transfer counterparts in terms of convergence speed, and  performs en par with  and . In this experiment, we also compared to  with input warping <cit.>, which exhibited a comparable boost when used in conjunction with the  search space, slightly outperforming all other methods. Finally,  slightly outperforms .
Next, we compare  and  with two different transfer learning extensions of GP-based HPO, derived from <cit.>. Each black-box optimization problem is described by meta-features computed on the data set.[
  Four features: data set size; number of features; class imbalance; Naive Bayes
  landmark feature.]
In , the closest problem (among the 29 left out) in terms of ℓ_1 distance of meta-features is selected, and its k best evaluations are used to warm start the GP surrogate. Results are given in Figure <ref>. Our simple search space transfer learning techniques outperform these GP-based extensions for all k. 
We also considered , which transfers the k best evaluations from all the 29 left out problems, appending the meta-feature vector to the hyperparameter configuration as input to the GP (see Figure <ref> in Supplement <ref>). Results were qualitatively very similar, but the cubic scaling of GP surrogates renders  unattractive for a large T and/or k. In contrast, our transfer learning techniques are model-free. 

In the next experiment, we combine our  search space with these GP-based transfer techniques. In all methods, we use 256 random samples from each problem t: n_t go to , the remaining 256-n_t to . The results are given in Figure <ref>. It is clear that the  improves plain  regardless of n_t.
We also ran experiments with  and  <cit.>, a transfer HPO method which scales linearly in the total number of evaluations (as opposed to GP, which scales cubically). In all cases,  is significantly outperformed by some  or  variant, demonstrating that additional gains are achievable by using some of the data from the related problems to tighten the search space (see Figure <ref> and Figure <ref> in Supplement <ref>).
Next, we studied the effect of the number n_t of samples from each problem on . Results are reported in Figure <ref>. We found that with a small number (n_t=8) of samples per problem, learning the search space already provided sizable gains. 
We also studied the effects of the number of related problems.[
   For each of the 30 target problems, we pick k<29 of the remaining ones at random,
   independently in each random repetition. We transfer n_t=256 samples per problem.]
Results are given in Figure <ref>. We see that our transfer learning by reducing the search space performs well even if only 3 previous problems are available, while transfering from 9 problems yields most of the improvements. The results for  are similar (see Figure <ref>- <ref> in Supplement <ref>). 

Finally, we benchmark our slack variable extensions of  and  from Section <ref>. As the number of related problems grows, the volume of the smallest box or ellipsoid enclosing all minima may be overly large due to some outlier solutions. For example, we observed that the optimal learning rate η of XGBoost is typically ≤ 0.3, except η≈ 1 for one data set. Our slack extensions are able to neutralize such outliers, reducing the learned search space and improving the performance (see Figure <ref>  and Figure <ref> in Supplement <ref> for more details).






















 §.§ Tuning neural networks across multiple data sets
 

The last set of experiments we conduct consist of tuning the HPs of a 2-layer feed-forward neural network on 4 data sets <cit.>, namely {}. The search space for this neural network contains the initial learning rate, batch size, learning rate schedule, as well as layer-specific widths, dropout rates and activation functions, thus in total 9 HPs. All the HPs are discretized and there are in total 62208 HP configurations which have been trained with ADAM with 100 epochs on the 4 data sets, optimizing the mean squared error. For each HP configuration, the learning curves (both on training and validation set) and the final test metric are saved and provided publicly by the authors <cit.>. As a result, we avoided re-evaluating the HPs, which significantly reduced our experiment time.


Each black-box optimization problem consists of tuning the neural network parameters over 1 data set after using 256 evaluations randomly chosen from the remaining 3 data sets to learn the search space. The default search space ranges are provided in <cit.>. We compared plain , , and  to their variants based on . The results are illustrated in Figure <ref>, where significant improvements can be observed.  also outperforms classic BO baselines such as  and . Finally, Figure <ref> demonstrates that  can be further sped up by our transfer learning extensions.

These results also indicate that good solutions are typically found in the interior of the search space. To see how much accuracy could potentially be lost compared to methods that search over the entire search space, we re-ran the OpenML and neural network experiments using 16 times as many iterations (see Figure <ref> and Figure <ref> in Supplement <ref>). Empirical evidence shows that excluding the best solution is not a concern in practice, and that restricting the search space leads to considerably faster convergence.









§ CONCLUSIONS

We presented a novel, modular approach to induce transfer learning in BO. Rather than designing a specialized multi-task model, our simple method automatically crafts promising search spaces based on previously run experiments. Over an extensive set of benchmarks, we showed that our approach significantly speeds up the optimization, and can be seamlessly combined with a wide range of existing BO techniques. Beyond those we used in our experiments, we can further mention recent resource-aware optimizers <cit.>, evolutionary-based techniques <cit.> and virtually any core improvement of BO, be it related to the acquisition function <cit.> or efficient parallelism <cit.>. 

The proposed method could be extended in a model-based fashion, allowing us to simultaneously search for the best HP configurations _t's for each data set, together with compact spaces containing all of these configurations. 
When evaluation data from a large number of tasks is available, heterogeneity in their minima may be better captured by employing a mixture of boxes or ellipsoids.



abbrv







§ SUPPLEMENTARY MATERIAL





§ TUNING SGD FOR RIDGE REGRESSION



The problem we consider in the toy SGD example is the following: denoting the squared loss by ℓ_i() = 1/2(_i^⊤ - τ_i)^2, we focus on solving

    min_∈^p  L() = ∑_i=1^n{ℓ_i() + r ||||^2}

with the stochastic gradient (SGD) update rule at step k:


    =γ + η∇ L_i(^(k)) 
       ^(k+1) =^(k) -


where _i ∈^p and τ_i ∈ refer to input and target of the regression problem while we use the momentum γ∈[0.3, 0.999] together with the learning rate parametrization η∈ [0.001, 1.0] and r ∈ [0.001, 10]. The data (_i, τ_i)'s are otherwise generated like in <cit.>. 

The complete results for this setting are presented in Figure <ref>. The  and  approaches can significantly boost the baseline methods: , ,  and .



We next studied the impact of introducing slack variables in the  approach to exclude outliers. An example of a learned  search space for the 3 hyperparameters of SGD on one of the ridge regressions is illustrated in Figure <ref>, together with its slack counterpart. The slack extension effectively provides a more compact search space by leaving out the outlier learning rate value (∼ 0.06). A similar result was obtained with the -based learned search space.





§ TUNING BINARY CLASSIFIERS OVER MULTIPLE OPENML DATA SETS



We first give more details on the experimental setup and then discuss some additional results not included in the main text. We follow the protocol and data collection from <cit.>, which we describe below to provide a self-contained description.



 §.§ Experiment setup

In the OpenML <cit.> experiments, we considered the optimization of the hyperparameters of the following three algorithms:


  * Support vector machine (SVM,  5891),

  * Extreme gradient boosting (XGBoost,  6767). 

  * Random forest (RF.  6794).


Note that some hyperparameters can be log scaled. In Section <ref>, we show an additional set of results for the log scaled search spaces.


  §.§.§ Support vector machine

The SVM tuning task consists of the following 4 hyperparameters: 


  * cost (float, min: 0.000986, max: 998.492437; can be log-scaled),

  * degree (int, min: 2.0, max: 5.0),

  * gamma (float, min: 0.000988, max: 913.373845; can be log-scaled),

  * kernel (string, [linear, polynomial, radial, sigmoid]).

This tuning task exhibits conditional relationships with respect to the choice of the kernel.[For details, see the API from ]

For this , we considered the 30 most evaluated data sets whose  are: 10101, 145878, 146064, 14951, 34536, 34537, 3485, 3492, 3493, 3494, 37, 3889, 3891, 3899, 3902, 3903, 3913, 3918, 3950, 6566, 9889, 9914, 9946, 9952, 9967, 9971, 9976, 9978, 9980, 9983.


  §.§.§ XGBoost

The XGBoost tuning task consists of 10  hyperparameters: 


  * alpha (float, min: 0.000985, max: 1009.209690; can be log-scaled),

  * booster (string, ['gbtree', 'gblinear']), 

  * colsample_bylevel (float, min: 0.046776, max: 0.998424),

  * colsample_bytree (float, min: 0.062528, max: 0.999640),

  * eta (float, min: 0.000979, max: 0.995686),

  * lambda (float, min: 0.000978, max: 999.020893; can be log-scaled)

  * max_depth (int, min: 1, max: 15; can be log-scaled),

  * min_child_weight (float, min: 1.012169, max: 127.041806; can be log-scaled),

  * nrounds (int, min: 3, max: 5000; can be log-scaled),

  * subsample (float, min: 0.100215, max: 0.999830). 

This tuning task exhibits conditional relationships with respect to the choice of the booster.[For details, see the API from ]

For this , we considered the 30 most evaluated data sets whose  are: 10093, 10101, 125923, 145847, 145857, 145862, 145872, 145878, 145953, 145972, 145976, 145979, 146064, 14951, 31, 3485, 3492, 3493, 37, 3896, 3903, 3913, 3917, 3918, 3, 49, 9914, 9946, 9952, 9967.



  §.§.§ Random forest

The random forest tuning task consists of the following 5 hyperparameters: 



  * mtry (int, min: 1, max: 36),

  * num_tree (int, min: 1, max: 2000; can be log-scaled),

  * replace (string, [true, false]),

  * respect_unordered_factors (string, [true, false]),

  * sample_fraction (float, 0.1, 0.99999)


For this , we considered the 30 most evaluated data sets whose  are: 125923, 145804, 145836, 145839, 145855, 145862, 145878, 145972, 145976, 146065, 31, 3492, 3493, 37, 3896, 3902, 3913, 3917, 3918, 3950, 3, 49, 9914, 9952, 9957, 9967, 9970, 9971, 9978, 9983.



 §.§ Results

We first considered , which transfers the k best evaluations from each of the 29 left-out problems, appending the meta-feature vector to the hyperparameter configuration as input to the GP. The results are shown in Figure <ref>. It is clear that  and  combined with random already outperform this transfer learning baseline.

We also ran experiments with  and  [28], where n evaluations from each related problem are used to find the bounding box, and 256 - n are used for GP and ABLR. In all cases, both  and the vanilla transfer learning approaches are significantly outperformed by  (in Figure <ref>) and  (in Figure <ref>). This demonstrates that alternative transfer learning algorithms can benefit from additional speed-ups when a subset of the available evaluations from the related problems are used to tighten the search space.
 



Next, we studied the effect of the number n of samples from each problem on .
Results are reported in Figure <ref>. We found that with a small number (n = 8) of samples per problem,
learning the search space already provides sizable gains. We also studied the effects of the number
of source problems. Results are given in Figure <ref>. By reducing the
search space, our transfer learning approach performs well even if only 3 previous problems are available, while transferring from 9
problems yields most of the improvements. The results for  are qualitatively similar.



We then studied the ability of the proposed slack-extensions of our method to remove outliers and lead to a more compact search space. As the number of related problems grows, the volume of the smallest box or ellipsoid enclosing all minimum points may be overly large due to some outlier solutions. For example, we observed that the optimal learning rate η of XGBoost is typically ≤ 0.3, except that η≈ 1 for one data set. Our slack extensions are able to neutralize such outliers, as shown in Figure <ref> for an example 2-d slice of the slack-ellipsoid. On the XGBoost problems, the slack formulations are able to appropriately shrink the search space and considerably improve performance (Figure <ref>). The performance gain does not emerge for SVM in Figure <ref> and RF in Figure <ref>, which can be attributed to the available solutions being more homogeneous across problems.








§ EXPLORING THE SEARCH SPACE WITH MORE RESOURCES


The approach we propose aims to lift the burden of choosing the search space. When running experiments for a fixed amount of iterations, this has the effect of exploring the (restricted) search space more densely, which we showed to be beneficial. To assess how much accuracy can potentially be lost compared to methods that search the entire space (with more resources), we re-ran our experiments with 16 times as many iterations. Figure <ref> and Figure <ref> respectively show the OpenML and neural network results aggregated across all tasks: restricting the search space leads to considerably faster convergence and  fails to find a better solution, only eventually catching up in the neural network case. This suggests that there is almost no loss of performance, but just a speed-up effect of finding a very good solution in as few evaluations as possible.







§ TUNING OPENML BINARY CLASSIFIERS IN THE LOG SCALED SEARCH SPACE


We presented results on the OpenML data in the main text and Section <ref> of the supplementary material. One feature of the OpenML setting is that the hyperparameter search spaces can be wide, such as the n_rounds of XGBoost which can go up to 5000. Therefore, we re-ran the OpenML experiments in the alternative scenario of log-scaled search spaces. A key message is that the conclusions are qualitatively similar, while the gaps between the different models are smaller since the tasks are overall simpler.

We repeated the experiments on  combined with  and show the results in Figure <ref>, where we see consistent improvements using the  approach. Comparing to the vanilla transfer learning method, namely ,  also demonstrated improved performance as shown in Figure <ref>. Crucially, we can combine  with  to achieve even better performance as shown in Figure <ref>.



We then studied the effects of the number of samples and number of related problems used to learn the search space of  and . Both the  and  are quite robust to the number of samples: the difference is smaller than in the setting without log scaling, and they both improve over , as shown in Figure <ref> and Figure <ref>. Figure <ref> and Figure <ref> show that, while using 3 related problems seems not enough to learn a good search space for the two approaches, with 9 related problems both the  and the  improve on , especially at the beginning of the optimization. Finally, the  approach tends to outperforms , pointing to the benefits of a more flexible representation of the search space.







