\begin{document}
\maketitle


\begin{abstract}
Single-objective black box optimization (also known as zeroth-order
optimization) is the process of minimizing a scalar objective $f(x)$, given evaluations at adaptively chosen inputs $x$. In this paper, we
consider multi-objective optimization, where $f(x)$ outputs a vector of
possibly competing objectives and the goal is to converge to the Pareto frontier. Quantitatively, we wish to maximize the standard \emph{hypervolume indicator} metric, which measures the dominated hypervolume of the entire set of chosen inputs. In this paper, we introduce a novel scalarization function, which we term the \emph{hypervolume scalarization}, and show that drawing random scalarizations from an appropriately chosen distribution can be used to efficiently approximate the \emph{hypervolume indicator} metric. We utilize this connection to show that Bayesian optimization with our scalarization via common acquisition functions, such as Thompson Sampling or Upper Confidence Bound, provably converges to the whole Pareto frontier by deriving tight \emph{hypervolume regret} bounds on the order of $\widetilde{O}(\sqrt{T})$. Furthermore, we highlight the general utility of our scalarization framework by showing that any provably convergent single-objective optimization process can be effortlessly converted to a multi-objective optimization process with provable convergence guarantees.
\end{abstract}

\section{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 \cite{kutner2005applied} to ever-increasingly complicated
losses used in deep learning \cite{lecun2015deep} and reinforcement learning
\cite{sutton1998introduction}. 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 \cite{neal2018modern}, and accuracy
vs calibration \cite{guo2017calibration} but there are increasingly complex
tradeoffs between accuracy and robustness to attack
\cite{zhang2019theoretically}, accuracy and fairness
\cite{zliobaite2015relation}, between multiple correlated tasks in multi-task
learning \cite{kendall2018multi}, between network adaptations in meta-learning
\cite{finn2017model}, or any combination of the above.

To understand and visualize a growing number of complex tradeoffs, many turn to multi-objective optimization, which is the maximization of $k$ objectives
$F(x) := (f_1(x), ... , f_k(x))$ over the parameter space
$x\in \X \subseteq \R^n$. Since one often cannot simultaneously maximize all $f_i$, multi-objective
optimization aims to find the entire \emph{Pareto frontier} $\F$ of the objective
space, where intuitively $x$ is on the Pareto frontier if there is no way to
improve on all objectives simultaneously. To measure progress, a natural and widely used metric
to compare Pareto sets is the \emph{hypervolume indicator}, which is the volume of the
dominated portion of the Pareto set \cite{zitzler1999multiobjective}. The
hypervolume metric is especially desirable because it has strict Pareto
compliance meaning that if a set $A \subseteq B \subset \R^k$, then the
hypervolume of $B$ is greater than that of $A$. While the hypervolume indicator satisfies strict Pareto compliance, almost all other unary metrics do not, thereby explaining the popularity of using hypervolume as the predominant measure of progress
\cite{zitzler2003performance}.

While the hypervolume indicator remains the gold standard in evaluating
multi-objective algorithms, note that it is a function of a set of
objective vectors and not just a single evaluation. This means evolutionary algorithms often cannot use
the hypervolume as a fitness score although some discretized version exist
\cite{emmerich2005emo}. Furthermore, it is computationally inefficient: the best
current asymptotic runtime calculating the hypervolume indicator in $\R^k$ is
$O(n^{k/2})$ via a reduction to Klee's Measure Problem
\cite{beume2006faster}. This cannot be substantially sped up as hypervolume
calculation is shown to be {\bf $\#$P}-hard  
and even approximating the hypervolume improvement by a $O(2^{d^{1-\epsilon}})$ factor is {\bf
  NP}-hard for any $\epsilon > 0$ \cite{bringmann2010approximating}. For $k \leq 3$, fast albeit
complicated algorithms exist \cite{yang2019efficient}.

Due to the difficulty of using the hypervolume directly, many multi-objective
optimization problems use a heuristic-based scalarization strategy, which splits
the multi-objective optimization into numerous single "scalarized" objectives
\cite{roijers2013survey}. For some weights $\lambda \in \R^k$, we have
scalarization functions $s_\lambda(y) : \R^k \to \R$ that convert
multi-objective outputs into a single-objective scalars. Bayesian optimization
is then applied to this family of single-objective functions $s_\lambda(F(x))$
for various $\lambda$ and if we construct $s_\lambda$ to be monotonically
increasing in all coordinates, then $$x_\lambda = \arg\max_{x \in \X}
s_\lambda(F(x))$$ is on the Pareto frontier \cite{paria2018flexible}.

Early works on scalarization include heuristic-based algorithms such as ParEgo
\cite{knowles2006parego} and MOEAD \cite{zhang2007moea}. 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$
\cite{nakayama2009sequential}. However, the choice of weight distribution,
reference point, and even the scalarization functions themselves is diverse and
largely various between different papers \cite{paria2018flexible,
  nakayama2009sequential, zhang2007moea}. Recently, some works have come up with
novel scalarizations that perform better empirically \cite{aliano2019exact,
  schmidt2019min} and others have tried to do comparisons between different
scalarizations with varying conclusions \cite{kasimbeyli2019comparison}. Some
have also proposed adaptively weighted approaches that have connections to
gradient-based multi-objective optimization \cite{NIPS2019_9374} .

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 \cite{emmerich2018tutorial,
  zitzler2004tutorial, konak2006multi}. Furthermore, many Bayesian optimization approaches have been extended to the multi-objective setting, such as predictive entropy search \cite{hernandez2016predictive} or uncertainty measures \cite{picheny2015multiobjective}.  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 \cite{lu2019multi, oner2018combinatorial,turugay2018multi}. For
many scalarization functions, Paria et al provides a Bayes regret bound with
respect to a scalarization-induced regret \cite{paria2018flexible} 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 \cite{zuluaga2013active}.


\subsection{Our contributions}

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 $\X$ is suitably compact. This implies that our choice of scalarization functions and weight distribution $\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:

\begin{lemma}[Hypervolume Scalarization: Informal Restatement of Lemma~\ref{lem:hypervolume}]
  Let $Y = \set{y_1,.., y_m}$ be a set of $m$ points in $\R^k$ and let $z \in
  \R^k$ be a reference point such that $y_i \geq z$ for all $i$. Then, the
  hypervolume $\HV_z(Y)$ of $Y$ with respect to $z$ is given by:
  $$\HV_z(Y) := c_k \E_{\lambda \sim \D} \left [ \max_{y \in Y} s_\lambda(y - z) \right ]$$
  for some scalarization functions $s_\lambda(y)$ and fixed weight distribution $\D$.
\end{lemma}

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 \X$ denote the point chosen in step $t$, and let
$Y_t := \set{F(x_i) : i = 1, 2, \ldots, t}$, then the \emph{hypervolume regret} at
time $t$ is defined as $r_t := \HV_z(Y^*) - \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}\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
\cite{russo2014learning, srinivasgaussian}. Furthermore, since the single-objective bounds are shown to be tight up to poly-logarithmic factors \cite{scarlett2017lower}, our regret bounds are thus also tight for our dependence on $T$.  Our main theorem can be stated as
follows:

\begin{theorem}[Convergence of Bayesian Optimization with Hypervolume Scalarization: Informal Restatement of Theorem~\ref{thm:hyper_regret}]
The cumulative hypervolume regret for using random hypervolume scalarization with UCB or TS after $T$ observations is upper bounded as
$$\sum_{t=1}^T (\HV_z(Y^* ) - \HV_z(Y_t)) \leq O(k^2 n^{1/2} [ \gamma_T T\ln(T)]^{1/2})$$
Furthermore, $\HV_z(Y_T) \geq \HV_z(Y^*) - \epsilon_T$, where $\epsilon_T = O(k^2 n^{1/2} [ \gamma_T \ln(T)/T]^{1/2})$.
\end{theorem}

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.

\begin{theorem}[Convergence of General Optimization with Hypervolume Scalarization: Informal Restatement of Theorem~\ref{thm:hyper_regret_general}]
Let $\alg$ 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 $\alg$ 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. 
\end{theorem}
 
 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 \cite{tuvsar2016coco}. 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:
\begin{itemize}
    \item Introduction of new hypervolume scalarization function, with connections to hypervolume indicator and provable guarantees.
    \item Development of simple algorithm for approximating hypervolume indicator with hypervolume scalarizations that is accurate due to good smoothness and concentration properties.
    \item Novel hypervolume regret bounds for Bayesian optimization with UCB or TS when using hypervolume scalarization.
    \item Derivation of convergence hypervolume error bounds for any single-objective optimization procedure when using hypervolume scalarization.
\end{itemize}
\input{prelim.tex}
\input{scalarization.tex}
\input{regret.tex}


\section{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 \cite{tuvsar2016coco}. 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 $[-5,5]^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.
\begin{figure}[H]
\vskip 0.2in
\begin{center}
\centerline{\includegraphics[width=3in]{hypervolume_plot4}}
\centerline{\includegraphics[width=3.1in]{hypervolume_plot3}}
\caption{Dominated hypervolume plot of bi-objective optimization of SCHWEFEL and ELLIPSOID BBOB functions in 24D with no and Gaussian observation noise. Notice that Hypervolume scalarization is slightly better than Linear scalarization in both UCB and ES algorithms and this is more stark in the noiseless case.}
\label{fig:hypervolume_plot3}
\end{center}
\vskip -0.2in
\end{figure}

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 $\Sphere^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~\ref{alg:scalarization} with a constant standard deviation multiplier of $1.8$ and a standard Mat\'ern kernel, while we run the ES algorithms using Algorthm~\ref{alg:scalarization_general} with $T  = 1$ and $l = 70$ by relying on a well-known single-objective evolutionary strategy known as Eagle \cite{yang2010eagle}.


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~\ref{fig:hypervolume_plot1}). The superior performance of the hypervolume scalarization is seen in both UCB and ES algorithms (see Fig~\ref{fig:hypervolume_plot3}), 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~\ref{fig:hypervolume_plot1}, 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.


\begin{figure}[h]
\vskip 0.2in
\begin{center}
\centerline{\includegraphics[width=3in]{hypervolume_plot1}}
\centerline{\includegraphics[width=3.1in]{paretoplot.png}}
\caption{Dominated hypervolume and Pareto plot of bi-objective optimization of ELLIPSOID and SPHERE BBOB functions in 24D with no (UNSET) observation noise. Notice that the UCB algorithms outperform the ES algorithms and the Hypervolume scalarization is slightly better. Also, when comparing UCB-Hypervolume (blue points) and UCB-Linear (pink points) in the Pareto plot, the Hypervolume scalarization is slightly better and never suggests points that are significantly sub-optimal, although the difference is not very stark because of the convex nature of the Pareto frontier.}
\label{fig:hypervolume_plot1}
\end{center}
\vskip -0.2in
\end{figure}

\section{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~\ref{thm:hyper_regret_general}. 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. 


\newpage

\bibliographystyle{alpha}
\bibliography{main}


\appendix 
\newpage
\input{supplementary.tex}


\end{document}
{"config": "arxiv", "file": "2006.04655/main.tex"}