\section{Hypervolume Scalarization} \label{sec: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.

\begin{lemma}[Hypervolume as Scalarization]
\label{lem:hypervolume}
Let $Y = \set{y_1,..., y_m}$ be a set of $m$ points in $\R^k$. Then, the hypervolume of $Y$ with respect to a reference point $z$ is given by:
$$\HV_z(Y) = c_k \E_{\lambda \sim \Sphere^{k-1}} \left [ \max_{y\in Y} s_\lambda(y - z) \right ]$$
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.
\end{lemma}

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.

\begin{lemma}[Hypervolume Concentration]
\label{lem:concentration}
Let $Y = \set{y_1,..., y_m} \subseteq \R^k$ and $z$ be a reference point and assume for some $B
\geq 1$, we can bound $y_i \leq z + B$. Then, $s_\lambda(y)$ is $O(B^k
k^{1+k/2})-$Lipschitz for any $\lambda$ and we can independently draw
$\lambda_1, ..., \lambda_s$ such that
$$\left|\frac{1}{c_k}\HV_z(Y) - \frac{1}{s} \sum_j \max_{y \in Y} s_{\lambda_j}(y-z)\right| \leq \epsilon $$
holds with probability at least $1-\delta$ with $s = O(B^{2k}k^k\log(1/\delta)/\epsilon^2)$ samples.
\end{lemma}
{"config": "arxiv", "file": "2006.04655/scalarization.tex"}