Few for Many: Tchebycheff Set Scalarization for Many-Objective Optimization
Authors: Xi Lin
Yilu Liu
Xiaoyuan Zhang
Fei Liu
Zhenkun Wang
Qingfu Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: multi-objective optimization
many-objective optimization
Tchebycheff scalarization
Primary area: optimization
TL;DR: We propose a novel Tchebycheff set scalarization approach to find a small set of solutions to tackle a large number of optimization objectives.

Abstract: Multi-objective optimization can be found in many real-world applications where some conflicting objectives can not be optimized by a single solution. Existing optimization methods often focus on finding a set of Pareto solutions with different optimal trade-offs among the objectives. However, the required number of solutions to well approximate the whole Pareto optimal set could be exponentially large with respect to the number of objectives, which makes these methods unsuitable for handling many optimization objectives. In this work, instead of finding a dense set of Pareto solutions, we propose a novel Tchebycheff set scalarization method to find a few representative solutions (e.g., 5) to cover a large number of objectives (e.g., $>100$) in a collaborative and complementary manner. In this way, each objective can be well addressed by at least one solution in the small solution set. In addition, we further develop a smooth Tchebycheff set scalarization approach for efficient optimization with good theoretical guarantees. Experimental studies on different problems with many optimization objectives demonstrate the effectiveness of our proposed method.

Published as a conference paper at ICLR 2025
FEW FOR MANY: TCHEBYCHEFE SET SCALARIZATION FOR MANY-OBIECTIVE OPTIMIZATION
Lin', Yilu Liu', Xiaoyuan Zhang', Fei Liu', Zhenkun Wang", Qingfu Zhang': City University of Hong Kong, 'Southern University of Science and Technology tki.lin, yiluliu3, xzhang2523-c, fliu36-o emy. cityu. edu hk
wangzhenkun90@gall com, qingfu. zhang werigeiiitt..ee edu. edu.hk
ABSTRACT
Multi-objective optimization can be found in many real-world applications where some conflicting objectives can not be optimized by single solution. Existing optimization methods often focus on finding set of Pareto solutions with different optimal trade-offss among the objectives. However, the required number of solutions well approximate the whole Pareto optimal set could be exponentially large with respect to the number of objectives, which makes these methods unsuitable for handling many optimization objectives. this work, instead of finding a dense set of Pareto solutions, we propose a novel Tchebycheff set scalarization method to find a few representative solutions (c.g.. 5) to cover a large number objectives (e.g.. > 100) in collaborative and complementary manner. In this way, each objective can be well addressed by at least one solution in the small solution set. addition, we further develop smooth Tehebycheff set scalarization approach for efficient optimization with good theoretical guarantees. Experimental studies on different problems with many optimization objectives demonstrate the effectiveness of our proposed method.
INTRODUCTION
In real-world applications, it is very often that many optimization objectives should be considered the same time. Examples include manufacturing or engineering design with various specifications to
achieve (Adriana al.
2018
Wang et al.
2020), decision-making systems with different factors to
Hayes et al. 2022). and molecular generation with multiple criteria to satisfy (Jain et al. 2023 Zhu et al.) 2023). For non-trivial problem, these optimization objectives conflict one another. Therefore, it is very difficult, if not impossible, for a single solution to accommodate all objectives at the same time (Mettinen 1999 Ehrgoti 2005).
consider (Roijers et al.
2014
In the past several decades, much effort has been made to develop efficient algorithms for finding a set of Pareto solutions with diverse optimal trade-offs among different objectives. However, the Pareto set that contains all optimal trade-off solutions could be an manifold in the decision space, of which the dimensionality can large for a problem with many objectives (Hillermeier) 2001). The number of required solutions to well approximate the whole Pareto set will increase exponentially with the number of objectives, which leads to prohibitively high computational overhead. addition, large solution set with nigh-dimensional objective vectors could easily become unmanageable for decision-makee Indeed, a problem with more than objectives is already called the many-objective optimization problem (Fleming et al. 2005 Ishibuchi et al. 2008), and existing methods will struggle to deal with problems with a significantly larger number of optimization objectives (Sato & Ishibuchi] 2023).
In this work, instead of finding a dense set of Pareto solutions, we investigate a new approach for many-objective optimization, which aims to find small set of solutions (e.g., to handle large number of objectives (e.g., > 100). In the optimal case, each objective should be well addressed by least one solution the small solution set illustrated in Figure (d). This setting is important for different real-world applications with many objectives to optimize, such as finding complementary
"Corresponding author.

---

Published as a conference paper at ICLR 2025
04
600
41
U4
80
83
84 500
12
of 66
1,30
05
02
(a) 10 Solutions
(b) 100 Solutions
(c) 1,000 Solutions
(d) 5 Solutions (Ours)
Figure I: Large Set v.s. Small Set for Multi-Objective Optimization. (a)(b(() Large Set: Classic algorithms use 10, 100 and 1000 solutions approximate the whole Pareto front for 2 and 3-objective optimization problems. The required number of solutions for a good approximation could increase exponentially with the number of objectives. (d) Small Set: This work investigates how to efficiently find a few solutions (e.g.. 5) to collaboratively handle many optimization objectives (e.g., 100).
engineering designs to satisfy various criteria (Fleming et al. 2005), producing a few different versions of advertisements to serve a large group of diverse audiences (Matz 2017: Eckles et al. 2018), and building a small set of models to handle many different data (i et al. 2014 Zhong et al.
2016) tasks (Standley al.) 2020; Fifty al., 202T). However, this demand has received little attention from the multi-objective optimization community. To properly handle this setting, this work
makes the following contributions
We propose novel Tehebycheff set (TCH-Ser (ett) scalarization approach find few optimal solutions in collaborative and complementary manner for many-objective optimization.
We further develop a smooth Tchebycheff set (STCH-Set) scalarization approach tackle the non-smoothness of TCH-Set scalarization for efficient gradient- based optimization.
We provide theoretical analyses show that our proposed approaches enjoy good theoretical properties for multi-objective optimization.
We conduct experiments on various multi- nulti-objective optimization problems with many objectives to demonstrate the efficiency of our proposed method.
2 PRELIMINARIES AND RELATED WORK
2.1 MULTI-OBJECTIVE OPTIMIZATION
In this work, we consider the following multi-objective optimization problem:
min xEX
= (fi (m. (x)))
=
(1)
where E X' is solution and fxx) = (fi(z),
fm())) R are differentiable objective functions. For a non-trivial problem, there is no single solution x" that can optimize all objective functions the same time. Therefore, have the following definitions of dominance, (weakly) Pareto optimality, and Pareto set/front for multi-objective optimization (Miettinen 1999):
Definition (Dominance and Striet Dominance). Let (=))) (b) E X two solutions for problem I (()) is said to dominate (b), denoted as f(x(1)) f((("),, ifand only if f((x(()) I f((x(()) Vi
{I...,, m and fa(((a)) < (x)( 3j E {l....,m} In addition, x( is said to strictly dominate (b)) (i.e., f(x(1)) Karier (z)()))) and only if f((x!()) < f((x(()) Vi E (1....,m..
Definition 2 (( ((Weakly) Pareto Optimality). A solution x² E X is Pareto optimal if there is no a E X such that f(x) < (x=).. A solution x' E X' is weakly Pareto optimal if there
X such that
f(x) Kuriet f(x').
Definition 3 (Pareto Set and Pareto Front). The set of all Pareto optimal solutions X* {x A x()(()
f(æ) Vā E X} is called the Pareto set. Its image in the objective space f(X*) = (f(x) E 1 X*} is called the Pareto front.
'Our source cade is available http::/gtthb.ccm///iSSSCCCCC
2

---

Published as a conference paper at ICLR 2025
Under mild conditions, the Pareto set and front could be (m 1) d-mmennsional manifold in the decision or objective space (Hillermeier, 2001). which contains infinite Pareto solutions. Many optimization methods have been proposed to find finite set of solutions to approximate the Pareto set and front (Mietrinen 1999. Ehrgott 2005 Zhou et al., 2011). If at least & solutions are needed to handle each dimension of the Pareto front, the required number of solutions could be ((k(m=-1) for a problem with m optimization objectives. Two illustrative examples with set of solutions to approximate the Pareto front for problems with 2 and 3 objectives are shown in Figure However, the required number of solutions will increase exponentially with the objective number m. leading to an extremely high computational overhead. It could also be very challenging for decision-makers to efficiently handle such large set of solutions. Indeed, for problem with many optimization objectives, a large portion of the solutions could become non-dominated and hence incomparable with each other (Purshouse & Fleming, 2007: Knowles & Core 2007
In the past few decades, different heuristic and evolutionary algorithms have been proposed to tackle the many-objective black-box optimization problems (Zhang & Li 2007; Bader Zitzler 2011 Deb & Jain, 2013). These algorithms typically aim to find a set of a few hundred solutions to handle problems with 4 to a few dozen optimization objectives (Li et al., 2015: Sato & Ishibuchi] 2023). However, they still struggle to tackle problems with significantly many objectives (e.g., > 100), and cannot efficiently solve large-scale differentiable optimization problems. Dimensionality reduction (Deb & Saxenal 2005 Brockhoff & Zitzler 2006; Singh et al. (201I) is widely used technique to deal with many objectbee optimization problems with potential redundant objectives. By summarizing all objectives by 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
2.2
WAADIENT-BASED MULTI-OBJECTIVE OPTIMIZATION
When all objective functions are differentiable with gradient [V we have the following definition for Pareto stationarity:
Definition& 4 (Pareto Stationary Solution). A solution x E X is Pareto stationary if there exists a set of weights E m-1 {a Σ 0g 1,0; ;3 2 Vi} such that the corvex combination of gradients D O4 ((( = 0.
Multiple Gradient Descent Algorithm One popular gradient-based approach is to find a valid gra- dient direction such that the values of all objective functions can be simultancously improved (Fliege
& Svaiter 2000 Schäffler et al. 2002 Désidéri 2012). The multiple gradient descent algorithm (MGDA) (Désidéri 2012 Sener & Koltun 2018) obtains valid gradient d, E a. Vx( by solving the tollowing quadratic programming problem at each iteration:
06 (((()))) 8.l. Σn a. 1, a₁ 2 0, Vi
min| CC2
m,
(2)
and updates the current solution by a simple gradient descent 0; = xx - dr. If d, = 0, it means that there no valid gradient direction that can improve all objectives at the same time, and therefore 2; is a Pareto stationary solution (Désidéri 2012 | Fliege et al. 2019). This idea has inspired
many adaptive gradient methods for multi-task learning Yu et 2020 Liu et al. 202 b Momma
et al. 2022, Liu et al. [002]] Navon et al., 2022, Senushkin et al. 2023 Lin et al. 2023 Liu ct al.
2024). Different stochastic multiple gradient methods have also been proposed in recent years (L.i
Vicente 2021 Zhou et al. 2022 Fernando et al. 2023 Chen et al. 2023 Xiao et al. 2023
The location of solutions found by the original MGDA not controllable, and several extensions have been proposed to find set of diverse solutions with different trade-offs (Lin et al., 2019 Mahapatra & Rajan 2020; Ma et al. 2020) Liu et al. 2021c). However, large number of solutions still required for good approximation to the Pareto front. For solving problems with many objectives, MGDA and its extensions will suffer from a high computational overhead due to the high-dimensional quadratic programming problem (2) at each iteration. In addition, since large portion of solutions is non-dominated with each other, it could be very hard to find a valid gradient direction to optimize all objectives at the same time.
Scalarization Method Another popular class of methods for multi-objective optimization is the scalarization approach (Miettinen) 1999 Zhang & Li 2007). The most straightforward method is
3

---

Published as a conference paper at ICLR 2025
(a) Solution
(b) Solution
(c) Solution 3
(d) Solution 4
(e) Solution
(f) All Solutions
Figure 2: Few Solutions to Address Many Optimization Objectives. (a)-(e): different solutions
tackle different optimization objectives in a complementary manner. (I): They together successfully handle all 100 optimization objectives.
linear scalarization (Geoffrion 1967
(Linear Scalarization)
min g (x) = Σ Xch((a), #EX
(3)
where X (..,.... Am) is a preference vector
objectives on the simplex A A {A) > 1 A; = 1, A; 2 0 Vij. A set of diverse solutions can be obtained by solving the scalarization problem with different preferences. Recently, different studies have shown that well-tuned linear ccalarization can outperform many adaptive gradient methods for multi-task learning Kurin al. (2022);
m
y Xin et al. (2022): Lin al. (2022): Royer et al.] (2023). However, from the viewpoint of multi-objective optimization, linear scalarization cannot find any Pareto solution on the non-convex
part of the Pareto front (Das Dennis 1997 Ehrgoti 2005
Hu et al., 2023).
Many other scalarization methods have been proposed in past decades. Among them, the Tchebycheff scalarization with good theoretical properties a promising alternative (Bowman, 1976. Steuer &
Choo 1983):
(Tchebycheff Scalarization)
min 9
(CHH) (xc
A)
max (A((f(())=2?)) 15i5m
(4)
where A E A m-1 is the preference and x² E RD is the ideal point (e.g., 2, min fa( - with a small e > 0). It is well-known that the Tchebycheff scalarization is able to find weakly Pareto solutions for any Pareto front (Choo & Atkins 1983). However, the max operator makes it become nonsmooth and hence suffers from slow convergence rate by subgradient descent (Goffin 1977) for differentiable multi-objective optimization. Recently, smooth Tchebycheff scalarization approach (Lin et al. 2024) has been proposed to tackle the nonsmoothness issue:
m
(Smooth Tehebycheff Scalarization)
min xEX
(TTCH)
(z)
p log
(5)
where y is the smooth parameter with a small positive value (e.g., 0.1). According to (Ln et al. 2024
this smooth scalarization approach enjoys a fast convergence rate for the gradient- based method, while also having good theoretical properties for multi-objective optimization. A similar smooth optimization approach has also been proposed in He et al. (2024) for robust multi-task learning. Very recently, Qiu al. (2024) prove and analyze the theoretical advantages of smooth Tchebycheff scalarization (5) over the classic Tchebycheff' scalarization for multi-objective reinforcement learning (MORL).
The scalarization methods do not have to solve a quadratic programming problem at each iteration and thus have lower pre-iteration complexity than MGDA. However, they still need to solve large number of scalarization problems with different preferences to obtain dense set of solutions to approximate the whole Pareto set.
TCHEBYCHEFF SET SCALARIZATION FOR MANY OBJECTIVE OPTIMIZATION
3.1 SMALL SOLUTION SET FOR MANY-OBJECTIVE OPTIMIZATION
Unlike previous methods, this work does not aim to find a huge set of solutions for approximating the whole Pareto set. Instead, we want to find small set of solutions in collaborative and
4

---

Published as a conference paper at ICLR 2025
complementary way such that each optimization objective can be well addressed by least one solution. We have the following formulation of our targeted set optimization problem:
min f(x) min fi(),, min f2(x), min fm (x)),
(6)
Xx=(
#c x
xxXx
where Xx = (xx(0))
LK ]k is set of K solutions to tackle all m objectives (fi( With large K m, we will have a degenerated problem:
min f(z) X
min fI(2), min fa(z),.... min fm (x)), E.'
an(m)
where each objective function fi is independently solved by its corresponding solution x(1) E X via single objective optimization and the rest (K m) solutions are redundant. If K 1, the set optimization problem (6 will be reduced to the standard multi-objective optimization problem (
K < m, which finds a small set of solutions (e.g., K = 5) to tackle a large number of objectives (e.g., 2 100) as illustrated in Figure In the ideal case, the ground truth optimal objective group assignment already known (c.g.. which objectives should be optimized together by the same solution), it is straightforward to directly find an optimal solution for each group of objectives. However, for a general optimization problem, the ground truth objective group assignment is usually unknown in most cases, and finding the optimal assignment could be very difficult.
In this work, we are more interested in the case
Very recently, similar setting has been investigated in two concurrent works (Ding et al. 2024 Li et al., 2024). Ding et al. (2024) study the sum-of-minimun (SoM) optimization problem (((x(())} that can be found in many machine learning ap- plications such mixed linear regression (Yi al. 2014 Zhong et al. 2016). They generalize the classic k-means++ (Arthur) (007) and Lloyd's algorithm (Lloyd, 1982) for clustering to tackle this problem. but do not take oulti-objective optimization into consideration. L et al. (2024) pro- pose a novel Many-objective multi-solution Transport (MosT) framework to tackle many-objective optimization. With bi-level optimization formulation, they adaptively construct a few weighted multi-objective optimization problems that are assigned to different representative regions on the Pareto front. By solving these weighted problems with MGDA, diverse of solutions can be obtained to well cover all objectives. In this work, we propose a straightforward and efficient set scalarization approach to explicitly optimize all objectives by a small of solutions. A detailed experimental comparison with these methods can be found in Section
Ei min (f( (x."), fa
3.2 TCHEBYCHEFF SET SCALARIZATION
The set optimization formulation is still a multi-objective optimization problem. In non-trivial cases, there is no single small solution set Xx with K solutions that optimize all m objective functions } at the same time. To tackle this optimization problem, we propose the following Tehebycheff set (TCH-Set) scalarization approach:
TCH-Satt (xx(A)= = max 1si5m
As( min fi(x:) = x
min Xx= xx=(x({)) K
max Isism
X min ISkS
fi (2)) 22,)
(8)
where À (A1,.. Am) and 2" (2) ( )(m)) are the preference and ideal point for each objective function. In this way, all objective values ) among the whole solution set Xx (x(*)) k=1 are scalarized into a single function (TCH-Seet [XxlX (A). In this work, a simple uniform vector X = (2,,... 1
m is used in all experiments without any specific preference among the objectives. A discussion the effect of different preferences can be found in Appendix [D.2]
By optimizing this TCH-Set scalarization function we want to find an optimal small solution set X such that each objective can be well addressed by at least one solution (k) E XX with a low worst objective value maxiçism { (minn -nini<s<< & f. (*)) - } When the solution set contains only single solution (e.g., K 1), it will be reduced to the classic single-solution Tchebycheff
scalarization (4). To avoid degenerated cases and focus on the key cow-for-many setting, we make the following two assumptions in this work:
5

---

Published as a conference paper at ICLR 2025
Assumption 1 (No Redundant Solution). We assume that solution in the optimal solution set X = argminx, g (CH..Sot) (Xx] X) will be redundant, which means
Sct) (X < g (CCH- (Xx (x(())12)
holds for any 1 S k S K m with A O.
Assumption 2 (All Positive Preference). the few-for-many setting, we assume that the preferences should be positive for all objectives such that (E:=) X; 1, > 0 Vi}.
These assumptions are reasonable in practice, especially for the few-for-many setting (e.g.. K & m) considered in this work. For a general problem, it is extremely rare that small number of solutions (e.g., 4) can exactly solve large number of objectives (e.g., m 1, 000). From the viewpoint of clustering (Ding et al., 2024), it is analogous to the case that all the 1, 000 data points under consideration are exactly located in 4 different locations. If we do meet this extreme case with p redundant solutions, for-m-ohjectives problem. Similarly, if some of the preferences (e.g., q) are 0, we can also simply reduce the original m-objective problem into (m -bjjectiv problem that satisfies the positive preference assumption.
simply reduce the number of solutions to make it (K -)ssuuiiions-
From the viewpoint of multi-objective optimization, have the following guarantee for the optimal solution set of Tchebycheff set scalarization:
Theorem (Existence of Pareto Optimal Solution for Tchebycheff Set Scalarization). There exists
an optimal solution set Xi for the Tchebycheff set scalarization optimization problem (8) such that all solutions Xi are Pareto optimal of the original multi- oulri-objective optimization problem (7) In
addition, if the optimal set Xi is unique, all solutions in X k are Pareto optimal.
Proof Sketch. This theorem can be proved by construction and contradiction based on Definition for (weakly) Pareto optimality and the form of Tchebycheff set Scalarization A detailed proof provided in Appendix/A. A.
should be emphasized that, without the strong unique optimal solution set assumption, we only have a weak existence guarantee for the Pareto optimality. For an optimal solution set for the Tehebycheff set scalarization (8). it is possible that many of the solutions are not even weakly Pareto optimal for the original multi-objective optimization problem (I). This finding could be a bit surprising for multi-objective optimization, and we provide detailed discussion Appendix [A.5] In addition to the Pareto optimality guarantee, the non-smoothness of TCH-Set scalarization might also hinder its practical usage for efficient optimization. To address these crucial issues, we further develop a smooth Tchebycheff set scalarization with good optimization property and promising Pareto optimality guarantee in the next subsection.
3.3 SMOOTH TCHEBYCHEFE SET SCALARIZATION
The Tchebycheff scalarization formulation (8) involves max and min operator, which leads to its non-smoothness even when all objective Tunctions { are smooth. In other words, the Tchebycheff set scalarization g (TC Sal) (.X A) is not differentiable and will suffer from a slow convergence rate by subgradient descent. To address this issue, we leverage the smooth optimization approach (Nesterov 2005 Beck & Teboulle| 2012, Chen Chen 2012) to propose smooth Tchebycheff set scalarization for objei-obeective optimization.
According to Beck & Teboulle (012)) for the maximization function among all objectives maxigism (xx) (2( Jm (x) ()). we have the smooth maximization function:
smax ISis
= (nel
log
Σ
f((m) e
(10)
where y is smooth parameter. Similarly, for the minimization among different solutions for the i-th fi())(2),, (((
objective minigagx (f((z(1), ...., ((,(0)))...,_((((((()) we have the smooth minimization function:
K
(k))
smin Iskšk
f(((() ((()).,,((((()))))) = -44 -44 log
Σ
e
(11)

---

Published as a conference paper at ICLR 2025
where 14, is smooth parameter.
By leveraging the above smooth maximization and minimization functions, we propose the smooth Tchebycheff set scalarization (STCH-Set) scalarization for multi-objective optimization:
min
9 pm
(St)
(Xx
smax isism
A smin (zx(1) IskS
X (ax(k) ((a())) )
A 1INKS /=(=(()))=1
pog
1=1
A1 -14 log Mn x 12lank))/us) )
ps log Σ
(12)
If the same smooth parameter μl following simplified formulation:
Mm
μ are used for all smooth terms, we have the
m Xo
(- log Eter meatthye) - )+t)
min (x=(=
9N
Sel)
(xx = poo
(13)
When K 1, it will reduce to the single-solution smooth Tchebycheff scalarization (5) Similarly to the non-smooth TCH-Set counterpart, the STCH-Set scalarization also has good theoretical properties for multi-objective optimization:
Theorem 2 (Pareto Optimality for Smooth Tehebycheff Set Scalarization). All solutions in the optimal solution set X for the smooth Tchebycheff set scalarization problem (2) are weakly Pareto optimal of the original multi-objective optimization problem (7) In addition, the solutions are Pareto optimal if either
1. the optimal solution set X is unique, or
2. all preference coefficients are positive (A; > 0 Vi).
Proof Sketch. This theorem can be proved by contradiction based on Definition 2 for (weakly) Pareto optimality and the form of smooth Tehebycheff set scalarization I12 We provide a detailed proof in Appendix A.2
Theorem 3 (Uniform Smooth Approximation). The smooth Tchebycheff set (STCH-Set) scalarization
(STCH-Set)
X k (A) a uniform smooth approximation the Tchebycheff (TCH-Set) scalarization
( (TCH-Ser)
X k {)), and have:
lim (Tt) 10 V (m (X
(xxIA)
(xxlA)
(14)
for any valid set X₂ C
Proof Sketch. This theorem can be proved by deriving the upper and lower bounds of the TCH-Set scalarization g (TCH-Set) x ()) with respect to the smooth smax and smin operators the STCH-Set
scalarization (STCH.Ser)
(X A). A detailed proof is provided in Appendix A.3
(p.(pmmm 1m
According to these theorems, for any smooth parameters and {n]m all solutions the optimal X for STCH-Set scalarization (12) are also (weakly) Pareto optimal. In addition, with small (et)
smooth parameters
0, 4 0 Vi, the value of (u.)m m (X x [A) will be close to its non-smooth
counterpart g (TC Set) (X xc A) for all valid solution sets Xx. which is also the case for the optimal set
X arg min xx g (TCH Set)
X ()). Therefore, it is reasonable to find an approximate optimal so-
lution set for the original g (TCH-Set) (Xx (A) by optimizing its smooth counterpart (STCH. (X (A) with small smooth parameters j and
7

---

Published as a conference paper at ICLR 2025
Algorithm 1 STCH-Set Scalarization for Multi-Objective Optimization
1: Input: Preference X, Step Size (n:);= Initial X
2: for / = 1 to T do
3: X = X
Th Vg (TC (X
(A)
(2)
K
4: end for
5: Output: Final Solution x
The STCH-Set scalarization function Ir. (p.(,+ }
(Xx () can be efficiently optimized by any gradient- based optimization method, where we treat all solutions as a single solution matrix. A simple gradient descent algorithm for STCH-Set is shown in Algorithm [ However, when the objective functions (f.(z) Lmn are highly non-convex, it could be very hard to find the global optimal set X for (StCH-Set)
(StCH-Set)
(A) In this case, have the Pareto stationarity guarantee for the tradientbbsed (.
method:
Theorem 4 (Convergence to Pareto Stationary Solution). If there exists a solution set Xx such that (STCH-See) (X (A) 0 for all ((k)) E Åx, then all solutions in X are Pureto stationary V p. (m
solutions of the original multi-objecctive optimization problem
Proof Sketch. We can prove this theorem by analyzing the form of gradient for STCH-Set scalariza- Set)
(xx A) 0 for each solution (*) with the condition for Pareto stationarity in tion V g00g p.
Definition A detailed proof provided in Appendix A.4
When K reduces to 1, all these theorems exactly match their counterpart theorems for single-solution smooth Tchebycheff scalarization (Lin al. 2024
4 EXPERIMENTS
Baseline Methods In this section, compare our proposed TCH-Set and STCH-Set scalariza- tion with three simple scalarization methods: (1) linear scalarization (LS) with randomly sampled preferences, (2) Tehebycheff scalarization (TCH) with randomly sampled preferences, (3) smooth Tehebycheff scalarization (STCH) with randomly sampled preferences (Lin et al., 2022). as well as two recently proposed methods for finding small set of solutions: (4) the many-objectiv multi- solution transport (MosT)) method (Li et al. 2024), and (5) the efficient sum-of-minimun (SoM) optimization method (Ding al. 2024).
Experimental Setting This work aims to find a small set Xx with solutions to address all m objectives in each problem. For each objective f((x), care about the best objective value min fi( achieved by the solutions in Xx. Both the worst obtained value among all objectives maxigism minge Xg fi(x) and the average objective value Ex= millse xx fi(x) are reported
for comparison. Detailed experimental settings for each problem can be found in Appendix B Due to
the page limit, more experimental results and analysis can be found in Appendix
4.1 EXPERIMENTAL. RESULTS AND ANALYSTS
Convex Many-Objective Optimization We first test our proposed methods for solving convex multi-objective optimization with m 128 or m 1, 024 objective functions with different numbers of solutions (from 3 to 20). We independently run each comparison 50 times. In each run, we randomly generate m independent convex quadratic functions as the optimization objectives for all methods. The mean worst and average objective values for each method over 50 runs on the m 128 case are reported in Table I and the full table can be found in Appendix C.1 We also conduct the Wilcoxon rank-sum test between STCH-Set and other methods for all comparisons at the 0.05 significant level. The (+/- = /-) symbol means the result obtained by STCH-Set is significantly better, equal to, worse than the results of the compared method.
8

---

Published as a conference paper at ICLR 2025
Table 1:
The results on convex optimization problems with K (3,4,5,6, 10) solutions. Mean
worst and average objective values over 50 runs are reported. Best results are highlighted in bold, and the full table can be found in Appendix C.T
LS
TCH
STCH
MosT
SoM
TeH-Set
-TCH-Set
number of objectives 128
worst
4.64c+00(+) 4,44c+00(+) 4,41c+00(+) 2.12c+00(+) 1.86c+00(+) 1.02c+00(+))
6.08e-01
average
8.61c-01(+) 8.03c-01(+) 7.80c-0((+) 3.45c-01(+) 2.02e-01(-)
3.46c-01(4)
2.12c-01
worst
4.23e+00(+) 3.83e+00(+) 3.68e+00(+) 1.48e+00(+) 1.12e+00(+) 6.74e-01(+)
3.13e-01
=
average
7.45c-01(+)
6.54c-01(+) 6.41c-01(+) L.85c-0((+)
1.12c-01(+)
2.27c-01(+)
9.44e-02
worst 4.17e+00(+) 3.56e+00(+) 3.51e+00(+) 1.02c+00(+) 9.20e-01(+)
4.94e-01(+)
1.91c-01
K =
average
7.08e-01(+)
5.75c-01(+) 5.05c-01(+) 9.81e-02(+)
7.95e-02(+)
1.60e-01(+)
5.12c-02
worst 3.81e+00(+) 3,41e+00(+) 3.20++00(+) 9.56e-01(+) 7.03e-01(4) 3.72e-01(+)
1.36c-01
K- =
average 6.72c-01(+) 5.31c-01(+) 5.15c-01(+) 8.34e-02(+)
5.34e-02(+)
1.19c-01(+)
3.15c-02
K =
worst
3.69++00(+) 2.94c+00(+) 2.61e+00() 8.32e-01(+) 5.20e-01(4) 2.84c-01(+)
1.02e-01
average (.1e-00(+)) 4.57c-01(+) 4.22c-01(+) 6.91e-02(+)
3.40e-02(4)
8.53c-02(+)
1.78e-02
worst 3.68)+00(+) 2.69e+00(+) 2.40++00(+) 6.27e-01(+) 4.07e-01(+) 1.95e-0((+)
7.99e-02
K = average 5.69c-01(+) 4.07c-01(+) 3.20c-0(++) 4.59c-0((+) 2.43e-02(4)
5.92c-02(+)
1.34e-02
Wilcoxon Rank-Sum Test Summary
+/= =
worst
6/0/0
6/0/0
6/0/0
6/0/0
6/0/0
6/0/0
average
6/0/0
6/0/0
6/0/0
6/0/0
S/0/1
6/0/0
Table 2: The results on mixed linear regression with noisy level 0.1. Full table in Appendix C.2
LS
TCH
STCH
SoM
TCH-Set
STCH-Set
worst
3.84c+01(+) 2.45e+01(+) 2.43c+01(4) 2.50e+00(+) 4.19c+00(+)
2.10c+00
average 2.70e+00(+) 1.46e+00(+) 1.44e+00(+) 188e-01(() 6.53e-01(+)
4.72c-01
K 10
worst
2.21e+01(+) 2.49c+01(+) 3.92c+01(4) 3.46e+00(+) 2.04c+00(+)
5.00e-01
average 1.09e+00(+) 1.199+00(+) 3.01e+00(+) 2.33e-01(+)
3.83e-0((t)
2.00e-01
K 15
worst average 3.07c+00(+) 1.02c+00(+) 1.02c+00(+) 1.97c-01(+) 3.22c-01(+)
4.20c+01(+) 2.11c+01(+) 2.21c+01(4) 2.57c+00(+) 1.64c+00(+)
2.70e-01
1.66e-01
K = 20 worst 4.20c+01(+) 2.14c+01(+) 2.04c+01(+) 1.44c+00(+) 1.79c+00(+)
2.27e-01
average 3.09c+00(+) 8,35c-0((+) 8.87c-0((+) 1.84c-0((+) 3.29c-01(+)
1.66e-01
According to the results, the traditional methods (e.g., LS/TCH/STCH) fail properly tackle the few solutions for many objectives setting considered in this work. MosT achieves much better performance than the traditional methods by actively finding a set of diverse solutions to cover all objectives, but it cannot tackle the problems with 1024 objectives in reasonable time. In addition, MosT is outperformed by SoM and our proposed STCH-Set Set, which directly optimizes the performance for each objective. Our proposed STCH-Set performs the best in achieving the low worst objective values for all comparisons. In addition, although not explicitly designed, STCH-Set also achieves a very promising mean average performance for most comparisons since all objectives are well addressed. The importance of smoothness for set optimization is fully confirmed by the observation that STCH-Set significantly outperforms TCH-Set on all comparisons. More discussion on why STCH-Set can outperform SoM on the average performance can be found in Appendix D.4
Noisy Mixed Linear Regression We then test different methods' performance on the noisy mixed linear regression problem as in (Ding et al.) 2024 For each comparison, 1, 000 data points are randomly generated from K ground truth linear models with noise. Then, with different optimization methods, we train K linear regression models to tackle all 1, 000 data points where the objectives are the squared error for each point. Each comparison are run 50 times, and the detailed experiment setting is in Appendix B

---

Published as a conference paper at ICLR 2025
We conduct comparison with different numbers of K (5. 10, 15, 20} and noise levels {0.1, 0.5, 1.0). The results with o = 0.1 are shown in Table 2 and the full results can be found in Appendix C.2) According to the results, proposed STCH-Set can always achieve the lowest worst objective value, and achieves the hest average objective value in most comparisons.
(a) LS
(b) TCH
STCH
(d) SoM
(e) TCH-Set
(1) STCH-Set
Figure 3: Different methods' performance for the same mixed nonlinear regression problem. We report the performance on the same set of 100 randomly sampled objectives. STCH-Set can properly address all objectives and achieve the best overall performance. TCH-Set has a much better worst objective value than LS/TCH/STCH but is not reflected in this figure.
Table 3: Results mixed nonlinear regression with noisy level 0.1. Full table in Appendix C.3
LS
TCH
STCH
SoM
TCH-Set
STCH-Set
K = 5
worst
2.34c+02 (+) 1.68c+0((4) 1.57c+02(+) 1.68c+01(+) 1,94c+01(+)
7.43e+00
average 9.19e+00(+) 8.50e+00(+) 7.90e+00(+) 8.54c-01()) 3,48e+00(4)
1.89++00
3.23c+02(+) 1.72c+02(+) 1.57c+02(+) 4,42c+00(+) 6.07c+00(4) average 8.70e+00 (+) 6.65e+00(+) 5.85e+00(+) 1.22e-01(+)
worst
6.28e-01
K 10
1.03e+00(+)
5.99e-02
worst average 8.33c+00(+) 5.66c+00(+) 4.89c+00(+) 1.47c-01(+) 3.27e-01(+)
3.65c+02(+) 2. 1,c0+02(+)) 1.62c+02(+) 1.10c+00(+) 1,57c+00(+)
2.05e-01
K 15
1.27e-02
worst 3.36++02(+) 2,04c+02(+) 1.81++0((+) 5,59c+00(+) 4.37c+00(+)
6.22e-01
K 20
average 8.81e+00(+) 6.92c+00(+) 6.23c+00(+) 1124e-0((+) 9.09c-01(+) 6.27e-02
Noisy Mixed Nonlinear Regression Following (Ding et al. 2024). we also compare different methods on the noisy mixed nonlinear regression. The problem setting (details in Appendix B is similar to the mixed linear regression, but we now build nonlinear neural networks the models. According to the results in Table 3 and Appendix CC3] STCH-Set can still obtain the best overall performance for most comparisons. We visualize different methods' performance on 100 sampled data in Figure 3 and it is clear that STCH-Set can well address all objectives with the best overall performance.
CONCLUSION, LIMITATION AND FUTURE WORK
Conclusion In this work, have proposed a novel Tchebycheff set (TCH-Set) scalarization and a smooth Tchebycheff set (STCH-Set) scalarization to find a small set of solutions for many- objective optimization. When properly optimized, each objective in the original problem should be well addressed by at least one solution in the found solution set. Both theoretical analysis and experimental studies have been conducted demonstrate the promising properties and efficiency of TCH- SEEH-Se/SSTCH-SS scalarization. Our proposed method is complement rather than a replacement for the traditional multi-objective optimization method, and we hope it can inspire more interesting follow-up work to tackle the important lew-for-many problems that naturally arise in many real-world applications.
Limitation and Future Work This work proposes a general optimization method for multi- objective optimization which are not tied to particular applications. We do not see any specific potential societal impact of the proposed methods. This work only focuses the deterministic optimization setting that all objectives are always available. One potential future research direction is to investigate how to deal with only partially observable objective values in practice.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported by the Research Grants Council of the Hong Kong Special Adminis- trative Region, China (CityU11215622 and C1yU11221523),, the National Natural Science Foun- dation of China (Grant No. 02476118), the Natural Science Foundation of Guangdong Province (Grant No. 2024A1515011759) and the National Natural Science Foundation of Shenzhen (Grant 0o.JCY12002033011130133333
REFERENCES
Margareta Ackerman, Shai Ben-David, Simina Brânzei, and David Loker. Weighted clustering. In AAAI Conference on Artificial Intelligence (AAAI), 2012.
Schulz Adriana, Wang Harrison, Crinspun Eitan, Solomon Justin, and Matusik Wojciech. Interactive exploration design trade-offs. Acm Transactions on Graphics, 37(4):1-14, 2018.
David Arthur. K-means++: The advantages of careful seeding. In Proc. Eighteenth Annual ACM- SIAM Symposium on Discrete Algorithms, pp. 1027-1035, 2007.
Johannes Bader and Eckart Zitzler. Hype: An algorithm for fast hypervolume-based many-objective optimization. Evolutionary compulation, 19(1):45-76, 2011.
Amir Beck and Mare Teboulle. Smoothing and first order methods: A unified framework. SIAM Journal on Optimization, 22(2):557-580, 2012.
Dimitri Bertsekas, Angelia Nedic, and Asuman Ozdaglar. Convex analysis and optimization, volume 1. Athena Scientific, 2003.
Joseph Bowman. On the relationship of the tchebycheff norm and the efficient frontier of multiple- criteria objectives. In Multiple criteria decision making, pp. 76-86. Springer, 1976.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Dimo Brockhoff and Eckart Zitzler. Are all objectives necessary? on dimensionality reduction in evolutionary multiobjective optimization. Lecture Notes in Computer Science, 4193(1):533-542, 2006.
Lisha Chen, Heshan Fernando, Yiming Ying, and Tianyi Chen. Three-way trade-off in multi oulti-objective learning: Optimization, generalization and confdict-avoidance. In Advances Neural Information Processing Systems (NeurIPS), 2023.
Xiaojun Chen. Smoothing methods for nonsmooth, nonconvex minimization. Mathematical pro- gramming, 134:71-99, 2012.
Eng Ung Choo and DR Atkins. Proper efficiency in nonconvex multicriteria programming. Mathe-
matics of Operations Research, 8(3):477-770, 1983.
Indraneel Das and J.E. Dennis. A closer look at drawbacks of minimizing weighted sums of objectives for pareto set generation multicriteria optimization problems. Structural Optimization, 14(1): 63 63-69, 1997.
Kalyanmoy Deb and Himanshu Jain. An evolutionary many-objective optimization algorithm using reference-poiie point-based nondominated sorting approach, part i: solving problems with box constraints. IEEE transactions on evolutionary computation, 18(4):577-601, 2013.
Kalyanmoy Deb and Dhish Kumar Saxena. Searching for pareto-optimal solutions through dimension- ality reduction for certain large-dimensional multi-objective optimization problems. Computational Intelligence, pp. KanGAL Report Number 200501 1, 2005.
Jean-Antoine Désidéri. Mutipee-gradient descent algorithm for multiobjective optimization. In European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS 2012), 2012.
11

---

Published as a conference paper at ICLR 2025
Lisang Ding, Ziang Chen, Xinshang Wang, and Wotao Yin. Efficient algorithms for optimization. In Interaational Conference on Machine Learning (ICML), 2024.
Daniel M. Dunlavy and Dianne P. O'Leary, Homotopy optimization methods for global optimization. In Technical Report, 2005.
Dean Eckles, Brett R Gordon, and Garrett A Johnson. Field studies of psychologically targeted ads face threats to internal validity. Proceedings of the National Academy of Sciences, 115(23): E5254 E5255, 2018.
Matthias Ehrgott. Multicriteria optimization, volume 491. Springer Science & Business Media, 2005.
Heshan Devaka Fernando, Han Shen, Miao Liu, Subhajit Chaudhury, Keerthiram Murugesan, and Tianyi Chen. Mitigating gradient bias in multi-objective learning: A provably convergent approach. In International Conference on Learning Representations (ICLR), 2023.
Christopher Fifty, Ehsan Amid, Zhe Zhao, Tianhe Yu, Rohan Anil, and Chelsea Finn. Efficiently iden- tifying task groupings for multi-task learning. Proc. Advances in Neural Information Processing Systems (NeurIPS), 2021.
Peter J Fleming, Robin C Purshouse, and Robert Lygoe. Many-objective optimization: An engineering design perspective. In International conference on evolutionary multi-criterion optimization, pp. 14-32. Springer, 2005.
Jörg Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathe- matical Methods of Operations Research, 51(3):479-494, 2000.
Jörg Fliege, A Ismael Vaz, and Luis Nunes Vicente. Complexity of gradient descent for multiobjec- tive optimization. Optimization Methods and Software, 34(5):949 9599,9999999999 2019.
Yuan Gao, Shuguo Jiang, Moran Li, Jin- Gang Yu, and Gui- SuiiSong Xia. Dmtg: One-shot differentiable multi-task grouping. International Conference on Machine Learning (ICML), 2024.
Arthur M. Geoffrion. Solving bicriterion mathematical programs. Operations Research, 15(1):39-54, 1967.
Jean-Louis Goffin. On convergence rates of subgradient optimization methods. Mathematical programming, 13:329-347, 1977.
Conor Hayes, Roxana Rádulescu, Eugenio Bargiacchi, Johan Källström, Matthew Macfarlane, Mathieu Reymond, Timothy Verstracten, Luisa M Zintgraf, Richard Dazeley, Fredrik Heintz, et al. A practical guide to multi-objective reinforcement learning and planning. Autonomous Agents and Aulti-Agent Systems, 36(1):26, 2022.
Elad Hazan, Kfir Ychuda Levy, and Shai Shalev-Shwartz. On graduated optimization for stochastic non-convex problems. In International Conference on Machine Learning (ICML), 2016.
Yifei He, Shiji Zhou, Guojun Zhang, Hyokun Yun, Yi Xu, Belinda Zeng, Trishul Chilimbi, and Han Zhao. Robust multi-task learning with excess risks. In International Conference Machine Learning (ICML), 2024.
Claus Hillermeier. Generalized homotopy approach to multiobjective optimization. Journal of Optimization Theory and Applications, 110(3):557-583, 2001.
Yuzheng Hu, Ruicheng Xian, Qilong Wu, Qiuling Fan, Lang Yin, and Han Zhao. Revisiting scalarization in multi-task learning: theoretical perspective. Advances in Neural Information Processing Systems (NeurIPS), 36, 2023.
Hisao Ishibuchi, Noritaka Tsukamoto, and Yusuke Nojima. Evolutionary many-objective optimiza- tion: A short review. In IEEE congress on evolutionary computation (IEEE world congress on computational intelligence), pp. 2419-2426 IEEE, 2008
Moksh Jain, Sharath Chandra Raparthy, Alex Senanddz--Gariiaa Jarrid Rector-Brooks, Yoshua Bengio, Santiago Miret, and Emmanuel Bengio. Multi-objective GelowNets. In International Conference Machine Learning (ICML), pp. 14631-14653, PMLR, 2023.
12

---

Published as a conference paper at ICLR 2025
Joshua Knowles and David Corn. Quantifying the effects of objective space dimension in evolution- ary multiobjective optimization. In Evolutionary Suuti-CCritrrion Optimization: 4th International Conference, EMO 2007, Matsushima, Japan, March 5-8, 2007. Proceedings 4, pp. 757-771. Springer, 2007.
Vitaly Kurin, Alessandro De Palma, Ilya Kostrikov, Shimon Whiteson, and Pawan K Mudigonda. In defense of the unitary scalarization for deep multi-tast learning. Advances in Neural Information Processing Systems, 35:12169-12183, 2022.
Bingdong Li, Jinlong Li, Ke Tang, and Xin Yao. Many-objective evolutionary algorithms: A survey. ACM Computing Surveys (CSUR), 48(1):1-33)) 2015.
Ziyue Li, Tian Li, Virginia Smith, Jeff Bilmes, and Tianyi Zhou. Many-objective multi-solution transport. arXiv preprint arXiv:2403.04099 2024.
Baijiong Lin, YE Feiyang, Yu Zhang, and Ivor Tsang. Reasonable effectiveness of random weighting:
A litmus test for multi-task learning. Transactions on Machine Learning Rexearch, 2022.
Baijiong Lin, Weisen Jiang. Feiyang Ye, Yu Zhang, Pengguang Chen, Ying-Cong Chen, Shu Liu, and
James Kwok. Dual- balancing for multi-task learning, 2023.
Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qingfu Zhang, and Sam Kwong. Pareto multi-tasi task learning. In Advances in Neural Information Processing Systems, pp. 12060-12070, 2019.
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.
Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conflict-averse gradient descent for multi-task learning. Advances in Neural Information Processing Systems (NeurIPS), 34: 11890, 2021a.
Bo Liu, Yihao Feng, Peter Stone, and Qiang Liu. Famo: Fast adaptive multitask optimization. Advances in Neural Information Processing Systems (NeurIPS), 36, 2024.
Liyang Liu, Yi Li, Zhanghui Kuang, J Xue, Yimin Chen, Wenming Yang, Qingmin Liao, and Wayne Zhang. Towards impartial multi-task learning. In International Conference on Learning Representations (ICLR), 2021b.
Shikun Liu, Stephen James, Andrew Davison, and Edward Johns. Auto-lambda: Disentangling dynamic task relationships. Transactions on Machine Learning Research, 2022.
Suyun Liu and Luis Nunes Vicente. The stochastic multi-gradient algorithm for multi-objective optimization and its application supervised machine learning. Annals of Operations Research, pp. 1-30, 2021.
Xingchao Liu, Xin Tong, and Qiang Liu, Profiling pareto front with multi-objective stein variational gradient descent. Advances in Neural Information Processing Systems (NeurIPS), 34:14711-14733, 2021c.
Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28(2): 129-137, 1982.
Pingchuan Ma, Tao Du, and Wojeiech Matusik. Efficient continuous pareto exploration in multi-tast learning. International Conference on Machine Learning (ICML), 2020.
Debabrata Mahapatra and Vaibhav Rajan. Multi-task learning with user preferences: Gradient descent with controlled ascent in pareto optimization. Thirry-sevnnth International Conference on Machine Learning, 2020.
Sandra C Matz, Michal Kosinski, Gideon Nave, and David J Stillwell. Psychological targeting as an effective approach to digital mass persuasion. Proceedings of the national academy of sciences, 114444)):27144427199 2017.
Kaisa Miettinen. Nonlinear multiobjeetiive optimization, volume 12. Springer Science & Business Media, 1999.
13

---

Published as a conference paper at ICLR 2025
Michinari Momma, Chaosheng Dong, and Jia Liu. A mmlti--ojjectiv/mmttitasss learning framework induced by pareto stationarity. In International Conference on Machine Learning (ICML), pP- 15895-15907. PMLR, 2022.
Aviv Navon, Aviv Shamsian, Idan Achituve, Haggai Maron, Kenji Kawaguchi, Gal Chechik, and Ethan Fetaya. Multi-task learning as a bargaining game. In International Conference Machine Learning (ICML), pp. 16428-16446. PMLR, 2022.
Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103: 127-152, 2005.
Robin Purshouse and Peter Fleming. On the evolutionary optimization of many conflicting objectives. IEEE transactions evolutionary computation, 11(6):770-784, 2007.
Shuang Qiu, Dake Zhang, Rui Yang, Boxiang Lyu, and Tong Zhang. Traversing pareto optimal poli- cies: Provably efficient multi-objective reinforcement learning, arXiv preprint vrXiv:2407.17466 2024.
Diederik Marijn Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley. A survey of multi-objective sequential decision-making. Journal of Artificial Intelligence Research, 48(1): 67-113, 2014.
Amelie Royer, Tijmen Blankevoort, and Babak Ehteshami Bejnordi. Scalarization for multi-task and multi-domain learning at scale. Advances in Neural Information Processing Systems (NeurIPS), 36, 2023.
Hiroyuki Sato and Hisao Ishibuchi. Evolutionary many many-objective optimization: Difficulties, ap- proaches, and discussions. IEEJ Transactions on Electrical and Electronic Engineering, 18(7): 1048-1058, 2023.
Stefan Schäffler, Reinhart Schultz, and Klaus Weinzierl. Stochastic method for the solution of unconstrained vector optimization problems. Journal of Optimization Theory and Applications, 114:209-220 22000 2002.
Ozan Sener and Vladlen Koltun. Multi-task learning multi-objective optimization. In Advances in Neural Information Processing Systems, pp. 525-536, 2018
Dmitry Senushkin, Nikolay Patakin, Arseny Kuznetsov, and Anton Konushin. Independent component alignment for multi-task learning. In IEEE/VVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 20083-20093, 2023.
Hemant Kumar Singh, Amitay Isaacs, and Tapabrata Ray. A pareto corner search evolutionary algo- rithm and dimensionality reduction in many-objective optimization problems. IEEE Transactions Evolutionary Computation, 15(4):539-53) 2011.
Trevor Standley, Amir Zamir, Dawn Chen, Leonidas Guibas, Jitendra Malik, and Silvio Savarese. Which tasks should be learned together in multi-task learning? In Proc. International Conference on Machine Learning (ICML), pp. 9120-9132. PMLR, 2020.
Ralph E Steuer and Eng-Ung Choo. An interactive weighted tchebycheff procedure for multiple objective programming. Mathematical programming, 26(3):326-344 1983.
Hanrui Wang, Kuan Wang, Jiacheng Yang, Linxiao Shen, Nan Sun, Hae-Seung Lee, and Song Han. Gen-rl circuit designer: Transferable transistor sizing with graph neural networks and reinforcement learning. In 2020 57th ACM/IEEE Design Automation Conference (DAC), pp. 1-6. IEEE, 2020.
Peiyao Xiao, Hao Ban, and Kaiyi Ji. Direction -rrection-oriented multi-objective learning: Simple and provable stochastic algorithms. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
Derrick Xin, Behrooz Ghorbani, Justin Gilmer, Ankush Garg, and Orhan Firat. Do current multi-task optimization methods in deep learning even help? Advances in Neural Information Processing Systems, 35:13597-13661 2022.
14

---

Published as a conference paper at ICLR 2025
Xinyang Yi, Constantine Caramanis, and Sujay Sanghavi. Alteraating minimization for mixed linear regression. In International Conference on Machine Learning, pp. 613-621. PMLR,, 2014.
Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. Advances in Neural Information Processing Systems (NeurlPS), 33:5824-5836, 2020.
Qingfu Zhang and Hui Li. MOEAD: A multiobjective evolutionary algorithm based on decomposi- tion. IEEE Transactions on evolutionary computation, 11(6):712-731, 2007.
Kai Zhong, Prateek Jain, and Inderjit S Dhillon. Mixed linear regression with multiple components. Advances in neural information processing systems, 29, 2016.
Aimin Zhou, Bo- Yang Qu, Hui Li, Shi-Zheng Zhao, Ponnuthurai Nagaratnam Suganthan, and Qingfu Zhang. Multiobjective evolutionary algorithms: A survey of the state of the art. Swarm and Evolutionary Computation, 1(1):32-49, 2011.
Shiji Zhou, Wenpeng Zhang, Jiyan Jiang, Wenliang Zhong, Jinjie Gu, and Wenwu Zhu. On the convergence of stochastic multi-objective gradient manipulation and beyond. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Yiheng Zhu, Jialu Wu, Chaowen Hu, Jiahuan Yan, Tingjun Hou, Jian Wu, et al. Sample-efficient oblti-obeective molecular optimization with gflownets. Advances in Neural Information Processing Systems, 36, 2023.
15

---

Published as a conference paper at ICLR 2025
In this appendix, mainly provide:
Detailed Proofs and Discussion for the theoretical analysis are provide in Section A
Problem and Experimental Settings can be found Section B
More Experimental Results and Analyses are provided in Section
Ablation Studies and Discussions can be found in Section D
A DETAILED PROOF AND DISCUSSION
A.1 PROOF OF THEOREM 1
Theorem (Existence of Pareto Optimal Solution for Tchebycheff Set Scalarization). There exists
an optimal solution set Xi for the Tchebycheff set scalarization optimization problem (8) such that all solutions Xi are Pareto optimal of the original multi-objecctiv optimization problem addition, if the optimal set Xj unique, all solutions in X are Pareto optimal.
7 In
Proof. This theorem can be proved by construction and contradiction based on Definition for
(weakly) Pareto optimality and the form of Tehebycheff set Scalarization (8)
Existence of Pareto Optimal Solution We first prove that there exists an optimal solution set of which all solutions Pareto optimal by construction.
Step 1: Let Xx be an optimal solution set for the Tchebycheff set scalarization problem, we have:
Xx argminxx max (Ae( min f((x) ={)},
(15)
1sism #EXx
where Xx = {
JK=1
Step 2: Without loss of generality, we suppose the k-th solution (k) in Xx is not Pareto optimal,
which means there exists valid solution à E such that (()) f)x(()) In other words, we have:
fa(()) I (1) Vi E (1...,mm) m} and (z) < fz( (*) 3j E fl,.., m}.
(16)
Let Xx (Xx \ (0((0) U (.), we have:
max Isism
(>i(
min f((x) 2,)) S max {Aa( min fi(x) 2 xEXx
(17)
isism =EXx
Since Xx is already the optimal solution set for Tchebycheff set scalarization, we have:
max
(Ar min fa(x) x;]) max 18.5m #EXK
{)e( min f((x) x()}.
(18)
#EXx
We treat X as the current optimal solution set.
Step 3: Repeat Step 2 until no new solution & E X can be found dominate and replace any
solution in the current solution set, and let X & be the final found optimal solution set for TCH-Set scalarization.
According to the definition of Pareto optimality, all solutions in the optimal solution set Xx k should be Pareto optimal.
Pareto Optimality for Unique Optimal Solution Set This guarantee be proved by contradic- tion based on definition for Pareto optimality, the form of TCH-Set Scalarization, and the uniqueness of the optimal solution set.
Let Xi be an optimal solution set for the Tchebycheff set scalarization problem, we have:
X argminx, X
max (Ai( min f((x) =;));
(19)
15 #EXx
where X {k) jk=1
16

---

Published as a conference paper at ICLR 2025
Without loss of generality, suppose the k-th solution x xx) in Xx is not Pareto optimal, which means there exists valid solution i X such that f(Ø) < ((x) In other words, have:
f(())= S f( (k)). Vi E {1...., m) and f)(Ø) fj(e 3. {I.....) m).
(20)
Let Xx = (x (xx(k))) }) { we have:
max (Ar min fi(x) -;)) - max {Ap( min fi(x) 2;)} m5
(21)
xxXx
1s mexx
On the other hand, according to the uniqueness of X we have:
max {),( min fi(x) =,)) > max (M(( min fi(x) - 2;)}.
(22)
Isism #E8x
Isism xeXx
The above two inequalities contradict each other. Therefore, every solution *A) in the unique optimal solution set Xj should be Pareto optimal.
A.2 PROOF OF THEOREM
Theorem 2 (Pareto Optimality for Smooth Tchebycheff Set Scalarization). All solutions in the optimal solution set X for the smooth Tchebycheff set scalarization problem (12) are weakly Pareto optimal of the original multi-objective optimization problem (7). In addition, the solutions are Pareto optimal if either
1. the optimal solution set Xi is unique, or
2. all preference coefficients are positive (A₃ 0 0'i..
Proof. Similarly to the above proof for Theorem 1 this theorem can be proved by contradiction based on Definition 2 for (weakly) Pareto optimality and the form of smooth Tehebycheff set scalarization 12).
Weakly Pareto Optimality We first prove all the solutions in X are weakly Pareto optimal. Let
X k be an optimal solution set for the smooth Tchebycheff set scalarization problem (12. we have:
los Ek -
X = arg argmin plog Xx
Σe
(23)
where X = fx (k)) =k=1
Without loss of generality, we further suppose the k-th solution x (k) in X is not weakly Pareto
optimal for the original multi-objective optimization problem (T). According to Definition ( for
weakly Pareto optimality, there exists valid solution à X such that f( sstrit f(x* In other words, we have:
f(( < f((x Vi m.,
(24)
If we replace the solution x (k) in X by & (e.g., Xx = (X \ fx ( we have the new solution set Xx (1) x (k-1), i. x (k+1)) ,..... [K)),,,(())), Based on the above inequalities,
and further let - -J) x =(1) Vjj 4 l and 2 = ét it is easy to check:
- Ind A ((())((=(())) -
-M ind Inf (
log
ulog Σ
(25)
There is a contradiction between 25 and the optimality of i for the smooth Tehebycheff set scalarization 23 Therefore, every x= should be weakly Pareto optimal solution for the original multi-objective optimization problem
Then prove the sufficient conditions for all solutions in X % be Pareto optimal.
17

---

Published as a conference paper at ICLR 2025
1. Unique Optimal Solution Set Without loss of generality, we suppose the k-th solution xx)
in Xj is not Pareto optimal, which means there exists valid solution & E X such that f f(Ø) x f(x ).)) In other words, we have:
fi())= S fa (.) ViE {1.... m) and fī( < fy (x 3j E {1,.... m).
(26)
Also let Xxx (Xi (x) 1 { where x0) x0(1, Vj and 2x) it we have:
-y log E -cctr(a-(0))
- In ( Aelss((
m
m
4 log
Jllog
(27)
On the other hand, according to the uniqueness of x. we have:
m
-M lox
(EKK
m
lox [I (
I log
plog
(28)
The above two inequalitics (27) and 28 are contradicted with each other. Therefore, every solution in the unique optimal solution set (Kx) should be Pareto optimal.
2. All Positive Preferences Similar the above proof, suppose the solution (kk( is not Pareto
optimal, and there exists valid solution á X' such that f()) (x*(k)) Since all preferences
= {m
are positive, according to the set of inequalities in (26). it easy to check:
lox ER =A((f((r
lox EE Ap
log
< log
(29)
which contradicts the STCH-Set optimality of Xx Pareto optimal.
k in 23 Therefore, all solutions in X K should be
It should be noted that all positive preferences are not sufficient conditions for the solution to be Pareto optimal for the original (nonsmooth) Tchebycheff set (TCH-Set) scalarization. With all positive preferences, each component (e.g., all objective-solution pairs) in STCH-Set scalarization will contribute to the scalarization value, which not the case for the (non-smooth) TCH-Set scalarization.
A.3 PROOF OF THEOREM 3
Theorem 3 (Uniform Smooth Approximation). The smooth Tchebycheff set (STCH-Set) scalarization
(StC
[X k A) a uniform smooth approximation of the Tchebycheff set (TCH-Set) scalarization
(u. 1 g (TCH-)ee)
X K A), and we have:
(X A) 10 Vi f
lim
(TCC
(TCH-Se) (XxlA)
(30)
for any valid set X₁ C X.
Proof. This theorem can be proved by deriving the upper and lower bounds of (TCI (Xxl (A) (St) (Xx(A). We first provide the upper and lower bounds for the classic smooth approximation for max and min, and then derive the bounds for g (TCH-set) X (A).
with respect the smooth smax and smin operators in 9 (p.
Classic Bounds for max and min The log-sum-exp function log > n i==1 eli is widely-used smooth approximation for the maximization function max V/, y/. yn Its lower and upper bounds are also well-known in convex optimization (Bertsekas al. 2003 Boyd & Vandenberghe 2004):
max {v1, 1/ .2. yyn max 82........
18

---

Published as a conference paper at ICLR 2025
log( eb))
log(n g2ax
log mux (n
log (Manm1.. (2nnnnn))
(31)
By rearranging the above inequalities, we have:
m
log
log n S max (m), .2,.... ;nn S log Σ
(32)
With smooth parameter μ O, it is also easy show (Bertsekas et al. 2003
Boyd & Vandenberghe
2004)
p log Σ eull- plgg S max (v1, U2. ,.,..., Vnn S log
Σ enin.
(33)
d=1
Similarly, we have the lower and upper bounds for the minimization function:
m
m
-oloog
w:ll I minn {8r1 ,2..... Bn S -plog Σ
e -v// + plog n.
(34)
Lower and Upper Bounds for g (TC--Set) (Xx|A) By leveraging the above classic bounds, it is straightforward to derive the lower and upper bounds for the max operator over m optimization objectives for g (TCH.Set) (X mixisism {he (minigAsk fa(((()) - =²²)
min ISASK (1())(1)) -21 - } 2 log
Igkg )=(()()))=:))) - log m, (35)
max isism
Ae
2 } 1log
de min )
max 15t5m
Ai
min
(x(x)()))
(k) -
(36)
ISkSK
where the bounds are tight if μr O.
In a similar manner, we can obtain the bounds for the min operator over K solutions for each objective function fi(w)):
K
) + + log K, (37)
-14; log
Σ
De-i(u())) S min f((x!())) log Σ c (/(
1skSk
where the bounds are tight if J. O.
Combing the results above, have the upper bound and lower bounds for the Tehebycheff setscalar- ization g (CH. (Xx AA):
X (-we log e -=1200033)11)) -2; -s:)/0 -s log m,
X A) Z poog
Σ
(38)
X (- log loolEoEEEE mca(t))/ ) log K K=s;) k=
g Set)
[ A) S pog
(39)
which means g (TCH-Set) (Xx (A) is properly bounded from above and below, and the bounds are tight ft and μ4 1 for all < i < m. It straightforward see:
p40 vi Iu.
lim (el) (X A)
(TCH-Set) (xxIA)
(40)
for all valid solution sets Xx that include the optimal set X K
arg min g (TCH-Set) (Xx A).
(STCH-Set) is a uniform smooth approxi-
Therefore, according to Nesterov (2005) (Nesterov) 2005 mation of (TCH-Sa)) [xxt (A)
9 4p. (p.(a, )m
19

---

Published as a conference paper at ICLR 2025
A.4 PROOF OF THEOREM 4
Theorem (Convergence to Pareto Stationary Solution). If there exists a solution set Xx x such that (STCH See)
V Yaung, p ( solutions of the original multi-ohjective optimization problem U
(X (A) 0 for all ((k) E XK, then all solutions in X k are Pareto stationary
Proof. We can prove this theorem by analyzing the form of gradient for STCH-Set scalarization (STCH-Set)
V yaugg
9 "plaa 1m
for each solution x (x)) with the condition for Pareto stationarity in (X K A)
Definition 4
We first let
K
(:(x)) -Mi log
Σ
1A sis m,
(41)
1=1
y (g((x) - x*) R.
(42)
h(y) - log Σ velu
(43)
For the STCH scalarization, we have:
A1 -Ms los E -Sela(l0))/ ) -22
9 9p. (p
Set)
[x A)
μ log
(44)
p log
(45)
p =llog
(46)
= h(y)-
(47)
Therefore, according to the chain rule, the gradient of g (.([m.). (kk) in the set K can be written as:
(STCH-Set)
(Xx()) with respect to solution
0g
Sel (m (XxlA) = =
(48)
0g
Ox k))
It is straightforward to show
cu/n
dy X
0g:
c -
Vyh(y)= Evvip
(49)
0g
(x(()
Σg e fi((o()))//
Therefore, we have
AgeBiln e --((a(()))/1
(STCH-Sot) V a aaing 9p.tnr
(xx(A) (A) =
Σ
E, Eveul e fi(mmiti//u4 (zx()))))
(50)
Ae/ e- e-1ra(()/mn E, evi/o En e y/
Let w;
is easy to check w; 10 sis m. If set s Em w; >
and w. wi/8, 8, we have:
Neviin é )
(STCH V (K) g km
(XxlA)=
Σ, e0//1 ΣE e- Vi((20(1))
(51)
w; (.(
fz(z)
(52)
1=1
t=1
x
W f((x),
(53)
1=1
20

---

Published as a conference paper at ICLR 2025
where E A Am-
{w Σ i=1 W.
1,
0 Vi}.
For solution a(a) E XK, if
(STCH-Set) V Vacug (p 1im
A) O, we have:
m
m
(f) with mm1 {20
Wi 1, W. 2 Vi..
(54)
According to Definition 4 the solution x. (8) is Pareto stationary for the multi-objective optimization problem
Therefore, when V *00 pp. 1
(StCH-Sat) ( (A) = 0 for all a(*) E Xx, all solutions in Xx are Pareto
stationary for the original multi-objective optimization problem (
A.5 DISCUSSION ON THE PARETO OPTIMALITY GUARANTEE FOR (S)TCH-SET
According Theorem without the strong unique solution set assumption, the solutions general optimal solution set of TCH-Set are not necessarily weakly Pareto optimal. This result is bit surprising yet reasonable
the set-based few-for for-many problem. The key reason here that only the single worst weighted objective (and its corresponding solution) will contribute the TCH-Set scalarization value maxisism { (min f((x) } In other words, the rest of the solutions can have arbitrary performance and will not affect the TCH-Set scalarization value. For the classic
multi-objective optimization problem (e.g., K 1), this property makes the TCH scalarization only have weakly Pareto optimality guarantee (only the worst objective counts), and which becomes worse for the few-for-many setting.
Counterexample We provide counterexample to better illustrate this not-even--weall Paretto optimal property. Consider a 2 -solution-for-3-ojjeeee
problem where the best values for the three objectives are (1, 1, 1). With preference (0.98, 0.01, 0.01), an ideal optimal solution set can be two weakly Pareto optimal solutions with values {(1, 8, 8), (3, 1, 1)}. However, since only the largest weighted objective (xf) = 0.98 will contribute to the final TCH-Set value, we can freely make the other solution have worse objective value. For example, the set of solutions with value {(1, 8, 8). (3, 2, 2)} is still the optimal solution set for TCH-Set, but the second solution clearly not weakly Pareto optimal. Neither the positive preference assumption nor the redundant solution assumption can exclude this kind of counterexample.
Table 4: (Weakly) Pareto optimaility guarantee for TCH-Set and STCH-Set.
Assumption
All Positive Preferences
Unique Solution Set
TCH-Set
Pareto Optimal
STCH-Set
Weakly Pareto Optimal
Pareto Optimal
Pareto Optimal
(Weakly) Pareto optimality guarantee for STCH-Set In contrast to TCH-Set, STCH-Set enjoys good (weakly) Pareto optimality guarantee for its optimal solution set. The key reason that all objectives and solutions will contribute to the STCH-Set scalarization value. According to Theorem 2 all optimal solutions for STCH-Set are at least weakly Pareto optimal, and they are Pareto optimal 1) all preferences are positive or 2) the optimal solution set is unique. The comparison of TCH-Set and STCH-SA Set with different assumptions can be found in Table
21

---

Published as a conference paper at ICLR 2025
B PROBLEM AND EXPERIMENTAL SETTINGS
B.1 CONVEX MULTI-OBIECTIVE OPTIMIZATION
In this experiment, we compare different methods on solving m convex optimization problems with K solutions. We consider two numbers of objectives m {128, 1024) and six different numbers of solutions K f3, 4, 5, 6, 8, 10) or K f3, 5, 8, 10, 15, 203 for the 128-objective and 1024-objective problems separately, Therefore, there are total 2 x 6 12 comparisons.
For each comparison, we randomly generate m independent quadratic functions (f(x)) as the optimization objectives, of which the minimum values are all 0. Therefore, the optimal worst and average objective values are both 0 for all comparisons. Since the m objectives are randomly generated and with different optimal solution, the optimal worst and average objective value 0 cannot be achieved by any algorithms unless K 2 m. In all comparison, we let all solution be 10-dimensional vector R We repeat each comparison 50 times and report the mean worst and average objective value over 50 runs for each method.
B.2 NOISY MIXED LINEAR REGRESSION
We follow the noisy mixed linear regression setting from (Ding al. 2024). The i-th optimization objective is defined as:
f((x) 1 (1)2 =b00)² ||
(a
(55)
where {(at1, ((()) are data points and B 0.01 is fixed penalty parameter. The dataset {aa(1) HE is randomly generated in the following steps:
Randomly sample K i.i.d. ground truth ((c()) jkml (0, La);
Randomly sample m i.i.d. data (a ~ N(0, Ia). class index fcihm ~ Uniform((k)). and noise {e: o²),
Compute ((()) a (1T (c)) + Eg.
Our goal is to build K linear model with parameter x (4) tackle all m data points. this experiment, 1000 and E R.00 for all comparisons. We consider three noise levels {0.1, 0.5, 1} and four different numbers of solutions K = (5, 10, 15, 20} for each noise level, so there are total 3 x 4 12 comparisons. All comparisons are run 50 times, and we compare the mean worst and average objective values for each method.
B.3 NOISY MIXED NONLINEAR REGRESSION
The experimental setting for noisy mixed nonlinear regression also from (Ding et al. 2024) and similar to the linear regression counterpart. For nonlinear regression, the i-th optimization objective defined as:
f(x)) = (vbaa;: b,)2
(56)
where ((a, bm are m data points and 3 = 0.01 a fixed penalty parameter as in the previous linear regression case. However, now the model vaa;, x)) is neural network with trainale model parameters x = (W, p. q, o) with the form:
<b x.) (a p.P. p- ReLU + +
(57)
where a E Rdd W E d xd; p. E Rdd and o E R. The d, and du are the input dimension and hidden dimension, respectively. The data set (() b6)));m can generated similar to lincar regression but with K ground truth neural network models. We set dj 10 and dp 10 in all comparisons.
22

---

Published as a conference paper at ICLR 2025
B.4 DEEP MULTI-TASK GROUPING
In this experiment, we follow the same setting for the CelebA with 9 tasks in Gao et al. (002)). The goal is build few multi-task learning models (K 2, 3 or to handle all m tasks, where the optimal task group assignment is unknown in advance. The 9 tasks are all classification problems (e.g., 5-o-Clock Shadow, Black Hair, Blond Hair, Brown Hair, Goatee, Mustache. No Beard, Rosy Cheeks, and Wearing Hat) which are first used in Filty et al. (2021) for multi-task grouping. This is typical few-for-many optimization problem.
Following the setting in Gao et al. (2024), for all methods, we use ResNet variant as the network backbone and the eoos-ey loss for all tasks (the same setting as in Fifty al.) (202T)). All models are trained by the Adam optimizer with initial learning rates 0.0008 with plateau learning rate decay for 100 epochs. The results the existing multi-task grouping methods (Random Grouping, HOA (Standley et al.) (2020). TAG (Fifty al. 2021) and DMTG (Gao al.) (024)) are directly from Gao et al. (2024). We train the models with SoM, TCH-Set and STCH-Set ourselves using the codes provided by Gao al. (2024) More experimental details for this problem can be found in Gao et al.
(2024).
23

---

Published as a conference paper at ICLR 2025
C MORE EXPERIMENTAL RESULTS
C.I CONVEX MANY-ORIECTIVE OPTIMIZATION
Table 5: The results the convex optimization problems with different numbers of solutions K. Mean worst and average objective values over 50 runs are reported. Best results are highlighted in bold with gray background.
LS
TCH
STCH
MosT
SoM
TCH-Set
STCH-Set
number of objectives 128
worst
4.64c+00(+) 4.44c+00(+) 4.41e+00(+) 2.12c+00(+) 1.86c400(+) 1.02e+00(+)
6.08c-01
average
8.61e-01(+) 8.03e-01(4) 7.80e-0((+) 3.45e-01(+) 2.02c-01(-) 3.46e-01(4)
2.12e-01
worst
4.23e+00(+)
3,83e+00(+) 3.68c+00(+) 1,48c+00(+) 1.12c+00(+) 6.74c-01(+)
3.13e-01
average
7.45e-01(+)
6.54c-01(+) 6.41c-01(+) 1.85e-01(+)
1.12e-01(+)
2.27c-01(4)
9.44e-02
worst
4.17e+00(+) 3.56e+00(+) 3.51e+00(+) 1.02++00(+) 9.20e-01(+)
4.94e-0((+)
1.91e-01
=
average
7.08c-01(+) 5.75e-01(+) 5.05c-01(+) 9.81c-02(+)
7.95c-02(+)
1.60c-01(4)
5.12e-02
worst
3.81e+00(t) 3,41e+00(+) 3.20e+00(+) 9.56e-01(+) 7.03e-01(+) 3.72e-01(+)
1.36e-01
=
average 6.72e-01(+) 5.31e-01(+) 5.15e-01(+) 8.34e-02(+)
5.34e-02(+)
1.19e-01(+)
3.15e-02
worst
3.69)+00(+) 2.94++00(+) 2.61e+00(+) 8.32e-01(+) 5,20e-01(4) 2.84e-01(+)
1.02c-01
average
6.16e-0((+) 4.57e-01(+) 4.22e-01(+) 6.91e-02(+) 3.40e-02(4)
8.53e-02(+)
1.78c-02
worst
3.68++00(+) 2.69++00(+) 2.40e+00(+) 6.27e-01(+) 4.07e-01(4) 1,95e-01(4)
7.99c-02
=
average 5.69e-01(+) 4.07c-01(+) 3.20e-01(+) 4.59e-02(+) 2.43e-02(4)
5.92e-02(+)
1.34c-02
number of objectives 1024
worst 4.7le+00(+) 7.84e+00(+) 7.33e+00(+)
3,36c+00(+) 2.39c+00(+)
1887++00
=
average 1.15e+00(+) 9.92e-01(t) 9.70e-01(t)
3.54e-01(-) 4.55e-01(+)
3.92e-01
worst
4.48c+00(+) 6.77c+00(+) 6.57c+00(+)
2.34c+00(+) 1.68c+00(+)
9.93e-01
=
average 1.09++0((+) 8.02e-01(+) 7.65c-01(+)
1.95e-0((+) 2.59e-01(+)
1.87e-01
K = average 1.03e+00(+) 6.69e-01(+) 6.49e-01(t)
worst
4.25c+00(+) 5.65c+00(+) 5.58c+00(+)
1.74c+00(+) 1.25c+00(+)
4.90e-01
1.02e-0((+) 1.66e-01(+)
8.31e-02
K = 10
worst
4.1c++00(+) 5.61c+00(+) 5,44c+00(+)
1.78c+00(+) 1.16c+00(+)
4.05e-01
average 1.00c+00(+) 6.07c-01(+) 5.99c-01(t)
8.14c-0((+)
1.41c-01(+)
5.94e-02
worst 4.06c+00(+) 4.78c+00(+) 4.91c+00(+)
1.54c+00(+) 9.06c-01(+)
2.85e-01
K = 15
average 9.78c-01(+) 5.15c-01(+) 4.99c-01(t)
5,98c-02(+)
1.01c-01(+)
3.31e-02
3.97e+00(+) 4.64e+00(+) 4.57c+00(+) 4.63e-01(+) 4.68e-01(t)
1.52c+00(+)
8.04c-01(+)
2.28c-01
K = 20
average 9.56e-01(+)
5.30e-02(+)
8.40c-02(+)
2.27e-02
Wilcoxon Rank-Sum Test Summary
worst 12/0/0
12/0/0
12/0/0 12/0/
6/0/D
12/0/0
12/0/0
+/ --
average
12/0/0
12/0/0
6/0/0
10/0/2
12/0/0
The full results for the convex objectiee optimization are shown in Table Since the MosT method cannot tackle the problems with 1024 objectives in reasonable time, we did not include these results in the Table and marked it as "'" According to the results, STCH-Set can always achieve the best worst case performance for all comparisons and the best average performance for most cases.
24

---

Published as a conference paper at ICLR 2025
C.2 NOISY MIXED LINEAR REGRESSION
Table The results on the noisy mixed linear regression with different different noisy levels a and different numbers of solutions K. We report the mean worst and average objective values over 50 independent runs for each method. The best results are highlighted bold with the gray background.
LS
TCH
STCH
SoM
TCH-Set
STCH-Set
= 0.1
worst 3.84e+01(+) 2.45e+01(+) 2.43e+01(+) 2.50e+00(+) 4.19e+00(+)
2.10e+00
K 5
average 2.70e+00(+) 1.46e+00(+) 1.44e+00(+) 1.88e-01(-) 6.53e-01(+)
4.72e-01
worst 2.21e+01(+) 2. 2.49c+01(+) 3.92++01(+) 3.46e+00(+) 2.04e+00(+)
5.00e-01
K= 10
average 1.09c+00(+) 1.19c+00(+) 3.01c+00(+) 2.33e-01(+) 3.83e-0((+)
2.00e-01
worst 4.20e+01(+) 2.11e+0((+) 2.21e+01(+) 2.57c+00(+) 1.64c+00(+)
2.70e-01
K 15
average 3.07c+00(t) 1.02c+00(+) 1.02c+00(+) 1.97c-0((+) 3.22c-01(+)
1.66e-01
worst 4.20e+01(+) 2. 2.14e+01(+) 2.04e+01(+) 1.44e+00(+) 1.79e+(0(+))
2.27e-01
K = 20
average 3.09c+00(t) 8,35c-0((+) 8.87e-01(t) 1.8cc-1(+)) 3,29c-01(+)
1.66e-01
= 0.5
worst 3,93e+01(+) 2.53c+01(+) 2.50c+01(+) 5.33c+00(+) 4.37c+00(+)
2.45e+00
K = 5
average 2.74e+00(+) 1.51e+00(+) 1.52e+00(+) 3.08e-01(-) 7.05e-01(+)
5.54e-01
worst 4.20e+01(+) 2.39c+01(+) 2.56e+01(+) 3.68e+00(+) 2.38e+00(+)
6.03e-01
K 10
average 3.25e+00(+) 1.28c+00(+) 1.20c+00(+) 2.46c-01(+) 4.18)-0((+)
2.24e-01
K = 15
worst
4.36e+01(+) 2.37c+01(+) 2.35e+01(4) 3.00e+00(+) 1.72e+00(+)
3.07e-01
average 3.30e+00(+) 1.02e+00(+) 1.09c+00(+) 2.06e-01(+) 3.46e-01(+)
1.78c-01
worst 4.36e+01(+) 2. 2.18e+01(4) 2.23e+01(+) 1.93e+00(+) 1.27e+00(+)
2.39c-01
K = 20
average 3.22e+00(+) 9.15e-01(+) 9.99e-01(+) 1.92e-01(+) 2.94e-01(+)
1.74e-01
==1
worst 4.76e+01(+) 3.24c+01(+) 3.48c+01(+) 1.00c+01(+) 5,49c+00(+)
3.48e+00
K =
average 3.39c+00(+) 1.7 1.7lc+00(+) 1.93c+00(+) 5.21e-01(-) 8.45c-01(+)
7.44e-01
worst 4.86c+01(t) 2.93e+01(t) 3,30c+01(+) 4.86c+00(+) 3.31e+00(+)
7.82e-01
K 10
average 3.81c+00(+) 1.45c+00(+) 1.55e+00(+) 2.88e-01(+)
5.30e-01(+)
2.80c-01
worst
5.23e+01(t) 3. 3.11e+01(+) 2.78e+01(+) 3.41e+00(+) 2.45c+00(+)
3.55e-01
K = 15
average 3.84e+00(+) 1.19++00(+) 1.16e+00(+) 2.32e-01(+) 4.51e-01(+)
2.04e-01
worst 5.37e+01(t) 2.54e+01(+) 2.61e+01(+) 2.47e+00(+) 2.04c+00(+)
2.68e-01
K 20
average 3.81e+00(+) 1.08e+00(+) 1.08e+00(+) 2. 1212-00(++) 3.81e-01(+)
1.94e-01
Wilcoxon Rank-Sur Test Summary
+/
worst
12/0/0
12/0/0
12/0/0
12/0/0
12/0/0
average
12/0/0
12/0/0
12/0/0
12/0/0
9/0/3
The full results for the noisy mixed linear regression problem are shown in Table b According to the results, STCH-Set can always obtain the lowest worst objective values for all noise levels and different numbers of solutions. In addition, it also obtains the best average objective values for most (SoM) optimization method can achieve good and even better
comparisons. The average objective values, but with significantly higher worst objective value.
25

---

Published as a conference paper at ICLR 2025
C.3 NOISY MIXED NONLINEAR REGRESSION
Table 7: The results on the noisy mixed nonlinear regression with different noisy levels a and different numbers of solutions K. We report the mean worst and average objective values over 50 independent runs for each method. The best results are highlighted in bold with gray background.
LS
TCH
STCH
SoM
TCH-Set
STCH-Set
0.1
K 5
worst
2.34e+02 (+) 1.68e+02(+) 1.57e+02(+) 1.68e+01(+) 1.94e+01(+)
7.43e+000
average 9.19e+00(+) 8.50++00(+) 7.90e+00(+) 8.54e-01(-) 3.48e+00(+)
1.89e+00
worst 3.23e+02(+) 1.72e+02(+) 1.57e+0((+) 4.42e+00(+) 6.07e+00(+)
6.28e-01
K= 10
average 8.70e+00 (+) 6.65e+00(+) 5.85e+00(+) 1.22e-01(+) 1.03e+00(+)
5.99e-02
worst 3.65c+02(+) 2. 2.10++02(+) 1.62++0((+) 1.10c+00(+) 1.57c+00(+)
2.05e-01
K 15
average 8.33c+00(+) 5.66e+00(t) 4.89c+00(+) 1.47c-01(+) 3.27c-01(+)
1.27e-02
worst 3.36++02(+) 2.04e+02(+) 1.81e+02(+) 5.59e+00(+) 4.37e+00(+)
6.22e-01
K = 20
average 8.81c+00(+) 6,92c+00(+) 6.23c+00(+) 1.24c-01(+) 9.09c-01(+)
6.27e-02
σ 0.5
worst 2. 2.14c+02(+) 1.87++0((+) 1.62c+0((+) 2.00c+01(+) 1.82++0((+)
1.20e+01
K = 5
average 9.1 9.17e+00(+) 8.53e+00(+) 7. 7.96e+00(+) 8.63e-01(-) 3.49e+00(+)
2.31e+00
K 10
worst
3.36e+02(t) 2.04c+02(+) 1.1c++2(+)) 5.59c+00(+) 4.37c+00(+)
6.22e-01
average 8.81c+00(+) 6.92e+00(+) 6.23e+00(+) 1.24e-01(t) 9.09c-01(+)
6.27e-02
K = 15
worst average 8.38e+00(4) 5.63e+00(+) 4.59c+00(+) 1.81e-0((+) 3,97e-01(+)
3.46e+02(4) 1.99c+02(+) 1.53e+02(+) 2.00++00(+) 2.15e+00(+)
1.57e-01
1.26e-02
worst 3.75++02(+) 1.54)+02(+) 1.27e+02(+) 5.05e-01(+) 6.60e-01(+)
1.12e-01
K = 20
average 6.95e+00(+) 4.23e+00(+) 3.32e+00(+) 3.96e-03(-)
1.35e-01(+)
6.72e-03
0=1
worst 3,47c+02(4) 1.50c+02(+) 1.39c+02(+) 1.81c-0((t) 4.65c-01(+)
9.49e-02
K =
average 6.95c+00(+) 4.34c+00(+) 3.32c+00(+) 1.26e-03(-) 1.11c-0((+)
6.65e-03
worst 3,08c+02(+) 2.26e+02(+) 1.68++0((+) 5.08c+00(+) 6.91c+00(+)
6.44e-01
K 10
average 9.18c+00(+) 7.10c+00(+) 6. 6.13e+00(+) 1.32e-01(+)
1.10c+00(+)
5.77e-02
worst 3.35e+02(+) 2.03e+02(+) 1.64e+02(+) 1.89c+00(+) 1.91e+00(+)
2.11e-01
K = 15
average 8.47e+00(+) 6. 19e+00(() 4.92++00(+) 2.11e-02(+)
3,93e-01(+)
1.30e-02
worst 3,40c+02(t) 1.83e+02(+) 1. 1.21e+02(+) 1.81c-0((+) 4.65e-01(+)
9.08e-02
K = 20
average 7.20++00(+) 4. 4.44e+00(+) 3.45e+00(+) 3.24c-03(-)
1.11e-01(+)
6.73e-03
Wilcoxon Rank-Sun Sum Test Summary
+/
worst
12/0/0
12/0/0
12/0/0
12/0/0
12/0/0
average 12/0/0
12/0/0
12/0/0
7/0/5
12/0/0
The full results for the noisy mixed nonlinear regression problem are provided in Table 7 Similar to the linear counterpart, STCH-Set can also achieve the lowest worst objective value for all comparisons. However, it is outperformed by SoM on out of 12 comparisons on the average objective value. One possible result could be due to the highly non-convex nature of neural network training. Once solution is captured by bad local optimum, it will have many high but not reducible objective values, which might mislead the STCH-Set optimization. An adaptive estimation method for the ideal point could be helpful to tackle this issue.
26

---

Published as a conference paper at ICLR 2025
D ABLATION STUDIES AND DISCUSSION
D.1
THE EFFECT OF SMOOTH PARAMETER
25
((X)
f2(x)
FaDx)
(0) F,00. (x()))
20
AX)
smints, fa 6.s..m 10)+13
0-
5-
smint5, 6.
smints. 2) +5
smintf, f.
-00
(a) LS
(b) TCH
Figure 4: The effect of different smoothing parameters for the smooth minimization function:
(a) The function min {1 (z), (2(2,, fa(z)} is highly non-convex even when all {z)]]] are convex.
(b) The smooth smin function has a better optimization landscape, especially with large μ. When
+ 0, smin converges to min.
Table 8: Results of STCH-Set with different fixed μ and adaptive f schedule.
== 10
/ ==
/1 = 0.5
/ 0.1
Adaptive μ
K = 5 worst average
4.55e+00
4.38e+00
1.88++00
1.37e+00
1.20e+00
9.93e-01
1.25e+00
1.23e+00
1.95e-01
1.99e-01
1.94c-01
1.87e-01
worst
4.40e+00
4.00e+00
1.39e+00
9.20e-01
6.62e-01
4.90e-01 8.31e-02
= 8 average 1.19e+00
1.10e+00
9.44e-02
9.38e-02
9.06e-02
In this work, we use the same smoothing parameters for all smooth terms (e.g., μn ....... pm in equation (13) in STCH-Set for all experiments. The smoothing parameter hyperparameter for STCH-Set, and might need to be tuned for different problems. This subsection investigates the effect of different smooth parameters μ for both the STCH-Set scalarized function and the optimization performance.
Scalarized Objective Function In addition to non-smoothness, the highly non-convex nature of the min operator will also lead to poor optimization performance of TCH-Set. As can be found in Figure 4 a), the min of three convex functions can be highly non-convex, and a gradient- based method might lead et al. 2024), which generalizes the K K-mean clustering algorithm for optimization. is well-known that the K-mean clustering Na-Hard. On the other hand, as shown in Figure (b), the smooth version of min we used can lead to a better optimization landscape, especially with larger When μ becomes smaller, the smooth function smin will converge to the original non-convex min function.
bad local optimum. This not just the case for TCH-Set, but also for SoM (Ding
Optimization Performance We have conducted new ablation study for STCH-Set with different fixed smoothing parameters μ {10, 5, 1, 0.5, 0.1} and an adaptive schedule from large to small in Table 8 In this paper, the adaptive schedule gradually reduce from to 0.05 with t = 10, 000. According to the results, STCH-Set with adaptive targelto-small optimization (Dunlavy & O' D'Leary| 20055) Hazan et al.) (0166), which optimizes gradual sequence of problems from easy surrogates to the hard original problem.
is put) exp(-3 x 10 --), which
achieve the best performance. This strategy is also related to homotopy
27

---

Published as a conference paper at ICLR 2025
D.2 IMPACT OF DIFFERENT PREFERENCES
Table Results of STCH-Set with different preferences on the convex many-objective optimization
problem with K 1, 024 solutions.
K
3
K
10
20
worst
average
worst
average
worst
average
worst
average
Preference from Dir )
4.35e+00
4.27e-01
2.75e+00
2.10e-01
2.56e+00
1.39e-01
2.11e+00
1.02e-11
Preference from Dir( 5) )m)
4.22c+00
4.09c-01
2.22c+00
1,98c-01
8.43e-01
8.28e-02
5.66e-01
2.6le-02
Preference from Dir 100"")
3,90c+00
4.04c-01
1.74c+00
1.92c-01
7.08c-01
6.52c-02
4.48c-01
2.48c-02
Uniform Preference
1.87e+00
3.92e-01
9.93e-01
1.87e-01
4.05e-01
5,94e-02
2.28e-01
2.27e-02
The preference À also a hyperparameter in STCH-Set. In this paper, we mainly focus on the key cew-for-mayy setting, and use the simple uniform preference for all experiments. We believe that the preference À in the (SyTCH-Set can provide more flexibility to the user, especially when they have a specific preference among the objectives. More theoretical analysis can also be investigated with connection to the weighted clustering (Ackerman et al. 2012).
We have conducted experiment to investigate the performance of STCH-Set with different prefer- ences sampled from different Dirichlet distributions Dir([d]"). Dir([1]") is also called the uniform Dirichlet distribution, where the preference is diverse and uniformly sampled from the preference simplex. When the d becomes larger, the probability density will concentrate to the middle of the simplex, and therefore the preference for different objectives could be more similar to each other. In the extreme case, it converges to the fixed uniform preference we used in the paper. According to the results Table 9 if our final goal still to optimize the unweighted worst objective, we should assign equal preference for all objectives as in the paper. However, the À could be very useful if the decision- has a specific preference for different objectives, where the final goal is not to optimize the unweighted worst performance.
We hope our work can inspire more interesting follow up work that investigates the impact of different preferences, such preference inference from the optimal solution set.
iiferenceedriverr (S)TCH-Set adaptive preference adjustment, and inverse
D.3 RUNTIME AND SCALABILITY
Table 10: Runtime for different algorithms on the convex multi-objective optimization problem.
LS
TCH
STCH
MosT
SoM
TCH-Set
STCH-Set
128
56s
58s
59s
5500s
58s
57s
58s
m = 1024
59s
62s
61s
62s
61s
63s
The (S)TCH-Set approach proposed in this work is a pure scalarization methods. Just like other simple scalarization methods, does not have separately calculate and update the gradient for each objective with respect to each solution. What (S)TCH-Set has to do is to directly calculate the gradient of the single scalarized value and then update the solutions with simple gradient descent. Informally, if we treat the long vector that concatenates all solutions as single large solution Fall = [x1, x:2, .r,,..,, TK). STCH-Set just define a scalarized value of different objectives with respect to E l2nk It shares the same computational complexity with simple linear scalarization with m objective function on a solution x E RnK and can scale well to handle a large number of objectives.
In contrast, the gradient manipulation methods like multiple gradient decent algorithm (MGDA) will have to explicitly calculate the gradient for all objectives with respect to all solutions. Therefore, the MosT method that extends MGDA has to separately calculate and manipulate all mKK gradients at each iteration, which will scale poorly with the number of objectives.
We report the runtime of different methods for the convex objeetbee optimization in Table I0 According to the results, TCH-Set and STCH-Set both have similar runtime with simple linear scalarization, which will not significantly increase with the number of objectives In contrast, the
28

---

Published as a conference paper at ICLR 2025
MosT method that leverages the MGDA approach will require significantly longer runtime for m 128, and cannot be conducted on the m 1, 024 case with a reasonable run time.
D.4 BETTER PERFORMANCE OVER SOM
In the experiments, we observe that STCH-set can outperform SoM (Ding al. 2024) on the average metric in most cases, although SoM is designed to optimize the average metric. The performance advantage of STCH-Set over SoM can be analyzed from the following two perspectives:
Viewpoint of Optimization In the ideal case, SoM should achieve the best performance the final goal is optimize the average metric. However, similar the discussion in Appendix [.I] due to the non-smooth min operator, SoM also suffers from a slow convergence rate and has highly non-convex optimization landscape, which might lead to relatively worse final performance.
Viewpoint of Clustering According to the SoM paper (Ding et al.) 2024). SoM can be treated as generalization of the classic K K-means clustering problem with Lloyd's algorithm by alternatey updating the clusters (assign one of K solutions to each objective) and their centroids (update the solution for each group). However, the K-means clustering is well known to be NP-hard, and hence SoM is not guaranteed to assign the most suitable solution to each objective. From the experimental results, we can find that SoM will be outperformed by STCH-Set in most cases with a larger number of K, which might caused by wrong solution-objectio (which could be harder for a larger K). To some degree, our proposed STCH-SE Set can also be treated as smooth clustering method (in contrast to the hard K K-means clustering). We leave this interesting research direction future work.
matching during the optimization process
D.5 SETTING THE NUMBER OF SOLUTIONS
The number of solutions K is hyperparameter in the proposed (SYTCH-Set scalarization, which be properly set by:
Following the Requirement from Specific Application In many real-world few-for-many applica- tions, such as 1) training a few models for different tasks and 2) producing a few different versions of advertisements to serve diverse audiences, the number of solutions will be naturally required and limited by the (computational and financial) budget.
Conducting Hyperparameter Search As shown in the experimental results, there is a clear trade- off between the number of solutions and performance (S)TCH-Set. More solutions can lead to better performance, but they also require larger (computational and financial) budget. Therefore, it reasonable to solve the (S)TCH-SS) Set optimization problem with different and choose the most suitable number of solutions that satisfy the decision-make
preference.
More advanced methods, such as those for selecting the proper number of clusters in clustering, might also be generalized to handle this similar issue for (S)TCH-Set. We hope this work inspire more follow-up work on efficient selection for few-for-mant many optimization.
D.6 DISCUSSION WITH DIMENSIONALITY REDUCTION
Dimensionality reduction (Deb & Saxena 2005 Brockhoff & Zitzler 2006 Singh et al. 2011] is widely used technique to deal with many objectivee optimization problems with potential redundant objectives. By summarizing all objectives by few representative objectives, these methods can reformulate the originally challenging problem into simpler problem with much fewer objectives. For example, in Figure of the main paper, we show the result of our proposed method on synthetic optimization problem with 100 objectives. To clearly demonstrate the behavior of our proposed method, we intentionally construct the problem such that it has groups 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.
29

---

Published as a conference paper at ICLR 2025
On the other hand, the solution set optimization we investigated in this paper also has it own advantages for many-objective optimization.
Requirement from Real-World Application: 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 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 large group of diverse audiences. For these cases, is more natural to tackle the problem from the viewpoint of solution set optimization.
The requirement of finding a few solutions to tackle
No Redundant Objectives: In many real-world problems, the objectives care about are 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 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-objectivn group assignment known, 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- martooon---o--ma-oooooo -bje-tveess approach over the is also an interesting research topic in future work.
fow-solutions- wwr--oo---f----aeeeeeeeeeee-e--- summarized-objeetinn
Bridging Different Approaches: To some degree, proposed (S)TCH-Set method can be treated as a generalized (smooth) clustering method that assigns each solution to tackle different groups (clusters) of solutions. If we only keep one representative objective for each group, it could become a dimensionality reduction approach at the end. In addition, we treat the proposed (S)TCH-Se scalarization function as an indicator, 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.
D.7 MORE DISCUSSION ON THE MOTIVATION 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 (c.g., mixture of experts) to handle many different data tasks, training a few agents to handle large number of clients in federated learning, and producing a few different versions of advertisements to serve 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 (Ding et al., 20244] [L al. 2024) by researchers with backgrounds in machine learning, traditional optimization, and federated learning.
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-See method can efficiently handle this problem setting. The experimental results also show our proposed (SyTCH-Set can outperform the methods proposed in (Ding et al. [024]] Li et al. 2024] Standley et al. 2020 Fifty et al. 202T) on different application problems. Some application problems considered in this work, such as multi-task grouping (Standley et al. 2020: Fifty et al., (021). are already impactful in practice. We believe our proposed method will have significant practical impact solving a broad range of similar application problems that require set of complementary solutions.
D.8 RELATION WITH TRADITIONAL. METHODS
Rooted in multi-objective optimization, our proposed (SYTCH-Set method is a complement rather than replacement for the traditional multi-objective optimization method:
The proposed (S)TCH- scalarization is a natural extension of traditional multi oojei-- optimization method. If we set the number of solutions to K 1, it will reduce to the classic TCH-Set scalarization as well as the smooth TCH-Set scalarization Lin et al. (2024) that aims to find single Pareto solution with balanced trade-off.
30

---

Published as a conference paper at ICLR 2025
If we treat the (S)TCH-Se -etttttttto scalarization function an indicator, our proposed method is indeed a standard indicator based method for many-objective optimization. Here, we want to find a (small) set of solutions to optimize the newly proposed (S)TCH-Set scalarization value rather than the values of traditional indicators (e.g.. Hypervolume).
E NOTATION TABLE
Table 11: Notation Table
Notation
Definition
m
number of objectives
dimension of solutions
K
number of solutions solution
X
solution set objective vector i-th objective value gradient of the i-th objective decision space preference
f(x)
f((x))
(f(())
X
A m-1
preference simplex
31


Reviews:
[{"review_id": "vvfpBVfsin", "reviewer": "Reviewer_CNbj", "summary": "The authors propose a scheme for many-objective problems with large number of objectives (e.g > 100) where the idea is to find a few representative solutions that address them.\nTo make this scheme possible they use their newly proposed Tchebycheff Set scalarization function that is an extension of the original. Now instead of trying to find a point that minimizes the scalarized problem, is trying to find multiple points that minimize it, allowing it to be bad for some of the m objectives, but it should at least minimize some subset of it.\nThe original Tchebycheff function is non differentiable to the max and min operators, which makes it not the best option to work with gradient based optimization. Therefore they extend the smooth Tchebycheff function in the work Lin et.al 2024 to work on set of solutions.", "questions": "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.\nHave you consider some dimensionality reduction techniques to maybe reduce which objectives should be evaluated during the scalarization?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Scalarization that is well known to perform well on multi-objective problems as seen on different variants of the evolutionary algorithm MOEA/D. Tchebycheff as the scalarizing function has also been shown to cover the non-convex solutions in the Pareto Front. The regular approach only aims to have a solution per direction, by modifying the function to instead search for a set of points that while being good for the other objectives it should be the best for a subset of all objectives.\n\nThe text introduces well non multi-objective practitioners to the setting, the difficulty present in many-objective problems, and previous work and results on scalarization with the simple weighted sum and the Tchebycheff function.\nAppendices further explore the effect of the smoothness parameter and complement the main text with more experiments.", "weaknesses": "It would have been nice to touch or at least mention dimensionality reduction techniques and problems with redundant objectives.\nSeems 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?.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "pDgRx6y2Vl", "reviewer": "Reviewer_m2ed", "summary": "This paper proposes a novel scalarization method called TCH-Set to produce a limited number of solutions that handle many objectives. A relaxed version is also proposed to tackle the non-smooth situations. The theoretical properties of the proposed method are investigated, and an empirical study is conducted to verify its effectiveness.", "questions": "Please refer to \"Weaknesses\". Additionally, I suggest the authors summarize a notation table in the appendix.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper is well-written and easy to follow.\n2. The proposed method is well-motivated. \n3. The technical details are clearly presented, and the theoretical analyses seem correct. \n4. The literature review is comprehensive.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "hRMLcymIEl", "reviewer": "Reviewer_Uihz", "summary": "Different from general multi-objective optimization aiming to find a dense Pareto set, this paper focuses on identifying a few solutions that cover a large number of objectives in a complementary manner for many-objective optimization. To achieve this, a smooth Tchebycheff set scalarization approach is developed with good theoretical guarantees.", "questions": "1. After the Tchebycheff set scalarization, how is the scalarized problem solved, given that a set of solutions needs to be optimized?\n2. Did the methods compared in the experiments also propose the few-for-many prospective for many-objective optimization?\n3. What optimization methods are used under the scalarization methods for the convex multi-objective optimization in Section 4.1?\n4. A brief analysis of why STCH-Set performs slightly worse than SoM in two cases in Table 4 would be beneficial.\n5. It should be clarified why the part results of MosT are “-” in Table 6.\n6. All mathematical symbols (e.g., $K$ and $m$) in the tables should use the correct mathematical formatting.\n7. In line 227, a space is missing after the period.\n8. In line 1473, there is an incorrect line break, and “term0” appears to be a typo.\n9. In line 1487, a space is missing before “(S)TCH”.\n10. An open question is whether the proposed approach is especially suited for many-objective optimization with non-conflicting objectives. How would it perform when all objectives are conflicting?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. This paper introduces a novel and practical prospective in tackling for many-objective optimization.\n2. This paper develops a smooth Tchebycheff set scalarization approach under the few-for-many prospective.\n3. The theoretical analysis is thorough and well-supported.", "weaknesses": "Some descriptions lack clarity, and minor writing errors are present. Please refer to the questions below for the details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "rqiEUysH3E", "reviewer": "Reviewer_u9MJ", "summary": "Authors propose a novel Tchebycheff set scalarization method to find a few representative solution to cover a large number of objectives\n in a collaborative and complementary manner so that each objective can be well addressed by at least one solution in the small solution set.", "questions": "* The experiments are conducted with different K, how to choose the K of your algorithm?\n\n* Since the preference $\\lambda$ can greatly impacts the final result, could you please provide with some hints for choosing  $\\lambda$?\n\nReference：\n1.  Eng Ung Choo and DR Atkins. Proper efficiency in nonconvex multicriteria programming. Mathematics of Operations Research, 8(3):467–470, 1983.\n2.  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.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "* This paper is well-written and easy to follow.\n\n* The experiments are comprehensive and include necessary analyses, and the results are convincing.\n\n* The necessary proofs are included.", "weaknesses": "* 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].\n\n* The motivation is not quite clear. Why should you find a few representative solutions to cover a large number of objectives? \n\n* The work is not tied to particular applications. Can you briefly provide some scenarios where your method is applicable?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)