PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning search spaces for Bayesian optimization: Another view of hyperparameter transfer learning

Valerio Perrone, Huibin Shen, Matthias Seeger, Cedric Archambeau, Rodolphe Jenatton

arXiv:1909.12552v1stat.MLcs.LG

TL;DR

BO hyperparameter tuning requires users to specify a search space, while transfer across related black-box problems offers a way to use earlier evaluations. This paper learns compact box or ellipsoid search spaces from historical data for use with existing optimizers. Across benchmarks, the approach speeds optimization and can be combined with a range of BO techniques.

  • Problem

    BO still requires users to define a suitable search space, while evaluations of expensive black-box functions make optimization costly.

    Source: §1 · p. 1

  • Method

    The method learns compact box or ellipsoid search spaces from historical evaluations of related tasks for use by existing optimizers.

    Source: §1 · p. 1, §4.2 · p. 3, §4.3 · p. 4

  • Results

    The approach significantly speeds optimization over an extensive set of benchmarks and combines with a wide range of BO techniques.

    Source: §1 · p. 2, §7 · p. 9

  • Takeaways & Limitations

    The learned search spaces provide a modular way to add transfer learning to existing BO techniques.

    Source: §7 · pp. 8–9

    The formulation assumes the black-box functions are related, for example, evaluations of one model across multiple data sets.

    Source: §3 · p. 2

Abstract

from arXiv · show

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.

1 Introduction

Bayesian optimization automates hyperparameter tuning, but users still have to define its search space. The paper learns that space from historical evaluations so existing optimizers can transfer knowledge across related problems.

1 Introduction

  • BO uses a probabilistic surrogate and an acquisition function to select promising configurations, but the search space still requires a suitable definition by the user.Source: §1 · p. 1
  • The method learns BO search spaces from historical evaluations and can add transfer learning to existing optimization algorithms.It is demonstrated with random search, SMAC, and Hyperband.Source: §1 · pp. 1–2
  • The learned space can be an ellipsoid, which is simple to compute and manipulate and leads to faster optimization, especially as dimensionality increases.Source: §1 · p. 2

2 Related work and contributions

Prior BO transfer methods use joint models, meta-features, ordered-task residuals, or warm starts. This paper instead learns compact search spaces from historical data and reports that the approach can pair with existing optimizers.

2 Related work and contributions

  • Earlier transfer approaches include multi-task surrogate models, manually designed meta-features, residual-based updates for ordered tasks, and warm-starting from prior solutions.Source: §2 · p. 2
  • Unlike, the method needs no meta-features, works offline without optimization feedback, and is parameter-free and model-free.The paper notes that could be used on top of its approach, but not conversely.Source: §2 · p. 2
  • Search-space expansion and post-hoc hyperparameter-importance methods address related problems, but the cited work does not use transfer learning for expansion.The paper proposes using such techniques alongside its data-driven initial search space.Source: §2 · p. 2
  • The approach learns compact search spaces from historical data and consistently boosts paired optimizers across transfer-learning experiments.Combined with random search, it is presented as a strong, parameter-free baseline.Source: §2 · p. 2

3 Black-box function optimization on a reduced search space

The paper considers related, expensive black-box functions with no gradient access, using evaluations from prior tasks to construct a reduced search space for optimizing a target function.

3 Black-box function optimization on a reduced search space

  • The target functions are expensive to evaluate and available only through their values, without gradient information.Source: §3 · p. 2
  • The tasks are assumed related, such as evaluations of the same model on different data sets, and the objective is to minimize the target function f0.Source: §3 · p. 2
  • The method uses noisy evaluations from prior tasks as input and outputs a reduced search space for solving the target problem.Source: §3 · pp. 2–3
  • The reduced space should retain good local minima near the original global minima; its compactness is intended to let BO find retained minima with fewer evaluations.Source: §3 · p. 3

4 Data-driven search space design via transfer learning

The method constructs compact search spaces from the best configurations observed on related tasks, using either boxes or ellipsoids. These learned spaces can then be used by compatible optimizers, with rejection sampling for ellipsoids.

4.1 Search space estimation as an optimization problem

  • The estimation objective seeks a low-volume search space containing the best configurations from prior tasks, without comparing their objective values across tasks.The method applies to numerical parameters; categorical dimensions, when present, are left unchanged.Source: §4.1 · p. 3, §4 · p. 3

4.2 Search space as a low-volume bounding box

  • A bounding-box search space uses lower and upper bounds to contain the best configurations from previous tasks.Its compactness is encouraged by penalizing large ranges, and the resulting tight box can be used with optimizers defined on the original space.Source: §4.2 · pp. 3–4

4.3 Search space as a low-volume ellipsoid

  • An ellipsoidal search space is parameterized by a positive-definite matrix and an offset, with the lowest-volume ellipsoid covering the historical best configurations.The formulation is convex and has a unique solution.Source: §4.3 · p. 4

4.4 Optimizing over ellipsoidal search spaces

  • For an ellipsoid, rejection sampling maps uniform samples from a unit ball into the ellipsoid and rejects points outside the original feasible space.The paper notes that model-based BO would require constrained optimization over the ellipsoid, which it defers to future work.Source: §4.4 · p. 4

5 Handling outliers in the historical data

The method encloses optima from related problems in a compact hyperrectangle or hyperellipsoid, then extends these constructions with slack variables to exclude outliers. The slack penalty is calibrated through a scale-free grid and a chosen fraction of outliers.

5 Handling outliers in the historical data

  • The base search space is the smallest hyperrectangle or hyperellipsoid enclosing solutions found on related optimization problems.Source: §5 · p. 4
  • The slack extension modifies the box and ellipsoid formulations to penalize feasibility violations and exclude outliers.Source: §5 · p. 5
  • Slack variables let the learned box or ellipsoid ignore some historical solutions, tightening the search space when outliers inflate its volume.As the penalty increases, more solutions may be ignored; the original formulations are recovered as the penalty tends to zero.Source: §5 · p. 5
  • The penalty is selected by scaling a grid of candidate values by the original optimum and choosing the smallest that excludes no more than a fraction ν of solutions.The outlier fractions were selected on synthetic SGD tasks and used without extra tuning on real-world problems: ν_b = 0.5 and ν_e = 0.1.Source: §5 · p. 5

6 Experiments

Across the experiments, learned search spaces paired with diverse HPO algorithms improve performance, and the approach compares favorably with more complex transfer-learning alternatives. The experiments cover synthetic SGD tuning, OpenML classification tasks, and neural-network tuning across data sets.

6 Experiments

  • The method compares favorably to more complex transfer-learning models, while reducing the search space and improving optimizer performance across the reported experiments.Source: §6 · p. 5
  • Across leave-one-task-out experiments, curves report mean performance and standard error over 10 replications per run, normalized by each model’s best random-search value.The tested optimizers include Random, Hyperband, GP-based BO, GP warping, SMAC, and ABLR.Source: §6 · p. 5

6.1 Tuning SGD for ridge regression

  • Learned Box spaces boost Random, GP, and SMAC on 30 synthetic ridge-regression tasks, and the methods perform similarly once the space is learned.Box also improves GP warping, though less than it improves GP.Source: §6.1 · p. 6, Figure 1 · p. 6
  • Box and Ellipsoid transfer improve Hyperband, which becomes competitive with conventional BO methods on RMSE.Slack variables compact the learned space by discarding an outlier learning rate near 0.06.Source: §6.1 · p. 6, Figure 2 · p. 6

6.2 Tuning binary classifiers over multiple OpenML data sets

  • Slack extensions reduce learned spaces and improve performance when outlier solutions enlarge the enclosing box or ellipsoid.For XGBoost, the optimal learning rate was typically ≤0.3, except for one data set with η ≈1.Source: §6.2 · p. 7

6.3 Tuning neural networks across multiple data sets

  • For neural-network tuning across four data sets, Box variants significantly improve Random, SMAC, and GP, while Ellipsoid Random beats classic GP and SMAC baselines.Hyperband also becomes faster with the transfer extensions; experiments using 16 times as many iterations found that excluding the best solution was not a practical concern.Source: §6.3 · p. 8, Figure 5 · p. 8

7 Conclusions

The paper introduces a modular way to induce transfer learning in BO by crafting compact search spaces from historical experiments. Across benchmarks, the approach speeds optimization and can be combined with existing BO techniques; the authors identify model-based space learning and mixtures of geometries as possible extensions.

7 Conclusions

  • Rather than building a specialized multi-task model, the method automatically crafts promising search spaces from previously run experiments.Source: §7 · pp. 8–9
  • Across a broad set of transfer-learning experiments, the approach consistently speeds up paired optimizers and can be combined with a wide range of existing BO techniques.The authors also mention resource-aware and evolutionary optimizers, acquisition-function improvements, and efficient parallelism as possible combinations.Source: §7 · p. 9
  • The authors propose model-based extensions that jointly search for task-specific configurations and compact spaces, and mixtures of boxes or ellipsoids to capture heterogeneous minima.They suggest mixtures when many tasks are available.Source: §7 · p. 9

A Tuning SGD for ridge regression

The supplement reports SGD tuning results and experimental details for OpenML binary-classifier tasks. In the ridge-regression setting, Box and Ellipsoid transfer approaches boost several BO baselines, while slack extensions can exclude an outlier learning rate and compact the learned space.

A Tuning SGD for ridge regression

B.1 Experiment setup

  • The OpenML experiments consider SVM, XGBoost, and random forest, using the 30 most-evaluated data sets for each algorithm.Source: §B.1 · pp. 12–13

B.1.1 Support vector machine

  • The SVM task has four hyperparameters and conditional relationships associated with the kernel choice.Source: §B.1.1 · p. 13

B.1.2 XGBoost

  • The XGBoost task has ten hyperparameters, including booster-dependent conditional relationships.Source: §B.1.2 · p. 13

B.1.3 Random forest

  • The random-forest task consists of five hyperparameters.Source: §B.1.3 · p. 14

B.2 Results

Across OpenML and neural-network experiments, restricting the search space leads to faster convergence, with GP eventually catching up only in the neural-network case after more iterations. In OpenML, Box and Ellipsoid approaches also compare favorably with transfer baselines, while slack extensions help when outliers make the learned space too large.

B.2 Results

  • Box and Ellipsoid combined with random outperform GP warm-start T=29, while Box + GP warm-start and Box + ABLR outperform their vanilla transfer counterparts.The combined methods use some related-task evaluations to learn the box and the remaining evaluations for GP or ABLR.Source: §B.2 · p. 14, Figure 8 · p. 14
  • With eight samples per source problem, learning a Box search space already provides sizable gains; three source problems can work well, while nine yield most improvements.Ellipsoid + Random results are qualitatively similar.Source: §B.2 · p. 14, Figure 9 · p. 15
  • Slack extensions shrink the XGBoost search space and improve performance by neutralizing an outlier learning rate near 1, unlike on SVM and random forest, where solutions are more homogeneous.XGBoost learning rates are typically at most 0.3 except for one data set.Source: §B.2 · p. 15, Figure 10 · p. 15

C Exploring the search space with more resources

  • With 16 times as many iterations, restricting the search space still gives considerably faster convergence; GP only eventually catches up in the neural-network case.The authors interpret this as almost no performance loss, but rather a speed-up in finding a good solution with fewer evaluations.Source: C Exploring the search space with more… · p. 15

D Tuning OpenML binary classifiers in the log scaled search space

In log-scaled OpenML search spaces, the overall conclusions remain qualitatively similar, though gaps between models are smaller. Box and Ellipsoid approaches improve over Random, and combining Box with GP warm-start can improve performance further.

D Tuning OpenML binary classifiers in the log scaled search space

Related papers

Loading 1909.12552v1…