HEBO: An Empirical Study of Assumptions in Bayesian Optimisation

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

Abstract

Bayesian Optimization (BO) is a powerful tool for optimizing expensive black-box functions, such as hyperparameter tuning in machine learning. However, standard BO implementations often rely on idealized assumptions of homoscedasticity (constant noise) and stationarity (uniform smoothness). This paper introduces the Heteroscedastic and Evolutionary Bayesian Optimisation (HEBO) framework, which challenges these assumptions through non-linear input/output warping and a multi-objective acquisition ensemble. HEBO secured first place in the NeurIPS 2020 Black-Box Optimization challenge and demonstrates superior performance across extensive benchmarks, proving that accounting for real-world data complexities is essential for robust optimization.

Introduction

In the "wild" of real-world machine learning, the functions we seek to optimize rarely behave according to the "clean" assumptions of standard Gaussian Processes (GPs). Most BO solvers assume that noise levels are constant across the search space and that the function's smoothness remains consistent. Empirical analysis reveals that these assumptions are frequently violated: at least 66% of experimental tasks in common benchmarks exhibit significant heteroscedasticity. Failing to account for these factors leads to poor surrogate models and sub-optimal search trajectories.

The HEBO Framework

HEBO is designed to be robust against the messiness of real-world optimization tasks. It introduces several key innovations:

1. Input and Output Warping

To handle non-stationarity and heteroscedasticity, HEBO transforms the search space. It applies Kumaraswamy warping to inputs and Box-Cox or Yeo-Johnson transformations to outputs. This process "warps" complex, non-linear data into a space that better aligns with the Gaussian distribution assumptions of standard GPs, allowing for more accurate surrogate modeling.

2. Multi-Objective Acquisition Ensembles

A critical insight of this work is that different acquisition functions—such as Expected Improvement (EI), Probability of Improvement (PI), and Upper Confidence Bound (UCB)—often conflict, pointing to different regions of the search space as "optimal" for the next sample.

Comparison of acquisition functions (EI, PI, UCB) across different machine learning tasks, showing how their maxima (dashed lines) often diverge.

As shown in the figure above, the peaks for EI, PI, and UCB rarely coincide. HEBO treats this as a multi-objective problem, identifying a Pareto front of candidate points to "hedge its bets" across different exploration-exploitation trade-offs.

3. Evolutionary Solver (NSGA-II)

Hyperparameter spaces often contain discrete or categorical variables that break gradient-based optimization. HEBO employs the NSGA-II evolutionary algorithm to maximize its acquisition functions, ensuring it can navigate non-continuous domains effectively.

Experimental Results

HEBO was evaluated on the Bayesmark benchmark (108 tasks across 9 models and 6 datasets) and the NeurIPS 2020 Black-Box Optimisation Challenge.

  • Challenge Performance: HEBO placed first in the NeurIPS 2020 challenge, outperforming a wide array of competitive entries.
  • Benchmark Dominance: On Bayesmark, HEBO achieved the highest normalized mean score in 68.5% of the tasks.
  • Reliability: HEBO showed a 5% relative improvement over TuRBO and an 8% improvement over random search, maintaining the highest mean scores with the lowest standard deviation.

Ablation studies highlighted that output warping was the most significant contributor to performance gains, followed by the multi-objective acquisition strategy.

Conclusion

HEBO demonstrates that the standard assumptions of Bayesian Optimization are often too restrictive for practical applications. By incorporating robust warping techniques and a multi-objective approach to acquisition, HEBO provides a more reliable and efficient framework for hyperparameter tuning. Future work will explore deeper surrogate models and improved integration with trust-region methods to further enhance sample efficiency in high-dimensional spaces.

Summary updated

BibTeX
@article{cowenrivers2022hebo,
  author = {Alexander I. Cowen-Rivers and Wenlong Lyu and Rasul Tutunov and Zhi Wang and Antoine Grosnit and Ryan-Rhys Griffiths and Alexandre Max Maraval and Jianye Hao and Jun Wang and Jan Peters and Haitham Bou-Ammar},
  title = {{HEBO: An Empirical Study of Assumptions in Bayesian Optimisation}},
  journal = {J. Artif. Intell. Res.},
  year = {2022},
  doi = {10.1613/jair.1.13643},
}
Figure