Skip to content

Multi-objective acquisition functions

Bayesian optimization is a sample-efficient method for solving \(\min_{x \in \mathcal{X}} f(x)\) where \(f\) is a black-box function whose evaluations are expensive and possibly noisy.

When \(f\) is vector-valued, i.e. there are multiple outputs that we care to minimize, there is in general no single optimal point. Instead we have a set of optimal compromises (the Pareto front), where for each point we cannot improve any one output without worsening at least one other output.

There are two approaches for dealing with multiple objectives in the context of Bayesian optimization: 1) Use a multi-objective scalarization together with a single-objective acquisition 2) Use a multi-objective acquistion that aims for improving the knowledge of the Pareto front.

Regarding 1. the same scalarizations as in multi-objective optimization may be applied. An overview of scalarization methods in the context of Bayesian optimization is given in [Chugh2019]. Regarding 2. there is a growing list of multi-objective acquistions

Note: this post is work in progress.

Expected hypervolume improvement

Expected hypervolume improvement (EHVI), also known as S-metric-based expected improvement, is an extension of the expected improvement to multiple objectives. It's the expectation value of the improvement in hypervolume for a given candidate \(x\) with respect to the existing data \(\mathcal{D}\).

The first method to calculate EVHI was Monte Carlo integration [Emmerich2006], however the accuracy of this method strongly depends on the number of MC samples. For the 2D case an exact methods was proposed in [Emmerich2012] with complexity \(O(n^3 \log n)\), where \(n\) is the number of non-dominated points in the data set. An exact method for >2D was proposed in [Cockuyt2014] without an analysis of the complexity. [Hupkens2015] introduced a method with complexity of \(O(n^2)\) for 2D and \(O(n^3)\) for 3D. Asymptotically optimal algorithms with \(O(n \log n)\) complexity were proposed in [Emmerich2016] for the 2D case, and in [Yang2017] for the 3D case. In [Yang2019] this was extended to >4D and to the probability of improvement on the Pareto front. Codes are found here.

[Daulton2020] proposed q-EHVI (a quasi-MC formulation) with exact gradients via auto-differentiation to enable gradient based optimization. An implementation in BoTorch is anounced.