Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization

Introduction

Single-objective optimization has traditionally been the focus in the field of machine learning for many practical and interesting applications, from standard regression objectives [KNN+05] to ever-increasingly complicated losses used in deep learning [LBH15] and reinforcement learning [SB+98]. However, in the recent years, there has been a growing need to care about multiple objectives in learning and understanding the inherent tradeoffs between these conflicting objectives. Examples include classical tradeoffs such as bias vs variance [NMB+18], and accuracy vs calibration [GPSW17] but there are increasingly complex tradeoffs between accuracy and robustness to attack [ZYJ+19], accuracy and fairness [Zli15], between multiple correlated tasks in multi-task learning [KGC18], between network adaptations in meta-learning [FAL17], or any combination of the above.

Early works on scalarization include heuristic-based algorithms such as ParEgo [Kno06] and MOEAD [ZL07]. Even then, the most popular scalarizations are the linear scalarization $s_{\lambda}(y)=\sum_{i}\lambda_{i}y_{i}$ and the Chebyshev scalarization $s_{\lambda}(y)=\min_{i}\lambda_{i}(y_{i}-z_{i})$ for some reference point $z$ and some distribution over $\lambda$ [NYY09]. However, the choice of weight distribution, reference point, and even the scalarization functions themselves is diverse and largely various between different papers [PKP18, NYY09, ZL07]. Recently, some works have come up with novel scalarizations that perform better empirically [AFMPdO19, SST19] and others have tried to do comparisons between different scalarizations with varying conclusions [KOK+19]. Some have also proposed adaptively weighted approaches that have connections to gradient-based multi-objective optimization [LZL+19] .

In addition to scalarization, there are a large diverse array of multi-objective optimization rules that are often heuristic-based and lack theoretical guarantees, such as aggregation-based, decomposition-based, diversity-based, elitism-based, gradient-based, and hybrid approaches [ED18, ZLB04, KCS06]. Furthermore, many Bayesian optimization approaches have been extended to the multi-objective setting, such as predictive entropy search [HLHLSA16] or uncertainty measures [Pic15]. To our knowledge, there have been limited theoretical works that give regret and convergence bounds for multi-objective optimization. Some works show that the algorithms achieve small Pareto regret, which only guarantees that one recovers a single point close to the Pareto frontier [LWHZ19, ÖKET18, TÖT18]. For many scalarization functions, Paria et al provides a Bayes regret bound with respect to a scalarization-induced regret [PKP18] but small Bayes regret with a monotone scalarization only guarantees recovery of a single Pareto optimal point . Zuluaga et al provides sub-linear hypervolume regret bounds; however, they are exponential in $k$ and its analysis only applies to a specially tailored algorithm that requires an unrealistic classification step [ZSKP13].

In this paper, we introduce a new scalarization function, which we term the hypervolume scalarization, and present a novel connection between this scalarization function and the hypervolume indicator. We provide the first hypervolume regret bounds that are valid for common Bayesian optimization algorithms such as UCB and Thompson Sampling and can be polynomial in the number of objectives $k$ when $\mathcal{X}$ is suitably compact. This implies that our choice of scalarization functions and weight distribution $\mathcal{D}_{\lambda}$ is theoretically sound and leads to provable convergence to the whole Pareto frontier. Furthermore, we can utilize the connection of scalarization to hypervolume indicator to provide a computationally-efficient and accurate estimator of the hypervolume, providing a simple algorithm for approximating the hypervolume that easily generalizes to higher dimensions. The main lemma that we rely on in this paper is the following:

for some scalarization functions $s_{\lambda}(y)$ and fixed weight distribution $\mathcal{D}$.

Note our resulting hypervolume scalarization functions are similar to the Chebyshev scalarization approach $s_{\lambda}(y)=\underset{i}{\min}\lambda_{i}(y_{i}-z_{i})$ but they come with provable guarantees. Specifcally, using these scalarizations, we can first easily extend a single-objective optimization algorithm into the multi-objective setting: at each step, we first apply a random scalarization, then we attempt to maximize along that scalarization function via any single-objective optimization procedure to find the next suggested point. We show novel regret bounds for combining our hypervolume scalarization with popular and standard Bayesian optimization algorithms, such as Thompson Sampling (TS) and Upper Confidence Bound (UCB) methods.

If we let $x_{t}\in\mathcal{X}$ denote the point chosen in step $t$, and let $Y_{t}:=\left\{F(x_{i}):i=1,2,\ldots,t\right\}$, then the hypervolume regret at time $t$ is defined as $r_{t}:=\mathcal{HV}_{z}(Y^{*})-\mathcal{HV}_{z}(Y_{t})$, where $Y^{*}$ is the Pareto frontier. We show that our cumulative hypervolume regret at step $T$ for TS and UCB is bounded by $O(k^{2}\sqrt{\gamma_{T}T\ln T})$, where $\gamma_{T}$ is a kernel-dependent quantity known as the maximum information gain. Intuitively, the maximum information gain allows us to quantify the increase in certainty after evaluating $T$ points and is usually mild. For example, $\gamma_{T}=O(\text{poly}\operatorname{log}(T))$ for the squared exponential kernel and since $r_{t}$ is by definition monotonically decreasing, our regret bound translates immediately into a convergence bound of $\widetilde{O}(T^{-1/2})$ and we provably converge rapidly to the Pareto frontier. We note that the bound for the single-objective case can be recovered by setting $k=1$ and matches the bounds of previous work [RVR14, SKKS10]. Furthermore, since the single-objective bounds are shown to be tight up to poly-logarithmic factors [SBC17], our regret bounds are thus also tight for our dependence on $T$. Our main theorem can be stated as follows:

The cumulative hypervolume regret for using random hypervolume scalarization with UCB or TS after $T$ observations is upper bounded as

Furthermore, $\mathcal{HV}_{z}(Y_{T})\geq\mathcal{HV}_{z}(Y^{*})-\epsilon_{T}$, where $\epsilon_{T}=O(k^{2}n^{1/2}[\gamma_{T}\ln(T)/T]^{1/2})$.

Lastly, we show that if the single-objective optimization procedure admits good convergence properties, then we can solve multi-objective optimization by simply applying the single-objective procedure on sufficiently large number of randomly chosen hypervolume scalarizations. Furthermore, this method is provably correct as we can deduce hypervolume error bounds via concentration properties. Specifically, by using the single-objective procedure for $T$ iterations on $l=O(1/\epsilon^{k})$ different randomly chosen scalarizations, we can bound the hypervolume error by $\epsilon$ after the total number of observations of $T\cdot l=O(T/\epsilon^{k})$. Therefore, we present a novel generic framework that extends any single-objective convergence bound into a convergence bound for the multi-objective case that provably demonstrates convergence to the Pareto frontier. Note that these bounds hold for any algorithm but are not tight and can likely be improved, unlike those presented above in the Bayesian optimization setting.

Let $\mathcal{A}$ be any single-objective optimization algorithm with the guarantee that it converges to within $\epsilon_{T}$ of the maximum after $T$ iterations and observations.

Then, running $\mathcal{A}$ with random hypervolume scalarization converges to the Pareto frontier and admits an hypervolume error of $O(\epsilon_{T})$ after $O(T/\epsilon_{T}^{k})$ observations.

We empirically validate our theoretical contributions by running our multiobjective algorithms with hypervolume scalarizations on the Black-Box Optimization Benchmark (BBOB) functions, which can be used for bi-objective optimization problems [TBHA16]. We see that our multi-objective Bayesian optimization algorithms, which admit strong regret bounds, consistently outperforms the multi-objective evolutionary algorithms. Furthermore, we observe the superior performance of the hypervolume scalarization functions over other scalarizations, although that difference is less pronounced when the Pareto frontier is even somewhat convex.

We summarize our contributions as follows:

Introduction of new hypervolume scalarization function, with connections to hypervolume indicator and provable guarantees.

Development of simple algorithm for approximating hypervolume indicator with hypervolume scalarizations that is accurate due to good smoothness and concentration properties.

Novel hypervolume regret bounds for Bayesian optimization with UCB or TS when using hypervolume scalarization.

Derivation of convergence hypervolume error bounds for any single-objective optimization procedure when using hypervolume scalarization.

Preliminaries

Bayesian optimization uses a probabilistic model to fit to the blackbox function. Gaussian processes (GP) are a standard way to model distributions over functions and are commonly used to derive good regret bounds [WR06]. We will begin with a brief review of GPs and their role in Bayesian Optimization.

A Gaussian process, $\mathcal{GP}(\mu,\kappa)$, is a distribution over functions. In a GP, the similarity between points $x_{i},x_{j}$ are determined by the kernel function $\kappa(x_{i},x_{j})$ and for some finite set of points $X=\left\{x_{1},...,x_{m}\right\}\in\mathcal{X}$, the distribution of $f(x_{1}),...,f(x_{n})$ over $f$ is modeled as multivariate Gaussian whose covariance matrix is $\Sigma_{ij}=\kappa(x_{i},x_{j})$ and mean is given by $\mu_{i}=\mu(x_{i})$. Examples of popular kernels are the squared exponential, $\kappa(x_{i},x_{j})=\exp(-\gamma\|x_{i}-x_{j}\|^{2})$, and the Matérn kernel. The mean function, prior to receiving data, is often assumed to be zero.

When datapoints for values of $y_{i}=f(x_{i})+\epsilon_{i}$ are received with $\epsilon_{i}\sim\mathcal{N}(0,\sigma^{2})$, the GP is then updated into a posterior distribution over functions that attempts to fit the datapoints values. This is done by applying conditioning and because all relevant distribution are Gaussian, the resulting distribution is still a GP. This posterior GP induces an unique mean function $\mu(x)$ and standard deviation function $\sigma(x)$ given by the standard formulas:

where $\kappa(x,X)$ denotes the vector with entries as $\kappa(x,x_{i})$.

Examples of scalarizations are the simple linear scalarization $s_{\lambda}(y)=\sum_{i}\lambda_{i}y_{i}$ and the Chebyshev scalarization $s_{\lambda}(y)=\min_{i}\lambda_{i}(y_{i}-z_{i})$ for some input distribution $\mathcal{D}_{\lambda}$. However, these scalarizations lack provable guarantees and it is in fact known that the linear scalarization can only provide solutions on the convex part of the Pareto frontier [BV04]. Furthermore, the Chebyshev scalarization is criticized for lacking diversity and uniformity in the Pareto frontier [DD98].

Hypervolume Scalarization

In this section, we introduce our novel hypervolume scalarization function and demonstrate that the expectated scalarization value under a certain distribution of weights will give the dominated hypervolume, up to a constant factor difference. Our proof technique relies on a volume integration argument in spherical coordinates and exploits unique properties of the dominated volume. Later, we prove concentration of the empirical mean, allowing for an accurate estimator of the dominated hypervolume.

where $s_{\lambda}(y)=\underset{i}{\min}\,(\max(0,y_{i}/\lambda_{i}))^{k}$ and $c_{k}=\frac{\pi^{k/2}}{2^{k}\ \Gamma(k/2+1)}$ is a dimension-independent constant.

Intuitvely, this lemma says that although the maximization of any specific scalarization will bias the optimization to a certain point on the Pareto frontier, there is a specific combination of scalarizations with different weights such that the sum of the maximization of these scalarizations over $Y$ will give the hypervolume of $Y$. It is important for the maximization to be inside the expectation, implying that maximizing various randomized single-objective scalarizations could serve to also maximize the hypervolume, which is our ultimate objective. In fact, it is easy to see that the hypervolume of a set cannot be written solely as a maximization over the expectation of any scalarizations.

Furthermore, note that our scalarization function, similar to the Chebyshev scalarization, is a minimum over coordinates $s_{\lambda}(y)=\underset{i}{\min}\,(\max(0,y_{i}/\lambda_{i}))^{k}$. Intuitively, this minimization captures the notion that Pareto dominance is a coordinate-wise optimality criterion, as we can redefine $x_{1}$ being Pareto dominated by $x_{2}$ as $\underset{i}{\min}f_{i}(x_{2})-f_{i}(x_{1})\geq 0$.

Now that we can rewrite the hypervolume as a specific expectation of maximization of random scalarizations, we proceed to show that our random estimator has controlled variance and therefore concentrates. Specifically, we show that the hypervolume indicator can be computed efficiently via this integral formulation, providing a simple and fast implementation to give an approximation to the hypervolume indicator. Our argument relies on proving smoothness properties of our hypervolume scalarizations for any $\lambda>0$ and then applying standard concentration inequalities. We note that it is non-obvious why $s_{\lambda}(y)$ is smooth, since $s_{\lambda}(y)$ depends inversely on $\lambda_{i}$ so when $\lambda_{i}$ is small, $s_{\lambda}$ might change very fast. The full proof is in the appendix.

holds with probability at least $1-\delta$ with $s=O(B^{2k}k^{k}\operatorname{log}(1/\delta)/\epsilon^{2})$ samples.

Hypervolume Regret Bounds

In this section, we derive novel hypervolume regret bounds for Bayesian optimization with UCB and TS acquisition functions under the hypervolume scalarizations. Furthermore, we introduce an algorithmic framework to turn any single-objective optimization algorithm to a multi-objective optimization algorithm via scalarizations and show that single-objective convergence guarantees can provably translate into multi-objective convergence bounds.

For a fixed weight $\lambda$, if $X=\left\{x_{1},...,x_{m}\right\}$ is our dataset and recall $X^{*}$ is the maximal input set corresponding to the Pareto frontier $Y^{*}$, we define the scalarized regret to be

Note that Bayes regret cannot be minimized by a single point, rather it requires a set of points across the Pareto frontier to achieve a small Bayes regret. Let $X_{T}=\left\{x_{1},...,x_{T}\right\}$ be the set of chosen inputs up to time $T$. Then, we wish to bound $R(X_{T})$. We cannot analyze the Bayes regret directly. Rather, we bound it via a slightly surrogate regret measure. Let use define the instantaneous regret at time step $t$ as:

The cumulative regret at time step $T$ is then $R_{C}(T)=\sum_{t=1}^{T}r(x_{t},\lambda_{t})$. We will first bound the cumulative regret and then use the cumulative regret to bound the Bayes regret, which is a scaled version of our hypervolume regret when using hypervolume scalarizations.

Regret bounds are derived using a metric known as the maximum information gain (MIG), which captures an information-theoretic notion of uncertainty reduction of our blackbox function. For any $A\subseteq\mathcal{X}$, we define the random set $y_{A}=\left\{y_{a}=f(a)+\epsilon_{a}|a\in A\right\}$ be our noisy evaluations. The reduction in uncertainty of the distribution over functions $f$ induced by the GP by observing $y_{A}$ is given by the mutual information ${\bf I}(y_{A};f)={\bf H}(f)-{\bf H}(f|y_{A})={\bf H}(y_{A})-{\bf H}(y_{A}|f)$, where ${\bf H}$ denotes the Shannon entropy. The maximum information gain after $T$ observations is defined as :

The mutual information can also be explicitly calculated via a useful formula: ${\bf I}(y_{A};f)=\frac{1}{2}\operatorname{log}|I+\sigma^{-2}K_{A}|$, where $K_{A}$ is the $T$-by-$T$ covariance matrix of dataset A and $|\cdot|$ is the determinant operator. Using the formula, one can derive bounds of $\gamma_{T}=O((\operatorname{log}T)^{n+1})$ for the squared exponential kernel and similar bounds for the Matérn and linear/polynomial kernels for any $A$ [SKKS10]. When the maximum information gain is small, the $\mathcal{GP}$ function distribution induced by the corresponding is relatively easier to model and regret bounds are therefore tighter.

Let each objective $f_{i}(x)$ for $x\in^{n}$ follow a Gaussian distribution with marginal variances bounded by 1 and observation noises $\epsilon_{i}\sim\mathcal{N}(0,\sigma_{i}^{2})$ are independent with $\sigma_{i}^{2}\leq\sigma^{2}\leq 1$. Let $\gamma_{T,k}\leq\gamma_{T}$, where $\gamma_{T,k}$ is the MIG for the k-th objective. Running Algorithm 1 with $L$-Lipschitz scalarizations on either UCB or TS acquisition function produces an expected cumulative regret after $T$ steps that is bounded by:

where the expectation is over choice of $\lambda_{t}$ and $\mathcal{GP}$ measure.

Assume the conditions in Theorem 7 holds and let $F(\mathcal{X})\subseteq[0,2/5]^{k}$ and $z\geq 0$ and $Y_{t}=F(X_{t})$. Running Algorithm 1 with hypervolume scalarizations with reference point $z$ and $D_{\lambda}=\mathcal{S}_{+}^{k-1}$ on either UCB or TS acqusition function produces hypervolume regret after $T$ observations that is bounded by:

Furthermore, $\mathcal{HV}_{z}(Y_{T})\geq\mathcal{HV}_{z}(Y^{*})-\epsilon_{T}$, where $\epsilon_{T}=O(k^{2}n^{1/2}[\gamma_{T}\ln(T)/T]^{1/2})$.

WLOG, let $z=0$. From Lemma 5, we see that for our hypervolume scalarization, we can rewrite our regret using the Bayes regret.

Therefore, our Bayes regret is exactly a scaled version of our hypervolume regret with $c_{k}=\pi^{k/2}/(2^{k}\Gamma(k/2+1))\leq(\pi^{k/2}e^{k/2})/(2^{k}(k/2+1)^{k/2})$ with standard bounds on $\Gamma$. Next, we use the instantaneous regret to bound Bayes risk and note that $\lambda_{t}\sim\mathcal{S}_{+}^{k-1}$.

Therefore, by Theorem 7, we conclude that we can bound the Bayes and hypervolume regret by observing the following relations:

Lastly, by Lemma 6, we see that $L\leq 2^{-k}k^{1+k/2}$ and note that $c_{k}L\leq k(\pi^{k/2}e^{k/2})/(5^{k})\leq k$. Together, we finally conclude that

For the final claim, by definition of $\mathcal{HV}_{z}$ and our equivalence between $\mathcal{HV}_{z}$ and $R$, we conclude that $R(X_{t})$ must be monotonically decreasing. Our final claim follows from monotonicity and simple algebra. ∎

We note that our regret bounds hold for classical Bayesian optimization procedures that are widely used with no artificial modifications. Furthermore, we can generalize our results to show that for any single-objective optimization procedure, one can use hypervolume scalarizations to convert the procedure into a multi-objective optimization procedure via a natural extension (Algorithm 2). More remarkably, if the single-objective optimization procedure admits convergence bounds, we can immediately derive hypervolume convergence bounds by appealing to our previous connections between scalarization and hypervolume via the following theorem. Practically, this implies that any currently used single-objective optimization algorithms can be easily generalized to the multi-objective setting with minimal effort and enjoy provable convergence bounds. The full proof is in the appendix.

Let $F(\mathcal{X})\subseteq[0,B]^{k}$ and $z\geq 0$ and let $\mathcal{A}$ be any single-objective maximization algorithm on objective function $g(x)$ that guarantees that after $T$ iterations, it returns $x_{T}$ such that $g(x_{T})\geq g(x^{*})-\epsilon_{T}$, where $x^{*}$ is the optima. Then, running Algorithm 2 on hypervolume scalarizations with reference point $z$ and $D_{\lambda}=\mathcal{S}_{+}^{k-1}$ with $l=\widetilde{O}((2B)^{k^{2}}k^{k+1}/(c_{k}^{k-1}\epsilon_{T}^{k+1}))$ converges to the Pareto frontier and after $l\cdot T$ observations, we have

Experiments

We empirically demonstrate the utility of hypervolume scalarizations by running our proposed multiobjective algorithms on the Black-Box Optimization Benchmark (BBOB) functions, which can be paired up into multiple bi-objective optimization problems [TBHA16]. To emphasize the utility of a new theoretically sound scalarization, we focus on scalarization-related algorithms and comparisons were not made to the vast array of diverse multi-objective blackbox optimization used in certain practical settings. Therefore, our goal is therefore to compare scalarizations on commonly used optimization algorithms, such as UCB and evolutionary strategies. Furthermore, we note that scalarized algorithms have very fast practical runtimes and are especially relevant in settings with a low computational budget.

Our objectives are given by BBOB functions, which are usually non-negative and are minimized. The input space is always a compact hypercube $^{n}$ and the global minima is often at the origin. For bi-objective optimization, given two different BBOB functions $f_{1},f_{2}$, we attempt to maximize the hypervolume spanned by $(-f_{1}(x_{i}),-f_{2}(x_{i}))$ over choices of inputs $x_{i}$ with respect to the reference point $(-5,-5)$. Therefore, all relevant output points are contained in the square between $(-5,-5)$ and $(0,0)$, giving a maximum hypervolume of 25. Because BBOB functions can drastically different ranges, we first normalize the function by a measure of standard deviation computed by taking the empirical variance over a determinsitic set of $30$ different inputs. We also apply large random shifts/rotations as well as allow for adding moderate random observation noise to the objective function.

We run each of our algorithms in dimensions $n=8,16,24$ and optimize for $70$ iterations with $5$ repeats. Our algorithms are the Random algorithm, UCB algorithm, and Evolutionary Strategy (ES). Our scalarizations include the linear and hypervolume scalarization with the weight distribution $D_{\lambda}$ as $\mathcal{S}_{+}^{1}$. Note that for brevity, we do not include the Chebyshev scalarization because it is almost a monotonic transformation of the hypervolume scalarization with a different weight distribution. We run the UCB algorithm via an implementation of Algorithm 1 with a constant standard deviation multiplier of $1.8$ and a standard Matérn kernel, while we run the ES algorithms using Algorthm 2 with $T=1$ and $l=70$ by relying on a well-known single-objective evolutionary strategy known as Eagle [YD10].

From our results, there is a clear trend that UCB algorithms outperform both ES and Random algorithms in all cases, empirically affirming the utility of Bayesian optimization and its strong theoretical regret bounds. We believe that this is because evolutionary strategies tend to follow local descent procedures and get stuck at local minimas, therefore implicitly having less explorative mechanisms. Meanwhile, Bayesian optimization inherently promotes exploration via usage of its standard deviation estimates.

Furthermore, we see that the hypervolume scalarization slightly outperforms the linear scalarization, with UCB-Hypervolume being a clear winner in certain cases, even with Gaussian observation noise (see Fig 2). The superior performance of the hypervolume scalarization is seen in both UCB and ES algorithms (see Fig 1), and using the hypervolume scalarization is often never worse than using the linear scalarization. We note that the difference is more stark when there is no noise added, allowing for less variance when calculating the scalarization. Also, we note that when the Pareto frontier is almost convex, the difference in performance becomes hard to observe. As seen from the Pareto plot in Fig 2, we see that although UCB-Hypervolume does produce a better Pareto frontier than UCB-Linear, the convex nature of the Pareto frontier allows linear scalarizations to perform decently. A complete profile of the plots are given in the appendix.

Conclusion

We introduced the hypervolume scalarization functions and utilized its connection to the hypervolume indicator to derive hypervolume regret bounds for many classes of multi-objective optimization algorithms that rely on single-objective subroutines. Even though our scalarization function enjoys smoothness and concentration bounds, we note that possible improvements to the scalarizations can be made for variance reduction. We believe that a lower-variance and better-concentrated scalarization can be constructed that also can similar provable hypervolume error guarantees. Furthermore, it is conceivable that variance reduction techniques during the optimization process can be applied to achieve better concentration and convergence.

Furthermore, our regret bounds can likely be improved, especially the general regret bound for any single-objective optimization procedure given by Theorem 9. We believe the exponential dependence on $k^{2}$ can be improved, as well as removing the extra $l$ factor completely. However, to achieve these better convergence bounds, it will most likely require algorithmic changes. Lastly, our experiments could be improved by concocting a specific optimization with a concave Pareto frontier, looking at optimization with more than two objectives, or considering a more diverse set of algorithms. Understanding and quantifying the full impact of using random scalarizations to generalize single-objective algorithms to multi-objective algorithms is an open problem.

References

Appendix A Missing Proofs

Note that by definition of $p$ we have $p_{j}\leq y_{j}$ for all $j$ and there must exist $i$ such that $p_{i}=y_{i}$. Also $p_{j}/v_{j}=c=p_{i}/v_{i}$ for any $i,j$ since $p=cv$. It follows that $c\leq y_{j}/v_{j}$ for all $j$ and $c=y_{i}/v_{i}$, which proves $\|p\|=\min_{i}(y_{i}/v_{i})$.

Integrating in polar coordinates, we can approximate an volume via radial slivers of the circle, which for a radius $r$ sweeping through angles $d\theta$ have an volume proportional to $r^{k}d\theta$. Hence, the volume of the of the rectangle is

under a uniform measure $\theta$, where the $c_{k}$ is a constant that depends only on the dimension.

So far we assumed $y\geq 0$. Now, if any $y_{i}<0$, then our total dominated hypervolume is zero and $\min_{i}\frac{y_{i}}{v_{i}}<0$. So, by changing our scalarization slightly, we can account for any $y$ and the volume of the rectangle with respect to the origin is given by:

By definition of dominated hypervolume, note that $\mathcal{HV}_{z}(Y)=\operatorname{vol}(S)$ where

Since $S$ is simply the union of rectangles at $y_{1},...,y_{m}$ and note that wherever $p$ exists $S$, the length of $p$ is the maximal over all rectangles and so

To calculate $c_{k}$, we simply evaluate the hypervolume of the $k$-dimensional ball in the positive orthant. If the ball has radius and is centered at the origin. In this case we get $\int_{v\in\mathcal{S}_{+}^{k-1}}r^{k}d\mu(v)=r^{k}$ and $c_{k}\int_{v\in\mathcal{S}_{+}^{k-1}}r^{k}d\mu(v)=V_{k}(r)/2^{k}$ where $V_{k}(r)$ is defined as the volume of the $k$-dimensional ball of radius $r$, which is $\pi^{k/2}r^{k}\ /\ \Gamma(k/2+1)$. The formula for $c_{k}$ then follows from some basic algebra. ∎

Recall $s_{\lambda}(y)=\underset{i}{\min}(\max(0,y_{i}/\lambda_{i}))^{k}$ and $\|\lambda\|=1$. Note that there must exists $i$ such that $\lambda_{i}\geq k^{-1/2}$ and therefore $\left({\max(0,y_{i^{*}}/\lambda_{i^{*}})}\right)^{k}\leq(Bk^{1/2})^{k}$ where $i^{*}$ is the index that minimizes $\max(0,y_{i}/\lambda_{i})^{k}$. Note that the gradient of $s_{\lambda}(y)$, if non-zero, is $ky_{i^{*}}^{k-1}/\lambda_{i^{*}}^{k}$ and therefore, the Lipschitz constant is bounded by $k(Bk^{1/2})^{k}=B^{k}k^{1+k/2}$.

Since $0\leq s_{\lambda}(y-z)\leq B^{k}k^{k/2}$ for any $\lambda$ and $y$, we conclude by standard Chernoff bounds that if weight vectors $\lambda_{j}$ are independent samples,

Therefore, choosing $s=O(B^{2k}k^{k}\operatorname{log}(1/\delta)/\epsilon^{2})$ samples from $\mathcal{S}_{+}^{k-1}$ bounds the failure probability by $\delta$ and using Lemma 5, our result follows. ∎

WLOG, let $z=0$. Let $X_{T}=\underset{i}{\bigcup}\left\{x_{\lambda_{i}}^{(t)}\right\}_{t=1}^{T}$. Then, for $\lambda_{1},...,\lambda_{l}$, by the guarantees of $\mathcal{A}$, we deduce that

By Lemma 6, we see that for the Pareto frontier $Y^{*}$, we have concentration to the desired hypervolume:

when $l=O(B^{2k}k^{k}\operatorname{log}(1/\delta)/\epsilon^{2})$ with probability $1-\delta$. We would like to apply the same lemma to also show that our empirical estimate is close to $\mathcal{HV}_{z}(X_{T})$. However, since $X_{T}$ depends on $\lambda_{i}$, this requires a union bound and we proceed with a $\epsilon$-net argument.

We assume that $F(\mathcal{X})\subseteq[0,B]^{k}$ and let us divide the hypercube into a grid with spacing $\Delta$. Then, there are $O((B/\Delta)^{k})$ lattice points on the grid. Consider the Pareto frontier of any set of points, call it $S$. Out of the $(B/\Delta)^{k}$ small hypercubes of volume $\Delta^{k}$ in grid, note that by the monotonicity property of the frontier, $S$ intersects at most $(2B/\Delta)^{k-1}$ small hypercubes.

Therefore, we can find a set $S_{u}$ consisting of at most $(2B/\Delta)^{k-1}$ lattice points on the grid such that $|\mathcal{HV}_{z}(S)-\mathcal{HV}_{z}(S_{u})|\leq(2B)^{k}\Delta$. This can be done by simply looking at each small hypercube that has intersection with $S$ and choosing the lattice point that increases the dominated hypervolume. Since each small hypercube has volume $\Delta^{k}$ and there are at most $(2B/\Delta)^{k-1}$ hypercubes, the total hypervolume increased is at most $2^{k}\Delta$.

Finally, there are at most $(B/\Delta)^{k(2B/\Delta)^{k-1}}$ choices of $S_{u}$, so to apply a union bound over all possible sets $S_{u}$, we simply choose $l=O(B^{2k}k^{k+1}(2B/\Delta)^{k-1}\operatorname{log}(B/\Delta)/\epsilon^{2})$ so that for any possible $S_{u}$, we use Lemma 6 to deduce that with high probability,

Since $\mathcal{HV}_{z}(S)$ is close to $\mathcal{HV}_{z}(S_{u})$, we conclude that for any $S$,

By choosing $\epsilon=\epsilon_{T}$ and $\Delta=c_{k}\epsilon_{T}(2B)^{-k}$, we conclude.

Appendix B Figures