Optimal Scalarizations for Sublinear Hypervolume Regret

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.

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. Besides, 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. [1]. Zhang, Richard, and Daniel Golovin. "Random hypervolume scalarizations for provable multi-objective black box optimization." International conference on machine learning. PMLR, 2020.

Questions

See the weakness.

Rating

5

Confidence

2

Soundness

2

Presentation

2

Contribution

2

Limitations

The authors need to clarify the contribution first.

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.

Strengths

* Although this paper is technical, it is well-organized and easy to follow. * 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. * 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). * 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. References Zhang, R., & Golovin, D. (2020). Random hypervolume scalarizations for provable multi-objective black box optimization. In ICML (pp. 11096-11105). Qi, Y., Ma, X., Liu, F., Jiao, L., Sun, J., & Wu, J. (2014). MOEA/D with adaptive weight adjustment. Evolutionary Computation, 22(2), 231-264. Li, H., Zhang, Q., & Deng, J. (2016). Biased multiobjective optimization and decomposition algorithm. IEEE Transactions on Cybernetics, 47(1), 52-66.

Questions

P2, L74. "maximize the Pareto front"? P3, L130. Typo: "biojective".

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

No concerns.

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. The authors propose simple non-linear scalarizations that effectively explore the Pareto frontier and achieve optimal sublinear hypervolume regret bound. The 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. For the special case of multiobjective linear bandits, the paper gives an algorithm that achieves $O(dT^{−1/2} + T^{1/k})$ hypervolume regret. The paper also empirically justifies the effectiveness of hypervolume scalarizations via synthetic, linear bandit, and blackbox optimization benchmarks. -------------- I acknowledge that I have read the author's rebuttal.

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

.

Questions

.

Rating

6

Confidence

2

Soundness

2

Presentation

3

Contribution

3

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.

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})$.

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. In 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.

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. In 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?

Rating

7

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

This paper does not have any negative social impact.