Optimal Scalarizations for Sublinear Hypervolume Regret
Authors: Qiuyi Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: multiobjective optimization
scalarization
hypervolume
Primary area: optimization
TL;DR: Hypervolume scalarizations with uniformly random weights achieves optimal sublinear hypervolume regret.

Abstract: Scalarization is a general, parallizable technique that can be deployed in any multiobjective setting to reduce multiple objectives into one, yet some have dismissed this versatile approach because linear scalarizations cannot explore concave regions of the Pareto frontier. To that end, we aim to find simple non-linear scalarizations that provably explore a diverse set of $k$ objectives on the Pareto frontier, as measured by the dominated hypervolume. We show that hypervolume scalarizations with uniformly random weights achieves an optimal sublinear hypervolume regret bound of $O(T^{-1/k})$, with matching lower bounds that preclude any algorithm from doing better asymptotically. For the setting of multiobjective stochastic linear bandits, we utilize properties of hypervolume scalarizations to derive a novel non-Euclidean analysis to get regret bounds of $\tilde{O}( d T^{-1/2} + T^{-1/k})$, removing unnecessary $\text{poly}(k)$ dependencies. We support our theory with strong empirical performance of using non-linear scalarizations that outperforms both their linear counterparts and other standard multiobjective algorithms in a variety of natural settings.

Optimal Scalarizations for Sublinear Hypervolume Regret
Qiuyi (Richard) Zhang Google Deepmind qiuyize com
Abstract
Scalarization a general, parallizable technique that can be deployed in any multi- objective setting reduce multiple objectives into one, yet some have dismissed this versatile approach because linear scalarizations cannot explore concave regions of the Pareto frontier. To that end, aim to find simple non-linear scalarizations that provably explore diverse set of k objectives on the Pareto frontier, as mea- sured by the dominated hypervolume. We show that hypervolume scalarizations with uniformly random weights achieves an optimal sublinear hypervolume regret bound of (T--//k) with matching lower bounds that preclude any algorithm from doing better asymptotically. For the setting of multiobjective stochastic lin- ear bandits, we utilize properties of hypervolume scalarizations to derive a novel -on-Euclidean analysis to get regret bounds of Ö + TTT-/kk removing unnecessary poly(A dependencies. We support our theory with strong empirical performance of using non-linear scalarizations that outperforms both their linear counterparts and other standard multiobjective algorithms in variety of natural settings.
Introduction
Optimization objectives in modern Al systems becoming complex with many different components that must be combined to perform precise tradeoffs in machine learning models. Starting from standard Ep regularization objectives in regression problems [Kutner et al. 2005 to increasingly multi-component losses used in reinforcement learning (Sutton et 19998 and deep learning [LeCun]
et al. 2015], many of these single-objective problems are phrased scalarized form of inherently k-objective problem.
Scalarization Method. Practitioners often vary the weights of the scalarization method, with the main goal of exploring the entire Pareto frontier, which the set of optimal objectives that cannot be simultancously improved. First, chooses
weights À R and scalarization functions sx(v) : * + that convert multiple objectives F(a) := (fi (a), fx (a)) over some parameter space E C Rdd into single-objective scalar. Optimization single-objective functions sx (z)(z) for various À and since we often choose 5 to be monotonically increasing in all coordinates, æ arg max sx (a)) is on the Pareto frontier and the various choices of À recovers approximation to the Pareto frontier [Paria et al. 2018).
then applied to this family of
Due to its simplicity of use, many have turned heuristic-based based scalarization strategy to pick the family of scalarizer and weights, which efficiently splits the multi-objecting optimization into numerous single "scalarized" optimizations [Roijers et al. (2013). Linear scalarizations with varying weights are often used in multi-objective optimization problems, such as in multi-objective reinforce- ment learning combine task reward with the negative action norm [Abdolmaleki al. [202T] or in RLHF to align responses with human preferences Ouyang et al. 2022]. However, the appeal of
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

using scalarizations in multiobjectivv optimization declined as linear scalarizations are shown to be provably incapable of exploring the full Pareto frontier [Boyd and Vandenberghe 2004].
Beyond Linear Scalarization. To address this, some works have proposed piecewise linear scalar- izations inspired by economics (Busa-Fekete et al. 2017), while for multi-armed bandits, scalarized knowledge gradient methods empirically perform better with non-linear scalarizations (Yahyaa et al., 2014]. The classical Chebyshev scalarization has been shown to be effective in many settings, such as evolutionary strategies Qi et al. [014]) Li et al. [20T6]. general blackbox optimization [Kasim- beyli et al. 2019 or reinforcement learning Van Moffaert et al. [2013]. Other works have come up with novel scalarizations that perform better empirically in some settings [Aliano Filho et al. 2019] Schmidt et al.) 2019]. There also have been specific multi-objectivv algorithms tailored to specific settings such as ParEgo [Knowles] 2006) and MOEAD (Zhagg and Li, 22077 for black box optimization or multivariate iteration for reinforcement learning (Yang et al. 2019]. Furthermore, many adaptive reweighting strategies have been proposed in order to target or explore the full Pareto frontier, which have connections to gradient-based multi-ohjective optimization [Lin et al. 2019] Abdolmaleki et al.) 2021]. However these adaptive strategies are heuristic-driven and hard to compare, while understanding simple oblivious scalarizations remain very important especially in batched settings where optimizations are done heavily in parallel Gergel and Kozinov [2019].
Hypervolume Regret. To determine optimality, natural and widely used metric to measure progress of an optimizer is the hypervolume indicator, which is the volume of the dominated portion of the Pareto set [Zizzler and Thiele 1999]. The hypervolume metric has become gold standard because it has strict Pareto compliance meaning that if set A is a subset of B and B has at least one Pareto point not in A, then the hypervolume of B is greater than that of A. Unsurprisingly, multiobjective optimizers often use hypervolume related metrics for progress tracking or acquisition function, such as the Expected Hypervolume Improvement (EHVI) or its differentiable counterpart [Daulton et al. 2020 Hupkens et al. [ Only recently has some works provide sub-linear hypervolume regret bounds which guarantees convergence to the full Pareto frontier; however, they are exponential in & and its analysis only applies to specially tailored algorithm that requires an unrealistic classification step Zuluaga et al.) 2013). We draw inspiration on work by [Golovin and Zhang 2020) that introduces random hypervolume scalarizations but their work does not consider the fimite-sample regime and their regret bounds are in the blackbox setting, where the convergence rate quantifies the statistical convergence of the Pareto frontier estimation.
1.1 Our Contributions
We show, perhaps surprisingly, that a simple ensemble of nonlinear scalarizations, known as Hyper- volume scalarizations, are theoretically optimal to minimize hypervolume regret and are empirically competitive for general multiobjective optimization. Intuitively, we quantify how fast scalarizations can approximate the Pareto frontier under finite samples even with perfect knowledge of the Pareto frontier, which is the white-box setting. Specifically, as the hypervolume scalarization has sharp level curves, they naturally allow for the targeting of a specific part of the Pareto frontier, without any assumptions on the Pareto set or the need for adaptively changing weights. Additionally, we can oblivously explore the Pareto frontier by choosing T maximizers of randomly weighted Hypervolume scalarizations and achieve sublinear hypervolume regret rate of O1kk), where T is the number of points sampled.
Sublinear Hypervolume Regret. Given any set of objectives Y that are explicitly provided, our goal to choose points on the Pareto frontier in a way to maximize the hypervolume. In this white-box setting, we introduce the notion of the hypervolume regret convergence rate, which is both function of both the scalarization and the weight distribution, and show that the maxima of Hypervolume scalarization with uniform i.i.d. weights enjoy O(T-l/k) hypervolume regret (see Theorem 7). In fact, our derived regret rate of the Hypervolume scalarization holds for all frontiers, regardless of the inherent multiobjective function F or the underlying optimizer. Therefore, we emphasize that analyzing these -agnosic rates can be a general theoretical tool to compare and analyze the effectiveness of proposed multiobjective algorithms. Although many scalarizers will search the entire Pareto frontier as T + co, the rate at which this convergence occurs can differ significantly, implying that this framework paves the road for theoretical standard by which to judge the effectiveness of advanced strategies, such as adaptively weighted scalarizations.

---

Lower bounds. On the other hand, we show surprisingly that no multioojecctive algorithm, whether oblivious or adaptive, can beat the optimal hypervolume regret rates of applying single-objective optimization with the hypervolume scalarization. To accomplish this, we prove novel lower bounds showing one cannot hope for better convergence rate due to the exponential nature of our regret, for any set of 'T points. Specifically, we show that the hypervolume regret of any algorithm after T actions is at least 22TT-//k), demonstrating the necessity of the O(T-l/k) term up to small constants in the denominator. As a corollary. we leverage the sublinear regret properties of hypervolume scalarization to transfer our lower bounds to the more general setting of scalarized Bayes regret. Together, we demonstrate that for general multiobjective optimzation, finding maximas of the hypervolume scalarizations with a uniform weight distribution optimally finds the Pareto frontier asymptotically.
Theorem 1 (Informal Restatement of Theorem 7 and Theorem 8). Let YT = {yi..... .r) J be a set of yEy X (V) with X; ~ S+ randomly drawn i.i.d from an uniform distribation and HV are hypervolume scalarizations. Then, the hypervolume regret satisfies
T points in Re such that yi E arg max HV
HV()") +)V(Y))= O(T
where y is the Pareto frontier and HV is the hypervolume function. Furthermore, any algorithm for choosing these T points must suffer hypervolume regret of at least ((T=k).
Scalarized Algorithm for Linear Bandit. Next, we use a novel non-Euclidean analysis to prove improved hypervolume regret bounds for our theoretical toy model: the classic stochastic linear bandit setting. For any scalarization and weight distribution, we propose a new scalarized algorithm (Algorithm I) for multiobjective stochastic linear bandit that combines uniform exploration and exploitation via an UCB approach to provably obtain scalarized Bayes regret bounds, which we then combine with the hypervolume scalarization to derive optimal hypervolume regret bounds. Specifically, for any scalarization sy, we show that our algorithm in the linear bandit setting has scalarized Bayes regret bound of of the (-) the f, norm. Finally, by using hypervolume scalarizations and exploiting their 6x-- smoothness, we completely remove the dependence on the number of objectives, k, which had polynomial dependence in previous regret bound given by Golovin and Zhang [020].
+ T where Lp is the Lipschitz constant
Theorem (Informal Restatement of Theorem ITI. For the multiobjectivee linear bandit problem, let Ar S A be the actions generated by T rounds of Algorithm 1 then our hypervolume regret is bounded by:
HV=(0- A) (0* S O(dT
+ +
Experiments. Guided by our theoretical analysis, we empirically evaluate a diverse combination of scalarizations and weight distributions in multiple natural settings. First, we consider synthetic optimization that is inspired by our theoretical derivation of hypervolume regret when the entire Pareto front is known and analytically given. Thus we can explicitly calculate hypervolume regret as a function of the number of Pareto points chosen and compare the regret convergence rates of multiple scalarizations with the uniform St distribution with & = 3 objectives, for easy visualization. This is important since when k = 2, we show that the Chebyshev and Hypervolume scalarizations in fact equivalent.
In our setup, we consider synthetic combinations of concave, convex, and concave/convex Pareto frontiers in each dimension. As expected, non-linear Hypervolume and Chebyshev scalarizations enjoy fast sublinear convergence, while the performance of the Linear scalarization consistently lacks behind, surprisingly even for convex Pareto frontiers. We observe that generally the Hypervolume scalarization does better on concave Pareto frontiers and on some convex-concav frontiers, while the Chebyshev distribution have faster hypervolume convergence in certain convex regimes.
For multiobjective linear bandits, our experiments show that for many settings, despite having a convex Pareto frontier, applying linear or Chebyshev scalarizations naively with various weight distributions leads to suboptimal hypervolume progress, especially when the number of objective increase to exceed & 2 5. This is because the non-uniform curvature of the Pareto frontier, exaggerated by the curse of dimensionality and combined with stationary weight distribution, hinders uniform progress in exploring the frontier. Although one can possibly adapt the weight distribution to the varying curvature of the Pareto frontier when it is convex, the use of simple non-lines scalarizations allow for fast parallelization and are theoretically sound.
3

---

For general multiobjective optimization, we perform empirical comparisons on BBOB benchmarks for bi-ojective functions a bayesian optimization setting, using classical Gaussian Process models [Williams and Rasmussen 2006]. When comparing EHVI with hypervolume scalarization approaches, we find that EHVI tends to limit its hypervolume gain by over-focusing on the central portion of the Pareto frontier, whereas the hypervolume scalarization encourages diverse exploration of the extreme ends.
We summarize our contributions as follows:
Show that hypervolume scalarizations optimizes for the full Pareto frontier and enjoys sublinear hypervolume regret bounds of O(T-1/k), theoretical measure of characterizing scalarization effectiveness in the white-box setting.
Establish a tight lower bound on the hypervolume regret for any algorithm and Bayes regret ( 1/4) 1/k) by a packing argument on the Pareto set.
Introduce optimization algorithm for multiobjectivv lincar bandits that achieves improved 1/2 + T-1/4) hypervolume regret via a novel non-Euclidean regret analysis and metric entropy bounds.
Empirically justify the adoption of hypervolume scalarizations for finding diverse Pareto frontier in general multiobjective optimization via synthetic, linear bandit, and blackbox optimization benchmarks.
2 Problem Setting and Notation
For scalarization function 8x (x)),, 8x is L,p-Lipschizz with respect to x in the bp norm on X' C Bd for æı, 22 E X. (x1) ) - (x(22) S T.p 1 - T2 pl and Lx analogously for in the Fuclidean norm. We let S
{y E R ||al| = 1, y > 0} be the sphere in the positive orthant and by abuse of notation, we also let y St denote that y is drawn uniformly on St-1, Our usual settings of the weight distribution
st-1 will be uniform, unless otherwise stated.
For outputs y, = y R$ say that y is Pareto-dominated by if S and there exists such that yj < 2j. where y S. z is defined for vectors clement-wise. A point is Pareto- optimal if no point the output space y can dominates it. Let denote the set of Pareto-optimal points (objectives) in V, which is also known as the Pareto frontier. Our main progress metrics for multiobjective optimization is given by the standard hypervolume indicator. For S S RR* compact, let vol(S) be the regular hypervolume of S with respect to the standard Lebesgue measure.
Definition 3.
For set y of points in RR,, define the (dominated) hy pervoluu indicator of with respect to reference point 2 as:
HV) = vol(fa ( x 2 2, is dominated by some y E y))
We can formally phrase optimization objective as trying to rapidly minimize the hypervolume Let A be our action space and for some general multi-objective function F, let J be the image of A under F. Let Ar E TR. be any matrix of T actions and let Y F(Ar) RTx be the & objectives corresponding. Then, the hypervolume regret of actions Ar, with respect to the reference point 2, is given by:
Hypervolume- Regrettt)r HV*()') HV,
which is 0 for all z if and only if Y. contains all unique points in )
For various scalarizations and weight distributions, an related measure of progress that attempts to capture the requirement of diversity in the Pareto front is scalarized Bayes regret for some scalarization function 8Λ. For some fixed scalarization with weights X, 8) R R. the instantancous scalarized (psuedo-)regee Jregret as r(sx, a.) max (F)()) (x)()))) To capture diversity and progress, we will vary À according some distribution non-negative weight vectors and define regret with respect with respect to all past actions A,. Specifically, we define the (scalarized) Bayes regret with respect set of actions A, to be: BR(s), A,) = ExwD (max.5A S) (F(a)) - max sx(F(a))] ExND mminrti (Sx, a))
define

---

Unlike previous notions of Bayes regret in literature, we are actually calculating the Bayes regret of reward function that maximized with respect to an entire set of actions A,, Specifically, by maximizing over all previous actions, this captures the notion that during multi-objective optimization our Pareto set is always expanding. We will see later that this novel definition is the right one, as generalizes to the multi-objective setting in the form of hypervolume regret.
2.1 Scalarizations for Multiobjective Optimization
For multiobjective optimization, we generally only consider monotone scalarizers that have the property that if y > 2, then (y) 8x (2) for all X. Note this guarantees that optimal solution to the scalarized optimization on the Pareto frontier. A common scalarization used widely in practice the linear scalarization: S (y) A y for some chosen positive weights À R By Lagrange duality and hyperplane separation of convex sets, one can show that any convex Pareto frontier can be characterized fully by optimal solution for some weight settings.
However, linear scalarizations cannot recover the non-convex regions of Pareto fronts since the linear level curves can only be tangent to the Pareto front in the protruding convex regions (see Figure Ip. To overcome this drawback, another scalarization that is proposed is the Chebyshev scalarization: 5%% minAyy: Indeed,
show that the sharpness of the scalarization, due to its minimum operator, can discover non-convex Pareto frontiers.
Proposition 4 (Emmerich and Deutz (0088). For point y² E y for convex V, there exists X >> O 8 such that y arg max LIN (y). For a point y² E 3 for any possibly non-convex set y that lies in yEy the positive orthant, there exists À such that yf" arg max Sx (y)
yEy
Convox
Non-convex
Linear
Aamee 2 mosaa por is Manrey
Non-
linear
Ohigher better)
Figure 1: Left: Comparisons of the scalarized minimization solutions with various weights with convex and non-convex Pareto fronts. The colors represent different weights; the dots are scalarized optima and the dotted lines represent level curves. Linear scalarization does not have an optima in the concave region of the Pareto front for any set of weights, but the non-linear scalarization, with its sharper level curves, can discover the whole Pareto front (Figure from (Emmerich and Deutz (018)). Right: The dotted red lines represent the level curves of the hypervolume scalarization with À discovering b, whereas the linear scalarization would prefer a or c. Furthermore, the optima exactly the Pareto point that is in the direction of v.
3 Hypervolume Scalarizations
In this section, we show the utility and optimality of a related scalarization known as the Hyper-
volume scalarization, Ny (v) min(y,/A,)) that was introduced in Golovin and Zhang [2020]
To gain intuition, we visualize the non-linear level curves of the scalarization, which shows that our scalarization targets the portion the Pareto frontier in the direction of À for any À > (see Figure I. since the tangent point of the level curves of the scalarization is always the vector in the direction of This implies that with an uniform distribution on X, we are guaranteed to have uniform spread of Pareto points in terms of its angular direction.
5

---

Dominated Hypervolume (grey)
Dominated Hypervolume (grey)
(Higher is
Metric (Higher is
Metric (higher better)
Metric (higher better)
Figure 2: The hypervolume scalarization taken with respect to direction w corresponds to a differential area clement within dominated hypervolume and averaging over random directions is analogous to integrating over the dominated hypervolume in polar coordinates. We exploit this fact show that by choosing the maximizers of T random hypervolume scalarizers, quickly converge to the hypervolume of the Pareto frontier an optimal rate of O1kk) Figure from [Song et al. 2024
Lemma 5. For any point y" on the Pareto frontier of any set y that lies in the positive orthant, there exists such that y² = arg max HV (y). Furthermore, for any ar such that ax on the DEy
Pareto frontier, then at arg max (z).
yEy
This scalarization additionally has the special property that the expected maximized scalarized value under uniform weight distribution on S gives the dominated hypervolume, up to a constant scaling factor. Thus, the optima of the hypervolume scalarization over some static uniform distribution will be provably sufficiently diverse for any Pareto set in expectation.
Lemma 6 (Hypervolume in Expectation [Golovin and Zhang 2020). Let Y (y1, yr) be set of points in R Then, the hypervolume with respect to reference point is given by:
HV=(YT) Ck A-
E
HV 8 YEYT
max
(y
2)
4/2 where C 2 T(k/2+1) is constant depending only k.
While this lemma is useful in the infinite limit, supplement it by showing that finite-sample bounds on the strongly sublinear hypervolume convergence rate. In fact, many scalarizations will eventually explore the whole Pareto frontier in the infinite limit, but the rate which the exploration improves the hypervolume is not known, and may be exponentially slow. We show that the optimizing hypervolume scalarizations with uniform weight distribution enjoys sublinear hypervolume regret, specifically O 1/k) hypervolume regret convergence rates for any Pareto set y Note that this rate is agnostic of the underlying optimization algorithm or Pareto set, meaning this a general property of the scalarization.
Our novel proof convergence uses generalization argument connect hypervolume-scallriieedd Bayes regret and its finite sample form, exploiting the Lipschitz properties of sff to derive metric entropy bounds. Proving smoothness properties of our hypervolume scalarizations for any with À normalized on the unit sphere is non-obvious sIV (y) depends inversely on X; so when X; is small, HV might change wildly.
Theorem 7 (Sublinear Hypervolume Regret). Let Y (yr,.., yr be of points in I such that yi E arg max HV Xx (y 2) with respect to a reference point z and B S y4 B,, Then,
yEy
with probability at least 8 over X; S+ ii.dd, the hypervolume of Y with respect to satisfies

---

sublinear hypervolume regret in T:
HV=(0/) - HV 0(T सo + vin(1/8)T
where O hides constant factors in k. Bus Bv.
For 2, this also holds when Chebyshev scalarization is used: yi E arg max $ CS (y) - 2).
yey
We note that the distribution of Pareto points selected by the Chebyshev scalarizer is quite similar to the Hypervolume scalarizer as the formulas are almost identical, except for the inverse weights of the latter. In fact, we show that when k 2. both scalarizers behave the same and enjoy strong convergence rates; however for 2, the Pareto distributions are in fact different under St and we can empirically observe the suboptimality of the Chebyshev scalarizer. By definition, using the inverse weight distribution with the Chebyshev scalarizer will be equivalent to applying the Hypervolume scalarizer.
3.1 Lower Bounds and Optimality
The dominating factor our derived convergence rate is the O(T-1/(k+1)) term and we show that this cannot be improved. Over all subsets Yr S y of size T, note that optimal convergence rate is given by the the subset that maximizes the dominated hypervolume of Yr. although finding this is in fact a NP-hard problem due to reduction to set cover. By constructing lower bound via novel packing argument, we show that even this optimal set would incur at least (((-1//k) regret, implying that our convergence rates, derived from generalization rates when empirically approximating the hypervolume, are optimal.
Specifically, we show that for hypervolume regret, any algorithm cannot achieve better than O(T-1/((-1)) regret even when using linear objectives, and this matches the dominating factor in our algorithm up to a small constant in the denominator. By using hypervolume scalarizations and its connection to hypervolume regret, we conclude that this also implies a (((T lower bound on the scalarized Bayes regret.
Theorem 8 (Hypervolume Regret Lower Bound). There exists setting of linear objective parameters O' and A {a ||a|| = 1} such that for any actions AT, the hypervolume regret at after T rounds is
HV=(0* - HV=(0*AT) = OT xT))
Corollary 9. There a setting of objectives O' and A = {a : ||al| 13 such that for any actions Ar, the scalarized Bayes regret after T rounds is
BR( Ar) ((T
4 Multiobjective Stochastic Linear Bandits
We propose simple scalarized algorithm for linear bandits and provide novel fp analysis of the hypervolume regret that removes the polynomial dependence on in the scalarized regret bounds. When combined with the foo sharpness of the hypervolume scalarization, this analysis gives an optimal Odd/VT) bound on the scalarized regret, up to log(k) factors. This log dependence on A: is perhaps surprising but is justified information theoretically since each objective is observed separately. Note that our scalarized algorithm works despite of noise in the observations, which makes it difficult to even statistically infer measures of hypervolume progress. Our setup and algorithm given in the Appendix (see Section Ap.
By using the confidence ellipsoids given by the UCB algorithm, can determine each objective parameter , up to small error. To bound the scalarized regret, we utilize the E, smoothness of 8), L,p to reduce the dependence on & to be OK2//P), which effectively removes the polynomial dependence on & when p + oo. This perhaps not surprising, since each objective observed independently and fully, so the information gain scales with the number of objectives.
7

---

Lemma 10. Consider running EXPLOREUCB (Algorithm 1 for TorT: I max(k, d) iterations and for TT' even, let arr be the action that maximizes the scalarized UCB iteration T/2. Then, with probability at least - 6, the instantaneous scalarized regret can be bounded by
log(k/6) + (Tg
r(sx, aT) S 10k L
T
where Lp is the lp Ep-iisschitz constant for sx(-).
Finally, connect the expected Bayes regret with the empirical average of scalarized regret via uniform convergence properties of all functions of the form f()) maxs (+*a). By using !IV and setting oo, we derive our final fast hypervolume regret rates for stochastic linear bandits, which the combination of the scalarized regret rates and the hypervolume regret rates.
aEA
Theorem 11 (HyperVolume Regret of EXPLOREUCB). Let I& be reference point such that over all E A. B, S O*a - S B.. Then, with constant probability, rumning Algorithm 7 with (y) and S+ gives hypervolume regret bound, for k constant,
(Tg(T) T
HV=(0*A) (+) S0
dv
T
5 Experiments
In this section, we empirically justify our theoretical results by comparing hypervolume conver- gence curves for multiobjective optimization in synthetic, linear bandit and blackbox optimization environments with multiple scalarizations and weight distributions, Our empirical results highlight the advantage of the hypervolume scalarization with uniform weights maximizing the diversity and hypervolume of the resulting Pareto front when compared with other scalarizations and weight distributions, especially when there are a mild number of output objectives Our experiments are not meant to show that scalarizations is the best way to solve multiobjective optimization; rather, it is a simple yet competitive baseline that is easily parallelized in a variety of settings. Also, we use slightly altered form of our hypervolume scalarization as $ (y) min y: X, which is simply
monotone transform and does not inherently affect the optimization. All emror bars are given between the 30 70 percentile over independent repeats.
5.1 Synthetic Optimization
Our synthetic optimization benchmarks assume the knowledge of y and the Pareto frontier and thus we can compute the total hypervolume and compare the hypervolume regret of multiple scalarizations with the uniform S+ distribution. For our experiments, we fix our weight distribution and compare the three widely types of scalarizations that were previously mentioned: the Linear, Chebyshev, and the Hypervolume scalarization. We focus on the
setting and apply optimization for diverse set of Pareto frontiers in the region x, y E [0, 1], > O. We discretize our region into 30 points per dimension form discrete Pareto frontier and set our reference point to at [-c, -,, -c] for
le-4 and run for 10 repeats.
The synthetic Pareto frontiers that we are consider are a product of 1-dimensional frontiers and specifically, = g(x) s(y), where g(x) = exp(-z), exp(x)) cos(TTT) + 1, which form a concave, convex. and concave/convex Pareto frontiers respectively. Now that since the derivatives of these functions are all negative in our feasible region, is a valid Pareto front. From our combination of functions, we observe that both Hypervolume and Chebyshev scalarizations enjoy fast convergence, while the performance of the Linear scalarization consistently lacks behind, surprisingly even for convex Pareto frontiers (see full plots in C.T. Interestingly, we observe that generally the Hypervolume scalarization does better on concave Pareto frontiers and on some frontiers; however since these are static algorithms, is not surprising that the Chebyshev distribution can perform better in certain convex regimes. However, we still advocate the usage of the hypervolume indicator as guaranteed to have uniform spread especially when the number of objectives increased, shown by our later experiments.

---

z explxx
expl-x
Hypar mevervalume Begrat
0.6
0.4
0.2
0.6
theay
00
0.2
0.4
0.6
0.8
0.2
200
of Pareta Points
Figure 3: Comparisons multiple scalarizations for the synthetic concave Pareto frontier given by exp(-r y). The hypervolume regret for Linear is constant, and the Hypervolume enjoys faster regret convergence rate than the Chebyshev.
5.2 Stochastic Linear Bandits
We run Algorithm and compare scalarization effects for the multiobjective linear bandit setting. We our reference point be z 2 in ls dimension space, since our action of A = ||a|| = and our norm bound on O* ensures that our rewards are in [1,
In conjunction with the scalarizer, uniformly across the unit sphere. In addition, we also compare this with the bounding box distribution methods that were suggested by [Paria et al. 2018). which samples from the uniform distribution from the min to the max each objective and requires some prior knowledge of the range of each objective (Hakanen and Knowles 2017]. Given reward bounds,
weight distribution D = S4, which samples vectors
the bounding box of [-1,]] 1] for each of the & objectives. Following their prescription for weight sampling, we draw our weights for the linear and hypervolume scalarization uniformly in [1, 3] and take inverse for the Chebyshev scalarization. We name this the boxed distribution for each scalarization, respectively.
To highlight the differences between the multiple scalarizations, we configure our linear bandits parameters to anti-correlated, which creates convex Pareto front with non-uniform curvature. Note that perfect anti-correlated Pareto front would be linear, which would cause linear scalarizations to always optimize at the end points. We start with simple & = case and let 0g be random and 0, -0g + 7J. where 77 is some small random Gaussian perturbation (we set the standard deviation to be about 0.1 times the norm of 02). We renormalize after the anti-correlation to ensure | = We algorithm with inherent dimension d for T 100, 200 rounds with k 2, 6, 10.
As expected, we find the hypervolume scalarization consistently outperforms the Chebyshev and linear scalarizations, with linear scalarization as the worst performing (see Figure 4). Note that when we increase the output dimension of the problem by setting & 10, the hypervolume scalarization shows more distinct advantage. The boxed distribution approach of [Paria et al.] 2018 does not seem to fare well and consistently performs worse than its uniform counterpart. While lincar scalarization provides relatively good performance when the number of objective k 5. it appears that as the number objectives increase in multi-objective optimization, more care needs to be put into the design of scalarization and their weights due the curse of dimensionality. since the regions of non-umt non-uniformity will exponentially increase. We suggest that as more and more objectives are being added to modern machine learning systems, using smart scalarizations is critical to an uniform exploration of the Pareto frontier.
5.3 BBOB Functions
We empirically demonstrate the competitiveness of hypervolume scalarizations for Bayesian Opti- mization by comparing them to the popular BO method EHVI (Hupkens et al. 2015). Running our proposed multiobjective algorithms the Black-Boo Optimization Benchmark (BBOB) functions,

---

22-22-2--
200
Boar affine
Figure 4: Comparisons of the cumulative hypervolume plots with some anti-correlated 0. When the output dimension increase, there is a clearer advantage to using the hypervolume scalarization the linear and Chebyshev scalarization. We find that the boxed weight distribution does consistently worse than the uniform distribution.
which can be paired up into multiple bi-objective optimization problems (Tušar et al., 2016]. Our goal is to use wide set of non-convex benchmarks to supplement our experiments on our simple toy example of linear bandits. For scalarized approaches, we use hypervolume scalarizations with the scalarized UCB algorithm with constant standard deviation multiplier of 1.8 and all algorithms with use Gaussian Process the underlying model with a standard Matérn kernel that is tuned via ARD Williams and Rasmussen 20066..
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)"h and the global minima is often at the origin. For bi-objective optimization, given two different BBOB functions f1, f2, we attempt to maximize the hypervolume spanned by (-fi(xa) (x:). ff (2x)) over choices of inputs x; with respect to the reference point (-5, 5). We normalize each function due to the drastically different ranges and add random observation noise. We also apply vectorized shifts of the input space of 2, -2 on the two functions respectively, so that the optima of each function do not co-locate at the origin.
We run each of our algorithms in dimensions d 8, 16, 24 and optimize for 160 iterations with repeats. From our results, we see that both EHVI and UCB with hypervolume scalarizations are competitive the BBOB problems but the scalarized UCB algorithm seems be able explore the extreme ends of the Pareto frontier, whereas EHVI tends to favor points in the middle (see Appendix and Figure 5). From our experiments, this trend appears be consistent across different functions and is more prominent as the input dimensions d increase.
10

---

References
Michael H Kutner, Christopher J Nachtsheim, John Neter, William Li, et al. Applied linear statistical models, volume 5. McGraw-Hill Irwin Boston, 2005.
Richard S Sutton, Andrew G Barto, et al. Introduction to reinforcement learning, volume 2. MIT press Cambridge, 1998.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436 444, 2015.
Biswajit Paria, Kirthevasan Kandasamy, and Barnabás Póczos. A flexible framework for multi- objective bayesian optimization using random scalarizations. arXiv preprint 1rXiv:1805.12166 2018.
Diederik M Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley, A survey of multi- objective sequential making. Journal of Artificial Intelligence Research, 48:67-113, 2013.
Abbas Abdolmaleki, Sandy H Huang, Giulia Vezzani, Bobak Shahriari, Jost Tobias Springenberg, Shruti Mishra, Dhruva TB, Arunkumar Byravan, Konstantinos Bousmalis, Andras Gyorgy, et al. On multi-objective policy optimization as a tool for reinforcement learning. arXiv preprint arXiv:2106.08819, 2021.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744, 2022.
Stephen Poythress Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, Cambridge, 2004. ISBN 0-521-83378-7.
Róbert Busa-Fekete, Balázs Szörényi, Paul Weng, and Shie Mannor. Multi-ohjective bandits: Optimizing the generalized gini index. In International Conference on Machine Learning, pages 625-634. PMLR, 2017.
Saba Q Yahyaa, Madalina M Drugan, and Bernard Manderick. The scalarized multi-objective multi- armed bandit problem: An empirical study of its exploration vs. exploitation tradeoff. In 2014 International Joint Conference Neural Networks (IJCNN), pages 2290-2297. IEEE, 2014.
Yutao Qi, Xiaoliang Ma, Fang Liu, Licheng Jiao, Jianyong Sun, and Jianshe Wu. Moea/d with adaptive weight adjustment. Evolutionary computation, 22(2):231-264, 2014.
Hui Li, Qingfu Zhang, and Jingda Deng. Biased multiobjective optimization and decomposition algorithm. IEEE transactions cybernetics, 47(1):52-66, 66, 2016.
Refail Kasimbeyli, Zehra Kamisli Ozturk, Nergiz Kasimbeyli, Gulein Dine Yalcin, and Banu Iemen Erdem. Comparison of some scalarization methods in multiobjective optimization. Bulletin of the Malaysian Mathematical Sciences Society, 42(5):1875-1995 2019.
Kristof Van Moffaert, Madalina M Drugan, and Ann Nowé. Scalarized multi-objective reinforcement learning: Novel design techniques. In 2013 IEEE symposium on adaptive dynamic programming and reinforcement learning (ADPRL), pages 191-199. IEEE, 2013.
Angelo Aliano Filho, Antonio Carlos Moretti, Margarida Vaz Pato, and Washington Alves de Oliveira. An exact scalarization method with multiple reference points for bi-objective integer linear opti- mization problems. Annals of Operations Research, pages 1-35, 2019.
Marie Schmidt, Anita Schöbel, and Lisa Thom. Min-ordering and max-ordering scalarization methods for multi-objective robust optimization. European Journal of Operational Research, 275 (2):446-459, 2019.
Joshua Knowles. Parego: hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEFE Transactions on Evolutionary Computation, 10(1): 50-66, 2006.

---

Qingfu Zhang and Hui Li. Moea/d: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on evolutionary computation. 11(6):712-731, 2007.
Runzhe Yang, Xingyuan Sun, and Karthik Narasimhan. generalized algorithm for multi cojtti-objectivee reinforcement learning and policy adaptation. Advances in Neural Information Processing Systems, 32, 2019.
Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qing-Fu Zhang. and Sam Kwong. Pareto multi- task learning. In Advances in Neural Information Processing Systems 32, pages 12037- 12047. Curran Associates, Inc., 2019. URL http://papers nips. cc/paper/
9374 caxreto-multin setrreoommmm---teeeeeeeemennnno
Victor Gergel and Evgeny Kozinov. Parallel computations for various scalarization schemes in multicriteria optimization problems. In International Conference on Parallel Processing and Applied Mathematics, pages 174-184. Springer, 2019.
Eckart Zitzler and Lothar Thiele. Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE transactions on Evolutionary Computation, 3(4):257-271, 1999.
Samuel Daulton, Maximilian Balandat, and Eytan Bakshy. Differentiable expected hypervolume improvement for parallel multi-objective bayesian optimization. Advances Neural Information Processing Systems, 33:9851 196644 2020.
Iris Hupkens, André Deutz, Kaifeng Yang, and Michael Emmerich. Faster exact algorithms for computing expected hypervolume improvement. international conference on evolutionary multi-criterrion oplimization, pages 65-79. Springer, 2015.
Marcela Zuluaga, Guillaume Sergent, Andreas Krause, and Markus Püschel. Active learning for multi-objective optimization. International Conference on Machine Learning, pages 462-470, 2013.
Daniel Golovin and Qiuyi Zhang. Random hypervolume scalarizations for provable multi-objective black box optimization. arXiv preprint arXiv:2006.04655, 2020.
Christopher Williams and Carl Edward Rasmussen. Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA, 2006.
Michael TM Emmerich and André H Deutz. A tutorial on multiobjective optimization: fundamentals and evolutionary methods. Natural computing, 17(3)5855600, 2018.
Xingyou Song. Qiuyi Zhang, Chansoo Lee, Emily Fertig, Tzu-Kuo Huang. Lior Belenki, Greg Kochanski, Setarch Ariafar, Srinivas Vasudevan, Sagi Perel, et al. The vizier gaussian process bandit algorithm. arXiv preprint arXiv:2408.1 11527, 2024.
Jussi Hakanen and Joshua D Knowles. On using decision maker preferences with parego. In Optimization, pages 282-297. Springer,
International Conference on Evolutionary 2017.
Tea Tušar, Dimo Brockhoff, Nikolaus Hansen, and Anne Auger. Coco: the bi-objective black box optimization benchmarking bboob-biobj) test suite. ArXiv e-prints, 2016.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexitie: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
Lee-Ad Gottlieb, Arych Kontorovich, and Robert Krauthgamer. Adaptive metric dimensionality reduction. Theoretical Computer Science, 620:105- 2016.
Yasin Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:23 12-2320, 2011.
12

---

A Linear Bandit Setup and Algorithm
For theory, use the classic stochastic linear bandit setting. For the single-objective setting, in round = 1, 2, ..., T. the and receives a reward 8/2 = .a) + & where & is i.i.d a-sub-Gaussian noise and 0* E Rd is the unknown true parameter vector. In the multi-ohjective stochastic linear bandit setting, the learner chooses an action d, E Rd from the action set A and receives vectorized reward 3/2 = aa + ft. where θ" E R is now a matrix of k unknown true parameters and & E R is vector of independent 1 I-sub-Gaussian noise. We assume, for sake of normalization, that ||;; l| I and that ||au]| S 1, where || denotes the lz norm unless otherwise stated. Other norms that are used include the classical e, norms || Ilp and matrix norms ||>]|M = x. Ma for a positive semi-definite matrix M.
We also denote A, Rdxt to be the history action matrix, whose i-th column is ag, the action taken in round i. Similarly, y: is defined analogously. Finally, for sake of analysis, we assume that A contains an isotropic set of actions and specifically, there C A with size |3| O(d) such that Σ; ese; II where denotes the PSD ordering on symmetrie matrices. This assumption is not restrictive, as it can be relaxed by using optimal design for least squares estimators [Lattimore] and Szepesvári, 2020) and the Kiefer-Wolfrowiit Theorem (Kiefer and Wolfowitz 1960). which guarantees the existence and construction of an uniform exploration basis of size ((poly(d)).
Algorithm 1: EXPLOREUCB (T, D,
Input: number of maximum actions T, weight distribution scalarization 8A repeat
Play action e, E for n = i mod d
Let Cui be the confidence ellipsoid for θ and let UCB:(a) = maxpec, aTa Draw X ~ D, play a" argmax (x(UCB,(o))
until number of rounds i exceed T/2
B Missing Proofs
Proof of Lemma 5 Let À /ll"" Note that À >> O since y" is in the positive orthant and for the sake of contradiction, assume there exists z such that ex(2) > sx(x".. However, note that for any i, # 2 min; # > min; 3f yf where the last line follows since y />; = ||''|| for all i by construction. Therefore, we conclude that y² 2, contradicting that y" is Pareto optimal.
X
Finally, note that if aA on the Pareto frontier, then see that min; a A and furthermore, this min value is achieved for all i. Therefore, since aA is on the Pareto frontier, any other point y E y has some coordinate j such that yj < adyy, which implies that min, yı/ <
Let us denote 82 NV is the hypervolume scalarization and WLOG let 0. Note that we can first decompose our regret as
Proof of Theorem 7
HV=0"* - -VV=(0) s 1702()"" HV-00))
ck Σr max (x) + +1 Σl max 8x (v) T
< (1)=00/ - ΣL_ (x, E max sx, (v) HV==0+11
where the second inequality uses the fact that yi arg maxs (v). We proceed bound both parts vEy
separately and we note that it suffices to prove uniform concentration of the empirical sum to the expectation, as by choice of scalarization is the hypervolume by Lemma
Let (>,) = max,eY 82, (y). We let F = {/r Y C A} be our class of functions over all possible output sets Y. We will first demonstrate uniform convergence by bounding the complexity of F. Specifically, by generalization bounds from Rademacher complexities Bartlett and Mendelson 2002 over choices of X; D, we know that with probability 1 6, for all Y, we have the bound
13

---

1 m
8 ln(2/6)
E AnD
[fr]
Σ fr()
(m)
m
where Rem (F) = Ex.~D,a
sup 2 fEF
>, (x)
where or are i.i.d #1 Rademacher variables.
To bound Rm (F), appeal Dudley's integral formulation that allows the metric entropy of F. to bound
log(N(c, FF,F, 12)) 12
Ru (F)
inf a20
de
m
where N denotes the standard covering number for under the le function norm metric over À D.
Since D is the uniform distribution over S+,, this induces natural &o function norm metric on J. that >0 supxes, [-())]- By Lemma 15 since y; is bounded below and above by Bu, B respectively, (x is LA Lipschitz with respect to the Euclidean norm in A. Note that since the maximal operator preserves Lipschitzness, fx (A) is also Lx Lx-Lisschitz with respect to À E R for any Y. Since FF contains L -Lipschitz functions in 12 we can bound the metric entropy via covering of À via a Lipschitz covering argument (see Lemma 4.2 of Gottlicb et al. (2016)), so we have
log(N(c, l12)) s log(A((,, F,,, Il>))) - (4Tx/e)* log(8/k)
Finally, we follow the same Dudley integral computation of Theorem 4.3 of Gottlieb et al. 2016 to get that
(4Lx/c)* log(8/k)
Rm (F) < inf
4a + 12
de
asu
T
=((Ls/m//(+H))
Therefore, we conclude that with probability at least 8 over the independent choices of x ~ D. for all Y and setting m T
T
1
E A
max Ss (0
=
max SA (Q'a) YEY
aEY
T
1=1
LA T1/(++1) +
8ln(2/8)
0
T
where B is some loo upper bound on the output set Y. Finally, we conclude by using Lemma 6loo replace the expectation by the hypervolume and by setting Y yr respectively.
Now consider the case when & 2 and are using the Chebyshev scalarizer & We claim that the distribution Y, = {y1,... } is the same and specifically let denote that random variable over the choice of ~ S_ that corresponds to y arg max s (y). Then, note that standard yEy
way to draw a random weight on S+ to draw random absolute Gaussians and then renormalize, so if n2 = Σ, X. where X; are i.i.d. Gaussian, then Y = arg max min( yEy
[Xl A yı, [Xll 12). Note
that the optimization of the arg-max is unaffected by positive scalar multiples of the objective, so multiplying by R² /(Xxx (x2))
f gives Y = arg max min( 31, (x,732) Note since X,.X, ye>
i..d., conclude that Y is the same distribution the random variable that is given by
14

---

y E arg max HV (v). Since monotone transforms of the objective does not change the arg-max yEy distribution, we conclude.
B.1 Proofs of Lipschitz Properties
Again, recall that for a scalarization function (x)), 82 is LypLipschitz with respect to x in the ép norm on X for 22, X, (1x 5 (12)) - Lp x2l1p- and analogously for define LA for p 2 so |sx, (z) sxg [z)l S - - >2112- We utilize the fact that if 8 is differentiable
everywhere except for a finite set, bounding Lipschitz constants is equívalent to bounding the dual norm V gg. where 1/p + 1/q = 1, which follows from mean value theorem, which we state as
Proposition 12
Proposition 12. Let f : + R be continuous function that is differentiable everywhere except finite set, then if [+))ll I Lo all x E X, ((x is Lp-Lipshitz with respect to the Ep norm.
Lemma 13. Let (1) XTy be the linear scalarization with ||a|| < 1 and |!v|l>o S 1. Then, we may bound L, S max (1/// 1/0) and Lx S Vkk and |sxl Vk.
Proof of Lemma 13 Since VASA(I) = y, we use Proposition 12 to bound LA & max, ll S Vk|ll//loo = Vk. Similarly, since V yys X, we may bound for p S 2, L, S ||\|, s |||| I for 1/p + 1/9 = and for p 2 2, we may use Holder's inequality to bound Lp I | S k1/0- 1/ & k1/2-1/p.
To bound the absolute value of 8xs note 8x(1) = ATy s vk for all since llvlla V Villeuloo Vl.
S
17
Lemma 14. Let sx(y) = min, Aay be the Chebyshev scalarization with ||||| s 1 and llvllso S 1. Then, we may bound Lp S. and L, I and |sx| - 1/Vk.
Proof of Lemma 14] For a specific X, y, let i" be the optimal index of the minimization. Then, the gradient V xx)x is simply zero in every coordinate except at i", where it is y:.. Therefore, since we can only have finite number of discontinuities due to monotonicity, we use proppoosiiioon 12 bound TA S ye < 1. Similarly, since V (y) has only one non-zero coordinate except at i", which is X we may bound for I., S Ap S 1.
To bound the absolute value of 8x, note that there must exists X < 1/VK as |/ S 1. Thus, min; Agy < 1//VI for l| S 1.
Lemma 15. Let (x(r) = min((y//2s be the hypervolume scalarization with ||||| = and Bh-1
0< Bi < y < B,, Then, we may bound L, S B and LA S B,K 1773 and |sx] S
B
B p472
Proof of Lemma 15 For specific X, let i be the optimal index of the minimization. Then, the gradient V Vxsx(z) is simply zero in every coordinate except at i", which in absolute value is k />x. (1/A=-).
Let.j be the index such that by is maximized and since ||||| we know that A, 2 1/Vk. Therefore, we see that since />. I / I us/v Vk, we conclude that 1/Ac- I (B./Bi) VT.
Therefore, using Proposition 12 we have Lx S B++1
S k(B./ /V/ Kb) (B./B)
vk
And similarly, since V vysx(y) has only one non-zero coordinate except at 1 which is k(yz ( (1/Ast), we may bound for
L, < k(yt- />x- -1 k(B./VB)
(B./B)) vk
B
B
To bound the absolute value of sx. note that sx(y) < Bi <
15

---

B.2 Proofs for Linear Bandits
The following lemma about the UCB ellipsoid borrowed from the original analysis of linear bandits.
Lemma 16 Abbasi- Yadkori et al. (2011). Consider the least squares estimator 0₂ = A.v Yt. where the covariance matrix of the action matrix is M, A, A + XI, then with probability
100 - 0 1MM S vAl10*1I + 2 log( 8 + dlog(T/A)
Proof Lemma 10, Let Or be the least squares estimate of the true parameters after observing (Ar.yr) y. Since the noise & in each objective independent and 1-sub-Gaas Gaussian,, by Lemma 16 we Mt ATAT AI, then with regularization X
1 - |l S + 2 log(k/0) + d Dr
holds with probability at least - 8/k. Note that this describes the confidence ellipsoid, Cri {0 Rd |/Or: 0g Mr S Dr} for Ors-
By the definition of the UCB maximization of ar, we see a, Θ argmax max0,EC7: (x,07a) a). Note that since @* Cr, we can bound the instantaneous scalarized regret as:
r(sx; a+) max # (0* 8x sx((aa))) - -x
aEA
By the Lipschitz smoothness condition, we conclude that r55,, ax) Lp -*)aelll
To bound the desired E, norm, first note that by triangle inequality, ||0, 101|Mr S 2DDT. Since apply uniform exploration every other step and Σ, ege, 1 for e E & with size [9
conclude that Mr = I. Therefore, we conclude that ||θr; θi - 5 = ET with probability at least 1-8/k. Since ||a,ll 1, conclude by Cauchy- Schwarz, that 1 )aal s
Er. Together with our Lipschitz condition, we conclude that
r(sx, at) S 1/ Inp S 10K L.pd (log(k/0) log(T))
Theorem 17. Assume that for any E A, (s)(Oaa) B for some B and 8x. is I, Lxp-hiistitt with respect to the & norm in X. With constant probability, the Bayes regret of running Algorithm Mar round T can be bounded by
AT) 5 kb Lpdyy
log(kT) T
BL T
Proof of Theorem 17 For any set of actions A C A, we define fA) max (x"aaa). We
let F [A : A C A} be our class functions over all possible action sets and for any Bayes regret bounds, we will first demonstrate uniform convergence by bounding the complexity of F. Specifically, by generalization bounds from Rademacher complexities |Brtlettt and Mendelson 2002] over choices of X ~ D. we know that with probability 6, for all A, have the bound
1 m
8 ln(2/8)
E [fA] AND
m Σ (A(A))
S (m)
m
where Rm,(F) = Ex,ND.o,
sup 2 E, E(o(((s)) /EF
where o, are i.i.d. +1 Rademacher variables.
m
16

---

To bound Rm (F), we appeal to Dudley's 's integral formulation that allows us to use the metric entropy of JF bound
log(N Fc, 112))
Rm (F) S inf 4a 12
a>0
m
where N denotes the standard covering number for F under the & function norm metric over À D.
Since D is the uniform distribution over S+, this induces natural & function norm metric F that is Il = supxes, (f()). Since xx (0*a) a) is Lx Lipschitz with respect to the Euclidean norm in A. Note that since the maximal operator preserves Lipschitzness, fA(A) is also L Lx-Liscchitz with respect to E R Since F contains Lx-Lipschitz functions in TR we can bound the metric entropy via covering of À via Lipschitz covering argument (see Lemma 4.2 of Gottlieb et al. (2016) so
we have
log(N(e,, Il2)) z log(A Fl ll>))) z (4Lx/e)* log(8/k)
Finally, we follow the same Dudley integral computation of Theorem 4.3 of Gottlieb al. 2016 to get that
/- V
(ALa/e) log(8/k) m
Rm (F) S inf
4a 12
de
az0
=O(Lx/mm/Uttt)
=
Therefore, we conclude that with probability at least - 8 over the independent choices of A ~ D. for all A,
max aEA
S (0*a)
max S (0*a) aEA
ADD
m
BLx m m//(k+1)
8 (1/(8
0
m
Finally, note that for even, with constant probability,
BR(s,, A.) E
AND (SAA Ad)
E mmax SA (Q'a)
AND aEA
aEAT
T/2
Σ
max (0)a)
max 8x, (TTa) dEAr
T/2
REA
BL
+0
[1+++
T/2
Σ
max 81, (0"a) -800--xx.. (0* (0tazi)
7/2
aEA
BL
+0
T1/(H+1]
T/2
BLd
((8,,, (2s) +0
T/2
(1/(k+1)
log(kT"
BL
00
L
+
T
T1/(++17
17

---

where the last line used Lemma 10 with 1/T and applied a union bound over all O(T) iterations.
Proof of Theorem 17 Note that by Lemma 6 we connect the Bayes regret to the hypervolume regret for D
HV- -O
E mmx 8 (0"a)) max 82 (0*a)] AND aed
aEAr
where (v) min; (wi - 2z/
Note that since ||*ta|x < for all a E A and B is maximal, we have B 3 2 S B 22 Therefore, we conclude by Lemma 15 that 9y is Lipschitz with
B + 2)
(B 2B+
(B + 2)
p - Bk4/2-T.
Lr <
3k(k-1177 |sx| <
kh/2
Finally, we combine this with Theorem 17 with p = oo as the optimal choice p (since Lp does not depend on p) to get our desired bound on hypervolume regret.
Proof of Theorem 8 We let {a ||||| s }} be the unit sphere and θ = eg be the unit vector directions. Note that in this case the Pareto frontier is exactly s
Consider uniform discretization of the Pareto front by taking an grid with respect to each angular component with respect to the polar coordinates. Let ..., Pm be the center (in terms of each of the k -1 angular dimensions) in the m = (((1/)/f-) grid elements. We consider the output Yr Ar and assume that for some grid element it contains none of the T outputs yr. Since our radial component r = 1, by construction of our grid in the angular component, we deduce that c/10 by translating polar to axis-aligned coordinates.
min; 11 - Polloo >
Let é' = </10. Assume also that t < pi < 1 -. -. Next, we claim that the hypercube from - é e//k² to is not dominated by any points in Yr. Assume otherwise that there exists y, such that 8/ 2 p: e/kk. Now, this combined with the fact that since min; ||y= Pilloo impllis that there must exist coordinate such that Vtj Pj +e'.
However, this implies that
Σ (p: - -1/222 + (p5 + +2²
Vei z
ig
Σ p - 2(((k12)
p: + 22 > Σ
if1
where the last inequality follows since E. < 1/V and pj > 1 by assumption. However, this not dominated.
contradicts that ||yal| < so it follows that p;
Therefore, for any grid element such that > 1/k: if there is no in the grid, we must have hypervolume regret at least D(c"k) = 2((*)) be simply consider the undominated hypervolume from P: to p: c', which lies entirely within the grid element. fact, since there are ((1/c)*-) such grid elements satisfying p. 1/k, we see that if T (((1))*-11) by pigeonhole, there must be a hypervolume regret of at least (((1 ((11 s((e)
Therefore, for any 1/2 > > 0, HV* (V* Ar) < implies that T' = (((1/e)=-1).
Rearranging shows that
HV - -0* = -(T-1
18

---

C Figures
C.1
Synthetic Figures
Here are the relevant full plots from synthetic optimization of Pareto frontiers. Note that the title of each plots explicitly mention the optimized function. Generally, we observe that the hypervolume scalarizer has better performance on more concave curves. We also include plot of a concave function multiplied by linear combination of a convex and concave function, given by exp(-z) exp(-y) (1 - r3 exp(y))), which demonstrates that hypervolume scalarization performs competitively even with convex frontier regions.
z- exptxx13 expo)))
X- cws.-ttstt-tiooo ecalell
70
14
0.4
10
= (Seeata)itt meplyll
Z- 13 expicii expoi
06
luadl Essade
CW/Y
130
230
300
200
36
19

---

ex31 N2 dooop 4
2 13 CHEEK -ecsid--y
Br
8.3
720
C.2 BBOB Figures
Dral
Eon
-.555
28.55
24.27
-1.05
35.30
60 120 148
-3.25
+375 +15t +1.5 +200 +635 +ESE -1.
Figure Comparisons of the hypervolume indicator and the optimization fronts with BBOB functions. The left plot tracks the dominated hypervolume function of trials that were evaluated. The blue/orange dots represent the frontier points of the UCB-HV/EHVI algorithms respectively, over repeats. Especially in high dimensions, EHVI tends overly concentrate points in the middle of the frontier, limiting its hypervolume gain, while hypervolume scalarizations produce more diverse points.
20

---

2391
BM
38.31
3555
23.05
06.03
23.05
20.04
00.00
15:20
10.011
Dim 24
ELL FSOD SETATABLE
Dm: 24br: EJU SEPRAABLE
UCB
23.04
-3 100
20126
075
22464
2 20:05
20.1
15.00
312
10343
-26
Dm:: 9 Do. ELLISIID SITARAB
Di Exp: ELUTSOID SOWAABLE
20.02
36.49
00
2010
22
2 20.0
16405
21114
30965
30225
1550
Cez: ELLIOODD
SENTAAL SIRARABLE Me 24 ELLPSOO SERRRABLE BASTIGH SERVAOLE
25.17
Bix
22.95
21.15
10.104
16.14
10.01
38m Tap TLL POOTO
GERNNALEE SASTR GN STAM/BI Dyn 8 Tan: DUPSO SIMMBI ERASTRIG STMRARL
26.13
0330
23.30
21444
15331
15100
16300
11302
189
180
230
-20
Ep ELLPSOD SEPARAB SCHNETEL
20-03
26.45
75.12
21.71

---

46
209
360
Dm
0347
4 20.04
17.00
00.0
Dirc BLUPSDRD SEMMAABL SCRMEFEL
3402
Sby ELLPOOID SCPARABLE SCYPETEL
23.114
22.45
2LA04
2 18:56
16:33
11/55
16.7C
15:90
25-14
Dir 25 Exp.
SLUPSOID SEWARLEESSEE
3329
2mn 15 de: BLPPODD SERAALLE
UCB
26.19
20.09
00.03
66
300
180
-23
-20
36.55
2 23.00
21-24
20467
15:11
-15
Din: Dop CLUSSO STRVAABLE-SHISEE
ILLPOOD SEIATABLESSP EnC
18.12
2-41
24-11
21401
19-00
20.01
06m: 30 Eap
SASTR ON SEPARABLE
Dim 16 Tap: BASTRIC ZERARASLE
15.753
15,00
11:24
16304
16304
15:004
194
14
180
25
25
25-233
Ckm Exp
SEPANABLE
18:24
14:10
16427

---

D
Code
--- coding: utf-8
"""3D Hypervolume Experimentss
Automatically generated by Colab.
Original file is located at https://colab. corp.
A## Imports
import numpy as np
import matplottib.pyplott as plt
from wizier.pyvizie import multimetric
from vizier. wtt.:ppiiiee.ee.iiiee...... import xla_pareto
eps = 1e-4
origin np. zeros (shape=3) eps
front wuutt_mmttic..Paatttoottttt
points==p. (shape= 32) eps,
origin=origin,
num_vectors=10000,
hv_curve = front hypervolume awtprvoowuunsssscsssssaaaaaaaiie iis_cummlltiveeTnn
import numpy as
import matplotlib.pt pyplot as plt
pi np.pi 1e-4
Define the function to plot threshold 0.1
def (x)
if x <= threshold:
return co.cos (xxpi/ (2xthreshold)) +
else:
return np.exp (-3+ (x-threshold))
lambda x np.cos (x+pi)
Generate some data
np.linspace (0, 1, 500)
= np.vectorize (g) (x)
Plot the data
plt.plot (x, y, 'bo')
plt.xlabel ('x')
pit.ylabel ('y")
pit.title (" ID Function Plot')
plt.show() ()
def f (x, y)
# return np. we..ectorize (g) (x) vectoriiie (g) (y)
return (3 ex.exp (x) (x up. exp (-y) (1-x) (3-np.exp (y)
return (3 np.exp (x) (3= ex.exp (y)
23

---

return (-xexp(-x) (3-np. (y))
return (x-np.exp(a) (x)) (np.cos (y * pi) 1)
return np.exp (-x)
(-x (x ex.exp (-y) + (1-x) (3 - ex.exp (y) )
# return
y)
x np. linspaee (0, 1, 30)
y np. linspaee (0, 1, 30)
X, Y ap.meshgrid y)
= f [X, Y)
fig figuue 4))
ax = plt. (projection= 3d")
33.coottour3 (x, Y, 2, 500)
ax. ex.set_xlabel
ax.set_ylabbel ('y))
ax. ax.set_zlaape 3X.set_zlabeel'221 ('z')
ax. 2x.set_title(' (3 (3-exp (x)) (3 exp (y)) "
X.llttten
= Y.flatten ()
2.flatten()
_la_pareto.is__0 is_frontier (mp.aaarr ([x, y, .]).T)
total_ hetal_hypervolume front. htt.://peerrooonedaaaattaaaooooo ([x, y, 2]). .T)
total_hypervolum
#0title Hypervolume code
def get get_points
num pom_ts 50)
index_maxes []
for - in range (num_points):
outputs scalarizer_generate (np.array ([x, y, 2]))
index_max np.argmax (outputs)
(index_max
return index_maxes
def Iirerr_guussiaa..ggeerttttrroore weights = abs www.rraannommmm..oo. (array shape (0), 1)
return np. sum (weights array, axis=0)
def cheby_eaassiee__geerrr.oo (arrayy
weights = abs (np. www.rrannnn.nna..ao.. (size= shapee (0), 1)1)
return np. min (weights * array, axis=0)
def hr..ausiiar_eeeerrtttoaaaaaaa
weights = abs (np. www.mddo..oomoeo (size= eeeraa..shape. (0), 1))
return np.min ((1/((((1tt)) array, axis=0)
generators
'linear'; Linear_gaussian_cenerrtor. cheby' cheby__auusiian_eeeraaaoo
"hv': hw_gaussian_geeeratoo
index_maxes = get_points hwg.gaathhhhuuussiiegggeeraaooo
from mezier.benchmar .nalkzznnnaaarrrrraa import plot_meedian_converrnncc
24

---

num repeats 10
renerator_curvee ()
for in range (nu__rppeats): for key, generator in generators. items ():
index_maxes get_pointss (generator, num_pointss=50)
new_points np. np. ( (x(iiiie___xxxeesl y y[index_maxes]) [iidex
hv_curve front syont.hypervolume (is_cumllative-Tiiee regret_curve total_hypervolune
hv_curve
if key in generator_curvet
generator_curveer (key) np.vstack ( ([generatoo_courees (key], zegret_curve)) else:
generator_curven [key] regret_curve
fig, ax = plt. (1, 1, figsize=(4, (4,
#M.see_xlabel ('# of Pareto Points')
ax. sx.set_ylabel] (' HHypervvlume Regret')
ax ax.set_title''s (t.set_yscalee'
(3- exp(x)) (cos (pi y) 1)
for key, curves in generator_curves items ():
print (curvee.
plot ats__meiiianccovrreeeeeeee (ax, curves, label=key, percentiles- ( (25, 75), )
legend))
- coding: utf-8
""Multicbjective Linear Bandits
Automatically generated by Colab.
Original file is located at
https:///colle cwwpb. corp wtt.://www.....aaaa.e//.o//otooa
import dataclasses
import itertools import math import os import re
from absl import flags import matplotlib.pypll as plt import numpy as np
@title Simple LinUCB implementation { display-mode: "form" import numpy as np import pandas as pd import seaborn as sns
from from googlee3.earming..iii.. vizier import benchmark_v2
python import recordio
from googles.leamming..iiiee..... ben.hhirr.. import analysis from
benchai. import config_pby pb2
import google3.pyglii..ftt. as gfile
class LinUCB:
"""Simple LinUCB implementation. "*"
def init__
self, dimension: int, max Linst_regret: float 2.0,
25

---

reqularizer: float 1.0,
var_noise: float 1.0,
max_parameterr_nrm. float = 1.0,
failure_probabilty- float 0.1,
assert regularizer > 0.C
self.dimensinn dimension
reglarregu reqularizer
self._var_nooe = var_noise
self._max: htt._max_paart
htt___ax_paraaettr__mm norm. max wwwpppaaaaaaapaaa norm
self _al___ma__ins__eeerttt max_inst_regran
f falf_faallrrepprbbbbittty failuree_robbbbllg
self.reset
def reset (self):
covriinnvva =
* self._regularizer
self reff__reward_scaaeee features np. zeros wew.f.dmemssion.....
self cettametteresstimae
zerzeros (se.frosse... dii.iiiimmmnin
self self._num num _rl___nu_oss_eeee
observations
self lalf=_laat_con_rraddu self _o
None
def aed__ddd_beee www.oooeeationneeeee (self, action, reward:
float, context=None)
"""add observation (action, reward) to the learner.
This function updates the covariance matrix and parameter estimate.
Args:
action: action that was taken
reward: achieved reward
context: context for this observation
blamed: whether this algorithm is to be blamed for this observation. т**
se self._nun_observaaioon +=
# Sherman Morrison update of covariance matrix
y np.dot [ovaaiiiaco inv, action)
self._covariance inv - rp.outer (y, y) / (1 + np. inner (action, y)
regression target
sellf__reward_scaleeefffffeeeeee features += reward action
parameter estimate
self. self__parameterressttmteee np.
sel
self. relff_rrearddsssleee_efeetttete
self cell
self cel
def ucb (self, actions, senfidence_scale=111 """computes the upper- upper-confidence bound for batch of actions.
Args:
actions: A x d matrix
confidence_scale: scaling factor in front of the bonus prescribed by theory
Returns:
upper-confidence bound for each action, A vector
26

---

rewards np. (actions, self._ _ell:__arraeter_estteee -essssttttttee
var = np. sum sumaaciions np.dot (actions, _olf._covariance_iimm axis=1) beta ceaff__cof_ellipsiiii return rewards, beta np.sqrt (var)
confidence_scal
def drcoose_action (self, actions, [rriidenee_scalee___ "**chooses the action that maximizes the upper confidence bound.
Arqs:
actions: d matrix, possible actions to choose from confidence_scale: scaling factor in front of the bonus prescribed by theory
Returns:
chosen action (d vector)
rewards, conf_b self. uelf.ucbbacttons, confidence_scale)
action_inder index = randargmax (rewards + conf_b) return actions pection_index, :]
def _wcoo_ceoooppoeoe _ccnf__lllisccid_rrsssllll
# from Abbass1 et al. 2011
beta_t np. sqrt (self. reell.._re self._max www_paaaameeereerrrrr o log_dets -np. httr:ssf__aaalrreerrbaaaaa
log_dets self.dimensinn
mp. log reguar. zer)
log_dets - np
covelf._ovvrraanceeiiie [1] / 2
beta_t += ap.sqrt (2 * self. var noise log_dets)
return beta_t
def randargmax (b)
"""takes the argmax but randomly picks from the set of maximizers. return np. randomm. (np. flatnnnzzeee (b b.max )))
def linear_scallarizer (acquiiarii weights):
sum = 0.0
for acquisition, weight in zip (acquisitions, weights)
sum +- weight acquisition return sum
def seabyshev_scclarizer (acquisstioos, weights):
min = np. in.inf
for acquisition, weight in zip tap(uuquisssions, weights): min = np. momimummmm (acquisition reference) weight, min )
return min
def patevollue_scclaaiiaee (acquisitions, weights):
min np.inf
for acquisition, weight in
weights) min np.minimum (acquisition reference) / weight, min )
return min
def uniform_weights ():
weights np. random. normal (siiennnmmmtrrics) return abs (weights) /np. inalg. norm (weights))
27

---

def boxed_ diinar_wweihtte ()
Use bounding box.
= wnw.ndom.uiffomma111
high=3.00 size=num_metrics)
return np.linalg.norm (t, ord=1, keepdims-True)
def coxeed_chebysheev_wiights
Imda = bboxed_linear_wa
Imda_prime 1.0/1mda
return Inda aacpaprrmeemngg www.lg.ngi.... norm (1mda paimmd_priie,,____ ord=l, keepdims=True)
dim =
num_me num_metrics 16
thetas np. random. normal (size= (num_matrics, dim))
Anti-correlate thetas.
thetas (0, :1 -thetas [1, :] ra..ranomm size=thetas [1, : shape, scale=0.01
for i in range (int (num_metrics 2)) index = int (2 i)
thetas [index, :] -theras 1, :] np. aap.randmm
size=thetas [index + 1, :] shape, scale=0.01
Renormalize to make sure |theta| = thetas = thetas np. ww..linag..omm.. (thetas, axis=l, keepdims=True) reference = -2
def run www_lllnearbaaiie (thetas, scalarizer, weight__generator, nun_rounds=100)
algs = [LinUCB (dimension-dim) for theta in thetas]
np. empty (shape= (num coundr num_metrics)) actions np. random.do..mm noraa (size= (1000, dim)) actions = act acti / np. wep.linagg..... norm (actions, axis=1) [..., newaxxs for t in range (num_rounds):
expected_reware
index np. random. choice (len (actions))
action = senioess[idey,
expected_rewas np. in.inee (thetas, action)
rewards expected_reward + ap.random.normal (size=expected reward. shape)
for alg, reward in zilgs, rewards)
aaa___cbbervatiioaeetii.o. reward)
weights weight__eneratorr
acquisitions scalarizer ( [[uu (alg. ucb (actions)) for alg in algs], weights)
assert len (acquisitions) = len (actions)
index randargmax (acquisitions)
action actions [index]
expected reward inner (thetas, action)
rewards expected_reward np. nopxrddom.normll (size=expected wwtpppppeeeedeeeedeeeeer shape) for alg, reward in zip (algs, rewards)
add_osdd_obse (action, reward)
bebecteddrewardee [t] = expected_revard return actions, expected_rewards
scal acalarizations
'linear-uni form'; : (Lineer nniforr_weightst
'linear-boxed's
boxed linear, weights),
28

---

chebyshev-uniformm behebysshe__ccllriine uniform weiimm__eighhs
chebyshev-boxed's : beteeyshhe_ssclariiee boxed_chebyshev_ weights),
hypervolume-uni ttypervollume__caaaarrr uni uniform_wed uniform_weights)) cyppervolume-boxeer
boxed wiweernerreee bead_llneer_weihhheee
from vizier. pyvizier import multimetric from pyzzier.yyizzer..uue
import xla_pareto
pareto_alge algo = xla_pareto. waw.arrrtoopptnmallllloiitt...m.
import matplotl ltbl. pyplot as plt
num_rounds = 100
actions, Linear_rewarde run_liinearbanddtt
thetas, ecaleriaerbupperroommm...aaaaeee weight_generatorrmmooooo...eee
aallvalues = (action,, thetas)
all_frontier- ali_values (pareeetppreee__aeeee o (all_values)
frontier = linear rewerrd_eewadssteoe [pareto_atae salolaaalo___ is pas___paretpppppnoee Seihear_rewarde
att.saatterralll_aaaee plt.scatter
0], all values(;, 1], color='grey')
all_frontier(:; 0],
all_frontier(;, 1],
rolor='red', label=' Paree==-Prreooopttmme points', s=30,
plt. scatter
frontierl;, 0],
frontierl;, 1],
color=' green', Sabel='Discoverst Frontier', s=30,
plt.xlabe) ('y_l', fontsize=13) plt. 2'y_2', fontsize=13) plt.title(
F'Hypervolume scalarizer optimization at
fontsize=18
plt. (lt.legend()
origin = -2 np. oneo (shape=run_metricc) num_repeats fig, ax = plt. (1, 1, figsize= (12, 8))
for key, (scalarizer, weight_generator) in scalarizations ittma ()
hvs []
for in range (num hum__repeats:;
Linear_rewarde run ginerr bandit
thetas, scalarizer, weight_generator, jum_rounds-200
front miltinetric.Parrtttootiie points=linear__eeards, origin=origin,
hvs. append htt.p//aweaaaprrrroooooaaaao.ara
(is_cumul at ative=True)
y aap.prraa (hvs)
29

---

analysis.plot_pie pewpt__meeia__coovrreeeeeoo
ax, y, array (zange (y. shape [1])), label=key, percentiles- ((00))00(333)))) ((30, ,0),)
ax. legend ()
ax.set_title (f' Cumulative HV from (origin)', fontsize=15)
ax. se._yt_llabel (" hypervolume (HV)
ax.set_xlabell (' of Trials')
30

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: Abstract clearly state claims and introduction has a list of main contributions, both theoretical and experimental.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
31

---

Justification: In our introduction, we provide limitations of works given in the beyond linear scalarization and hypervolume regret subsections.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All the theorems, formulas, and proofs are given in the paper or appendix and are numbered and rross-eeferenced. All informal proofs have a formal complement and all assumptions are clearly stated.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
32

---

The hypervolume scalarization is easy to code up and try on wide variety of benchmarks. All the code released and all data is generated synthetic or via open open-soureed benchmarks.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All the code is released and all data is generated synthetic or via open sourced benchmarks.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https://nips... cc/
public/ /wwi///u///////eee// Seee//odeuummme swwinsssoooooooo cesionnPoicyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https? //nips. cc/ /ntpps.cc//ubllcc/gnlddgg// www.e/eeweeeeeeeebmmmmoomm
wwm.mmisssiioooooooooooooooooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
33

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes)
Justification: Yes, all experimental details are provided in the core of the paper or in the appendix/code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Yes error bars are provided and we assume the standard reporting 30-70 percentile for error bars over independent repeats, stated.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative eтror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
34

---

Our paper do not compare resource usage, rather it improves in Trial efficiency, Furthermore, the use of different scalarizations does not affect resource usage.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Research is mainly theoretical and conforms with code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our research is mainly theoretical and improves optimization pipelines on synthetic data.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
35

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our research is mainly theoretical and improves optimization pipelines on synthetic data.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Our research is mainly theoretical and all previous usages are cited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, (paperswi wwwrsswwthcooooo choode com/ data asatssets has curated licenses for some datasets. Their licensing guide help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No assets released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
36

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
37


Reviews:
[{"review_id": "4fbaa1ZQS7", "reviewer": "Reviewer_9Trh", "summary": "The paper addresses the challenge of exploring the Pareto frontier in multi-objective optimization problems, particularly focusing on minimizing hypervolume regret. Linear scalarizations are often inadequate as they fail to explore certain non-convex regions of the Pareto frontier. The authors propose using non-linear scalarization with weights chosen uniformly at random. Specifically, the scalarization function $s_\\lambda(y) =  \\min_{i \\in [k]} (y_i/\\lambda_i)^k$, where $y$ is a $k$-dimensional vector and $\\lambda$ is chosen uniformly at random. This achieves optimal sublinear hypervolume regret bounds of $O(T^{-1/k})$ with matching lower bounds.  Furthermore, the authors show that hypervolume scalarization uniformly explores the Pareto frontier in terms of the angular direction, thereby covering the entire Pareto frontier. They further demonstrate the theoretical and empirical performance of these scalarizations across various optimization settings. For multi-objective linear bandits, the authors introduce a scalarized algorithm based on the UCB algorithm and prove that this algorithm achieves a regret bound of $O(d \\sqrt{T} + T^{-1/k})$.", "questions": "The paper briefly discusses Chebyshev scalarization (which has a similar form except that $\\lambda_i$ is in the numerator), mentioning that it enjoys similar advantages as hypervolume scalarization when dealing with a non-convex Pareto frontier. However, it is not clear how the hypervolume regret would scale for this function. The paper could benefit from a theoretical comparison with other scalarizations as well.\n\nIn the case of linear bandits, the UCB extension works for other scalarization functions (Chebyshev, linear) as seen in the algorithm and achieves sublinear regret as shown in the experiments. I wonder if the theoretical guarantees differ significantly for different scalarization functions. What exact properties of the scalarization function impact the regret?", "limitations": "This paper does not have any negative social impact.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper makes relevant contributions to multi-objective optimization literature. The setting itself is well justified, and the authors thoroughly compare their contributions to previous work. Although the scalarization functions are not novel, given the prior work, the results presented in this work make notable advances.\n\nIn particular, Lemma 5 offers good insight into why hypervolume scalarization is potentially a good strategy even for complicated optimization problems. The fact that hypervolume scalarization uniformly explores the Pareto frontier (in an angular sense) ensures that hypervolume regret is small. Moreover, while it is known that the expected value of the scalarization function (with uniform exploration) gives the hypervolume, this result is asymptotic, and Theorem 7 quantifies the actual convergence rate (with finite samples). Additionally, the lower bound in Theorem 8 establishes that the convergence rate is optimal.", "weaknesses": "Please see the questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful review. \n\n**Comparison with Other Scalarizations:** The hypervolume regret convergence rate is both a function of both the scalarization and the weight distribution and is a guarantee in the worst case for all frontiers in the whitebox setting. Even the hypervolume scalarization, with a skewed weight distribution, stands no chance of a sublinear hypervolume convergence rate. Therefore, we need to compare theoretical convergence rates using the scalarization along with the weight distribution. \n\nAs you stated, we have mentioned that the Chebyshev scalarization with an appropriate “inverse” weight distribution enjoys the same convergence rate as the hypervolume scalarization. But to your point, we hope to add a theoretical analysis of the worst case convergence rate of the Chebyshev scalarization with a uniform weight distribution, which can likely be done via a KL analysis of the weight distribution. \n\nAs for the linear scalarization, since hypervolume convergence is a worst case measure, note that any scalarization that uses a linear component will not be able to achieve sublinear hypervolume regret rates (regardless of weight distribution), as it will not be able to explore the whole Pareto frontier in adversarially designed concave settings.\n\n**Scalarization on Regret:** The bandits section showcases the improved non-euclidean analysis of the hypervolume regret and the algorithm is primarily introduced as a tool to demonstrate the utility of the hypervolume scalarization in theory and later in experiments. The theoretical guarantees for linear bandit regret bounds are based on the $\\ell_p$ smoothness of the scalarization function, where $p$ is the norm chosen for the artifact of analysis. \n\nThe bounds can differ significantly as the number of objectives $k$ increases, as the Hypervolume scalarization has an $\\ell_\\infty$ smoothness that is independent of $k$ whereas this is not true of other scalarizations, which grow polynomially in $k$. In our experiments, we do find that as $k$ increases, we have more advantage in using the Hypervolume scalarization, over other scalarizations. We will make this more clear in the final draft.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BVvJHj8Fun", "reviewer": "Reviewer_3k2M", "summary": "For multi-objective optimization, a common technique is to use scalarizations to reduce the multi-objective to one single objective. While it is easy to use linear function/scalarizations, it does not fully explore a concave region of Pareto frontier. The paper focuses on non-linear scalarization, in particular, it focuses on hypervolume scalarizations.\n\nThe authors propose simple non-linear scalarizations that effectively explore the Pareto frontier and achieve optimal sublinear hypervolume regret bound. \n\nThe main contribution of this paper is to show that hypervolume scalarizations with uniformly random weights achieves a sublinear hypervolume regret bound of order $O(T^{-1/k})$ together with a matching lower bound.\n\nFor the special case of multiobjective linear bandits, the paper gives an algorithm that achieves $O(dT^{−1/2} + T^{1/k})$ hypervolume regret.\n\nThe paper also empirically justifies the effectiveness of hypervolume scalarizations via synthetic, linear bandit, and blackbox optimization benchmarks.\n\n\n\n--------------\nI acknowledge that I have read the author's rebuttal.", "questions": ".", "limitations": "One minor suggestion to improve the readability of this paper is to give some concrete examples on scalarization, and in particular, for hyper volume regret.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The multi-objective optimization task is very common and the technique scalarization seems to be very important (both practical and theoretically). The paper explores non-linear scalarization technique and gives sublinear regret bound.", "weaknesses": ".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful review. \n\n**Scalarizations and Hypervolume Regret:** Our study considers both the scalarization and the weight distribution (see Figure 1 for visualization) and provides a regret guarantees in the worst case for all frontiers. We have included some novel synthetic experiments that gives a complete whitebox characterization of the Pareto frontiers and explicitly calculates the hypervolume regret given our optimization procedure using different scalarizations. We hope to make this more clear in our final draft with better visualization.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "i5Hdk0iHYx", "reviewer": "Reviewer_ooQr", "summary": "This paper shows that the hypervolume scalarization has sublinear hypervolume regret bounds of $O(T^{-1/k})$, and further proves a lower bound of hypervolume regret of $\\Omega(T^{-1/k})$. An optimization algorithm for multiobjective linear bandits is proposed. An empirical study is conducted to verify the effectiveness of hypervolume scalarizations.", "questions": "P2, L74. \"maximize the Pareto front\"?\n\nP3, L130. Typo: \"biojective\".", "limitations": "No concerns.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* Although this paper is technical, it is well-organized and easy to follow. \n* The proposed theoretical results are interesting and non-trivial.", "weaknesses": "* This paper has a significant overlap with a previous paper (Golovin and Zhang, 2020), which proposed hypervolume scalarization and its hypervolume regret. The main focus of these two papers seems similar, so I suggest the authors summarize the differences and new contributions.\n* The authors claim that the concept of the so-called \"hypervolume scalarization\" originated from (Golovin and Zhang, 2020). However, similar scalarization methods were already proposed in (Qi et al., 2014) and have been widely used in the field of multi-objective optimization (Li et al., 2016).\n* The authors regard hypervolume as the gold standard, but I have reservations about this. Hypervolume has two main drawbacks: (1) the hypervolume optimal distribution may not cover the entire Pareto Front, and (2) HV's behavior is highly dependent on the choice of the reference point. Therefore, in practical applications, maximizing HV does not necessarily yield ideal results. Additionally, the paper assumes reference points multiple times, such as in Theorem 8 where it is assumed that $z=0$. Given the characteristics of HV, I would question whether such assumptions may limit the generalizability of these theorems.\n\nReferences\n\nZhang, R., & Golovin, D. (2020). Random hypervolume scalarizations for provable multi-objective black box optimization. In ICML (pp. 11096-11105).\n\nQi, Y., Ma, X., Liu, F., Jiao, L., Sun, J., & Wu, J. (2014). MOEA/D with adaptive weight adjustment. Evolutionary Computation, 22(2), 231-264.\n\nLi, H., Zhang, Q., & Deng, J. (2016). Biased multiobjective optimization and decomposition algorithm. IEEE Transactions on Cybernetics, 47(1), 52-66.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful review. \n\n**Novelty of our paper:** Our paper is focused on describing how fast scalarizations can approximate the Pareto frontier under finite samples even with *perfect knowledge of the Pareto frontier (whitebox setting)* and is first of its kind (see Theorem 7). Specifically, we introduce the notion of the hypervolume regret convergence rate, which is both a function of both the scalarization and the weight distribution and is a guarantee in the worst case for any frontier. This is complementary to the results of Golovin & Zhang, which showed the expected hypervolume regret bounds is $T^{-1/2}$ under the assumption that the scalarizations, with no generalization error, already cover the whole Pareto frontier in expectation. Specifically, note that their bounds in Golovin & Zhang do not even include the $T^{-1/k}$ rate, which we have shown to be tight. We will make this more clear in contributions section in the introduction.\n\nAs mentioned in the introduction, we emphasize that our derived regret rate of the Hypervolume scalarization holds regardless of the multi-objective function or the underlying optimization algorithm; furthermore, we believe these agnostic rates can be a general theoretical tool to compare and analyze the effectiveness of proposed scalarizers (see our experiments on synthetic Pareto frontiers). In addition to this main contribution, we also include a linear bandits section showcases the improved non-euclidean analysis of the hypervolume regret and the algorithm is primarily introduced as a tool to demonstrate the utility of the hypervolume scalarization in theory and later in experiments. We will make these contributions clearer in the paper.\n\n**Scalarization Origination:** The hypervolume scalarization origination is indeed difficult to pinpoint but we mainly cite Golovin and Zhang as it contains theoretical analysis of the scalarization, specifically its relation to hypervolume, which is novel to our knowledge. We recognize in our paper that “the classical Chebyshev scalarization has been shown to be effective in many settings, such as blackbox optimization”, and acknowledge the relationship between the two: the Chebyshev scalarization with an appropriate “inverse” weight distribution enjoys the same convergence rate as the hypervolume scalarization. We will add more discussion and the recommended citations to the other similar scalarization methods.\n\n**Hypervolume Standard:** The hypervolume as a standard metric is classically used because it does cover the full Pareto frontier, as the hypervolume metric 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$ [see Golovin & Zhang]. We will clarify this in our final version.\n\n**Reference Point:** We acknowledge that the choice of the reference point can be a bit tricky in practice but many packages use reasonable heuristics and we find that our experiments are not sensitive to this choice [see Daulton et. al. 2020].  In theory, our assumptions on reference point are held without loss of generality and our hypervolume convergence bounds hold for ANY choice of reference point. Therefore, for Theorem 8, we only need to find a specific counterexample to establish a lower bound and so we choose $z = 0$, but the generalization is in fact not affected, as the lower bound can be extended to any reference point by shifting the outputs. We will clarify the role of the reference point more in the final version.\n\nWe fixed the typos, thank you, and hope that our clarifications have improved the reviewer's confidence about the quality of our work.\n\nRefs:\n\nDaulton et. al 2020. Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OzbiOS1Flv", "reviewer": "Reviewer_LEgt", "summary": "This abstract presents a study on non-linear scalarization techniques for multi-objective optimization, specifically focusing on hypervolume scalarizations with random weights. The authors prove that this approach achieves optimal sublinear hypervolume regret bounds and apply it to multiobjective stochastic linear bandits, deriving improved regret bounds. Their theoretical findings are supported by empirical results demonstrating superior performance of non-linear scalarizations compared to linear alternatives and other standard multiobjective algorithms in various settings.", "questions": "See the weakness.", "limitations": "The authors need to clarify the contribution first.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper provides both theoretical and empirical analyses of hypervolume scalarization performance.", "weaknesses": "First of all, most lemmas are from the reference [1]. The authors should primarily focus on highlighting differences or contributions compared to this reference. Given that the key scalarization method was proposed in [1], simply conducting experiments on synthetic data adds little value, as this was likely already verified in the original proposal.\n\nBesides, the applicability of hypervolume regret to the multi-armed bandit setting is questionable, especially in scenarios with finite action sets. The identification of the optimal arm in such cases needs to be carefully defined.\n\n\n[1]. Zhang, Richard, and Daniel Golovin. \"Random hypervolume scalarizations for provable multi-objective black box optimization.\" International conference on machine learning. PMLR, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Novelty of our paper:** Our paper is focused on describing how fast scalarizations can approximate the Pareto frontier under finite samples even with *perfect knowledge of the Pareto frontier (whitebox setting)* and is first of its kind (see Theorem 7). Specifically, we introduce the notion of the hypervolume regret convergence rate, which is both a function of both the scalarization and the weight distribution and is a guarantee in the worst case for any frontier. This is complementary to the results of Golovin & Zhang, which showed the expected hypervolume regret bounds is $T^{-1/2}$ under the assumption that the scalarizations, with no generalization error, already cover the whole Pareto frontier in expectation. Specifically, note that their bounds in Golovin & Zhang do not even include the $T^{-1/k}$ rate, which we have shown to be tight. In addition to this main contribution, we also include a linear bandits section showcases the improved non-euclidean analysis of the hypervolume regret and the algorithm is primarily introduced as a tool to demonstrate the utility of the hypervolume scalarization in theory and later in experiments. We will make this more clear in contributions section in the introduction.\n\n**Borrowing Previous Work:** We strongly disagree with the assessment that our work is borrowed from the previous work of Golovin and Zhang. Note that only 1 of our results is borrowed from (and attributed to) the previous work (Lemma 5), while all other results are novel, especially Theorem 7 in the whitebox setting. Furthermore, the experiments on synthetic data were not done before, as the notion of hypervolume convergence rate (in the whitebox setting) was not introduced in the previous paper, which focuses on blackbox optimization and derives a regret bound rate of $T^{-1/2}$.\n\nAs mentioned in the introduction, we emphasize that our derived regret rate of the Hypervolume scalarization holds regardless of the multi-objective function or the underlying optimization algorithm; furthermore, we believe these agnostic rates can be a general theoretical tool to compare and analyze the effectiveness of proposed scalarizers (see our experiments on synthetic Pareto frontiers). We will make this distinction clearer.\n\n**Multi-armed Bandit:** Lastly, we do not mention the multi-armed bandit setting in our paper and we focus on only continuous action sets.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a non-linear scalarization with weights chosen uniformly at random to reduce multiple objectives into one. A sublinear hypervolume regret bound of O(T^{-1/k}) is achieved, as well as a matching lower bound. Scalarization in multi-objective optimization is an important problem. The reviewers found the results and techniques interesting and non-trivial.
Decision: Accept (poster)