Revisiting Scalarization in Multi-Task Learning: A Theoretical Perspective
Authors: Yuzheng Hu
Ruicheng Xian
Qilong Wu
Qiuling Fan
Lang Yin
Han Zhao
Venue: NeurIPS 2023 poster (2023)
Keywords: multi-task learning
scalarization
Pareto front
TL;DR: We show that scalarization is inherently limited in tracing out the Pareto front in multi-task learning.

Abstract: Linear scalarization, i.e., combining all loss functions by a weighted sum, has been the default choice in the literature of multi-task learning (MTL) since its inception. In recent years, there is a surge of interest in developing Specialized Multi-Task Optimizers (SMTOs) that treat MTL as a multi-objective optimization problem. However, it remains open whether there is a fundamental advantage of SMTOs over scalarization. In fact, heated debates exist in the community comparing these two types of algorithms, mostly from an empirical perspective. To approach the above question, in this paper, we revisit scalarization from a theoretical perspective. We focus on linear MTL models and study whether scalarization is capable of fully exploring the Pareto front. Our findings reveal that, in contrast to recent works that claimed empirical advantages of scalarization, scalarization is inherently incapable of full exploration, especially for those Pareto optimal solutions that strike the balanced trade-offs between multiple tasks. More concretely, when the model is under-parametrized, we reveal a multi-surface structure of the feasible region and identify necessary and sufficient conditions for full exploration. This leads to the conclusion that scalarization is in general incapable of tracing out the Pareto front. Our theoretical results partially answer the open questions in Xin et al. (2021), and provide a more intuitive explanation on why scalarization fails beyond non-convexity. We additionally perform experiments on a real-world dataset using both scalarization and state-of-the-art SMTOs. The experimental results not only corroborate our theoretical findings, but also unveil the potential of SMTOs in finding balanced solutions, which cannot be achieved by scalarization.

Revisiting Scalarization in Multi-Task Learning: A Theoretical Perspective
Yuzheng Hult
Ruicheng Xian
Qilong Wul
Qiuling Fan
Lang Yin
Han Zhao
Department of Computer Science DDeaatmeent of Mathematics
University of Illinois Urbana- ChaapaCCm rrh46,xxiann qilong3, qiuling2, langyin2, banzhao) edu
Abstract
Linear scalarization, i.c.. combining all loss functions by a weighted sum, has been the default choice the literature of multi-task learning (MTL) since its inception. In recent years, there is surge of interest in developing Specialized Multi-Task Optimizers (SMTOs) that treat MTL as multi-objective optimization problem. However, it remains open whether there is fundamental advantage of SMTOs over scalarization. fact, heated debates exist the community comparing these two types of algorithms, mostly from an empirical perspective. To approach the above question, this paper, we revisit scalarization from a theoretical perspective. We focus on linear MTL. models and study whether scalarization is capable of fully exploring the Pareto front. Our findings reveal that, in contrast to recent works that claimed empirical advantages of scalarization, scalarization is inherently incapable of full exploration, especially for those Pareto optimal solutions that strike the balanced trade-offs between multiple tasks. More concretely, when the model is under- paadler-rrameriized, we reveal a multi-sute surfft structure the feasible region and identify necessary and sufficient conditions for full exploration. This leads to the conclusion that scalarization in general incapable of tracing out the Pareto front. Our theoretical results partially answer the open questions in Xin et al. (2021), and provide a more intuitive explanation on why scalarization fails beyond non-convexity. We additionally perform experiments on a real-world dataset using both scalarization and state-of-the-art SMTOs. The experimental results not only corroborate our theoretical findings, but also unveil the potential of SMTOS in finding balanced solutions, which cannot be achieved by scalarization.
Introduction
When labeled data from multiple tasks are available, multi-task learning (MTL) aims learn a joint model for these tasks simultancously in order to improve generalization (Caruana) 1997 Zhang and Yang 2021 Ruder 2017). One common approach towards this goal learning a joint feature representation that is shared among multiple tasks, where each task then uses a separate task-specific head for its own prediction. The hope that by sharing joint feature representation, the effective sample size for feature learning will be larger than that for single-task learning, hence leading to better generalization across related tasks. This simple and natural idea has proven to be successful in many applications, including object segmentation (Misra et al. 20166. natural language processing [Collobert and Weston 2008), autonomous driving Yu et al. 2020a), name a few.
One typical approach to learning the shared feature model from multiple tasks is called linear sealar- ization, where the learner provides set of convex coefficients (in the form of a probability vector) to
1 Corresponding author.
* Equall contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

linearly combine the loss from each task and reduces the learning problem into scalar optimization problem. Since its inception, scalarization has been the default approach for MTL (Caruana 1997,
Ruder 2017 Zhang and Yang. 2018 Crawshaw 2020; Zhang and Yang. 2021), mainly due to its simplicity, scalability, as well as empirical success. However, in recent years, variants of the multiple gradient descent algorithm (MGDA) (Fliege and Svaiter (0000) have been proposed and used in MTL (Sener and Koltun, 2018 Yu et al. 2020b] Chen et al. 2020: Liu et al. 202 102lap b Zhou et al., 2022). Referred to as specialized multi-task optimizers (SMTOs), the main idea behind them is to cast the learning problem explicitly as a multi-objective (multi-criteria) optimization problem, wherein the goal is to enforce convergence to a Pareto optimal solution across tasks. In the literature, main driving force behind these studies has been the belief that they are better than linear scalarization when confticting gradients among tasks are present (Yu et al. 2020b Liu et al. [222 Nevertheless, recent empirical results tell an opposite story (Kurin et al. 2022; Xin et al.) 2022] Lin et al. 2022)
with proper choices of hyperparameters and regularization techniques, scalarization matches even surpasses SMTOs. Hence, it largely remains an open problem regarding whether there is an inherent advantage of using SMTOs for MTL over scalarization, at least from theoretical perspective.
In this paper, we revisit scalarization from a theoretical perspective, We study whether scalarization is capable of fully exploring the Pareto front in linear MTL. Technically, we aim to understand the following question on full exploration:
For every Pareto optimum v on the Pareto front induced by multiple tasks, does there exist a weighted combination of task losses such that the optimal solution of the linearly scalarized objective corresponds to v?
Our fundamental thesis is that, if the answer to the above question is affirmative, then there is no inherent advantage of SMTOs over scalarization on the representation level; otherwise, there might be cases where SMTOs can converge to Pareto optimal solutions that cannot be obtained via any scalarization objective. Our findings suggest that, in contrast to recent works that claimed empirical advantages of scalarization, it is inherently incapable of full exploration. Specifically, our contributions are as follows:
1. We reveal a multi-surface structure of the feasible region, and identify a common failure mode of scalarization, which we refer to as "gradient disagreement" (Section B.I). This serves as an important first step towards understanding when and why scalarization fails to achieve a specific Pareto optimum.
2. We provide necessary and sufficient conditions for scalarization to fully explore the Pareto front, which lead to the conclusion that scalarization is incapable of tracing out the Pareto front in general (Section 3.2). To the best of our knowledge, we are the first to establish both necessary and sufficient conditions for full exploration in the non-convex setting.
3. We proceed to discuss implications of our theoretical results (Section 4.1 demonstrating how they answer the open questions in Xin et al. (2022), and provide a remedy solution via randomization to counteract the fundamental limitation of scalarization (Section 4.2).
4. We additionally perform experiments on a real-world dataset using both scalarization and state-of- the-art SMTOs (Section 5) The experimental results not only corroborate our theoretical findings, but also demonstrate the potential of SMTOs in finding balanced solutions.
2 Preliminaries
We introduce the setup of multi-task learning (MTL) and relevant notations, along with essential background on the optimal value of the scalarization objective and the concept of Pareto optimality.
Problem setup. Following prior works, we consider multi-task learning with k regression tasks (Wu) ... vi:-...
et al. 2020: Du et al. 2021). The training examples {(z), vi
) }y are drawn i.i.d. from ... x Jkk., where X' C IRP is the shared input space and ) C TR is the output space for task i. We denote the label of task as yi . v. T E R., and concatenate the
some ja E (xXx x 31
inputs and labels in matrix forms: X - [z], ................................ _. E R and Y = ........ ykl E Rnn
We focus on linear MTL, in which a linear neural network serves as the backbone for prediction. Despite its simplicity, this setting has attracted extensive research interest in the literature (Maurer 2006; Maurer et al. 2016 Wu et al. 2020 Du et al. 2021 Tripuraneni et al., 2021). Without loss of

---

generality, the model that will be used for our study is two-layer linear network which consists of shared layer W RPxq and a task-specific head a; E R7 for each task. The prediction for task i on input x is given by fa W a:) == x Wa az. We adopt Mean Squared Error (MSE) as the loss function, and the training loss for task is given by I, a²) == I|XWa; a; - vvll..
Notation. We use [k] to denote the index set {1,-.- ,... For two square matrices M and N with the same dimension, we write M = N if M NN is positive semi-definite, and M > N if M N is positive definite. We denote (D) as the diagonal matrix whose diagonal entries are given by D = (e() set of real numbers; and span(V) as the linear space spanned by V = )e())) a set of vectors. For two vectors with the same size, we use O and @ to denote entry-wise multiplication and division. When there no ambiguity, operations on vectors (e.g., absolute value, square, square root) are performed entry-wise. For any matrix M, Mt stands for its Moore-Penrose inverse. We use range( (M) and rank(M) to denote its column space and rank, respectively. The expression || denotes the l2 norm of a vector, (.,)) the inner product of two vectors, || matrix, and p(.) the spectral radius of a square matrix.
|| the Frobenius norm of a
Optimal value of scalarization (restated from Wu et al. 2020 The objective function of
scalarization is a weighted sum of losses: Eiz >e (W, a.). Here, the convex coefficients {Az kell)
satisfy A 2 0 and E; A = 1, and are typically obtained via grid search (Vandenhende et al. 2021
For each task, we can decompose its loss based on the orthogonality principle (Kay) 1993)
L,W,, a.) = I|XWa, a, - y 112 = | XWa, - lil? + 1 - -vill
(1)
where 0e = X(X x y, is the optimal predictor for task i. Denote A = diag(IvA))
A [al,-.. , ax) E 1o y 1.,,... Ux] Ra The scalarization objective can be compactly expressed as
IXX A Y I(XW A - 4)AEE + II( - Y)
Throughout this paper, we assume the optimal linear predictions {D: JeeM are linearly independent fl This leads two distinct cases, depending on the width of the hidden layer q:
1. When q 2 k, the minimum value of the first term is zero, i.c., every task can simultancously achieve its optimal loss 10: 3
2. When q < k. the minimum value of the first term is given by the rank-q approximation. In particular, let Y'A = >x
=i=ı oru,y be the SVD of Ý A. According to the Eckart-Young-irrkky Theorem (Eckart and Young 1936), the best rank-q approximation of Y A under the Frobenius norm is given by the truncated SVD: Y,,AA = E/= "eu.s Hence, the minimum training risk is |1 - A) + II - Y) This regime, referred to as the perameeerreeeere regime, constitutes the main focus of our study.
Pareto optimality. In the context of MTL, a point 0* (shared model parameters) a Pareto optimum (PO) if there does not exist a 6' that achieves strictly better performance on at least one task and no worse performance on all other tasks compared to l", Formally, for a set of objectives { {Le) (e()) that need be minimized, if (,(d') < (0") for some point 8', then there must exist another task j such that (0') > L, (0*). The Pareto front (a.k.a. Pareto frontier) is the collection of objective values (0), (0)) corresponding all PO.
3 Linear scalarization through the lens of exploring the Pareto front
In this section, we provide a fine-grained analysis of the feasible region (formally defined in Sec- tion 3.J revealing its multi-surface structure. We proceed to analyze whether scalarization is capable of tracing out the Pareto front, and identify necessary and sufficient conditions for full exploration.
Reformulation. Recall that minimizing Equation I is equivalent to minimizing the squared loss [[ a, - 2 where i; = X X(X X)1 T y, is the optimal linear predictor for task i. Additionally, the task-specific heads be optimized independently for each task. Thus, if we let Z XW and
Any deep linear networks for MTL be reduced the case of a lay- linear network, with one layer of shared representations and one layer of task specific heads. As long as n 2 k. an arbitrarily small perturbation can make (ū hveee linearly independent. We mainly adopt this assumption for ease of presentation.
3

---

Feasible MSEs restricted to each surface
All feasible MSEs
Gradient disagreement
33
MSEg
91
MSE}
MSE
MSE2
MSE;
Fe
Intersection (balanced PO)
Figure 2: When restricted a sin- gle surface, each contains (dif- ferent) optimum point, and the gradients (w.rt. minimizing total MSE) on each surface disagree at their intersection.
Figure 1: Feasible MSEs of three-task linear MTL problem with q = 1, formed by a union of multiple feasible MSEs
surfaces defined in Theorem 3.1 Note that the balanced PO located at the intersection of the surfaces is not achievable by scalarization. See Appendix A.1 for implementation details.
a; (Z Z)tZT D: (the optimal task-specific head), then minimizing Equation equivalent to min [Z 2)t2T in - 0il?, Z=XW
which can be further transformed into
max U. Pzúi, Pz Z(2 Z Z)'ZT
Therefore, the original MTL, problem can be reformulated into the following multi-objective problem
max (0] Pzir, ... 01 P2
(4)
Pz
where Pz is a projection matrix with rank at most g (i.e., hidden layer width) and maps to the column space of X. Each quadratic term can be further expressed as || From here it is clear (also see Section 2) that when q 2 le (the over over- peer-parmetrizeed regime), the & quadratic terms can be maximized simultaneously, meaning that the network has sufficient capacity to fit the target tasks. In this case, the Pareto front reduces a singleton, and can be achieved by scalarization with any choice of convex coefficients. In fact, this holds true even for general non-linear networks as long as is wide enough, i.e., over-parametrized. and we defer more discussions to Appendix A.2
The main focus of our study, in contrast, lies in the mnder--aramerrieed regime < k. where various tasks compete for the network's 's capacity for better prediction. We comment that this regime has been the focus of previous work and demonstrated to be beneficial in MTL (Wu et al. 2020 Wang et al. 2022). We study two extreme cases within the paddeerrrrmetee regime, q and g doing so, we anticipate that our results will hold for other k in between.
By
3.1 The multi-surface structure of the feasible region
The objective function of task i is Paú ||2, i.e., the square of the projection of úi on Pz. Since we are interested the Pareto front, we can assume w.l.o.g. that rank(P2) = and range( Pz) c span((), ( )ee) (otherwise there is a loss of model capacity, and the corresponding point will no longer be a PO). Consequently, we define the feasible region as
Pzth. Fq = (0i TPih ... 1A P20k)
P2 Pz, rank(Pz) = range (Pz) C span(((i)ec)))
(5)
We now provide a fine- grained characterization of Fi (corresponding to q = 1) in the following theorem, which also serves the basis for q k
Theorem 3.1. Let G- TT and Q G-1 Define
Qi Di QDi,..i> 0 0<1sk, 15 <...
(6)
where Dig..ie is diagonal matrix with all diagonal eniries equal to 1, except for the entries at positions .. ii which are equal to -. Consider the following surface parameterized by v:
Eig = {o Vol Qu Vo

---

We have:
J h= U U
U
Eip
(8)
OSISk 1USk
L.., Fi is the union 2 surfaces in the non-negative orthant (note Eiy..h
Bi by symmetry).
To help the readers gain some intuitions on the multi-surfaa structure demonstrated in Theorem 3.1 we visualize the feasible region of a three-task (i.e., k 3) example in Figure ( details the end of the subsection). We also provide a proof sketch below (detailed proof in Appendix (A.3).
(more
Proof sketch of Theorem 3.1 A rank-1 projection matrix can be expressed as 8s" T with ||||| 1.
The feasible region can therefore be equivalently characterized as
A- -
F
s)))
|| = 1, a e span spaan(())eew)))
(9)
Define vt (ūi, 8) and v (vi.... ux) We will show the set of u forms the boundary of an ellipsoid determined by Q. As a consequence, the set of |u] is the union of multiple surfaces, each corresponding the boundary of an ellipsoid (reflection of Q) in the non-negative orthant. The reflection is represented by the diagonal matrix Di in the theorem statement. Finally, Fi, which is the set of v², can be obtained by squaring the coordinates in the previous set. This finishes the proof of Theorem 3.1
Since the orthogonal complement of 1 1-dimensional subspace of span (ish))))) is (k 1)- dimensional subspace, we immediately have the following result (proof deferred to Appendix [A.4].
Theorem 3.2. Let = (11 ...... 118& ) Consider the following surface parametrized by u:
1i-i = e: Vt- U T
Qui Vt vt-u=
(10)
We have:
F 1--1- UU
U
(11)
USISk 15: Siskk
Le., FR-1 is the union 2 surfaces in the non-negative orthant (Ti,--i, = 1.... by symmetry).
Theorems 3.1 and 3.2 not only offer us a glimpse into the shape of the feasible region but also provide valuable insights into the fundamental limitation of linear scalarization. The key observation is that, scalarization fails to reach the intersection points two (or more) surfaces when the gradients with respect to the two (or more) surfaces disagree (i.e., they lie in different directions). We refer this phenomenon as gradient disagreement, and provide an illustrating example in Figure 2 Essentially, the multi-surface structure that have revealed implies the abundance of intersection points on the feasible region Fg. Moreover, if any of these points were to be an PO, scalarization would not be able to trace out the Pareto front (see Appendix A.5 for a detailed explanation).
We illustrate this observation using a concrete example with three tasks in Figure [ The feasible region consists of four surfaces, among which Eg is dominated by other surfaces. The intersection of E1, Eg, E3 (the red point) is a PO that achieves balanced performance across tasks, yet scalarization cannot reach this point since it lies in valley.
3.2 Necessary and sufficient conditions for full exploration
In this section, we provide an in-depth analysis of the Pareto front, which is subset of the feasible region. Concretely, we develop necessary and sufficient conditions for scalarization to fully explore the Pareto front.
We first review some important concepts that will be frequently used in this section. Denote Q (Qi,.., 1 < 1 < k. 1 15 i1 < <... < < k} as the collection of matrices which define the surfaces in the previous section. Denote G == (G.,, = Q 0 < l < k. 1 S i <
i S k}. Note Giy-ri, = Di..... &T Dig...i = ( T( (........ Therefore, G is collection of gram matrices which measure the task similarity, and each element is obtained by flipping the signs of some optimal predictors. We use and I to denote the collection of surfaces defined in Equations and 10 respectively. We also formally define class of matrix as follows.
5

---

Definition 3.3 (Doubly non-negative matrix), A doubly non-negative matrix M is real positive semi-definite (PSD) matrix with non-negative entries.
Our analysis begins with observation that the distribution of PO across different surfaces plays a vital role in the success of scalarization. Specifically, we want to avoid the "bad" case like the one demonstrated in Figure [ where PO lies on the intersection of multiple surfaces. A natural solution to circumvent this issue is to force the Pareto front to lie on a single surface. We therefore draw our attention this particular scenario, and provide necessary and sufficient condition for such configuration in the following lemma.
Lemma 3,4. When q I, the Pareto of the feasible region belongs to a single surface E* E E, and only if the corresponding G = (Q"))= E G is doubly non-negative. We refer to the existence of such doubly non-negative G in 9 as C1.
We outline the proof sketch below. The detailed proof can be found in Appendix B.1
Proof sketch of Lemma 3.4, For the if part, we employ geometric argument. Specifically, denote the acute cone formed by the optimal predictors as A. We will show that, if (a unit vector in Equation 9 does not belong to the dual cone A", then its reflection w.r.t. the dual cone s' is a better point than 8. As a consequence, we can remove the absolute value from the proof sketch of Theorem 3.1 This further implies that the Pareto front belongs to a single surface.
For the only if part, we consider the points which achieve maximum value along an axis. We will show these points are PO. Finally, we will show that if C1 does not hold, then these points must belong to different surfaces in 3.
We have a similar result for k 1. The details of the proof are deferred to Appendix B.2
Lemma 3.5. When q = k - 1, the Pareto front of the feasible region belongs to a single surface 1s I, if and only if the corresponding Q" E Q doubly non-negative. We refer to the existence of such a doubly non-negative Q" in Q as C2.
Lemmas 3.4 and 3.5 provide a refined characterization of how the PO distributed within the feasible
region: unless C1 (resp. C2) holds, the Pareto front will belong to multiple surfaces in & (resp. I). This easily leads to the existence a PO on the intersection of different surfaces (see Figure D which will render the failure of scalarization as consequence. It is therefore natural for us to conjecture that C1 (resp. C2) is necessary for full exploration. We make the following assumption regarding the topology of the Pareto front.
Assumption 3.6. For q= and k 1, assume the Pareto front is path-connected, i.e.. for every pair of PO x and y. there exists a contimuous curve on the Pareto front with x and y being the two endpoints.
Assumption 3.6 combined with Lemma 3.4 (resp. Lemma 3.5 will help locate PO P on the intersection of two surfaces when C1 assumption to circumvent degenerated cases.
(resp. C2 does not hold. We make an additional technical
Assumption 3.7. We assume P (the intersection point) is relative interior point (Rockafellar 1997 Section 6) of the Pareto front.
We are now ready present the main results in this section (full proofs in Appendices B.3 and B.5
Theorem 3.8 (Necessity of C1 (resp. C2 For q = 1 (resp. g k 1), under Assumptions 3.6 is a necessary condition for scalarization to fully explore the Pareto front.
and 3.7
C1 resp.
C2
Assumption 3.7 allows us to perform dimensionality analysis in small neighborhood of the intersection point P, from which we can demonstrate the existence of a PO lying on the intersection of two surfaces with gradient disagreement. This point cannot be achieved by linear scalarization.
Proof sketch of Theorem 3.8
Remark 3.9. Assumptions 3.6jand..7
mainly used to simplify analysis, and they are nol necessary
for Theorem 3.8 hold. As matter of fact, we can show the necessity of of resp. C2) when k = 3 without these assumptions. We refer the readers to Appendix B.4 B.4for more details.
Finally, without relying on the above assumptions, we can show that C1 and C2 are sufficient.

---

Theorem 3.10 (Sufficiency of C1
(resp. C2 For = 1 (resp. = h 1),
C1
(resp.
C2
is
sufficient condition for scalarization to fully explore the Pareto front.
For g = 1, we consider the tangent plane at a PO and attempt to show it lies above the feasible region. This is transformed into demonstrating the positive semi- definiteness matrix, which can be conquered by applying the Perron-Frobenius theorem (Shaked- Monderer and Berman 2021 Section 1.3) non-negative matrices. For g k 1, we show the boundary of the feasible region concave, and apply the supporting hyperplane theorem (Boyd et al.
Proof sketch of Theorem 3.10
2004 Section 2.5.2) conclude the proof.
4
Discussion
We discuss the implications of our theoretical results, and provide a remedy solution for linear scalarization to address its inability of full exploration.
4.1 Implications of the theoretical results
Fundamental limitation of linear scalarization. From Theorem it is clear that linear scalariza- tion faces significant challenges fully exploring the Pareto front the case of q = and q = k 1, since both C1 and C2 require the existence of a doubly non-negative matrix, which is a very small subset of the PSD matrix. To illustrate this point, we consider a simplified probabilistic model: when the optimal predictors {ús kejj are drawn independently from symmetric distribution centered at the origin, the probability that C1 holds is 2 20(kk", which decays exponentially with the number of tasks. Thus, comment that C1 and C2 in general does not hold in practical cases.
Towards understanding when and why scalarization fails. Among the vast literature that studies Pareto optimality in MTL, there is noticeable absence of systematic and rigorous exploration of when and why scalarization fails to reuch a Pareto optimum. Prior work typically resorts to hypothet- ical examples (e.g., Figure 4.9 in (Boyd et al., 2004g) to demonstrate the failure of scalarization. Our study, which identifies the multi-surface structure of the fcasible region and reveals the phenomenon of gradient disagreement in concrete setting, serves pioneering step in addressing this gap in the literature.
A closer examination of the failure mode. For the extreme under- under-parametiin parametrized case (g 1), on the one hand, we can prove that scalarization is able to achieve points which attain maximum value along one direction (i.e., best performance on one task). On the other hand, by examining Figure we shall see that scalarization is incapable of exploring the interior points (i.e.. balanced performance across all tasks). This suggests that scalarization has the tendency to overfit to a small fraction of tasks, and fails to strike the right balance between different tasks. We provide more empirical evidence to support this argument in Section 5
Criteria for practitioners. Theorem 3.10 demonstrates that and C2 are sufficient for scalar- ization to fully explore the Pareto front. As such, these conditions can serve as valuable criteria for practitioners when deciding which tasks to combine in linear MTL. Note a naive enumeration of G or Q will lead to time complexity of (2*²). ). We instead provide an O algorithm checking whether Coldss (Algorithm[]] A Appendix C In essence, the algorithm aims to find set of flipping signs [eshee E }+.-} that ensure positive zero correlation between all pairs in {8:0) he(j)- It scans through the predictors in ascending order and either determines the signs 8j for each optimal predictor ú; if not determined yet, or checks for conflicts between signs that are already determined. A sign can be determined when the predictors ÚJ and új are correlated. A conflict indicates the impossibility of finding such set of flipping signs, thus falsifying C1 A similar algorithm can be devised for c2 with an additional step of Cholesky decomposition beforehand, leading to an (1:a)) time complexity.
Open questions in Xin et al. 2022). We (partially) answer the open questions in Xin et al. (002)).
Q1. "Is it the case that neural networks trained via combination of scalarization and standard first-order optimization methods are not able to reach the Pareto Frontier?"
A1 For Linear MTL, our answer is definitive "Yes". We demonstrate that linear scalarization with arbitrary convex coefficients cannot trace out the Pareto optima general. Our results are strong in the sense that they hold representation level, meaning that they are independent of the specific
7

---

optimization algorithm employed. This suggests that the weakness we have revealed in scalarization fundamental nature.
Q2. "Is non-convexity adding additional complexity which makes scalarization insufficient for tracing out the Pareto front?"
A2. Yes, even some mild non-convexity introduced by two-layer linear networks will render scalariza- tion insufficient. On the other hand, we do believe the multi-surface structure that we have unveiled in Section 3.J is both universal and fundamental, which also contributes to the observed non-convexity in practical scenarios. In essence, what we have done partly is to penetrate through the surface and gain a holistic view of the feasible region. Notably, the key obstacle in linear scalarization, as revealed by our analysis, lies in the phenomenon of gradient disagreement. This cannot be readily discerned by solely examining the surface.
We make two additional comments to further clarify our standing point in comparison to this work.
1. We do not aim to refute the claims in Xin et al. 2022); as a matter of fact, we consider their empirical findings highly valuable. Instead, we would like to emphasize a discrepancy between their theory and experiments. Given that we have shown the conclusion that linear scalarization can fully explore the Pr-no long holds in the non-convex setting, their theory does not account for their experiments on modern neural networks. Therefore, we urge the research community develop new theory elucidating the empirical efficacy of linear scalarization.
2. While the differing settings render the results from these two papers non-comparable, they collectively offer a broader perspective on the pros and cons of scalarization and SMTOs. We believe this is of great significance both researchers and practitioners.
4.2 A remedy solution
Given the fundamental weakness of linear scalarization in fully exploring the Pareto front, one might wonder whether there exists any model class where linear scalarization is sufficient to fully explore the Pareto front. The answer is affirmative if allow ourselves to use randomized multi-task neural networks. More specifically, given two MTL networks f() and f()) over the same input and output spaces and a fixed constant & [0, 1]. we can construct randomized MTL network follows. Let S ~ U(, 1) be a uniform random variable over (0, 1) that is independent of all the other random variables, such the inputs. Then, consider the following randomized neural network:
(x) S f(x) = (x) otherwise
(12)
Essentially, the randomized network constructed by Equation 12 will output f(0) with probability I and (1))()) (1:) with probability I. Now if we consider the loss of f(-), we have
E, E,EsfI - r12 = [lIE,lIff( - 1
=(x))11((X) - VII. S 51 (I)() Y12
(tE,111(00) (x) - Y11) (1- ()E - YI
(13)
which means that the loss of the randomized multi-task network a convex combination of the losses from (+) and (-). Geometrically, the argument above shows that randomization allows us to "convexify" the feasible region and thus the Pareto front will be convex. Now, by a standard application of the supporting hyperplane thcorem (Boyd et al. 2004 Section 2.5.2) we can see that every point on the Pareto front can be realized via linear scalarization. We empirically verify the effectiveness of randomization in Appendix D.3
We comment that randomization powerful tool that has wide applicability in machine learning. For instance, it has achieved great success in online learning, specifically in the Follow-the- therttrueerrrddd Leader algorithm (Kalai and Vempala (005)). also appears the literature of fairness to achieve the optimal regressor or classifier (Zhao and Gordon| 2022 Xian et al. 2023). Here we further demonstrate that it can be applied to MTL. to facilitate the exploration of linear scalarization. In essence, randomization increases the representation power of the original neural network.
8

---

5 Experiments
In this section, we corroborate our theoretical findings with linear MTL experiment, where we show that linear scalarization fails to fully explore the Pareto front on a three-task problem that does not satisfy c1 with q 1. In comparison, SMTOs can achieve balanced Pareto optimum solutions that are not achievable by scalarization.
Dataset and setup. We use the SARCOS dataset for our experiment (Vijayakumar and Schaal 2000p, where the problem is to predict the torque of seven robot arms given inputs that consist of the position, velocity, and acceleration of the respective arms. For ease of visualization, we restrict the tasks to arms 3, 4, and 5; in particular, they do not satisfy C1
Our regression model is a two-layer linear network with hidden size 1 (no bias). To explore the portion of the Pareto front achievable by linear scalarization, we fit 100,000 linear regressors with randomly sampled convex coefficients and record their performance. These are compared to the solutions found by SMTOs, for which we use MGDA (Désidéri 2012) and MGDA-UB (Sener and Koltun 2018)) Specifically, to guarantee their Pareto optimality, we run the SMTOs with full- batch gradient descent till convergence (hence each SMTO method has one deterministic solution).
Additional details, including hyperparameter settings, can be found in Appendix D.I
Results. In Figure plot the MSEs achieved by scalarization under randomly sampled weights. We observe that the solutions achieved by scalarization are concentrated near the vertices and partly along the edges, indicating their tendency to overfit 1- 2 of the tasks. Scalarization also fails to explore a large portion of the Pareto front in the center-whice have more balanced performance across task; the inability of full exploration corroborates the neces- sary condition (Theorem 3.8) discussed in Section 3 In contrast, SMTOs are capable of finding solutions not achievable by scalarization that are located in the center of the Pareto front. This showcases the relative advantage and practical utility of SMTOs in MTL over scalarization, especially in scenarios where equitable performance on all tasks are desired. To strengthen our results, we experiment with mul- tiple random initializations and observe consistent results (see Appendix D.2].
Scaerrakan
0.3
14
8.7
Figure 3: Linear scalarization has the ten- dency to overfit to a subset of tasks by find- ing peripheral blue points of the Pareto front. MGDA (magenta) and MGDA-U UB (red) con- verge to more balanced PO in the interior.
Discussion. We would like to note that we are not endorsing any specific SMTO algorithm, such as MGDA or MGDA-UB. As a matter of fact, we hypothesize that no single algorithm is universally effective (also see (Chen et al. 2023), ). notably in overcoming the limitation of scalarization in terms of full exploration. Instead, by revealing the limitation of scalarization and the potential benefits of some SMTO algorithms, we aim to strengthen SMTO research, challenge the notion that linear scalarization sufficient, and advocate for a more balanced progression in the field of MTL.
6 Limitations and future directions
I Limitations. There are two major limitations of our work. First, while the techniques we develop in this paper are highly non-trivial, we only cover the two extreme cases = and q = h - in the mnder-parametrizedd regime, and the analysis for general < k is missing. Second, the setting of our study is relatively restricted. Specifically, we focus on linear MTL where different tasks share the same input. A more realistic setting should factor in different inputs for different tasks (Wu et al. 2020). as well as some non- non-linearity in the model architecture (Kurin et al. 2022).
Future directions. We expect the geometry of the feasible region to transition smoothly as we increase 4, meaning that it will not abruptly collapse into a single surface. Providing a rigorous basis for this assertion would facilitate the analysis for general g's, thereby complementing our study, Regarding the assumption of shared input, while our analysis persists under the propprtionnl covariance assumption' adopted by Wu et al. 2200)) we find this assumption excessively restrictive,

---

and hope future work could relax it further. The generalization to neural networks with ReLU activation is interesting but also challenging, and it is unclear whether the techniques and results developed in this paper can be extended to the non-linear setting. Another interesting avenue to explore is interpreting the multi-surface structure we have uncovered, which we hypothesize to have connections with game theory. Finally, our paper dedicates to demonstrating the weaknesses of linear scalarization, while we consider an important future direction to theoretically analyze the advantage of SMTOs, as partially revealed in our experiments. In all, we hope our study can initiate line of works on MTL, which provide theoretical justifications for the usage of specific algorithms beyond empirical evaluations across various settings.
7 Related work
SMTOs. There is a surge of interest in developing specialized multi-task optimizers (SMTOs) in the literature. One of the earliest and most notable SMTOs the multiple-gradien descent algorithm (MGDA) (Désidéri 2012). For each task, MGDA solves an optimization problem and performs updates using the gradient of the objective function with both shared and task-specific parameters. However, MGDA cannot scale to high dimension (e.g., neural networks), and computing the gradients for every task is prohibitively expensive. To counter these drawbacks, [Sener and Koltun| (2018) introduce a scalable Frank-Wolfe-bon Wolfe-based optimizer which is more efficient. Another prominent issue in MTL is that the gradients from multiple tasks could conflict with each other and the performance of some tasks could be significantly affected. To this end. Yu et al. (2020b) propose gradient surgery to mitigate the negative interference among tasks: Chen et al. (2020) and et al. (202 la) propose to manipulate the gradients or the gradient selection procedures; Fernando et al. (2022) devise stochastic gradient correction method and prove its convergence. More recently, Navon et al. (2022)
cast the gradient update as a Nash bargaining game, yielding well-balanced solutions across the PF.
Empirical comparison of SMTOs and scalarization. A recent line of works empirically compare SMTOs and linear scalarization. Their central claim is that the performance of linear scalarization comparable with the state-of- tfate-of-the-ae aht SMTOs despite the added complexity of SMTOs. Xin et al.) (2022) argue that multi-task optimization methods do not yield any improvement beyond what can be achieved by linear scalarization with carefully-tuned hyperparameters: Kurin et al. (2022) show that the performance of linear scalarization matches or even surpasses the more complex SMTOs when combined with standard regularization techniques. In addition to classification tasks, Vandenhende et al. (2021) conduct extensive experiments on dense prediction tasks, i.e., tasks that produce pixel- level predictions. They conclude that avoiding gradient competition among tasks can actually lead to performance degradation, and linear scalarization with fixed weights outperforms some SMTOs.
Exploration of the Pareto front. It is well-known that minimizing scalarization objectives with positive coefficients yields Pareto optimal solutions (Boyd et al.) 2004), while using negnnegte coefficients yields weak Pareto optimal ones (Zadeh, 1963). On the other hand, exploration of the entire Pareto front has been long- man-sstnninng and difficult open problem in MTL. For the simplest case, all loss functions are convex or the achievable region is a convex set, then scalarization can fully explore the PF (Boyd et al.) 2004 Xin et al. 2022). A slightly weaker condition for full exploration is directional convexity (Holtzman and Halkin 1966), established by Lin| (1976). Several recent works in MTL develop algorithms to generate PO subject user preferences, in particular on trade-offs among certain tasks (Lin et al. 2019) Mahapatra and Rajan| 2020; Momma et al. 2022). There is also line of empirical works that focuses on designing algorithms to efficiently explore the PF (Ma et al.
2020 Lin et al., 2020; Liu et al. 2221cc Navon et al. 2021 Ruchte and Grabocka 2021 Ye and Liu
2022). As far as know, are the first to establish both necessary and sufficient conditions for full exploration in the non-convex setting.
8 Conclusion
In this paper, we revisit linear scalarization from a theoretical perspective. In contrast to recent works that claimed consistent empirical advantages of scalarization, we show its inherent limitation in fully exploring the Pareto front. Specifically, we reveal a multi-surface structure of the feasible region, and identify necessary and sufficient conditions for full exploration in the under-parametrizer regime. We also discuss several implications of our theoretical results. Experiments on real- wellworldd dataset corroborate our theoretical findings, and suggest the benefit of SMTOs in finding balanced solutions.
10

---

Acknowledgement
We thank the anonymous reviewers for their constructive feedback. Yuzheng Hu would like to thank Fan Wu for useful suggestions in writing. Han Zhao's work was partly supported by the Defense Advanced Research Projects Agency (DARPA) under Cooperative Agreement Number: HR001 12320012, an IBM-IL Discovery Accelerator Institute research award, a Facebook Research Award, research grant from the Amazon- Illinois Center on Al for Interactive Conversational Experiences, and Amazon AWS Cloud Credit.
References
R. Bhatia. Matrix analysis, volume 169. Springer Science Business Media, 2013.
Boyd, P. Boyd, and L. Vandenberghe. Conver optimization. Cambridge university press, 2004.
R. Caruana. Multitask learning. Machine learning, 28:41-75, 1997.
L. Chen, H. Fernando, Y. Ying, and T. Chen. Three-way trade-off in multi-objeccive learning: Optimization, generalization and conffit--avoidance. arXiv preprint arXiv:2305.2003: 2023.
Z. Chen, J. Ngiam, Y. Huang, T. Luong, H. Kretzschmar, Y. Chai, and D. Anguelov. Just pick a sign: Optimizing deep multitask models with gradient sign dropout. Advances in Neural Information Processing Systems, 33:2039-2050, 2020.
G. Ciarlet. Linear and nonlinear functional analysis with applications, volume 130. Siam, 2013.
R. Collobert and Weston. A unified architecture for natural language processing: Deep neural networks with multitask learning. In Proceedings of the 25th international conference on Machine learning, pages 160-167, 2008
M. Crawshaw. Multi-task learning with deep neural networks: A survey. arXiv:2009.09796, 2020.
arXiv preprint
J.-A. Désidéri. Multiple-gradien descent algorithm (mgda) for multiobjective optimization. Comptes Rendus Mathematique, 350(5-6):313-318 2012.
S. Du, W. Hu, S. M. Kakade, D. Lee, and Q. Lei. Few-shot learning via learning the representation. provably. In International Conference on Learning Representations, 2021. URL https:// openreview
C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3)2211-218, 1936.
H. D. Fernando, H. Shen, M. Liu, S. Chaudhury, K. Murugesan, and T. Chen. Mitigating gradient bias in multi-objective learning: A provably convergent approach. In The Eleventh International Conference Learning Representations, 2022.
J. Fliege and B. F. Svaiter. Steepest descent methods for multicriteria optimization. Mathematical methods of operations research, 51(3):479 494, 2000.
Hastie, Tibshirani, J. Friedman, and H. Friedman. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009.
J. M. Holtzman and H. Halkin. Directional convexity and the maximum principle for discrete systems. SIAM Journal on Control, 4(2):263-275. 1966.
A. Kalai and S. Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-307, 2005.
S. M. Kay. Fundamentals of statistical signal processing: estimation theory. Prentice-Hall, Inc., 1993.
V. Kurin, A. De Palma, I. Kostrikov, S. Whiteson, and P. K. Mudigonda. In defense of the unitary scalarization for deep multi-task learning. Advances in Neural Information Processing Systems, 35:12169-12 12183, 2022.
11

---

B. Lin, Y. Feiyang, Y. Zhang, and I. Tsang. Reasonable effectiveness of random weighting: A litmus test for multi-task learning. Transactions on Machine Learning Research, 2022.
G. Lin. Three methods for determining pareto-optimal solutions of multiple-objective problems. In Directions in Large-Scale Systems: Many-Person Optimization and Decentralized Control, pages 117-138. Springer, 1976.
X. Lin, H.-L. Zhen, Z. Li, Q.-F. Zhang, and S. Kwong. Pareto multi-task learning. Advances in neural information processing systems, 32, 2019.
X. Lin, Z. Yang, Q. Zhang, and S. Kwong. Controllable pareto multi-task learning. arXiv preprint arXiv:2010.066 06313, 2020.
B. Liu, X. Liu, X. Jin, Stone, and Q. Liu. Conflict-averse gradient descent for multi-tan learning. 2021a.
Advances in Neural Information Processing Systems, 34:1
L. Liu. Y. Li, Z. Kuang, J.-H. Xue, Y. Chen, W. Yang, Q. Liao, and W. Zhang. Towards impartial multi-task learning. In International Conference on Learning Representations, 2021b. URL IMPNRXEMP
htttps://openreviex
X. Liu, X. Tong. and Q. Liu. Profiling pareto front with multi-objective stein variational gradient descent. Advances in Neural Information Processing Systems, 34:14721-14733, 2021c.
P. Ma, T. Du, and W. Matusik. Efficient continuous pareto exploration in multi-task learning. In International Conference on Machine Learning, pages 6522-65311 PMLR, 2020.
D. Mahapatra and V. Rajan. Multi-task learning with user preferences: Gradient descent with controlled ascent in pareto optimization. In International Conference on Machine Learning, pages 6597-6607, PMLR, 2020.
A. Maurer. Bounds for linear multi-task learning. The Journal of Machine Learning Research, 7: 117-139, 2006.
A. Maurer, M. Pontil, and B. Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1-32, 2016.
I. Misra, A. Shrivastava, A. Gupta, and M. Hebert. Cross-stitch networks for multi-task learning. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 3994-4003, 2016.
M. Momma, C. Dong, and J. Liu, A multi-objectivv/mtttttesk learning framework induced by pareto stationarity. In International Conference on Machine Learning, pages 15895-15907. PMLR, 2022.
A. Navon, A. Shamsian, E. Fetaya, and G. Chechik. Learning the pareto front with hypemeetorrs.. In International Conference on Learning Representations, 2021. URL http:///////oeerrreriee net net:/foruu//d--k)777722222
A. Navon, A. Shamsian, I. Achituve, H. Maron, K. Kawaguchi, G. Chechik, and E. Fetaya. Multi- task learning as a bargaining game. In International Conference on Machine Learning, pages 16428-16444 PMLR, 2022.
R. T. Rockafellar. Convex analysis, volume 11. Princeton university press, 1997.
M. Ruchte and Grabocka. Scalable pareto front approximation for deep multi-objective learning. In 2021 IEEE international conference on data mining (ICDM), pages 1306-1311. IEEE, 2021.
S. Ruder. An overview of multi-task learning in deep neural networks. arXiv preprint arXiv: 2017.
O. Sener and V. Koltun. Multi-task learning as multi-objective optimization. Advances in neural information processing systems, 31, 2018.
N.
and A. Berman. Copositive and completely positive matrices. World Scientific,
2021.
12

---

N. Tripuraneni, C. Jin, and M. Jordan. Provable meta-learning of linear representations. In Interna- tional Conference on Machine Learning, pages 10434-10443. PMLR, 2021.
Vandenhende, S. Georgoulis, W. Van Gansbeke, M. Proesmans, D. Dai, and L. Van Gool. Multi- task learning for dense prediction tasks: A survey. IEEE transactions pattern analysis and machine intelligence, 2021.
R. S. Varga. Matrix iterative analysis, volume 27. Springer Science & Business Media, 1999.
S. Vijayakumar and S. Schaal. Locally weighted projection regression: An o (n) algorithm for incremental real time learning in high dimensional space. Proceedings of the seventeenth international conference on machine learning (ICML 2000), volume I, pages 288-293, Morgan Kaufmann, 2000.
Y. Wang, Z. Zhao, B. Dai, C. Fifty, D. Lin, L.. Hong, L.. Wei, and E. H. Chi. Can small heads help? understanding and improving multi-task generalization. In Proceedings of the ACM Web Conference 2022, pages 3009-3019, 2022.
S. Wu, H. R. Zhang, and C. Ré. Understanding and improving information transfer in multi- task learning. In International Conference Learning Representations, 2020. URL https //openreview.eee www.://wwnneeeorummmmmmm dy
R. Xian, L. Yin, and H. Zhao. Fair and optimal classification via post-processing. In Proceedings of the International Conference Machine Learning (ICML), 2023.
D. Xin, B. Ghorbani, Gilmer, Garg, and Firat. Do current multi-task optimization methods in deep learning even help? Advances in Neural Information Processing Systems, 35:13597-13609, 2022.
M. Ye and Q Liu. Pareto navigation gradient descent: a first-order algorithm for optimization in pareto set. In Uncertainty in Artificial Intelligence, pages 2246-2255. PMLR, 2022.
F. Yu, H. Chen, X. Wang, W. Xian, Y. Chen, F. Liu, V. Madhavan, and T. Darrell. Bdd100k: A diverse driving dataset for heterogeneous multitask learning. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 2636-2645, 2020a.
T. Yu, S. Kumar, A. Gupta, S. Levine, K. Hausman, and C. Finn. Gradient surgery for multi-task learning, Advances in Neural Information Processing Systems, 33:5824-5836, 2020b.
L. Zadeh. Optimality and non-scalar-value performance criteria. IEEE transactions on Automatic Control, 8(1):59-66 60, 1963.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Y. Zhang and Q. Yang. An overview of multi-task learning. National Science Review, 5(1):30 2018.
Y. Zhang and Q Yang. A survey on multi-task learning. IEEE Transactions on Knowledge and Data Engineering. 34( 34(12):5586-5609 2021.
H. Zhao and G. Gordon. Inherent tradeoffs in learning fair representations. The Journal of Machine Learning Research, 23(1):2577-2552 2022.
S. Zhou, W. Zhang, J. Jiang, W. Zhong, J. Gu, and W. Zhu. On the convergence of stochastic multi-objective gradient manipulation and beyond. Advances Neural Information Processing Systems, 35:38 103-38115 15, 2022.
13

---

A Omitted details from Section 3.1
A.1 Implementation of Figure
Figure is generated from a simple three-task linear MTI problem that we constructed, using Equa- tion (4). Specifically, set ý/ = (0.98, 0, 0.2). f2 (-0.49, -0.85, 0.2), Ús R: (-0.49, 0.85, 0.2) (the number of data points is = 3; this is rotated version of the equiangular tight frame), set q I (the width of the network is one, i.e., under-parrmeeterize),, and plotted the achievable points of Equation (4) by sweeping Pz (the set of rank-1 projection matrices). The software we used is Mathematica.
A.2
Over-parametrization reduces the Pareto front to singleton
For general non-linear multi-task neural networks, we will show that increasing the width reduces the Pareto front to a singleton, where all tasks simultancously achieve zero training loss. As consequence, linear scalarization with any convex coefficients will be able to achieve this point.
To illustrate this point, we follow the same setting as in Section 2 except changing the model to be two-layer ReLU multi-task network with bias terms. Concretely, for task i, the prediction on input is given by Ji (2,, W, b, 0;) = a! max(Wx x + b. 0). We have the following result.
Theorem A.1. There exists a two-layer ReLU multi-task network with hidden width = nk and parameters (W, b, "...................... (k),, such that
Ma(a W,b,a))= = vl. Vj E (m), Vi E [A]]
(14)
This implies that the network achieves zero training loss on each task.
Proof. For every E [k)]. we can apply Theorem in (Zhang et al. 2021) and find (W, b,, a.) such that
a max + b,, vl. Vj [n].
(15)
Here, W; E Roxp and b, āg E R". Now consider
Wi
b1
W2
b2
W
E
Rnn
a; = e, @ āj RR vi E [n].
(16)
W
by
where e denotes the i-th unit vector in IR" and stands for the Kronecker product. It is straightfor- ward to see that
0. max War + by 0) = vi Vj E [m]. Vi E [M]].
(17)
This finishes the proof desired.
A.3 Proof of Theorem
3.1
Proof of Theorem
3.7
Define v (Úi, 8) and = (e1," ... , ,kk) We are interested the set
S = (v ||||| 1, E spann(0i)iejp)
(18)
We will show S is equivalent to the following set
B = (v Qu = 1), Q= Q
(19)
which is essentially the boundary of an ellipsoid.
Step 1: S C B. Note v = TT s, so it suffices to show
8 ( s=
(20)
Denote Py - which projection matrix that maps to the column space of Y
Since E span((ai (tu he(k), we have
Pys==st = =1
(21)
14

---

Step 2: B C S. Since Y has full row rank, for every e E R², we can always find s IR" such that 8T 8 == v. We can further assume span((ūr)ieju) by removing the component in the null
space of BT. Assuming v E B, we have
s Pps==
s E span NEt)))
(22)
Since Py is projection matrix that maps to the column space of Y, we have s sT = 1, which implies ||+|| = 1.
Now we have S = B. The set
:=
:= {1vl | ||||| = 1 & E span((0e)ett))
(23)
can be obtained by reflecting E to the non-negative orthant. Formally, reflection is determined by collection of axes 11 (0 I < ks). The image of such reflection in the non-negative orthant is given by
B = {ol v Qin v= 1, 2 0),
(24)
where Qi = Pi
As a consequence, we have
s' U U
Big
(25)
ogigk <...ssk
Finally, the feasible region can be equivalently characterized as
=i (0² ||||| 1, E span ()e
(26)
which can be obtained by squaring the coordinates of S". Therefore, if we denote
E, = {ol Ve
(27)
then (note the square root naturally implies 0)
= U U
(28)
OSISA Ciiisk
This finishes the proof desired.
A.4 Proof of Theorem 3.2
Proof Theorem 3.2 Note the orthogonal complement of a 1-dimensional subspace of span( (9s he(() is (k- -)-dimensional subspace, and that the objective function for each task is the
square of the projection of D. Denote := (lls) 11 .................. 11 13) T. By the Pythagorcan theorem (Bha tia 2013 Section 1.6), if o E F1, then we must have - E F and vice versa. As consequence,
denote
In = {o Vl Qinmi vi-
(29)
and we have
F U
U
In
(30)
ogick <ins
by Theorem
3.1
A.5 Why scalarization fails in the presence of gradient disagreement
We explain why linear scalarization is incapable of exploring intersection point with gradient
disagreement.
We first recall the geometric interpretation (see Figure 4.9 in (Boyd et al. 2004) )) of linear scalarization: a point lying at the boundary of the feasible region can be achieved by scalarization, if and only there exists hyperplane at P and the feasible region lies above the hyperplane. The normal vector of the hyperplane is proportional to the scalarization coefficients. By definition, if a hyperplane at P lies below the feasible region, its normal vector must be subgradient of the surface. When the boundary of the feasible region differentiable and the subdifferential set non-empty, the normal vector must be the gradient of the surface, and the hyperplane becomes the tangent plane at P.
15

---

Now suppose P lies at the intersection of two differentiable surfaces S1 and S2, and that P can be achieved by scalarization. Applying the above argument to S₁ and P. we know that the scalarization coefficients are proportional to the gradient w.r.t. St. Similarly, applying the above argument to S2 and P yields that the scalarization coefficients are proportional to the gradient w.r.t. S2. This will result in contradiction if the two gradients w.r.t. S₁ and S2 at P lie in different directions, phenomenon we refer to as gradient disagreement. In this case, scalarization cannot reach P.
B
Omitted details from Section 3.2
B.1 Proof of Lemma 3.4
We begin by reviewing some basics of convex analysis. We refer the readers to Rockafellar (1997) for more background knowledge.
Definition B.1 (Convex hull). Let = (ai be collection of points in R". The convex hull of X, denoted as conv cXnv(X), is the set of all convex combinations of points in X, i.e.,
conv(X)=
Σ acT; kE(m]
ag 2
0,
Σ 0. = *E(m]
(31)
Definition B.2 (Cone and convex cone). A set K C R" is called cone if x E K implies az E K for all a A convex cone is cone that is closed under addition. The convex cone generated by X = {2: [iem))]
R", denoted as cone(X), is given by
cone(X) conv(ray(X)),
(32)
where rXy = {Xr; 2 E [m]]]
Definition B.3 (Dual cone). The dual cone C C R", denoted as C", given by
C² {y (y, x) 2 0, Vr E
(33)
Definition B.4 (Projection onto a convex set), Let be a closed convex set in R". The orthogonal projection of E R² onto the set C, denoted as Pay, is the solution to the optimization problem
=EC Pay == inf ( [1x - y|l}-
(34)
Theorem B.5 (Bourbaki-Chenn Chaaie-Ceeeeeyye-teiiin inequality (Ciarlet 2013 Let C' be closed convex set in R" For any x E R", we have
(x Pex,y Pax) S0,
E.
(35)
Theorem Theorem B.5 is also known as the variational characterization of convex projection. We will use to prove the following lemma, which serves as a crucial ingredient the proof Lemma 3.4 Lemma B.6. Let C be closed convex set R.. For any z RR, we have
() 2 (2,0),
Ve E C,
(36)
where z' = =P is the reflection of w.r.l C.
Proof. Plugging in z' =2p - 2, it suffices to show
(Poz - 2, 20, E.
(37)
This is true because
(Poz - -o -- - 20, E
(38)
by Theorem
B.5 and that
(z - Poz, Poz) =0.
(39)
We are now ready prove Lemma 3.4
16

---

Proof of Lemma 3.4 For the if part, we assume w.l.o.g. that G = PT is doubly non-negative. This implies that the angle between each pair of optimal predictors is non-obtuse. Denote A cone( (is he(e)) and A" as its dual cone. We have A A².
Our goal is to show that, for every ||s]| = I, we can always find E A", such that 1) || = 1: 2) [k:] This implies that when restricting
discussion the Pareto front, can safely ignore the absolute value which appears in the proof of Theorem 3.1 As a consequence,
(s', (s) (ss, 0:)l: Vi
the Pareto front belongs to the surface determined by Q = =
Consider s' A 8. is straightforward to see that ||| since it is the reflection s w.r.t. A". To show 2), we will prove:
(b' 2 (8, Ve E A.
(40)
We break the discussion into two cases.
Case 1: (x 2 O. Since A C A", have
(6', (s, (8,
(41)
by Lemma B.6
Case 2: (s, x) < O. Consider -8 and denote C {al (a, PA-s) 2 0}. It straightforward to see that CCC.
We will show Pcu PA-S 8. In fact, for any C, we have
|| 2 || (PA-5 5) S
||2 (PA.S s)]l + P s|I 2(2 (PA.S s). Pa.
2 P -|1² + +2(z, PA-S)
2 P|
P 8 8- ul?
Therefore, we have
s 2P2P 8=
(42)
With another application of Lemma B.6 we have
(s',x) xx) 2 (u, x) (-8,x) = [s,,))1
(43)
This finishes the proof of the if part.
For the only if part, we consider the point p; which achieves maximum value along the i-axis. For given i, it straightforward to see that such p; unique, and therefore a PO of the feasible region.
Now, P. belongs to a surface determined by Q', if and only if there exists a non-negative vector Us such that Q'u; e; (the normal vector p; aligns with the i-th axis). In other words, G'e, 2 0 where G = (Q')-1 When C1 does not hold, there does not exist a G* E G, such that e; 2 0 for all i [k). This implies that these p; must belong to different surfaces.
B.2 Proof of Lemma 3.5
Proof of Lemma 3.5 For the if part, we assume w.l.o.g. that Qe = G is doubly non-negative.
This essentially implies that Eg is dominated by all other surfaces in E, which further implies that la dominates all other surfaces in I. Therefore, the Pareto front must belong to Tz-
For the only if part, we study the Pareto front of F through the lens of Fi. Specifically, point is a PO of F if and only Ff, and the non-negative orthant of 2 intersects only at z. Denote the corresponding point of on F1 as z' non-positive orthant z' intersects only at z'. We can therefore consider a special type of zf whose coordinates zero except for i, j-h entry. If 2/ further lies surface Q with qız 0, then the corresponding will be a PO of F,
An equivalent characterization is that J, and the
When C2 does not hold, there exists row of Qu which contains both positive and negative entries. We assume w.l.o.g. the first row of Qo satisfies this condition. By the above observation, we can find two PO of F--1 that correspond to Q2 and Q1, respectively. This finishes the proof desired. D
17

---

B.3 Proof of Theorem 3.8
Proof of Theorem 3.8 We only prove for the case of q 1, and the proof for g = k can be done similarly. Suppose P (whose coordinate is v) lies at the intersection of two surfaces defined by Q and Q'. We denote the intersection of Q and Q' as S. which
non-linear manifold with dimension (k - 2). Since P is relative interior point of the PF, there exists some >> O, such that any point in Sn (P) is PO. We will show there exists some P E S B. (P) (whose coordinate v'), such that the gradients at P' w.r.t. the two surfaces disagree, i.e.,
Q * Q'V
(44)
To why this is true, note that Q' can be expressed as Q' = DQD, where D is diagonal matrix whose diagonal entries are either or - 1. As consequence, the set
{ Qu = Q'u}
(45)
a subspace of R whose dimension is at most (A: - 2), so it cannot fully contain a non non-linear manifold whose dimension is (kt - 2). This finishes the proof as desired.
B.4 Proof of Theorem 3.8 without assumptions (k 3)
Here we provide proof for Theorem 3.8
under
3, without relying on Assumptions 3.6 and 3.7
Proof. We prove the necessity of C1 and separately.
C1 is necessary. Suppose C1 not true.
We assume w.l.o.g. that (01, 02) 0, (#1, 03)
(0, (3) > O. Now we can write
q1
Q12
-13
Q
Q21
Q22
Q23
(46)
431
Q32
433
where Qi > 0 for all pairs of (i,j). We also have
911423 > 412913 Q22913 > 912923, 433912 > 913423-
(47)
The boundary of the feasible region formed by Egg, E1, Ez. Our goal find point / E Eg E such that 1) I is a PO of the feasible region; 2) the gradients at I w.r.t. Eg and E₁ disagree. We write the coordinate of I as (x, y l 2 / /) where
I + 9229's + 033982 2912423931 1,
(48)
8
and < Q1192 + 4224/3 4334/2 20124233/11
is straightforward to see that 2) can be satisfied as long as x + Therefore, we will focus on the realization of I). This further requires two conditions: i) / is a PO w.r.t. Eg and Et, meaning that the normal vectors are non-negative; ii) is PO w.r.t. E2, meaning that the non-negative orthant at I does not intersect with Ez.
Some simple calculations yield that i) is equivalent to
422 2 g23v2 + g2ve and g3sV 2 /23//000-- + gIvV..
(49)
Setting x = 0, we have
(22 J
/ and g > /2
(50)
by Equation 47). Therefore, it suffices to show the non-negative orthant at (0, fis/s, f /
4224/8 4334/2 20122223311 does not intersect with Ez, and by continuity we can find some 4g > 0 such that i) and ii) hold simultaneously.
To prove the above claim, suppose 0,b 2 g../s, 2 9/2/s. We will show (a, b, T) must lie above the surface defined by Eg, i.c.,
b(a,b.c) 9i1a + g22b + 9330 2 2 ab 2913 + 2423 be 1.
(51)
18

---

Let a² givbbgaaee
We have
911
c)) 2 _(aa,,00 ,0,,,,,)) b,
922
Qi2
b
933
4is
2
911
912913
vbc
911
911
911
21 (122 + 92
+ 2012025931)
4992993
8Q11
qui (122vis + 2ano22 - 2/ 2023(31)
8q11
=1.
As a consequence, by choosing a small zo, we can guarantee both 1) and 2). is therefore a PO that cannot be achieved via scalarization.
C2
necessary,
Suppose
C2 not true. We can write
Q11
Q12
913
Q =
421
Q22
423
(52)
431
Q32
433
for all pairs of (i,j). The inner boundary of Fi is formed by E1, Ez, E3, and the coordinates of their intersection I given by (42a/r, 9132 //2/r) where 911 Q229i8 + Q339i2 + 2912423931- Our goal is to show the corresponding I' on F2 (i.e., t v) is PO which cannot be achieved by scalarization.
where 9t
To see why this is true, first note that the gradients at w.r.t. the three surfaces disagree, since di > for all pairs of (i, Now, to demonstrate 1' is PO of F2, it suffices to show the non-positive orthant of intersects with Fi only at By symmetry, suffices to show that 7 does not dominate any point on Ej
To prove the above claim, suppose a < / S fs//r, S R/2/r. We will show, J = (a, b, c) must lie below the surface defined by E₁ unless J equals I. In fact, let
g(a, b, c) = 911a + q22b + q3ac + 2912 V ab 2413 2423 be.
(53)
We have
gla,b, b) S g(92s/r,
S 9 l
< g /r, sar/ l
1,
where the equalities hold iff I = JJ This finishes the proof as desired.
B.5 Proof of Theorem 3.10
We first present several useful lemmas regarding non-negative matrices.
Lemma B.7. Let A be non-negative, irreducible and real symmetric matrix, then there only exists one eigenvector of A (up to scaling), such that v >
Proof. Since is non non-negative and irreducible, by Perron-Frobenius theorem (Shaked-Monders and Berman 2021). the eigenvector associated with the largest eigenvalue p(A) (a.k.a. Perron root) can made positive, and unique up to scaling. We denote
v.
We will show the cigenvectors associated with other cigenvalues cannot be positive. In fact, assume 0 is eigenvector associated with À < p(A). Since A is symmetrie, we have
p(A)u u = TT u T T Au = Av Tu
(54)
This is contradiction since TT 0 and p(A) X.
19

---

Lemma B.8. Let A be non-negative and real symmetrie matrix. Suppose is an eigenvector of A such that O, then corresponds to the largest eigenvalue of A.
Proof. Consider the normal form Varga
1999)
of A:
B11
B12
B1d
0
B22
B2h
PAP
B,
(55)
Bad
where is permutation matrix and Bü (b)) are irreducible. It straightforward to see that non-negative. Furthermore, since permutation matrix is an orthogonal matrix, B is also symmetric (implying that B.j for i # j) and has the same spectrum as A.
Now suppose Av Ao for some 0. Since B PAPT, have Bub X with & Pv 0. Denote
2/2
2b
(56)
where each 4/ has the same dimension as Byg- Now we have
Bush Xths
Vi E [h].
(57)
Since Bü is non-negative, irreducible and real symmetric, by Lemma B.7 by corresponds to the largest eigenvalue of By Note a block diagonal matrix, so the spectrum of B is essentially the union of the spectrum of Bu. As a consequence,
Amax = Amax(() max Amax (Bi)) = A.
(58)
=E[h)
Proof of Theorem 3.10
We prove the sufficiency of C1 and C2 separately.
C1 is sufficient. We have demonstrated in Lemma 3.4 that the Pareto front belongs to single surface E, whose gram matrix doubly non-negative. Let (a1.-.. .a)) be a PO of E, and denote t vp. We will show that the tangent plane this point lies above the feasible region, implying that it can be achieved by scalarization.
Concretely, the tangent plane is given by
EjEM
aj
U1
(59)
EE[M]
To show it lies above the feasible region, it suffices to prove that it lies above every surface in E, i.c.,
ΣSER
Σ
+2
Σ
Vetuj
(60)
Va:
VE(A]
ISKjŠk
where d represents the (i, entry of Qn- Note Equation (60) can treated a quadratic
form w.r.t. Vv. so it suffices to prove the corresponding matrix is PSD. Writing compactly, it suffices show
Qu - diag(Qi @ 1) = Di (Q diag (QU ())
(61)
PSD. As a consequence, we only need to show the positive semi-definiteness the following matrix
T = Q - diag Qt 2 t}.
(62)
Since p is PO of E, have Qt 2 0. Let Qt, we have
= G diag @ Gw).
(63)
20

---

Assume w.l.o.g. that w > 0 (otherwise we simply remove the corresponding rows and columns in G- Denote
= Vdiag(w @ Gw)
and
Φ = V ② Gw >
(64)
We have
RGR = /Gad ( @ Gw V w O Gw
RGw
/diag(w @ Gw
Vi w 3 Gw
Φ.
By Lemma B.8 we have p(RGR) 1. Since RGR is positive definite, we have
1 RGR > 0.
(65)
This further implies that R 2 2 G, and
T= R
(66)
C2 is sufficient. We have demonstrated Lemma 3.5 that the Pareto front belongs to a sin- gle surface Ig. Here will further show Iø is concave, and apply the supporting hyperplane
theorem (Boyd et al. 2004 Section 2.5.2) to conclude the proof. In fact, Eg is parametrized by
Σ
qa0 +
Σ
465 M.y
(67)
KE|M]
ISKijK
Since the first term is a summation of linear functions, f(x, y) = vay is concave function and that quj O, conclude that Eg is convex, and La is concave. This finishes the proof as desired. O
C A polynomial algorithm for checking C1
We explain how Algorithm ! works.
Essentially, the goal is to find set of flipping signs (8))EE))) {+,-} that ensure positive correlation between all pairs in ( (except for those pairs that are not correlated). We state an observation which is critical for our algorithm -iven pair ÿ; and ûj. whether their signs are the same or opposite can be determined by whether Ús and új is positively or negatively correlated. Thus, given determined 8;, the signs of its subsequent predictors 8j, evaluating (Wr, " ) This allows us to determine the signs for predictors 8; in ascending order, and check for potential conflicts in the mean time.
can be uniquely determined by
We state one loop invariant in our algorithm- when entering iteration in the outer loop, s; has been determined by its preceding predictors and no confict has occurred, or it has remained undetermined (i.c., None) all the way because not correlated with any preceding predictors. At this point, what is left to be done is to examine the subsequent predictors. If s; is undetermined (lines 2-7), we attempt to use subsequent predictors determine it (line 5), and break out of the loop once gets determined. Now that we make sure that is determined after line 9, we can proceed to check the remaining subsequent predictors, either determine their signs (lines 12-13) or check for potential conflicts (lines 14-15).
We comment that caution needs be taken for the pairs that not correlated (i.e., (Ūi. (5) 0). In this case, one cannot determine the sign of s, by the relationship between these two predictors; basically, the sign has no influence on their correlation. Thus, the predictor Ø retains the flexibility to be determined by other predictors other than 9:. Additionally, it is possible that at the end of line sy is still undetermined; this only occurs when Ú is not correlated with any other optimal predictor. In this case, t will take the value of k + 1 and the following loop (lines 10-15 (5) will not be executed.
D Additional experimental details and results
D.1 Additional experimental details
Dataset. The SARCOS dataset (Vijayakumar and Schaal 2000) consists of the configurations (position, velocity, acceleration) of the robotic arms, and the problem is to predict the torque of the
21

---

Algorithm 1: An O(k²) algorithm of checking C1
Input: Optimal predictors V1, ....... Oz
Output: True if C1 met, and False otherwise
Initialize: $1
1,
82 1,
None
if x > 0
Define: sgn(x)
-,
if x < 0
None, for i 1 to k do
if x =
b Check whether 8, has been determined by its preceding optimal predictors
(
not, determine it using the subsequent ones.
if (; = None then
for j = to do if 8 * None and sgn( 0y)) # None then 8 1+ 8) sgn(( (9:. Dz))
break
1 < i+1
else
L t i+1
D Now that has been determined, proceed check the remaining optimal predictors to either determine the sign for them or check for conflicts. for j = 1 to do if sgn( (Ji, ú5)) * None then if 83 None then
I1
13
+ 8 sgn (it. 02})
14
else if s2 8y sgn (0t, 03)) = -1 then
return False
16 return True
respective arm given its triplet configuration. Since our study concentrates on the training procedure and does not concern generalization, we conduct the experiments on the training set alone, where size of the training set of the SARCOS dataset (Vijayakumar and Schaal 2000) is 40, 000. Regression tasks normally benefit from standardization as pro-processing step (Hastie et al.) 2009). so we standardize the dataset to zero mean and unit variance.
Tasks. Following our theoretical analysis in Section 3 we study the scenario where q 1. this case, it is straightforward to see that the minimal that may lead to violation of is 3. To show the violation
leading to the failure of scalarization exploring the Pareto Front, we constrain our study to & 2 3; furthermore, for ease of visualization, we focus on k = 3. In our experiments, we take the arms 4, and 5 for which do not satisfy C1
Network. We use a two-layer linear network for the reason explained in Section 2 We merge the bias term b into the weight matrix W by adding additional all-one column the input X. The input dimension of the network is 22 (seven (position, velocity, acceleration) triplets plus the dummy feature induced by b). the hidden size g 1, and the output size (i.e., the predicted torque). The same network architecture is used for both experiments in scalarization and that in SMTOs.
Implementation of linear scalarization. For linear scalarization, uniformly sample 100, 000 sets of convex coefficients from a three- dimensionl simplex (i.e., a tetrahedron). Concretely, we first sample mi. m2
d. (0, 1), and then craft À (A1, A2, As) (min(m), m2), max(m1, m2)
min(m, m22, 1- max(m1, m2) + min(m,, m2)) as the weights. For a given set of convex co- efficients, we calculate the optimal value directly based on the analysis in Section 2 instead of performing actual training. More specifically, the optimum of the scalarization objective is given by Y, := Σ Juu.i from which compute the corresponding MSE for each task.
22

---

SMTOs. We consider two state-of sfate-of-the-arr SMTOs, MGDA Désidéni 2012) and MGDA-UB (Sener and Koltun 2018). MGDA an optimization algorithm specifically devised for handling multiple objectives concurrently. It utilizes composite gradient direction to facilitate simultaneous progress across all objectives. MGDA-UP is an efficient variant MGDA that focuses on maximizing the minimum improvement among all objectives. It is a gradient-based multi-objective optimization algorithm aimed at achieving balanced optimization outcomes across all objectives.
F Implementation of SMTOs. Our code is based on the released implementation of MGDA-UB, which also includes the code for MGDA. We apply their code on the SARCOS dataset. For both methods, we use vanilla gradient descent with a learning rate of 0.5 for 100 epochs. following the default choice the released implementation. We comment that early stopping can also be adopted, i.e. terminate once the minimum norm of the convex hull of gradients is smaller than a threshold, for which we set to be 10-3
D.2 Additional experiments on random initialization
To eliminate the influence of random initialization, we perform 300 trials for each algorithm using different random seeds. We filter out solutions whose maximum MSE is larger than 1 for clearer presentation, which leads to 198 solutions for MGDA and 240 solutions for MGDA-UB UBB We plot all these solutions Figure 4 We see that MGDA and MGDA-UB are consistently capable of finding balanced solutions regardless of the random seed.
Scaovibtte
VW.30 1B
Stoker (ollinn
2.4
6.1
0.8
08
58
6.
68
5.4
64
04
38
26
(a) MGDA with multiple initializations
(b) MGDA-UB with multiple initializations
Figure 4: More solutions of MGDA and MGDA-UB obtained by varying the initializations. Both algorithms tend to find solutions located at the interior of the Pareto front.
D.3 Additional experiments on randomization
To verify the effectiveness randomization as discussed in Section 4.2 we plot the region achievable
by randomized linear scalarization. Specifically, according to Equation (I3), the region can be expressed as the collection of the convex combination of two points from the feasible region. To this end, randomly sample 100,000 weight pairs (the same number in Figure For each weight pair (W1, W2). we uniformly draw ( ~ UO, 1) and get two corresponding optimal networks f1 and f2 by SVD. For each sample, with probability i,, the model uses f1, otherwise f2, calculate the MSE. The final result is demonstrated in Figure 5 It is straightforward to see that randomization allows scalarization to trace out the PF since there is hole within the blue region, thus validating our theoretical analysis. We additionally comment that randomization convexifies the feasible region, such, the solutions found by MGDA and MGDA-UB are dominated.
23

---

MGDA
MB
Rar domizezed Stalarization
0.2
335
0.4
1.0
0.2
0.0
Figure 5: The region achievable by randomized linear scalarization
24


Reviews:
[{"review_id": "74a0uJh2wC", "reviewer": "Reviewer_nBcV", "summary": "In this paper, the authors introduce a novel mathematical framework to answer the problem “Under what conditions can (or cannot) linear scalarization recover the Pareto front of a given multi-objective optimization problem?”. To this end, the paper considers the multi-task learning setting  using a simple linear multi-task learning model in the under-parameterized regime, and introduce new concepts like “feasible regions” and \"gradient disagreement\", and state that the intersection points of aforementioned feasible regions are unattainable by optimizing any linear scalarization of the multiple objectives. Accordingly, the paper derives necessary and sufficient conditions as to when optimizing any linear scalarization of the multiple objectives can recover the Pareto front by checking for situations where the Pareto front of the problem lies entirely in one so called feasible region. The paper then provides some empirical validation of the theory that suggest linear scalarization indeed fail to cover the Pareto front, especially the “balanced” Pareto optimal points. The empirical results further suggest that Specialized Multi-Task Optimizers (SMTOs) like MGDA and MGDA-UB can achieve a more “balanced” Pareto optimal points compared to linear scalarization.", "questions": "* What is the mathematical definition of the gradients depicted in Figure 3, and what is the precise relationship between the “gradient disagreement” and the inability to recover this point by optimizing a linear scalarization of the objectives?\n\n* Could the authors provide some intuition or some physical meaning of the feasible regions described in the paper, and how they relate to the multiple objectives?\n\n* Would an implementation change of the experiments as described in the previous section (point 4) change the solution distribution of each algorithm compared to Figure 3?\n\n* Given the nature of MGDA algorithm as described in previous section (point 5), could the authors provide the reason for the convergence of MGDA like algorithms for the interior point of the Pareto front of the problem?", "limitations": "Limitations of the proposed framework are discussed discussed in the paper. In addition to these limitations, the paper does have limited validation as to SMTOs can overome the weaknesses of linear scalarization, as described in previous sections.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* The paper is aimed at finding necessary and sufficient conditions for when scalarization can not recover the Pareto front, which is an important and pertinent problem in the field of multi-objective optimization.\n\n* This paper provides a mathematical framework for analyzing the aforementioned problem, which may provide insights into how to select a method of solution for a multi-objective optimization problem based on the nature of the problem.", "weaknesses": "* The necessary and sufficient conditions derived for linear scalarization to recover the Pareto front in this paper requires Pareto optimal objective vectors to be “on the same feasible surface”, rather than being at an “intersection point of feasible surfaces”, as described in  Lemmas 3.4, 3.5. Yet, it is unclear why these intersection points cannot be attained by some scalarization of the objectives. Specifically, the “gradient disagreement” concept is unclear; for example how to mathematically characterize this gradient in the objective space, and why this gradient is related to the optimization of the multiple objectives.\n\n* It is unclear what is the origin ((0, 0, 0) point ) of the objective spaces used in the Figures 1 and 3. Thus, it is a bit hard to understand the provided illustrations of feasible regions in the objective space.\n\n* While the paper provide some weakness (i.e. the inability to recover the whole Pareto front of a problem) of scalarization in the under-parameterized regime, it does not give theoretical validation whether SMTOs can overcome this weakness. The empirical validation for showing that SMTOs can overcome the aforementioned weakness have some limitations, as described in following points. Thus, the conclusion of the paper seems to be not justified from the theoretical and empirical results.\n\n* The experiments done to verify theory seems inconsistent for SMTOs and linear scalarization methods. Specifically, SMTOs are optimized using iterative methods for 100 epochs, while scalarization solutions are obtained from the corresponding closed form expression for the optimum solution. A fair comparison of methods would be either running SMTO methods for a very large number of iterations, or using an iterative updating scheme for scalarizations for the same number of epochs. \n\n* By nature of the MGDA algorithm, if deterministic gradients are used, the algorithm should terminate at the first encounter of a Pareto stationary point (a notion of stationarity for multiple objectives similar to stationarity in single objective optimization), which is often a point either at least one objective have achieved stationarity, or the point where the objectives begin to conflict with one another (see some discussion on this here [1]). Thus, this kind of point is usually a point that will favor one objective over the others (unless the objectives are perfectly aligned). In this sense, it is unclear how MGDA have achieved an interior point of the Pareto front, as implied by Figure 3.\n\n* At the beginning of the paper (such as in the abstract) the authors pose the weakness of scalarization over SMTOs as the inability to “fully recover” the Pareto front, while the empirical evaluations suggests that SMTOs can also only recover a single Pareto optimal point, which seems to not align with the initial message.\n\nMinor comments\n\n* Definition of Pareto front introduced in the paper seems not standard (line 119). Specifically, in this paper it is referred to as the collection of  Pareto optimal points (PO) $\\theta^*$, while usually Pareto front is the set of objective values $\\\\{L_i(\\theta^*)\\\\}_{i\\in[k]}$  corresponding to Pareto optimal points.\n\n[1] Liu, Xingchao, Xin Tong, and Qiang Liu. \"Profiling pareto front with multi-objective stein variational gradient descent.\" Advances in Neural Information Processing Systems 34 (2021): 14721-14733.\n\nEdit: Added missing reference.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer nBcV for their insightful comments and constructive feedback. We address concerns and answer questions posed by the reviewer below, following the order they were made.\n\n**Why scalarization cannot explore intersection points (Weakness 1 and Question 1).** Please refer to point 3 of the general response. \n\n**The origin point in the figures (Weakness 2).** Figures 1 and 3 are generated from MTL problems with three tasks, and the feasible regions indicate the achievable set of MSEs (each axis corresponds to the MSE on a task; the smaller the better). Hence, the origin point (0,0,0) indicates solving the MTL problem perfectly, whereas the point (1,1,1) corresponds to a bad solution and is not Pareto optimal. We will regenerate Figure 3 to ensure consistency with Figure 1 by setting the origin (0,0,0) on the front and the point (1,1,1) on the back. \n\n**Advantages of SMTO methods (Weakness 3).** We agree this is a valid point, and have replied in point 4 of the general response. In short, we don’t think one SMTO method can fix the issue of scalarization and we were not advocating for any specific method. On the other hand, we do believe that developing novel SMTO methods is a valuable line of research as they provide flexibility in exploring different parts of the feasible region, and the prevalent argument that scalarization is sufficient for MTL does not hold in all the cases, at least in the under-parametrized regimes. We also perform additional experiments on MGDA and its variants to show that their capabilities of finding balanced solutions are not affected by the choice of random seed (see Figure C in the attached PDF in the general response).\n\n**Unfair comparison (Weakness 4 and Question 3).** We respectfully disagree with this point since 1) using closed-form solutions will only favor scalarization. Therefore, if our conclusion is valid in the current setup, it’s going to hold with finite iterations as well; 2) in this paper, we study the weakness of scalarization on the *representation* level. Using finite iteration methods without resorting to the existing closed-form solutions will unnecessarily introduce artifacts from the *optimization* procedure. \n\n**Why does MGDA converge to interior points? (Weakness 5 and Question 4)** After checking the reference, we failed to find a precise statement/theorem that claims or implies that MGDA will converge to a point on the periphery of the Pareto front. We would appreciate it if the reviewer could elaborate further on this point, or point to the precise location in the reference. \n\nTo further strengthen our empirical findings, we perform some additional experiments. First, we plot the optimization trajectories of MGDA and MGDA-UB in Figure A in the attached PDF. Both algorithms first overfit task 2 and approach scalarization optimal points, but then turn sharply twice and finally reach more balanced solutions. Second, Figure C demonstrates that the balancedness of the final solution is not affected by the random seed. \n \n**Deviation from the initial message (Weakness 6).** We apologize for the confusion here. We did not intend to show that a particular SMTO method can overcome the weakness of scalarization. Instead, here are some high-level messages that we would like to deliver:\n- Xin et al. (2022) observed that scalarization is capable of tracing out the PF when the objective functions are convex, and used it to support their hypothesis that there is no inherent advantage of SMTO methods and scalarization is sufficient for MTL. Our theoretical analysis demonstrates that the reasoning is untenable. Specifically, even with some mild non-convexity, scalarization is incapable of fully exploring the PF. This calls for further research on explaining the empirical success of scalarization and reconciling with the theoretical limit that we have revealed. \n- For the experiment on MGDA, we did not intend to show that it can overcome the limitation of scalarization. As a matter of fact, we do not think there exists a single SMTO method that can fully explore the PF in every scenario and can be taken as the gold standard in MTL. Rather, we would like to demonstrate that certain parts of the PF, which are not achievable by scalarization yet are of potential interest (e.g., a region that contains more balanced solutions), can be achieved by certain SMTO methods. This implies that research on SMTO is not futile, and helps to reject the claim that scalarization is sufficient for MTL. In doing so, we hope to foster a healthier and more balanced development in the field of MTL. \n\n**Explanation of the feasible region (Question 2).** Feasible region is originally defined as the set of all possible points in $\\mathbb{R}^k$ (each dimension is a quadratic function, as shown in Eq. (4)) that can be achieved by varying $P_Z$, a projection matrix determined by the weight of the hidden layer $W$. Intuitively, the feasible region is a reflection of the network's representation power. In our work, we slightly modify the definition of feasible region by imposing some restrictions on $P_Z$ (see Eq. (5)). This helps to simplify the subsequent analysis, while keeping the PF intact, meaning that the original PF is still a subset of our defined feasible region.    \n\nThe multi-surface structure arose when we were performing a fine-grained analysis of the feasible region. A possible hypothesis is related to game theory—viewing each task as a player, the number of surfaces equals the possible coalitions formed by the $k$ players ($2^k$). Each surface corresponds to one particular coalition and represents a set of possible outcomes the coalition can obtain, potentially favorable to the players within. Finally, the intersection of different surfaces indicates conflict among coalitions. \n"}, {"review_id": "tXy5qKC5bD", "reviewer": "Reviewer_J52d", "summary": "This paper revisits linear scalarization in multi-task learning from a theoretical perspective.\nThe authors reveal that scalarization is, in general, incapable of tracing out the Pareto front.\nSpecifically, when the model is under-parametrized, a multi-surface structure of the feasible region is revealed by the authors and it can be used to identify necessary and sufficient conditions for full exploration.\nExperimental results further verify the theoretical findings.", "questions": "Please check the weakness.", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides rigorous analysis to answer an important question in multi-task learning: whether linear scalarization is capable of\nfully exploring the Pareto front?\nThe authors provide insightful remarks for the theories, and the figures provide intuitive explanations for the multi-surface structure of the feasible region.\n\n2. The paper is well-written and easy to follow. Sufficient preliminaries and explanations are provided.", "weaknesses": "1. The paper only studies the under-parametrized regime. It remains unclear whether the conclusion still holds for over-parametrized regimes where the model capacity is large enough and task competence does not exist.\n\n2. The paper mainly focuses on a two-layer neural network. Therefore, it remains unclear whether the conclusion still holds for non-convex functions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank Reviewer J52d for taking the time to review our paper. We are grateful that the reviewer appreciates our theoretical contributions. The concerns raised by the reviewer are addressed in the general response. Specifically,\n\n**The under-parameterized regime.** Please refer to point 1 of the general response. In short, while the over-parameterized regime is indeed more practical, and that our results might not directly transfer, we still find it important to identify *certain* problem settings, in which we can demonstrate the weakness of linear scalarization while revealing potential benefits of SMTO methods. This helps to counter the recent arguments in the field which suggest linear scalarization is sufficient for MTL, and encourages further research in developing novel SMTO methods. \n\n**Toy models.** Please refer to point 2 of the general response. We emphasize that even for two-layer linear networks, the loss function is *not* convex w.r.t. the model parameters, and that both the techniques and results in this paper are novel (to the best of our knowledge) and greatly advance those in the literature of convex analysis. \n\n\n"}, {"review_id": "pA7GdiS4pt", "reviewer": "Reviewer_c3Pi", "summary": "This paper studies the linear scalarization approach in multi-task learning (MTL). It shows theoretically that the linear scalarization is not able to fully capture the Pareto optimal (PO) solutions. It also identifies necessary and sufficient conditions of full exploration of the PO solutions for under-parameterized two-layer linear MTL models.\nThis explains why scalarization fails in certain cases. Experiments are performed to further verify the theoretical findings.", "questions": "1. I do not agree with the claimed contribution 2, line 63-65, where the authors claimed to give the \"first guarantee for full exploration in the presence of non-convexity.\"\n\n- Please see reference [1], where necessary conditions of Pareto optimality are given for the linear scalarization method with \"p-directionally convex\" requirement of the criterion space, which is not convex.\n\n- Please see reference [2,3], where sufficient conditions of (weak) Pareto optimality are given for the linear scalarization method.\n\n- Please discuss the difference and relations with the listed prior works. Perhaps you need to add the specific settings, such as \"for under-parameterized two-layer linear networks\".\n\n2. Since this paper is focused on the underparameterized model with $q < k$, how does the theory in this paper helps understanding the question posed in Xin et al. (2022), which is for deep models usually overparameterized?\n\n3. What are the implementation details for visualization in Figure 1?\n\n4. In line 170, what does \"gradients disagree\" mean? Does it mean they are not in the exactly same direction or the angle between the two gradients is larger than a threshold? There should be a formal definition.\n\n\n\n---\n[1] Lin, Jiguan G. “Three Methods for Determining Pareto-Optimal Solutions of Multiple-Objective Problems”\n\n[2] Zadeh LA, \"Optimality and non-scalar-valued performance criteria\"\n\n[3] Goicoechea A, Hansen DR, Duckstein L, \"Multiobjective decision analysis with engineering and business applications\".\n\n\n\n---\n\n### Minor\n\nTypos and grammar errors:\n\nLine 2: \"since its inception\" -> \"because of its inception\"\nLine 96: \"vecotrs\" -> \"vectors\"", "limitations": "The authors have adequately addressed the limitations in Section 5.\n\nI expect the authors to conduct a thorough review with the most relevant works, see Weaknesses-1.\n\nOverall, this paper studies an important problem with a unique perspective.\nI am willing to increase my score if the authors can address these questions.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper studies an important and timely problem, focusing on whether the popular approach -- linear scalarization for MTL are able to fully capture the Pareto front.\n\n2. The perspective of this paper and techniques to develop the theory under the specific two-layer linear models are unique.\n\n3. Paper is well written and easy to follow.", "weaknesses": "1. There is a lack of discussion of related works that also identifies the failure cases of linear scalarization fully capturing the Pareto front. See [1,2,3,4].  \nWhat is the unique contribution of this paper compared to these prior works? Some discussions need to be provided to distinguish with the prior works.\n\n---\n[1] Lin, Jiguan G. “Three Methods for Determining Pareto-Optimal Solutions of Multiple-Objective Problems”\n\n[2] Zadeh LA, \"Optimality and non-scalar-valued performance criteria\"\n\n[3] Goicoechea A, Hansen DR, Duckstein L, \"Multiobjective decision analysis with engineering and business applications\".\n\n[4] R. Timothy Marler, Jasbir S. Arora, \"The weighted sum method for multi-objective optimization: new insights\"\n\n[5] Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, Qiang Liu, \"Conflict-Averse Gradient Descent for Multi-task Learning\"\n\n---\n\n2. In line 56-57, it is too restrictive to claim that \"if scalarization cannot fully explore the Pareto front, there is no inherent advantage of SMTOs over scalarization.\" In fact, there are other benefits of SMTOs beyond this. For SMTO methods like MGDA, the motivation is to find the steepest common descent direction for all objectives at each iteration. And the benefit sometimes lies in the optimization procedure besides the solutions they find. See the toy example in [5]\n\n3. Even though the paper shows that linear scalarization approach is not able to fully explore the Pareto set in some settings, there is no discussion on whether SMTOs are able to fully explore the Pareto set in the same settings.\n\n4. Some questions need to be clarified. See **Questions**\n\n\n\n-----------------------------update post rebuttal-------------------------------\n\nI have read the rebuttal and participated in the discussion. \n\nThe rebuttal partially addressed my concerns so I remained relatively positive about this work.\n\nIt could further improve with a more thorough discussion of the classical works and more precise positioning of their contributions.\n\n--------------------------------------------------------------------------------------", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our sincere gratitude to Reviewer c3Pi for taking the time to review our paper, providing valuable and constructive feedback, and pointing out useful references. We hope to address all comments in the review below, following the order they were made. \n\n**Comparison with prior works (Weakness 1 and Question 1).** Thank you for pointing out the references! After carefully checking these papers, we find that [1] does provide a sufficient condition (p-directionally convex) for full-exploration (rather than a necessary condition), which we were previously unaware of. We are grateful to the reviewer for pointing this out and will for sure 1) incorporate it in the related work; 2) revise the second point of contribution accordingly. However, we are unable to find necessary or sufficient conditions for full-exploration in [2,3,4]. We kindly request the reviewer to further refer to the relevant content in these papers.\n\nOne obvious difference between our work and prior works, as the reviewer has mentioned, is that we focus on a specific setting with a concrete model (linear networks), while prior works provide more general (and therefore much weaker) results, concerning the properties of the objective functions. But we believe the most important difference that allows our work to stand out is that the conditions we uncover are **both necessary and sufficient**, so they provide a complete picture as to when scalarization can fully explore the PF in our setting. Importantly, this facilitates the understanding of the *hardness* of full-exploration. By examining the restrictiveness of the condition, we come to the conclusion that such weakness of scalarization is fundamental. In contrast, to the best of our knowledge, there is no prior work that identifies a both necessary and sufficient condition in any non-convex setting. A sufficient condition alone is not as indicative of the hardness of full-exploration or the fundamental weakness of scalarization.\n\n**Overclaiming (Weakness 2).** We agree with the reviewer's comment and will revise this sentence. We understand that there are other aspects in comparing scalarization and SMTOs aside from the one we take, and have pointed out in the future direction (Line 356-357) that a rigorous analysis of the advantages of SMTOs is an important future work.\n\n**Advantages of SMTO methods (Weakness 3).** We agree this is a valid point, and have replied in point 4 of the general response. In short, we don’t think one SMTO method can fix the issue of linear scalarization in every scenario and we were not advocating for one particular method such as MGDA. On the other hand, we do believe that developing novel SMTO methods is a valuable line of research as they provide great flexibility in exploring different parts of the feasible region, and the argument that linear scalarization is sufficient for MTL should be rejected. We also perform additional experiments on MGDA and its variants to showcase that their capabilities of finding balanced solutions are not affected by the choice of random seed (see Figure C in the attached PDF in the general response).\n\n**The under-parametrized regime (Question 2).** Please refer to point 1 of the general response. In short, our results do not have direct implications on the results of Xin et al. (2022), as they are established under different settings. Rather, they complement each other by providing a more complete view on the strengths and weaknesses of linear scalarization and SMTO methods. \n\n**Implementation details of Figure 1 (Question 3).** Figure 1 is generated from a simple three-task linear MTL problem that we constructed, using Eq. (4). Specifically, we set $\\hat y_1\\approx(0.98,0,0.2), \\hat y_2\\approx(-0.49,-0.85,0.2), \\hat y_3\\approx(-0.49,0.85,0.2)$ (the number of data points is $n=3$; this is a rotated version of the equiangular tight frame), set $q=1$ (the width of the network is one, i.e., under-parameterized), and plotted the achievable points of Eq. (4) by sweeping $P_Z$ (the set of rank-1 projection matrices). The software we used is Mathematica. We will include the details in the Appendix. \n\n**Gradient disagreement (Question 4).** We are sorry for the confusion. ‘Gradient disagreement’ refers to a situation where a point lies at the intersection of two surfaces, and the tangent planes to each surface at that point are different. Equivalently, it means that the two gradients are not in the exactly same direction, so your first hypothesis is correct. We will formally define this concept in the revision. The reviewer can also refer to point 3 of the general response for more explanations. \n\n**Minor.** Thanks for pointing them out, we will revise accordingly. \n\n\n**References**\n\n[1] Lin, Jiguan G. \"Three methods for determining Pareto-optimal solutions of multiple-objective problems.\" Directions in Large-Scale Systems: Many-Person Optimization and Decentralized Control. Boston, MA: Springer US, 1976. 117-138.\n\n[2] Zadeh, Lofti. \"Optimality and non-scalar-valued performance criteria.\" IEEE transactions on Automatic Control 8.1 (1963): 59-60.\n\n[3] Goicoechea, Ambrose, Don R. Hansen, and Lucien Duckstein. \"Multiobjective decision analysis with engineering and business applications.\" (No Title) (1982).\n\n[4] Marler, R. Timothy, and Jasbir S. Arora. \"The weighted sum method for multi-objective optimization: new insights.\" Structural and multidisciplinary optimization 41 (2010): 853-862."}, {"review_id": "XwlfRyGKlB", "reviewer": "Reviewer_2hHW", "summary": "This paper revisits linear scalarization from a theoretical perspective. The authors study multi-task learning with a two-layer linear network and reveal a multi-surface structure of the feasible region. They show the necessary and sufficient conditions for full exploration in the under-parameterized regime. Their theoretical results imply that linear scalarization has fundamental limitations and that scalarization tends to overfit a small fraction of tasks. They answer some open questions proposed in Xin et at.(2022) and also provide experiments on a three-task learning problem to verify the theoretical results.", "questions": "Please see the weaknesses.", "limitations": "The theoretical analysis in this paper is only applied to the linear network and under-parametrized regime, which is a limitation of this paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- It is a novel and interesting problem to study whether linear scalarization can fully explore the Pareto front. The authors provide necessary and sufficient conditions for this in the under-parametrized regime, which is the main contribution of this paper.\n- The notations and presentations in this paper are clear and the proofs seem to be correct.\n- They empirically study the validity of the theoretical results, and the experiments are reasonable, and the results are convincing to me.", "weaknesses": "- The authors study only two cases (q = 1 and q = k - 1) in the under-parametrized regime, but are these two extreme cases representative for other cases in the under-parametrized regime?\n- This paper discusses linear scalarization in the under-parametrized regime. However, over-parameterization is common in deep learning, where the network has sufficient capacity to adapt to the target tasks. Does this mean that linear scalarization in the overparameterized regime does not have the fundamental limitations discussed in this paper?\n- I commend the authors for attempting to answer some open questions in Xin et al. (2022), but it lacks an explanation for why SMTOs have no improvement over linear scalarization in deep multitask learning, which is found in Xin et al. (2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank Reviewer 2hHW for taking the time to review our paper. We appreciate that they found our work interesting and novel. Below we attempt to answer the reviewer’s questions, following the order they were made.\n\n**Are $q=1$ and $q=k-1$ representative?** A rigorous study for the general under-parametrized regime is challenging, primarily due to the hardness of characterizing the feasible region. As demonstrated in Section 3, our analysis crucially relies on the algebraic form of the surfaces, but we are unable to obtain a closed form for general $q$. Nevertheless, we do think deeply about this question, and would like to share some of our thoughts here: \n\n- The capacity of the network (reflected by $q$) is the most important quantity in this problem, as different tasks are competing for the capacity of the network for better prediction. We note that $q=1$ and $q=k-1$ represent two extreme cases, corresponding to extreme under-parameterization (least capacity) and mild under-parametrization (close-to-optimal capacity). Since the results for these two cases are similar, plus it is reasonable to assume a *smooth* change when $q$ varies, we expect the same conclusions to hold for the $q$'s in between. \n\n- We make a conjecture regarding the general conclusion. We hypothesize there is a function $F$ that transforms the gram matrix to its inverse as we increase $q$. Specifically, $F$ takes $q$ as input and outputs a matrix, $F(1)$ equals the gram matrix, and $F(q-1)$ equals the inverse of the gram matrix. The necessary and sufficient condition of full-exploration for general $q$ will then be: '$F(q)$ is doubly non-negative'. \n\n- Finally, we strongly believe that the multi-surface structure that we have revealed is both universal and fundamental. As a matter of fact, we observed a similar phenomenon when working on a toy example in a generalized setting, in which different tasks have different input $X$.  This is strong evidence showing that our conclusion can have broad applicability.\n\n**The under-parametrized regime.** Please refer to the first paragraph in point 1 of the general response. In short, while the over-parameterized regime is indeed more practical, we find it important to identify *certain* problem settings, in which we can demonstrate the weakness of linear scalarization while revealing potential benefits of SMTO methods. This helps to counter the recent arguments in the field which suggest linear scalarization is sufficient for MTL, and encourages further research in developing novel SMTO methods. \n\n**Comparison with Xin et al. (2022).** Please refer to the second paragraph in point 1 of the general response. In short, the results in these two works are not directly comparable and do not necessarily contradict each other; instead, they complement each other by providing a more complete view on the strengths and weaknesses of linear scalarization and SMTO methods. "}, {"review_id": "IY4HJNpYNY", "reviewer": "Reviewer_CFe6", "summary": "This paper is related to multi-objective optimization area.\nThey post a research question: if linearly weighting multiple objectives can fully explore the Pareto front?\nThrough theoretical analysis and a simple experiment, the answer is negative.\nHence, this might prove that multiple gradient descent algorithm is inherently better than linear objective weighting.", "questions": "1. if MTL has different objectives like one regression task and one classification task, will your conclusion hold?\n\n2. If MTL has non-linear transformation like Sigmoid, will your conclusion hold?\n\n3. Do we have practical usage of randomization for linear scalarization?", "limitations": "No negative social impact", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Recently, many report that linear weighting is no worse and even better than gradient balancing algorithms like multiple gradient descent algorithm (MGDA). \nHowever, these findings are empirical,\nThis paper targets on an important question: if multiple gradient descent algorithm is inherently better than simple linear weighting when conflict gradients are presenting.\nThrough theoretical analysis and a simple experiment, the answer is yes, which lay a good foundation for this area.\n", "weaknesses": "The MTL model is this paper is very simple. I am not sure if this could reflect the real problem in the industry system.\nThis model only have one layer of shared layer and one layer of task-head. And this is a linear neural network. (I am not sure if pure linear can be called neural network).\nSo, seems this MTL model is a convex optimization.\nHowever, in real industry systems, there are many layers (maybe millions of parameters) with non-linear transformation and hence a non-convex optimization.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank Reviewer CFe6 for taking the time to review our paper. We appreciate that they found the problem of our study important. Below we attempt to address the reviewer’s concerns, following the order they were made. \n\n**Weaknesses.** Please refer to point 2 of the general response. We emphasize that even for two-layer linear networks, the loss function is *not* convex w.r.t. the model parameters, and that both the techniques and results in this paper are novel (to the best of our knowledge) and greatly advance those in the literature of convex analysis. \n\n**Question 1 and 2.** The honest answer to the first two questions is 'we don't know'. We understand that a more sophisticated setting or model architecture will be more appealing to the reviewer. However, we would like to share a few points in this aspect: \n\n- While a more complicated setting or model generally necessitates more advanced techniques, it is not the case conversely. For instance, ridge regression is probably one of the simplest models in machine learning, yet it is still being extensively studied in the literature [1,2,3]. In analogy, while we focus on linear MTL for regression, we are targeting an important question in MTL from an unique perspective, and the techniques that we have developed in this paper are highly non-trivial (e.g., the innovative application of Perron-Frobenius theorem, bridging full-exploration with doubly non-negative matrices, etc). We therefore believe the theoretical contribution of this paper is significant, and shouldn't be dimmed by the setting. \n\n- We carefully compile a list of implications derived through our theoretical analysis. We believe that sharing such insights with the broader community is more important than proving similar results in variations of the original setting. \n\n- Building up a strong and robust theory requires collaborative effort from the research community. As stated at the end of our paper, we hope this work can initiate a line of work that provides theoretical justifications of the usage of specific algorithms in MTL. We therefore believe that follow-up works will answer the reviewer's questions.\n\nWe sincerely hope the reviewer can reconsider their evaluation of the paper based on the above response.\n\n**Question 3.** We are not aware of existing literature on using randomization in linear scalarization. But the caveat here is that randomization helps to enlarge the feasible regions beyond the ones that could be achieved by any deterministic models. Specifically, the new PF is going to be the convex hull of the original one, and this implies that 1) it can lead to better solution points (in the Pareto sense) overall; 2) it guarantees that the new PF can be fully explored by linear scalarization according to standard results in convex analysis (e.g., [4]). In essence, randomization increases the representation power of the original neural network. \n\nWe additionally comment that randomization is a powerful tool that has wide applicability in machine learning. For instance, it has achieved great success in online learning, specifically in the Follow-the-Perturbed-Leader algorithm (see [5]). It also appears in the literature of fairness to achieve the optimal regressor or classifier (see [6]). In our work, we further demonstrate that it can be applied to MTL, specifically, to convexify the feasible region and allow linear scalarization to fully explore the PF. \n\n\n**References**\n\n[1] Richards, Dominic, Jaouad Mourtada, and Lorenzo Rosasco. \"Asymptotics of ridge (less) regression under general source condition.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.\n\n[2] Cheng, Chen, and Andrea Montanari. \"Dimension free ridge regression.\" arXiv preprint arXiv:2210.08571 (2022).\n\n[3] Tsigler, Alexander, and Peter L. Bartlett. \"Benign overfitting in ridge regression.\" J. Mach. Learn. Res. 24 (2023): 123-1.\n\n[4] Boyd, Stephen P., and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.\n\n[5] https://users.soe.ucsc.edu/~sesh/Teaching/2020/CSE290A/Slides/Lecture18.pdf\n\n[6] Zhao, Han, and Geoffrey J. Gordon. \"Inherent tradeoffs in learning fair representations.\" The Journal of Machine Learning Research 23.1 (2022): 2527-2552.\n"}, {"review_id": "3xzVnDMO12", "reviewer": "Reviewer_aGcP", "summary": "In recent years, there has been a surge in papers suggesting Specialized Multi-Task Optimizers (SMTOs). These papers show the empirical advantage of using SMTOs compared to linear scalarization (LS). However, recently, there have been several papers that suggested that LS with proper tunning can match SMTOs performance. The paper analyzes scalarization from a theoretical perspective, and studies whether scalarization is capable of fully exploring the Pareto front in linear MTL. It reveals some inherent limitations of LS for MTL optimization. ", "questions": "1. How realistic is the case $q<k$ for real-world applications?", "limitations": "Addressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper addresses an important open question in MTL optimization.\n1. The paper is (mostly) well-written and well-structured.\n1. The paper provides an in-depth theoretical analysis with implications for both MTL researchers and practitioners.\n", "weaknesses": "1. A primary argument is that LS cannot reach a point in the intersection of surfaces. However, it is not clear from Section 3.2 why this is the case. Please elaborate on this point and revise the manuscript accordingly.\n1. Please discuss the main results and novelty w.r.t the known result ([1]), which states that LS cannot reach non-convex parts of the Pareto front.\n1. It would be beneficial to revise Section 3, by either breaking it into two sections or summarizing the main results at the beginning of the Section.\n1. Please add an experiment with the proposed randomization approach to empirically verify that it can explore the entire Pareto front.\n1. Missing citations in related work:\n    1. SMTOs: \n        - Multi-Task Learning as a Bargaining Game, ICML 2022. \n        - Towards Impartial Multi-task Learning, ICLR 2021.\n        - Gradient Vaccine: Investigating and Improving Multi-task Optimization in Massively Multilingual Models, ICLR 2021.\n    1. Exploration of the Pareto front: There’s a line of work for methods trying to learn the entire Pareto front, so it is important to mention it. The two pioneering papers for Pareto front learning are:\n        - Learning the Pareto Front with Hypernetworks, ICLR 2021.\n        - Controllable Pareto Multi-Task Learning, 2021. \n\n[1] S. Boyd, S. P. Boyd, and L. Vandenberghe. Convex optimization. 2004.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank Reviewer aGcP for their constructive feedback. We are grateful that the reviewer appreciates the significance of the problem we tackled as well as the theoretical contributions. We hope to address all points in the review below, following the order they were made. \n\n**Why scalarization cannot explore intersection points.** Please refer to point 3 of the general response, in which we provide detailed reasoning steps and explanations. We will elaborate on this point in the revision.\n\n**Comparison with [1].** We have carefully checked the reference by searching the keyword 'scalarization', but were unable to find the result that you mentioned. Could you kindly refer to the relevant content in the book? As far as we know, [1] only states that, when the objective functions are convex, the Pareto front can be fully explored by LS. Figure 4.9 in [1] provides an example of PO ($f_0(x_3)$) that cannot be achieved by LS, but it is unclear how it corresponds to the 'non-convex part' of the PF, and how $f_0(x_1)$ and $f_0(x_2)$ corresponds to 'convex parts' of the PF. We believe that these terms (convex or non-convex part of a set) are not well-defined, as one can only talk about the convexity or non-convexity of the PF as a whole.\n\nIn our work, we note that the PF is only a subset of the feasible region. Proving the PF is convex does not directly yield the result of full-exploration. As a consequence, we approach this problem from a different perspective. After revealing the multi-surface structure of the feasible region, we examine when the PF lies on a single surface instead of checking when it is convex. This allows us to derive a both necessary and sufficient condition for full-exploration.\n\n**Structure of Section 3.** Thanks for the suggestion! We agree that the current Section 3 is too long, and will break it into two sections to increase the readability.\n\n**Experiments on randomization.** We conduct experiments based on the equation derived before Line 300. Specifically, the region achievable by randomization can be expressed as the collection of the convex combination of two points from the feasible region. To this end, we randomly sample 100000 weight pairs (the same number as in the original experiment). For each weight pair $(w_1,w_2)$, we uniformly draw $t \\sim U(0,1)$, and get two corresponding optimal networks $f_1$ and $f_2$ by SVD. For each sample, with probability $t$, the model uses $f_1$, otherwise $f_2$, to calculate the MSE. Finally, we plot the set of all MSEs in Figure B (see the attached PDF in the general response). It is straightforward to see that randomization allows scalarization to trace out the PF since there is no hole within the blue region, thus validating our theoretical analysis. We additionally comment that randomization convexifies the feasible region, as such, the solutions found by MGDA and MGDA-UB are dominated. \n\n\n**Missing references.** We thank the reviewer for pointing out the references, and will for sure incorporate them in the revision.\n\n**The $q<k$ assumption.** Please refer to the first point of the general response. \n\n\n**References**\n\n[1] Boyd, Stephen P., and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004."}]

Author rebuttal:
Here we address some common concerns raised by multiple reviewers.

**1. The under-parameterized regime.** (Reviewer J52d, c3Pi, 2hHW, aGcP)

We acknowledge that the over-parameterized regime is more practical, and the conclusions in this paper may not directly generalize. As a matter of fact, even for linear over-parameterized models, scalarization can fully explore the Pareto front (PF), and the limitation that we have revealed no longer holds. Nevertheless, our main focus is to show that under *certain* problem settings, scalarization has fundamental limitations, while SMTO methods can provide benefits (e.g., finding balanced solutions). In doing so,  we strive to bolster research in SMTO by addressing and countering recent arguments found in [1,2], which excessively laud the merits of scalarization, consequently diminishing the perceived value of SMTO. Our aim is to provide a more balanced perspective on the subject and clarify the importance of SMTO in the context of relevant research.

We emphasize that we take a different perspective—the full exploration of PF—in comparing scalarization and SMTO methods than [1], which focuses on the *accuracy*. As such, the conclusions in these two works are not directly comparable. In contrast, they complement each other by providing different views on the strengths and weaknesses of these two lines of work, which we believe is of great significance to both researchers and practitioners.

**2. Simple models.** (Reviewer J52d, CFe6)

Generalization to the non-linear setting is an important future work that goes beyond the scope of our paper. Additionally, 
- Even for linear networks, the objective functions are not convex w.r.t. the model parameters, so the theoretical analysis demands fundamentally different techniques than those in convex analysis (see [3]). 
- As stated in the paper, our results are strong in the sense that they are inherent, i.e., our conclusions are independent of the specific optimization algorithms used to minimize the scalarization objective. Furthermore, our results can be easily generalized to multi-layer linear networks, as they have the same representation power as their two-layer counterparts.

**3. Why scalarization cannot explore intersection points?** (Reviewer nBcV, c3Pi, aGcP)

We apologize for the confusion, and provide detailed explanations in what follows.

We use Figure 4.9 in [3] for ease of illustration (see [this link](https://drive.google.com/file/d/1d-5PWLSs-MJSGpxgLr_sDdCHS2IVQpyR/view?usp=drive_link)). A point $P$ lying at the boundary of the feasible region can be achieved by scalarization, if and only if there exists a hyperplane at $P$ and the feasible region lies above the hyperplane. In Figure 4.9, $f_0(x_1)$ and $f_0(x_2)$ are positive examples as the dashed lines do not intersect with the shaded region, while $f_0(x_3)$ is a negative example. The normal vector of the hyperplane is proportional to the scalarization coefficients.

By definition, if a hyperplane at $P$ lies below the feasible region, its normal vector must be a subgradient of the surface. When the boundary of the feasible region is differentiable and the subdifferential set is non-empty, the normal vector must be the gradient of the surface, and the hyperplane becomes the tangent plane at $P$. So the mathematical characterization of ‘gradient’ would be the normal vector of the tangent plane.

Now suppose $P$ lies at the intersection of two differentiable surfaces $S_1$ and $S_2$, and that $P$ can be achieved by scalarization. Applying the above argument to $S_1$ and $P$, we know that the scalarization coefficients are proportional to the gradient w.r.t. $S_1$. Similarly, applying the above argument to $S_2$ and $P$ yields that the scalarization coefficients are proportional to the gradient w.r.t. $S_2$. This will result in a contradiction if the two gradients w.r.t. $S_1$ and $S_2$ at $P$ lie in different directions, a phenomenon we refer to as ‘gradient disagreement’.

We hope the above explanation clarifies the reviewers’ concern. 

**4. Advantages of SMTO methods.** (Reviewers nBcV, c3Pi)

We acknowledge this is a limitation of our work, and have mentioned it in the future work section. Additionally, 
- We hypothesize that there does not exist a *single* SMTO method that can trace out the PF in every case and therefore dominate the others. But the abundance of SMTO methods does provide flexibility for practitioners: depending on the problem structure and specific requirement, one may select proper SMTO methods that are capable of exploring *some* part of the PF. For instance, when the balancedness of solution is of utmost importance, [4] is a good fit. 
- As a consequence, it is not our goal to advocate for any specific SMTO method like MGDA. Instead, by pointing out a fundamental limitation of scalarization, we hope to reject the prevalent claim that scalarization is sufficient for MTL, and bolster research in the development of novel SMTO methods. We believe our paper, combined with [1,2], provides a more comprehensive understanding of the strengths and limitations of scalarization and SMTO methods, and contributes to a healthier and more balanced understanding of different MTL paradigms.
- Finally, we conduct additional experiments on MGDA and MGDA-UB. As reflected in Figure C in the attached PDF, their capabilities of finding balanced solutions are not affected by the choice of random seed. This further strengthens our argument on the potential benefit of some SMTO methods.

**References**

[1] Xin, Derrick, et al.  Do Current Multi-Task Optimization Methods in Deep Learning Even Help? NeurIPS 2022

[2] Kurin, Vitaly, et al.  In defense of the unitary scalarization for deep multi-task learning. NeurIPS 2022

[3] Boyd, Stephen P., and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004

[4] Navon, Aviv, et al. Multi-task learning as a bargaining game. arXiv:2202.01017

Meta-review: The paper is theoretically studying the linear scaling for multi-task learning. The most interesting result is the finding that no static scaling is guaranteed to find a Pareto efficient solution for the under-parameterized setting. The paper was reviewed by 6 reviewers and they all unanimously suggested acceptance. I would strongly recommend authors to incorporate reviewers' feedback and as well as add a discussion about possible extensions to over-parameterized regime.
Decision: Accept (poster)