Few for Many: Tchebycheff Set Scalarization for Many-Objective Optimization

Thank you very much for your time and effort in reviewing our work. Our responses to your concerns are as follows.

W1. Relation to Previous Work: This novelty is somewhat limited. It seems the line 74 “a novel Tchebycheff set (TCH-Set) scalarization approach” has been proposed in [1] and the line 75 “a smooth Tchebycheff set (STCH-Set) scalarization approach” has been proposed in [2].

[1] Eng Ung Choo and DR Atkins. Proper efficiency in nonconvex multicriteria programming. Mathematics of Operations Research, 8(3):467–470, 1983.

[2] Xi Lin, Xiaoyuan Zhang, Zhiyuan Yang, Fei Liu, Zhenkun Wang, and Qingfu Zhang. Smooth tchebycheff scalarization for multi-objective optimization. arXiv preprint arXiv:2402.19078, 2024.

We believe there is a misunderstanding here regarding our contribution. In this work, our proposed (S)TCH-Set approaches significantly extend the traditional (S)TCH approaches [1,2] to tackle the novel and important few-for-many problem setting for many-objective optimization.

• The scalarization methods proposed in [1,2] are to find a single Pareto solution with a specific trade-off among all objectives. The work [1] proposed the classic Tchebycheff (TCH) scalarization, while the work [2] proposed a smooth version (STCH) for efficient gradient-based optimization. Both of them cannot tackle the few-solutions-for-many-objectives problem setting considered in this work.

• In this work, we propose the (S)TCH-Set scalarization method to find a small set of solutions to cover a large number of objectives in a collaborative and complementary way such that each optimization objective can be well addressed by at least one solution. This problem setting is important for many real-world applications (see discussions below).

• The (S)TCH-Set scalarization is an important and non-trivial extension of the classic TCH-Set scalarization, and it will naturally reduce to TCH-Set scalarization with the number of solutions $K = 1$. We have also provided a detailed theoretical analyses to show that our proposed (S)TCH-Set approach enjoy good theoretical properties for multi-objective optimization.

• Experimental results show our proposed (S)TCH-Set can significantly outperform the classic (S)TCH as well as two very recently proposed methods on multi-objective optimization problems with many objectives.

Therefore, we believe our proposed (S)TCH-Set scalarization method is a novel contribution to many-objective optimization.

[1] Eng Ung Choo and DR Atkins. Proper efficiency in nonconvex multicriteria programming. Mathematics of Operations Research, 8(3):467–470, 1983.

[2] Xi Lin, Xiaoyuan Zhang, Zhiyuan Yang, Fei Liu, Zhenkun Wang, and Qingfu Zhang. Smooth tchebycheff scalarization for multi-objective optimization. arXiv preprint arXiv:2402.19078, 2024.

Thank you for the author's response. I consider this work to be rigorous and thorough. Most of my concerns have been resolved, hence I have increased my score.

I am not very familiar with the field of multi-objective optimization, but I hope to see the author's research have more potential applications in practical scenarios.

We are very glad to know most of your concerns have been resolved, and you consider this work to be rigorous and thorough.

We are currently trying to apply TCH-Set to tackle more real-world applications. Given the workload, new experimental results would not be available during the rebuttal period. We will try our best to include more experimental evaluation on new tasks in the revised paper, and explore the potential of TCH-Set to tackle different real-world applications in future work.

Thank you again for your time and effort in reviewing our work.

Thank you very much for your time and effort in reviewing our work. Our responses to your concerns are as follows.

Q1. Optimization for (S)TCH-Set: After the Tchebycheff set scalarization, how is the scalarized problem solved, given that a set of solutions needs to be optimized?

In short, all solutions are simply optimized together by a gradient-based method.

• If we treat the (S)TCH-Set scalarization function as an indicator, our proposed method is indeed a standard indicator-based method for many-objective optimization.

• To minimize the scalarized (S)TCH-Set value, we treat the set of solutions as a whole (i.e. a solution matrix) and optimize them together using a gradient-based optimization method as shown in Algorithm 1 in the paper.

We have revised the related description for algorithm 1 to make this point more clear.

Q2. Few-for-Many Prospective: Did the methods compared in the experiments also propose the few-for-many prospective for many-objective optimization?

Yes, some methods also propose the few-for-many problem setting, but not necessarily consider many-objective optimization. In the experiments, we compare our proposed (S)TCH-Set with traditional multi-objective optimization algorithms as well as two recently proposed methods that aim to find a small set of solutions to tackle many optimization objectives. Among them:

• The traditional multi-objective optimization methods, such as linear scalarization and (smooth) Tchebycheff scalarization, focus on finding solutions with specific trade-offs and do not consider the few-for-many problem setting.

• The SoM method generalizes the classic k-means clustering method to handle a specific Sum-of-Minimization (SoM) problem $\frac{1}{m} \sum\_{i=1}^m \min \{f_i(x^{(1)}), f_i(x^{(2)}), \ldots, f_i(x^{(K)})\}$ with a few solutions $\\{x^{(k)}\\}\_{k=1}^K$ and many optimization functions $\\{f_i(\cdot)\\}\_{i=1}^m$. However, it does not take multi-objective optimization into consideration.

• The Many-objective multi-solution Transport (MosT) method leverages bi-level optimization, optimal transport, and MGDA to find a small set of diverse solutions on different representative regions of the Pareto front. However, unlike SoM and our (S)TCH-Set method, it does not have an indicator to explicitly take each objective value into consideration.

In this work, we propose a straightforward and efficient set scalarization approach to explicitly optimize all objectives by a small set of solutions for many-objective optimization.

Q3. Optimization Methods: What optimization methods are used under the scalarization methods for the convex multi-objective optimization in Section 4.1?

We use a simple SGD optimizer with learning rate $0.01$ to all methods for the convex multi-objective optimization problem.

Q4. STCH-Set and SoM: A brief analysis of why STCH-Set performs slightly worse than SoM in two cases in Table 4 would be beneficial.

Thank you for this valuable suggestion.

• Table 4 reports the results for a real-world deep multi-task grouping problem with $9$ tasks (objectives) and $\{2, 3, 4\}$ models (solutions). Our proposed STCH-Set method can outperform SoM in all cases on the worst-case performance, but is slightly worse than SoM in two cases on the average performance.

• SoM is designed to explicitly optimize the average performance by its definition. Therefore, in the ideal case, SoM should always achieve the best average performance if it has been properly optimized. However, due to the non-smoothness of the SoM objective and NP-hard nature of the clustering algorithm, SoM is outperformed by STCH-Set on the average performance in most cases for the convex optimization and mixed (non)linear regression problem with a large number of objectives ($128$ to $1024$). A brief discussion can be found in Appendix D.4.

• For the deep multi-task grouping problem, we only have a relatively small number of objectives ($9$). In this case, it seems that SoM can properly assign a suitable solution to each objective much more easily than those with many more objectives, which leads to a good average performance. By definition, our proposed (S)TCH-Set is to minimize the worst-case performance among all objectives. Therefore, it is inevitable that STCH-Set can not achieve the best average performance at the same time for a non-trivial problem.

The above discussion has been added for analyzing the results of multi-task grouping in the revised paper.

W1. Problem Setting: My major concern is about the problem setting. The proposed method aims to find a few solutions that collaboratively optimize many objectives. This problem setting is quite different from the common setting in multi- or many-objective optimization, which aims to find some solutions with diverse trade-offs. I agree with the authors that one of the main obstacles in many-objective optimization is that, with the increase in the number of objectives, the number of solutions has to increase exponentially to cover the whole PF. The idea proposed in this paper is interesting; however, I do not think it really solves this problem. When the number of objectives is very high, it only searches for extreme points, that is, solutions with very low values for some objectives but significant sacrifices in others. By putting together these multiple extreme points, it appears as if multiple objective functions can be "simultaneously" optimized. Actually, although many MOAs output a set of solutions, after multi-objective decision-making, typically only one solution is finally selected, and, in practice, solutions with a more balanced tradeoff are often preferred. Therefore, while the TCH-Set offers a novel idea for many-objective optimization, I think its practical impact and significance are limited.

Thank you very much for raising this valuable concern. First of all, we want to be very clear that our proposed method is not to replace the traditional methods that find a single or a set of solutions with balanced trade-offs. In contrast, it provides a new approach to tackle a type of application problem that was originally not considered by the traditional many-objective optimization method. Therefore, our proposed method is a complement rather than a replacement for the traditional methods for many-objective optimization.

We provide the following discussion on 1) the problem setting and practical impact of our method and 2) its relation with traditional methods to address your concerns.

Problem Setting and Practical Impact. Our proposed (S)TCH-Set method is motivated by the need of finding a few complementary solutions to tackle many different optimization objectives that naturally arise in many real-world applications. Some typical applications include building a small set of machine learning models (e.g., mixture of experts) to handle many different data or tasks, training a few agents to handle a large number of clients in federated learning, and producing a few different versions of advertisements to serve a large group of diverse audiences. A single solution with a balanced trade-off is not enough to properly address these applications. Very recently, this problem setting has also been investigated in two concurrent works [1,2] by researchers with backgrounds in machine learning, traditional optimization, and federated learning. Therefore, we believe the problem setting considered in this work is valid and important for many real-world applications.

Due to the requirement on finding a set of complementary solutions, traditional multi-objective optimization methods cannot be directly used to solve these problems. In contrast, our proposed (S)TCH-Set method can efficiently handle this problem setting. The experimental results also show our proposed (S)TCH-Set can outperform the methods proposed in [1,2,3,4] on different application problems. Some application problems considered in this work, such as multi-task grouping [3,4], are already impactful in practice. We believe our proposed method will have a significant practical impact on solving a broad range of similar application problems that require a set of complementary solutions.

In addition, our proposed (S)TCH-Set method provide a novel viewpoint of multi-objective optimization to tackle the few-for-many problem setting. We hope it can further bridge these fields, attract practitioners' attention to multi-objective optimization, and also inspire more interesting follow-up work on multi-objective optimization to handle novel application problems.

[1] Lisang Ding, Ziang Chen, Xinshang Wang, Wotao Yin. Efficient Algorithms for Sum-of-Minimum Optimization. ICML 2024.

[2] Ziyue Li, Tian Li, Virginia Smith, Jeff Bilmes, Tianyi Zhou. Many-Objective Multi-Solution Transport. arXiv:2403.04099.

[3] Trevor Standley, Amir R. Zamir, Dawn Chen, Leonidas Guibas, Jitendra Malik, Silvio Savarese. Which Tasks Should Be Learned Together in Multi-task Learning? ICML 2020.

[4] Christopher Fifty, Ehsan Amid, Zhe Zhao, Tianhe Yu, Rohan Anil, Chelsea Finn. Efficiently Identifying Task Groupings for Multi-Task Learning. NeurIPS 2021.

I greatly appreciate your effort in improving the manuscript and providing detailed responses. With your help, I have a clearer understanding of your work. Now I think this paper matches the standard of ICLR, and I support the acceptance of this paper.

However, I still have some minor suggestions for further improvements or future work. This paper does not seem to present adequate evaluations in downstream tasks. You mentioned some potential applications of TCH-Set, such as MoE. I also think this is a very promising application scenario. Perhaps many audiences would also be curious to know if TCH-Set can demonstrate the same superior performance in these real-world tasks.

Viewpoint of Solution Set Optimization. On the other hand, we also want to show the solution set optimization we investigated in this paper also has it own advantages for many-objective optimization.

• Requirement from Real-World Application: The requirement of finding a few solutions to tackle many optimization objectives will naturally arise in many real-word applications such as building a small set of machine learning models (e.g., mixture of experts) to handle many different data or tasks, training a few agents to handle a large number of clients in federated learning, and producing a few different versions of advertisements to serve a large group of diverse audiences. For these cases, it is more natural to tackle the problem from the viewpoint of solution set optimization.

• No Redundant Objectives: In many real-world problems, the objectives we care about are not redundant or not highly correlated with each other. By keeping all objectives, the solution set optimization method can more flexibly tackle the trade-offs among all different objectives. For example, when all objectives are conflicting, our proposed (S)TCH-Set will actually find a Pareto solution with the optimal (S)TCH scalarization value for each group of objectives while the groups are adaptively assigned during the optimization process. If the best solution-objective group assignment is known, it is analogous to running the traditional (S)TCH scalarization to find a Pareto solution for each group of objectives. The flexibility of the few-solutions-for-many-objectives approach over the few-solutions-for-few-summarized-objectives is also an interesting research topic in future work.

• Bridging Different Approaches: To some degree, our proposed (S)TCH-Set method can be treated as a generalized (smooth) clustering method that assigns each solution to tackle different groups of solutions. If we only keep one representative objective for each group, it could become a dimensionality reduction approach at the end. In addition, if we treat the proposed (S)TCH-Set scalarization function as an indicator, it is actually an indicator-based method for many-objective optimization. We hope this paper can inspire more interesting follow-up works on bridging these different but related approaches.

We have added the above discussion in Appendix D.6 in the revised paper.

Q1. Objectives Redundancy for (S)TCH-Set: Is possible this scheme to solve many-objectives problems works well due to some redundancy in the objectives, meaning, objectives are correlated so some solutions that perform well on one of them should also perform well in the positively correlated objectives. Have you consider some dimensionality reduction techniques to maybe reduce which objectives should be evaluated during the scalarization?

We hope the discussions above can already clarify the relation between dimensionality reduction and our proposed method for solution set optimization. Our proposed method will work well for problems with some redundant objectives, where one solution will be assigned to tackle all the redundant objectives together. For problems without redundant objectives, our proposed (S)TCH-Set scalarization method can still find a set of few solutions to minimize the worst values of all objectives as much as possible.

In this work, we did not use any dimensionality reduction techniques to reduce the objectives during the optimization process. However, it could be a useful approach to significantly reduce the computational overhead, especially when there are redundant objectives in the problem. We leave the investigation of this research direction to future work.

Thank you very much for your time and effort in reviewing our work. Our responses to your concerns are as follows.

W1. Dimensionality Reduction for Many Objective Optimization: It would have been nice to touch or at least mention dimensionality reduction techniques and problems with redundant objectives. Seems its the other side of the coin, given that there is some correlation in the objectives for them to be satisfied or addressed well with a single solution. As shown in Figure 2, each solution address 20 of the 100 objectives, does this mean that the underlying 100 objective problem can be summarized by a 5 objective problem?

Thank you very much for bringing our attention to the research direction on dimensionality reduction. We fully agree with you that dimensionality reduction (focuses on the objectives) is an important counterpart of our proposed method (focuses on the solutions), and should be discussed in this paper.

Discussion on Dimensionality Reduction. First of all, following your suggestion, we have added the below brief introduction for dimensionality reduction in the related work section:

Dimensionality reduction [1,2,3] is a widely used technique to deal with many-objective optimization problems with potential redundant objectives. By summarizing all objectives by a few representative objectives, these methods can reformulate the originally challenging problem into a simpler problem with much fewer objectives. A detailed discussion with the dimensionality reduction can be found in Appendix D.6 due to the page limit.

[1] Kalyanmoy Deb and Dhish Kumar Saxena. On Finding Pareto-Optimal Solutions Through Dimensionality Reduction for Certain Large-Dimensional Multi-Objective Optimization Problems. KanGAL Report Number 2005011, 2005.

[2] Dimo Brockhoff and Eckart Zitzler. Are All Objectives Necessary? On Dimensionality Reduction in Evolutionary Multiobjective Optimization. PPSN 2006.

[3] Hemant Kumar Singh, Amitay Isaacs, Tapabrata Ray. A Pareto Corner Search Evolutionary Algorithm and Dimensionality Reduction in Many-Objective Optimization Problems. TEVC 2021.

We also agree with you that the dimensionality reduction technique is very useful for many-objective optimization, especially for problems with highly correlated or even redundant objectives. For example, in Figure 2, we show the result of our proposed method on a synthetic optimization problem with 100 objectives. To clearly demonstrate the behavior of our proposed method, we intentionally construct the problem such that it has $5$ groups of very similar $20$ objectives. Therefore, from the viewpoint of dimensionality reduction, these 20 objectives can be represented by a single objective. In this way, the original 100-objective problem can be summarized by a 5-objective problem as you mention.

Thank you very much for your support and for pointing out the error in the appendix. We will carefully revise the appendix and the whole paper.

We very much appreciate you pointing out the connection between STCH-Set and dimensionality reduction and bringing our attention to this promising research direction that we ignored. We will explore more ideas in this direction in future work.