The case for fully Bayesian optimisation in small-sample trials

Sample efficiency is the predominant motive for use of Bayesian optimisation (BO) when optimising black-box functions that are expensive to evaluate. Function evaluations are said to be expensive when each evaluation costs a significant amount of resources including time and money. Function evaluations take place typically in the form of either real-world trials or computer simulations. While the former case clearly can be expensive, because of the lack of analytic expressions for objective functions and/or constraints, the latter case can also be expensive. For example, researchers used BO to learn robot controllers with only a handful of trials \citepchatzilygeroudis_survey_2020. Consequently, in practical applications of BO, small-sample performance is of the greatest concern.

Gaussian process (GP) is the de facto standard surrogate model for BO, and GPs must be specified in terms of kernel hyperparameters before applying BO. Since hyperparameters suitable for particular problems are rarely known beforehand, these are estimated based on observations and sequentially updated throughout the trials, commonly using type II maximum likelihood (ML-II) \citepjones_efficient_1998, mackay_comparison_1999, lalchand_approximate_2020. In practice, estimating hyperparameters with small samples is a challenging task \citepwang_theoretical_2014. In particular, maximisation of the marginal likelihood is numerically difficult because a wide range of length-scales, both very short and intermediate values, are generally consistent with small data \citeprasmussen_gaussian_2006. Several studies provide detailed accounts of how BO fails in various situations \citepjones_taxonomy_2001, forrester_global_2008,bull_convergence_2011,benassi_robust_2011. Nonetheless, despite the challenge, this is precisely the kind of problems for which researchers use BO—locating inputs that yield good enough function values using only small samples.

To address the challenge, the fully Bayesian approach has been proposed in the context of GP regression \citepohagan_curve_1978,handcock_bayesian_1993 and specifically in the context of BO \citeplocatelli_adaptive_1995,locatelli_bayesian_1997,osborne_gaussian_2009. \citetbenassi_robust_2011 demonstrated that fully Bayesian optimisation (FBO) was statistically more robust in adversarial circumstances than ML-II. However, the study imposed strong assumptions, namely, the use of conjugate prior for output-scale, the lack of automatic relevance determination, and discretisation of length-scale. In today’s hardware and software environments, these assumptions are unnecessarily restrictive and should be relaxed to obtain more general insights.

Over the past decade, a handful of studies adopted FBO that took advantage of more sophisticated algorithms and modern software platforms \citepsnoek_practical_2012,hernandez-lobato_predictive_2014,eriksson_high-dimensional_2021. However, in these studies, FBO was adopted only because it served for evaluating their theoretical claims, and no further justification for the adoption was provided \citepde_ath_how_2021. Apart from these studies, the research on FBO remains sparse, and direct comparison between ML-II and FBO is virtually non-existent in the recent literature.

This paper provides three compelling reasons why researchers should consider adopting FBO for their applications where evaluations are expensive. First, failures of ML-II are more commonplace than implied by the existing studies which used the contrived scenarios. To support this argument, the experiments are set up only using common specifications, which other researchers may find in their applications, including those of the objective function, random initialisation, models, and algorithms. Second, FBO is more robust than ML-II, and the price of the robustness is almost trivial. This is shown in the results obtained from the identical experimental settings. In addition, to make the results relevant in modern applications, the restrictive assumptions in FBO specifications previously used in the literature are relaxed. Third, thanks to the modern software platforms, FBO is now simple to implement and fast enough to be practical. To demonstrate this, the experiments are implemented using Pyro \citepbingham_pyro_2019 and BoTorch \citepbalandat_botorch_2020. In addition, the code used to implement the experiments is written deliberately in a simple fashion so that it can serve as a template for other applications. The last point is a small but practical contribution because the existing code examples for FBO found in BoTorch package are written specifically for the particular study [eriksson_high-dimensional_2021], and modification for other FBO applications is not very straightforward.

In what follows, first, BO is reviewed as a technique to address a dynamic problem, which is deemed a more accurate formulation when involving evaluation budgets. The reader is reminded that, in this formulation, an optimal solution is intractable and suboptimality of BO is by design in practical applications (Section 2). Next, FBO is reviewed where the marginalised acquisition function and its approximation are highlighted as the key difference (Section 3). Then, the experiments are described with emphasis of the roles played by Pyro and BoTorch, and the results are discussed (Section 4). Finally, some concluding remarks are provided for future applications (Section 5). All the code and data are available on the website (https://github.com/ysaikai/case4fbo).

A common formulation of the BO problem is a static optimisation problem:

where $f$ is the black-box objective function, and $X$ is a compact subset of Euclidean space. When BO is adopted in practice, however, it is often the case that function evaluations are expensive, and there is an evaluation budget. If an evaluation budget is explicitly modelled, a more accurate problem formulation is the following.

Let $N$ be the total number of evaluations allowed. Then, the BO problem is a sequential decision problem; that is, choose $x_n\in X$ for each $n\in \{1,\dots ,N\}$ based on the history, the preceding observations

in order to minimise the best observed value after $N$ evaluations:

Note that this is a dynamic problem as each choice depends on the preceding choices.

Since evaluations are allowed to be made only $N$ times, it is necessary to alternatively search for an optimal sequence $x_1^{\ast },\dots ,x_N^{\ast }$ without directly evaluating $f$. This is where the notion of surrogate comes in. When BO with a GP surrogate is used to address the problem, an implicit assumption is that $f$ is a sample path of the specified GP as a stochastic process. For the fixed GP, it is known that an optimal sequence ${\hat{x}}_1,\dots ,{\hat{x}}_N$ in terms of the Bayes risk is, in principle, obtained by dynamic programming \citepbetro_bayesian_1991. However, except for trivial cases, the problem is numerically intractable \citepbenassi_robust_2011. Furthermore, as mentioned above, specifying a suitable GP for a particular problem beforehand is rarely possible in practical problems. Instead, it is specified based on observations and sequentially updated throughout the trials.

The expected improvement (EI) acquisition function is a practical one-step lookahead strategy \citepmockus_application_1978, jones_efficient_1998. As a myopic strategy, EI is necessarily suboptimal \citepginsbourger_towards_2010 but proved reasonable in many applications \citepshahriari_taking_2015. Although many different acquisition functions have been proposed, EI maintains the practical advantage owing to the intuitive notion of “improvement”, the relatively light computational requirement, and the proven performance.

Performance of BO is dictated by the GP surrogate and the acquisition function. Since the former seems to take precedence over the latter [shahriari_taking_2015], and a GP is characterised by kernel hyperparameters, it is vitally important to carefully handle kernel hyperparameters and their uncertainty for successful BO applications. The principled way to handle parameter uncertainty is to follow the Bayesian formalism \citepgelman_bayesian_2013, according to which functions of uncertain parameters are weighted by the posterior probabilities of the parameters. (While the maximum a posteriori estimation is also used in practice to incorporate prior information, in the light of the Bayesian formalism, it does not fully reflect the parameter uncertainty and omitted in this paper.)

Let $\theta$ and $D_n$ denote respectively the hyperparameter and the data observed for the first $n$ steps. Also, let $\alpha (x|\theta ,D_n)$ and $p\left(\theta |D_n\right)$ denote respectively the acquisition function and the posterior of $\theta$. Then, the marginalised acquisition function, the weighted average according to $p\left(\theta |D_n\right)$, is

In FBO, this is the function to maximise for the next query point

In other words, due to the randomness in $\theta$, it is a stochastic optimisation problem. Since the above integral generally permits no analytic expression for $\alpha \left(x|D_n\right)$, in practice, use of approximation methods is required to carry out the maximisation. In BO contexts, the maximisation is commonly addressed by the sample average approximation \citephomem-de-mello_monte_2014, which is well supported by BoTorch as reviewed below.

Except for trivial cases, the posterior $p\left(\theta |D_n\right)$ is a complicated distribution, for which no off-the-shelf sampler is available, so it is necessary to use some approximation methods to obtain samples. Among many different methods, Hamiltonian Monte Carlo is the gold standard \citeperiksson_high-dimensional_2021 and, in particular, the No-U-Turn sampler \citephoffman_no-u-turn_2014 is an attractive option as it spares researchers the trouble of manually tuning the step size and path length in Hamiltonian Monte Carlo.

After obtaining $M$ Monte Carlo samples, the marginalised acquisition function is approximated by the finite sum:

Given $M$ samples, the right-hand side is a deterministic function, which is commonly maximised using quasi-Newton methods such as L-BFGS-B [byrd_limited_1995].

While small-sample performance is the main reason to use Bayesian optimisation when function evaluations are expensive, the standard approach based on type II maximum likelihood may fail in many practical applications. The paper made the case for fully Bayesian optimisation as a more robust and viable alternative. Thanks to the modern software and hardware technologies, the implementation is simple, and the execution is fast enough to be practical in many cases. Since the benefits seem to outweigh the costs, researchers should consider adopting fully Bayesian optimisation for their applications so that they can guard against potential failures that end up wasting precious research resources.