PaperlayerView exact revision on arXiv

Source-linked AI summary

HEBO Pushing The Limits of Sample-Efficient Hyperparameter Optimisation

Alexander I. Cowen-Rivers, Wenlong Lyu, Rasul Tutunov, Zhi Wang, Antoine Grosnit, Ryan Rhys Griffiths, Alexandre Max Maraval, Hao Jianye, Jun Wang, Jan Peters, Haitham Bou Ammar

arXiv:2012.03826v6cs.LGmath.OC

TL;DR

Hyperparameter tuning depends on black-box optimization, but common modeling and acquisition assumptions may not fit tuning tasks. The paper analyzes these assumptions and proposes HEBO with input/output warping and robust acquisition choices. It reports heteroscedasticity and non-stationarity across tasks, improved warping performance, and a first-place result in the 2020 NeurIPS challenge.

  • Problem

    Common Bayesian-optimization modeling and acquisition assumptions may be misspecified for hyperparameter tuning, where tasks can be heteroscedastic or non-stationary.

    Source: §1 · p. 2, §2.1 · p. 4, §2.2 · p. 6

  • Method

    The paper proposes HEBO and evaluates revised Bayesian-optimization choices, including input/output warping and robust acquisition formulations.

    Source: §1 · p. 3, §4.2.2 · p. 12

  • Results

    Hyperparameter tuning tasks exhibit significant heteroscedasticity and non-stationarity, and input/output warping yields higher mean and median performance across all 108 examined black-box functions.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The authors conclude that Bayesian optimization can be a competitive tuning baseline under revised assumptions and that their findings may guide practitioners.

    Source: §7 · p. 18

    The authors believe the trust region is not modeled correctly with input warping.

    Source: §6 · p. 16

Abstract

from arXiv · show

In this work we rigorously analyse assumptions inherent to black-box optimisation hyper-parameter tuning tasks. Our results on the Bayesmark benchmark indicate that heteroscedasticity and non-stationarity pose significant challenges for black-box optimisers. Based on these findings, we propose a Heteroscedastic and Evolutionary Bayesian Optimisation solver (HEBO). HEBO performs non-linear input and output warping, admits exact marginal log-likelihood optimisation and is robust to the values of learned parameters. We demonstrate HEBO's empirical efficacy on the NeurIPS 2020 Black-Box Optimisation challenge, where HEBO placed first. Upon further analysis, we observe that HEBO significantly outperforms existing black-box optimisers on 108 machine learning hyperparameter tuning tasks comprising the Bayesmark benchmark. Our findings indicate that the majority of hyper-parameter tuning tasks exhibit heteroscedasticity and non-stationarity, multi-objective acquisition ensembles with Pareto front solutions improve queried configurations, and robust acquisition maximisers afford empirical advantages relative to their non-robust counterparts. We hope these findings may serve as guiding principles for practitioners of Bayesian optimisation. All code is made available at https://github.com/huawei-noah/HEBO.

1. Introduction

The paper examines how modeling and acquisition assumptions affect black-box hyperparameter tuning, then tests whether revised Bayesian optimization choices improve performance. Its findings identify heteroscedasticity, non-stationarity, and conflicting acquisition solutions as important considerations, and report HEBO’s competition result and component ablations.

1. Introduction

  • Bayesian optimization offers sample-efficient evaluations but can require high computational effort, while unguided bandit approaches can fail to converge.The paper motivates autonomous tuning as increasingly important as machine-learning models grow larger and more complex.Source: §1 · p. 2
  • The paper identifies restrictive modeling and acquisition assumptions, including Gaussian-process defaults and acquisition choices, as targets for empirical analysis.Gaussian processes are described as the default surrogate because of their flexibility and sample efficiency.Source: §1 · p. 2
  • The study evaluates 2,140 experiments across 108 real-world UCI problems, with multi-seeding and attention to random initialization.The authors chose a benchmark testbed also used in the NeurIPS 2020 Black-Box Optimisation challenge.Source: §1 · p. 3
  • Hyperparameter tuning tasks exhibit significant heteroscedasticity and non-stationarity, challenging the homoscedastic and stationary assumptions common in Gaussian-process surrogates.The authors note that misspecified assumptions can inhibit Bayesian-optimization performance even when computational efficiency improves.Source: §1 · pp. 2–3
  • Acquisition functions can conflict in their preferred solutions, and a multi-objective formulation significantly improves performance.The paper frames this against implementations that presume one acquisition function performs best for a given task.Source: §1 · p. 3
  • HEBO placed first in the 2020 NeurIPS Black-Box Optimisation Challenge, while ablations ranked output warping, multi-objective acquisitions, and input warping ahead of robust acquisition formulations.The paper also reports that input and output warping yield higher mean and median performance across all 108 examined black-box functions.Source: §1 · p. 3

2. Standard Design Choices in BO

The section outlines Bayesian optimization as a sequential search that alternates surrogate modeling and acquisition maximization, then examines common assumptions in both stages. It focuses on stationarity, noise homoscedasticity, and acquisition choices, noting that these assumptions can be violated in tuning tasks.

2. Standard Design Choices in BO

  • Bayesian optimization searches a bounded black-box objective sequentially: it fits a Bayesian model, maximizes an acquisition function to select new queries, and balances exploration with exploitation.The objective is to approach the unknown maximizing configuration using observed function values.Source: §2 · p. 4

2.1 Modelling Assumptions

  • For real-valued black-boxes, Gaussian processes are presented as flexible surrogates that maintain calibrated uncertainty estimates.The GP is specified through a mean function, covariance kernel, and likelihood, with Gaussian observation noise typically assumed.Source: §2.1 · p. 4
  • Gaussian-process surrogates commonly assume stationary kernels and constant observation-noise variance, while heteroscedastic noise varies with the input.A homoscedastic GP can be misspecified for heteroscedastic data, and a stationary GP may fail to track non-stationary targets.Source: §2.1 · p. 4
  • The section asks whether tuning tasks are stationary and homoscedastic; tests may reject the corresponding null hypotheses even for simple tasks.The authors state that heteroscedasticity and non-stationarity require a different optimization approach from typical homoscedastic synthetic functions.Source: §2.1 · pp. 4–5

2.2 Acquisition Function & Optimisation Assumptions

  • Expected Improvement, Probability of Improvement, and Upper Confidence Bound are the three widely used myopic acquisitions considered, based on the posterior predictive distribution.The acquisitions use posterior information to balance exploration and exploitation.Source: §2.2 · p. 5
  • Practitioners often presume one acquisition is best for a task and that the GP approximates the black-box accurately, assumptions the authors say are difficult to validate in real applications.The section poses whether acquisition-function solutions conflict in hyperparameter tuning tasks.Source: §2.2 · p. 6
  • Acquisition solutions can conflict even on simple tuning tasks, and a robust formulation for acquisition maximization can improve overall performance.The authors refer to this as a response to misspecification during acquisition maximization.Source: §2.2 · p. 6

3. Modelling Assumption Analysis

The analysis tests whether common Bayesian-optimisation assumptions fit hyperparameter-tuning tasks. It finds substantial heteroscedasticity and non-stationarity, alongside conflicting acquisition optima.

3. Modelling Assumption Analysis

  • The study covers 108 classification and regression tasks with stochastic objective values, and tests for equal variance using repeated evaluations of hyperparameter configurations.For each task, the tests evaluate 50 configurations 10 times each.Source: §3 · pp. 6–7

3.2 Answers A.II.: Simple Hyper-parameter Tuning Tasks are Heteroscedastic

  • At least 66% of the 108 tasks exhibit heteroscedastic behaviour: Levene’s and Fligner-Killeen tests flag 72 and 73 tasks, respectively.Source: §3 · p. 7

3.1 Answer A.I.: Simple Hyper-parameter Tuning Tasks are Non-Stationary

  • 106/108 tasks favor input warping on log probability, with gains significant in 79/108; the authors report improved GP fit and BO performance.Source: Table 1 · p. 7, §3.1 · pp. 7–8

3.3 Answer A.III.: No Clear Winner

  • In illustrative two-dimensional cases, acquisition functions can have conflicting optima, including one function’s minimum coinciding with another’s maximum.Source: Figure 1 · p. 8, §3.3 · p. 9

3.2 Answers A.II.: Simple Hyper-parameter Tuning Tasks are Heteroscedastic

  • Output transformations yield more favorable log probability in 70/108 tasks, with gains significant in 58/108.Source: Table 1 · p. 7, §3.2 · p. 8

4. Optimising Bayesian Optimisation

HEBO combines GP input and output transformations with robust and multi-objective acquisition strategies to address heteroscedasticity, non-stationarity, model misspecification, and acquisition conflict.

4.1 Tackling Heteroscedasticity and Non-Stationarity

  • Kumaraswamy input warping and Box-Cox or Yeo-Johnson output transformations make the GP surrogate more flexible for non-stationary and heteroscedastic data.Transformation parameters are fitted from observed data; the combined model maximizes a marginal likelihood.Source: §4.1 · pp. 9–10

4.2 Tackling Acquisition Conflict & Robustness

  • The acquisition step addresses both surrogate misspecification and conflicts among acquisition functions, which can favor different query locations.The paper presents robustness and multi-objective acquisition as complementary design choices.Source: §4.2 · p. 11, §4.2.1 · p. 11, §4.2.2 · p. 12

4.2.1 A Robust Acquisition Objective

  • Instead of relying on a perfect GP or a worst-case parameter setting, the robust acquisition seeks query locations that perform well on average over surrogate models.The authors note that unconstrained max-min optimization can produce overly conservative solutions and lacks known global convergence guarantees in the non-convex, non-concave case.Source: §4.2.1 · p. 11

4.2.2 Multi-Objective Acquisition functions

  • A Pareto-front, multi-objective acquisition hedges among conflicting acquisition functions so no single acquisition dominates the selected solution.HEBO uses NSGA-II, an evolutionary solver suited to mixed real-valued and integer-valued inputs.Source: §4.2.2 · p. 12

5. Experiments and Results

Across 108 Bayesmark tasks, HEBO outperforms the evaluated competitors; the experiments also compare solver components and evaluate performance across task types and search domains.

5.1 Black-Box Functions

  • The benchmark comprises 108 model–dataset–metric tasks, evaluated over 20 random seeds using 16 iterations of eight-query batches and normalized task scores.Tasks cover regression and classification models, datasets, and loss metrics.Source: §5.1 · pp. 14–15

5.2 Black-Box Optimisation Input Variables

  • Figure 3 reports a 5% relative improvement over SOTA optimizers such as TuRBO and an 8% improvement over random search; HEBO has the largest mean and smallest score standard deviation across 108 tasks and leads on 74/108.Figure 2 reports the highest normalized mean score on 68.5% of the 108 functions.Source: Figure 2 · p. 13, Figure 3 · p. 15, §5.2 · pp. 15–16
  • The tested hyperparameter spaces mix continuous and integer variables and range from 2 to 9 dimensions.Some domains use log or logit transformations to facilitate optimization.Source: §5.2 · p. 15
  • In the 100-iteration, single-query asynchronous setting, HEBO performs best while Dragonfly-BB and BOHB-BB underperform other black-box optimizers.The authors note that asynchronous methods trade sample efficiency for speed.Source: §5.2 · p. 16

5.3 Ablation Results

  • The ablation ranking is heteroscedasticity first, followed by multi-objective acquisitions, non-stationarity, and robustness.The study evaluates components both by removing them from HEBO and by adding them sequentially to basic BO.Source: §5.3 · p. 16

6. Related Work

The related work covers input and output warping, multi-objective acquisition ensembles, and robust acquisition methods. It positions HEBO’s choices against prior approaches and describes the comparisons and ablations in Figure 4.

Bayesian optimisation in hyper-parameter tuning

  • Figure 4 compares HEBO with black-box baselines over 100 iterations at batch size 1 and tests component ablations against TuRBO and BO Base.BOHB-BB and Dragonfly-BB omit their multi-fidelity components; the ablation removes one HEBO component at a time or adds one to BO Base.Source: Figure 4 · p. 17

Non-stationarity with input warping

  • HEBO uses Kumaraswamy input warping, a generalized Beta distribution, which the authors report performed better than traditional Beta-CDF warping.They note this confirms results reported by Balandat et al. (2020).Source: §6 · p. 17

Heteroscedasticity with output transforms

  • Prior work uses input warping for non-stationary objectives, while output transformations offer an approach to heteroscedasticity through warped Gaussian processes.Output transformations have also been extended to compositions of elementary functions and normalizing flows.Source: §6 · pp. 16–17

Multi-objective acquisition ensembles

  • Multi-objective acquisition ensembles seek Pareto-efficient solutions across acquisition functions, and HEBO’s framework can use any multi-objective optimizer.The cited ensemble approach is related to portfolios of acquisition functions.Source: §6 · pp. 17–18

Robustness of acquisitions

  • Unlike prior robust Bayesian optimization methods based on max-min objectives and gradient ascent-descent, HEBO perturbs acquisition functions randomly and supports mixed-variable solutions through evolutionary solvers.The passage notes gradient-based methods require real-valued variables and are not guaranteed to converge in general non-convex, non-concave settings.Source: §6 · p. 18

7. Conclusion & Future Work

The conclusion reports that hyperparameter-tuning tasks can exhibit heteroscedasticity and non-stationarity, and highlights differences between synchronous and asynchronous methods. The appendices provide hypothesis-test details and an acquisition-perturbation approach to robustness.

7. Conclusion & Future Work

  • The study finds that even simple machine-learning problems can exhibit heteroscedasticity and non-stationarity, and reports a large discrepancy in suggestion power between synchronous and asynchronous methods.The authors propose that future work integrate the strongest aspects of both approaches.Source: §7 · p. 18

Appendix A. Addition Detail Of Hypothesis Tests

  • The appendix presents Levene’s and Fligner-Killeen test results for six datasets; the latter ranks absolute deviations from the median and is robust to outliers.The datasets are Boston, breast cancer, diabetes, digits, iris, and wine.Source: Appendix A · pp. 18–19

Appendix B. Details of Robust Acquisition

  • Randomly perturbing acquisition functions can approximate robust acquisition using only the GP predictive mean and variance, avoiding the need to access GP hyperparameters.The appendix notes this can be implemented with evolutionary solvers, whose query paths change with the random perturbations.Source: Appendix B · p. 19

B.0.1 Proof of the Robustness Bound

The proof develops a probabilistic bound for approximating a robust acquisition function with stochastic perturbations. It uses stated assumptions and a UCB acquisition function to make an otherwise intractable integral tractable.

B.0.1 Proof of the Robustness Bound

  • The proof considers a GP with mean function m(x) and covariance kθ(x, x′), and assumes bounded observations when deriving the robustness bound.The passage specifies |y| ≤ C and a desired probability threshold δ and accuracy parameter ρ.Source: §B.0.1 · p. 20
  • Because the integral is intractable, the proof substitutes the UCB acquisition function and restricts this derivation to batch size q = 1.The passage identifies UCB as the chosen approximation for the integral.Source: §B.0.1 · p. 20
  • Combining intermediate bounds yields the stated probabilistic result, supporting robust acquisition formulations based only on the GP predictive mean and variance.The appendix concludes that these formulations can be implemented without relying on GP hyperparameters.Source: §B.0.1 · pp. 22, 28

Appendix D. Task-Level Results Breakdown

The appendix describes a task-level breakdown of black-box optimizer results, reporting performance means and variances across seeds and organizing results by dataset, metric, and model.

Appendix D. Task-Level Results Breakdown

  • The task-level results summarize each black-box optimizer’s mean and variance across 20 seeds.Table 11 provides a summary plot.Source: Appendix D · p. 28
  • The breakdown covers combinations of metric, dataset, and model for each black-box optimizer.The passage describes the full task-level result breakdown.Source: Appendix D · p. 28
  • For each of six datasets, the appendix reports optimizer performance across 18 tasks: two metrics and nine models.The six datasets are listed as Boston, breast cancer, diabetes, digits, iris, and wine.Source: Appendix D · p. 28

D.1 Boston Data Set

Table 4 reports significant mean-score improvements by HEBO over competitor algorithms across 108 black-box functions. In the Boston task tables, the highest-mean optimizer varies by loss and model, though HEBO leads in many configurations.

D.1 Boston Data Set

D.2 Breast Cancer Data set

In the breast cancer tasks, the optimizer with the highest mean normalized score differs across models and metrics. HEBO leads in five listed ACC tasks and eight listed NLL tasks.

D.2 Breast Cancer Data set

D.3 Diabetes Data Set

Across the Diabetes MAE and MSE task tables, HEBO has the highest mean normalized score in several model settings, while other optimizers lead in the remaining listed settings.

D.3 Diabetes Data Set

D.4 Digits Data Set

Across the Digits, Iris, and Wine task tables, the optimizer with the highest mean normalized score varies by model and loss. HEBO leads in multiple listed configurations, alongside wins by other optimizers.

D.4 Digits Data Set

D.5 Iris Data Set

D.6 Wine Data Set

Loading 2012.03826v6…