Leveraging Variable Sparsity to Refine Pareto Stationarity in Multi-Objective Optimization
Authors: Zeou Hu
Yaoliang Yu
Venue: ICLR 2025 Poster (2025)
Keywords: Multi-Objective Optimization
Machine Learning
Deep Learning
Multi-task Learning
Gradient-Based Optimization
Primary area: optimization
TL;DR: We introduce the solution concept called RPS, together with an algorithm RP-MGDA, that gives sharper solutions for gradient-based MOO

Abstract: Gradient-based multi-objective optimization (MOO) is essential in modern machine learning, with applications in e.g., multi-task learning, federated learning,  algorithmic fairness and reinforcement learning. In this work, we first reveal some limitations of Pareto stationarity, a widely accepted first-order condition for Pareto optimality, in the presence of sparse function-variable structures. Next, to account for such sparsity, we propose a novel solution concept termed Refined Pareto Stationarity (RPS), which we prove is always sandwiched between Pareto optimality and Pareto stationarity. We give an efficient partitioning algorithm to automatically mine the function-variable dependency and substantially trim non-optimal Pareto stationary solutions. Then, we show that gradient-based descent algorithms in MOO can be enhanced with our refined partitioning. In particular, we propose Multiple Gradient Descent Algorithm with Refined Partition (RP-MGDA) as an example method that converges to RPS, while still enjoying a similar per-step complexity and convergence rate. Lastly, we validate our approach through experiments on both synthetic examples and realistic application scenarios where distinct function-variable dependency structures appear. Our results highlight the importance of exploiting function-variable structure in gradient-based MOO, and provide a seamless enhancement to existing approaches.

Published as a conference paper at ICLR 2025
LEVERAGING VARIABLE SPARSITY TO REFINE PARETO STATIONARITY IN MULTI-OBIECTIVE OPTIMIZATION
Zeou Hu
Yaoliang Yu
University of Waterloo, Vector Institute
University of Waterloo, Vector Institute
zeou. hu@wwaterloo.ca
ABSTRACT
Gradient-based multi-objective optimization (MOO) is essential in modern ma- chine learning, with applications in e.g., multi-task learning, federated learning, algorithmic fairness and reinforcement learning. In this work, we first reveal some limitations of Pareto stationarity, a widely accepted first-order condition for Pareto optimality, in the presence of sparse function- vvaribble structures. Next, to account for such sparsity, we propose a novel solution concept termed Refined Pareto Sta- tionarity (RPS), which we prove is always sandwiched between Pareto optimality and Pareto stationarity. We give an efficient partitioning algorithm to automatically mine the vaarible- dependency and substantially trim non-optimal Pareto stationary solutions. Then, we show that gradient-based descent algorithms in MOO can be enhanced with our refined partitioning. In particular, we propose Multiple Gradient Descent Algorithm with Refined Partition (RP-MGDA) as an example method that converges RPS, while still enjoying a similar per-step complexity and convergence rate. Lastly, we validate our approach through ex- periments on both synthetic examples and realistic application scenarios where distinct function-variable dependency structures appear. Our results highlight the importance of exploiting function-varian structure in gradient-basee MOO, and provide seamless enhancement to existing approaches.
INTRODUCTION
Multi-objective optimization (MOO) aims to optimize several objective functions simultaneously over shared parameters, seeking solutions where no objective can be improved without worsening another. Many modern machine learning applications naturally involve multiple objectives. For example, in fair machine learning, one needs to balance model utility with various faimess notions, while in multi-task learning, models are trained across different tasks with shared representations. Similarly, federated learning and reinforcement learning often involve optimizing the performance of multiple agents or entities distributed across environments. The solutions to such problems are known as Pareto optimal (PO) solutions, representing balance across the competing objectives. However, finding PO solutions becomes challenging in complex (e.g. high-dimensional) problems.
Among various approaches for solving MOO problems. one that has gained significant attention recently is the Multiple Gradient Descent Algorithm (MGDA) (Mukai, 1980; Fliege and Svaiter, 2000; Désidéri, 2012). MGDA extends classical gradient descent to optimize multiple objectives simultancously. Unlike traditional linear scalarization, which requires predetermined weights for each objective, MGDA directly optimizes the vector-valued problem without such weighting. At each iteration, MGDA identifies common descent direction that improves all objectives, a feature not guaranteed by scalarization methods. MGDA's ability to converge to a Pareto stationary solution, which serves as first-order necessary condition for Pareto optimality, has made it widely applicable in areas like multi-task learning (Sener and Koltun, 2018), federated learning (Hu et al., 2022), and generative modeling (Albuquerque al., 2019). While Pareto stationarity provides solid theoretical foundation (as shown in Lemma I below), it can fall short in complex, especially sparse settings, creating room for more refined approach, as we illustrate in Section 4.

---

Published as a conference paper at ICLR 2025
W1
W2
W3
W/
005
W1
f1
111
W1
U22
(W',
W1g Wg
fi
*
2
U2
f2
11/2
f2
*
J2
*
fa
33
W/
f3
f'3
*
*
W33
44
f4
f4
W14
f4
W4
55
f3
W15
86
W
Figure 1: A simple illustration of our main idea. From left to right: adjacency matrix showing the canction-variable dependency structure; the underlying bipartite graph with cycle highlighted in red; merging the variables the cycle to a subset and contracting the graph; adjacency matrix showing the new dependency structure. The process is iterated until the graph becomes acyelic.
In this work, we reveal that Pareto stationarity (PS), while necessary for Pareto optimality, is often insufficient. Even in convex settings, PS can frequently lead to sub-optimal PO solutions, especially when sparse cunction-variable
dependencies cause strict convexity to fail. To address this, propose Refined Pareto Stationarity (RPS), which leverages sparsity to identify a valid partition of variables and refines PS with respect this partition. We prove that RPS is (strictly) sandwiched between PS and Pareto optimality (PO), making it a more useful and practical goal. Additionally, under partial strict convexity, we prove RPS reduces exactly Pareto optimality, whereas the widely-used PS does not. These advantages are illustrated through intuitive examples and validated experimentally.
Since RPS is defined with respect refined partition, propose efficient partitioning procedure (REFINED PARTITION) to automatically discover, if needed, the correct refined partition of variables, based on an input adjacency matrix encoding iunction-variable dependencies. Figure illustrates our main idea through simple example. More importantly, our results enable practitioners to enhance existing gradient-bar based descent algorithms for MOO by incorporating this partitioning routine and the refined stationary condition RPS. Specifically, we introduce Multiple Gradient Descent Algorithm with Refined Partition (RP-MGDA) to exploit these advances and we formally prove its convergence.
We summarize our contributions below, with further context provided in the next section:
We present illustrative examples to reveal some limitations of Pareto stationarity, and motivate the need for valid partitioning variables when function-variabl dependency sparse.
We propose RPS, novel solution concept that refines Pareto stationarity, together with an efficient partitioning procedure REFINED REFINED_ PARTITION to automatically discover the refined partition.
We introduce RP-MGDA, an example of enhancing gradient-base based descent algorithms in MOO by incorporating refined partitioning. We establish the convergence and complexity of RP-MGDA.
We validate the effectiveness of our approach through experiments on synthetic and benchmark datasets, showcasing its application to ML scenarios with diverse dependency structures.
Our code is available at https: /ttptttttttt//tg////////t com cwm/watml http:/atallllm..ao.././.o...t.aa /RP -RRMADDA..
2 RELATED WORKS
Multi-objective optimization (MOO) and Pareto solution have been extensively studied, with tradi- tional approaches such as evolutionary algorithms (Deb et al., 2002). However, these techniques face challenges when applied to modern machine learning problems, which are often better addressed by gradient-based methods. Consequently, in this work we focus on gradient-based MOO.
Gradient-based MOO. Gradient-based MOO involves optimizing multiple objectives using gradient information. A foundational algorithm this regard MGDA (Mukai, 1980; Fliege and Svaiter, 2000; Désidéri, 2012), which computes common descent direction for all objectives by solving for the minimum-noot -nom vector in the convex hull of gradients. Fliege et al. (2019) offered a detailed convergence analysis of MGDA, while subsequent works have also extended classical single-objective
2

---

Published as a conference paper at ICLR 2025
methods to the multi-objective setting, including Newton's method (Fliege et al., 2009), (accelerated) proximal gradient (Tanabe et al., 2019; Tanabe et al., 2023), conditional gradient (Assunção et al., 2021), and subgradient method (O. Montonen and Mäkelä, 2018), among others. Another important line of research focuses on stochastic variants of MGDA, e.g. Mercier et al. (2018), due to their practical relevance in machine learning. particularly for mini-batch training of deep neural networks. Liu and Vicente (2021) introduced SMG as direct stochastic counterpart of MGDA, albeit with biased estimate of the common descent direction. Subsequent works of Zhou al. (2022) and Fernando et al. (2023) track historical information to reduce bias, while Chen et al. (2023) and Xiao al. (2023) propose unbiased estimate of the update direction through double sampling.
MOO in Multi-task Learning (MTL). MTL aims to train a common model that can solve multiple, potentially related tasks. Sener and Koltun (2018) first framed MTL. as a multi-objective optimization problem and addressed it using MGDA. Since then, numerous works in MTI. have approached this problem within the general MOO framework, treating task losses as objectives and proposing novel gradient aggregation schemes to mitigate task conflicts while addressing various aspects of MTL (e.g., Lin et al., 2019). PCGrad (Yu et al., 2020) projects each gradient onto the normal plane of other conflicting gradients and aggregates them. CAGrad (Liu et al., 2021a) balances minimizing the average task loss and improving the worst- porss-per objective by constraining the search region for the common direction in MGDA. Nash-MTL (Navon al., 2022) formulates MTL as a bargaining game to weigh the gradients. I-MTI. (Liu et al., 2021b) separately searches for the magnitude and direction of the common gradient. FairGrad (Ban and Ji, 2024) proposes new gradient aggregation scheme to ensure a-fairness in MTL.
MOO in Fair machine learning (FML). FML is inherently a multi-objective problem, due the trade-off between utility and various notions of fairness that need not be compatible with each other (Kleinberg et al., 2017). A common strategy in FML is to linearly combine the multiple objectives through scalar weights (Kamishima et al., 201 1), corresponding to the well-known scalarization technique MOO, while later work, such as Padh et al. (2021), applies MGDA to handle these competing objectives more directly.
The works mentioned above either 1) adopt the general MOO formulation that treats all learnable parameters as single variable E RR thereby disregarding any underlying function-variable structure, or 2) are confined to the MTL setting presented in Sener and Koltun (2018), whose variable partition scheme can be viewed
special case of our more general framework. To our best knowledge, our work is the first to systematically investigate and refine Pareto stationary solutions in gradient-based MOO, by taking into account the function-vvriable structure. Our results complementary to the above approaches and potentially integrable with many of them.
PRELIMINARIES
In this section, we briefly review the concepts of Pareto optimality and Pareto stationarity in multi- objective optimization. We then introduce the widely used MGDA method.
3.1 OULTI-OBJECTIVE MINIMIZATION (MOO)
In mathematical terms, Multi-Objective Minimization (MOO) problem can be written as min f f(w), where f(w): == (f) fe(w),...,,
and the minimum is defined w.r.t. the partial ordering²
f(w) < f(z) > Vi = 1,...,... m, fi(w) S f((z). Unlike single objective optimization, with multiple objectives is possible that
(2)
f(w) z f(z) and f(z) 1 f(w),
in which case we say w and z are not comparable. As a result, there is usually a set of solutions that are all optimal (a.ka. Pareto Optimal) for a given MOO problem, whose objective values form the Pareto front.
We focus on minimization in this work, while maximization can be treated similarly. We remind that algehraic operations such as S and +, when applied to a vector with another vector or sealar, are always performed component-wise.
3

---

Published as a conference paper at ICLR 2025
3.2 PARETO OPTIMALITY AND PARETO STATIONARITY
Definition (Pareto Optimality), We call w. a Pareto optimal solution of (1) if its objective value f(w.) minimum element w.r.t the partial ordering in (2); equivalently,
Vw, f(w) S f(w.) = f(w) = f(w.).
In other words, is not possible improve any component objective in f(w.) without compromising some other objective.
Definition (Weakly Pareto Optimality). We call w. weakly Pareto optimal solution if there does not exist any w such that f(w) < f(w.), ) i.e., it is not possible to improve all component objectives in f(w.) simultaneously.
Clearly, any Pareto optimal solution also weakly Pareto optimal but the converse may not hold.
Next, we recall the concept of Pareto Sationarity (also referred to as Pareto Criticality), which is the first order necessary condition for Pareto optimality.
Definition 3 (Pareto Stationarity). We call w. Pareto stationary iff
conv (V Si (w.).... ... S (w-)]- L.e. there exists some X 2 0 such that Σ; A; = 1 and Σ, X. fiVW(((")) 0.
(5)
The relevance of Pareto stationarity is captured in the following lemma:
Lemma 1 (e.g., Mukai, 1980, Theorem 1). Any Pareto optimal solution is Pareto stationary. Con- versely, all functions are convex (resp., strictly convex), then any Pareto stationary solution is weakly Pareto optimal (resp., Pareto optimal).
3.3 MULTIPLE GRADIENT DESCENT ALGORITHM (MGDA)
MGDA has been independently proposed by Mukai (1980) and Fliege and Svaiter (2000) and Désidéri (2012) as a gradient-based method to find Pareto stationary solutions of an MOO problem. It has gained notable attention in machine learning in recent years, largely because of its gradient-based nature, in contrast to traditional MOO techniques. Compared with the scalarization technique (i.e., linearly combining different objectives), MGDA removes the need to pre-determine any weight vector. More importantly, MGDA is guaranteed to improve all objectives of any starting solution while scalarization cannot (Mukai, 1980).
In each iteration, MGDA seeks new solution that minimizes the maximum change among all objectives, i.e.,
W 1+1 argmin max A T(((w) f(w")), dEA
where A is the standard simplex. Next, upper bound f(w) by the usual quadratic approximation:
min max A A (w")(w w') 2m ||w-ww w'12
(7)
where Jr = fI.1.... fmm] ] Rd is the Jacobian and n > 0 is the step size. This approximation
(7) is (strongly) convex w (even for nonconvex f' and concave in X, and hence strong duality holds. Swapping min with max in (7) and setting the derivative w.r.t. w to O, we deduce the following "minimum-norm" direction:
d' Jr(w")Xf, where X argmin |Je(w")A|2.
(8)
Aea
MGDA then performs the update along the direction d
++1 w' rjd".
Common stopping criteria include ||d'] < tol for some tolerance tol or by capping at a maximum number of iterations.
When the step size is sufficiently small (so that (7) is indeed an upper bound on (6)). the MGDA update (9) simultaneously decreases all objectives (seen easily by the feasible choice w W, in (7)). It is clear that the fixed points of MGDA are exactly Pareto stationary solutions, In fact, Fliege et al. (2019) proved that the minimum norm ||d']| converges to 0 at rate O(1/Vt,, matching the well-known result in single objective optimization.
4

---

Published as a conference paper at ICLR 2025
Wip W1
101 U2
f
f
f2
J2
f2
*
f2
fg
*
f3
Figure 2: Illustration of Example and Example 2. Left: conction-variablle dependency structure of Example There is no cycle the underlying bipartite graph so our method partitions each variable into its own block. Right: function-variabl dependency structure of Example 2. There is a cycle (highlighted red) in the underlying bipartite graph so our method merges both variables into single block. In both examples, MGDA treats all variables as single block.
4 ILLUSTRATIVE EXAMPLES
We construct two examples that illustrate the various definitions above and reveal some subtle issues about Pareto stationarity and the (coordinate-wist MGDA update.
Example 1. Let fi(w) = w + w/. fa(w) = w + w/ and fa(w) = w + w Clearly, all component functions are convex. There is a unique Pareto optimal solution = (0, 0, O, 0)0. but
there are infinitely many Pareto stationary (in fact, weakly Pareto optimal) solutions:
{ O, w, 2), (0, w. 0, 2). (0, w, 2, 0) w, E R..
(10)
is clear the MGDA update (8)-19) could get trapped at any of the Pareto stationary solutions. However, if we update the variables separately, the coordinate-wise MGDA converges to the unique Pareto optimal solution. See Figure 2 for pictorial illustration.
We note that Example does not contradict Lemma 1, since of the component functions is strictly convex. In general, strict convexity, or even convexity, is rarely satisfied in deep learning.
It is then tempting to always partition the variables and update them separately using MGDA (i.e., coordinate- MGDA). However, the following example shows this idea may also lead us astray.
Example 2. Let fi(w) (wi w2)² + w and f2(w) (w) w2)² + wzz. Clearly, both functions are strictly convex. There is unique Pareto stationary (and hence Pareto optimal) solution w. (0, 0). However, if we apply MGDA to each variable separately, it may converge to any point on the diagonal {ww, w): w E R]. On the other hand, the vanilla MGDA (treating both variables as a whole) converges to the unique Pureto stationary solution. See Figure for pictorial illustration.
In the next section, by leveraging on the (sparse) function-variable dependency structure, we prove that it is possible identify valid partition of variables and define refined Pareto stationary solutions that are sandwiched by Pareto optimal solutions and Pareto stationary solutions.
5 REFINED PARETO STATIONARY SOLUTIONS
Motivated by the afforementooeed examples, we now consider partitioning the variables in the MOO problem (1). Let P (Pı,... .P..... Pk) be partition of [d] == (1,...,0 d). For subset P of variables, we use p to denote the set of functions f. that depend on some variable in P.
Definition (Generalized Pareto Stationarity). We call w. Pareto stationary w.rl. the partition P iff
0 E
II conv (Vwr, p. (w.)) (the Cartesian product), j=1
(11)
i.e., for all E [k], there exists X E A such that E, XV fi(w") and X = 0 if f: does not depend on the variables in Pz-
When P = [d] is the trivial partition, our definition reduces to Pareto stationarity Definition 3. The following lemma slightly generalizes direction of Lemma 1.
5

---

Published as a conference paper at ICLR 2025
Lemma 2. Any Pareto optimal solution is Pareto stationary w.r.t. any partition.
(All proofs can be found Appendix A.) However, the converse part Lemma under (strict) convexity is harder to extend: we need to find the right partition first. Indeed, Example 2 already showed Pareto stationarity w.r.t the finest partition is not equal Pareto optimality, or put slightly differently, Pareto stationary w.r.t. arbitrary finer partition does not necessarily imply Pareto stationary w.r.t. a courser partition'.
Consider the adjacency matrix A E {0, 1jmed of bipartite graph, with
Av [
if ft depends on wy
(12)
0,
otherwise
Our next goal is to find the (finest) partition P of variables (i.e., columns of A) that Pareto stationary w.r.t P is also Pareto stationary (w.r.t. the trivial partition). This is particularly useful when the dependency matrix A is sparse, since it enables us largely reduce the of Pareto stationary solutions (without missing any Pareto optimal ones); see Example 1.
The main idea is find cycles in the underlying bipartite graph, merge and contract the resulting variables, and repeat until the graph becomes acyclic; see Figure I for an illustration and Appendix A.J for pseudo-code. We recall from Cormen et al. (2009, Exercise 22.4-3, p. 615) that detecting a cycle in an undirected graph using fepth-first search costs Omm + d) (the number of nodes) for our bipartite graph. Since merging the variables
cycle reduces the graph size by at least 1, the process can repeat at most (dd) times. Therefore, the entire process, which we denote REFINED_PARTTI PARTITION (A), costs (d(mm + d)) to output a partition P == (Pi,..., Pa) of the variables.
We formally justify the above partition procedure in: Theorem 1. Let P REFINED PARTITION(A) (A) where A is desined in (12). Then, any w. that is Pareto stationary w.t.. P, which we call refined Pareto stationary from now, is Pareto stationary.
We are finally ready to provide converse of Lemma 2, under (partial) strict convexity.
BEFINED_PARTITION Theorem Let P =PP..... P be returned by REFINED PARTITION. Suppose each fi is strictly convex in Wi, where I; C IP is the set of blocks of variables that ft depends on. Then, any refined Pureto stationary solution (w.rt. P) is Pureto optimal.
To summarize, refined Pareto stationarity (based on our partition procedure) is sandwiched be- tween Pareto optimality and Pareto stationarity; Figure 3 illustrates the relationships between these concepts. In particular, we have identi- fied a valid partition to sharpen Lemma in its full extent. Importantly, applying our refined Pareto stationarity to Example and Example successfully identifies the unique Pareto opti- mal solution while climinating infinitely many spurious Pareto stationary solutions.
PO
RPS
Figure 3: Euler diagram for Pareto Optimal (PO), Refined Pareto Stationary (RPS) and Pareto Sta- tionary (PS).
6 IMPROVING EXISTING ALGORITHMS WITH THE REFINED PARTITION
The refined Pareto stationarity introduced in the previous section is a solution concept. Broadly, be used enhance existing gradient-based descent algorithms for MOO. Indeed, we can simply cycle through or randomly pick the blocks of variables identified by REFINED. _ARTTPPPRRNNNNN and update each block with chosen gradient-based descent algorithm turn. The resulting algorithm is guaranteed to be descending, i.e., it improves all objectives in each step.
Interestingly, for certain MOO algorithms we can even afford update all blocks sinultaneously. We demonstrate this possibility and its practical value by modifying and analyzing the MGDA algorithm from Section 3.3, enabling which we call RP-MGDA, is summarized in Algorithm 1. The algorithm again terminates when |||||2 < tol, or when a maximum number iterations achieved.
converge to a refined Pareto stationary solution. The full algorithm,
'The subtlety lies on the requirement that each X Lee. cannot set any of them

---

Published as a conference paper at ICLR 2025
Algorithm 1: Multiple Gradient Descent Algorithm with Refined Partition (RP-MGDA)
Input: vvriibblee dependency structure A, functions f, initializer w E R learning rate (Pi....: : REFINED REFINEDDPARTITIOON PARTITION(A) // partition variables based on
for t 1,2, do
parfor j = 1, 1,2,.... ...,..,,, do
// in parallel // compute gradients // solve the dual subproblem // minimum-norm rirction in Pj // update
J (w) - VwF, f
A + argmin [w)]22
d'p; + (w)
WPy WP; 73 d
Output: final weights w
Following Fliege et al. (2019) we prove that the direction d in RP-MGDA (Algorithm 1) converges to the rate O(1/Vt,, and hence matching the usual result for single objective optimization.
Theorem 3. Suppose the functions fü are bounded from below and Lipschitz smooth with constant
Li. Set flj = < min; I. Then, minigesT
||d'|
Combining Theorem I and Theorem 3 we immediately have the following result: Corollary 1. Assuming RP-MGDA converges, then it converges to a Pareto stationary solution at the rate O(1/Vl).
A few remarks regarding RP-MGDA are in order: 1) When the sublevel set {w f(w) < f(w')] is compact, RP-MGDA admits a limit point that is refined Pareto stationary and hence Pareto stationary, thanks to its descending property. 2) In practice we do not need to know the Lipschitz constants L;: standard line search procedure on to test the quadratic upper bound (7) suffices to achieve the same convergence rate. 3) Theorem and hence Corollary continue to hold if we replace the partition P with any coarser partition (such as the trivial partition [d). Thus, our results strictly generalize those about MGDA (e.g., Fliege et al., 2019).
Complexity. We emphasize the inner loop of Algorithm is executed in parallel, as they correspond to updating different blocks of w simultaneously. We have analyzed the complexity of the subroutine REFINED PARTITION avoided if one knows the domain application well, Barring the one-time overhead in line I, Algorithm is theoretically cheaper than the vanilla MGDA, since the most costly step in line (solving the dual subproblem) often has superlinear dependence on m (the number of objectives) and hence dividing it into blocks of smaller sizes reduces the runtime.
the previous section, and we note that this one-time cost can often be
experiments in Section 7 for examples.
7 EXPERIMENTS
In this section, we present experiments comparing RP-MGDA and MGDA across both synthetic examples and realistic benchmark datasets. These experiments explore varying variable dependency structures and convexity assumptions, demonstrating RP-MGDA's effectiveness and versatility. More experimental details and discussions can be found in Appendix B.
7.1 SYNTHETIC EXAMPLES
We examine two settings. First, quadratic MOO problems with randomly generated adjacency matrices, focusing on the behaviour of REFINED, PARTITION and the effectiveness of RP-MGDA. Second, in Appendix B.I, we consider two-objective convex problem, where we visualize and compare solution fronts, observing how often MGDA converges to sub-optimal PS solutions.
Randomly generated sparse adjacency matrix. We randomly generate x d adjacency matrices with varying degrees of sparsity to set up the function-variabl dependency structures of quadratic MOO problems with objectives and d input variables. The sparsity of dencies is controlled by 'density' parameter, which determines the percentage of non-zere entries in the adjacency matrix. We use proposed
depen-
procedure automatically

---

Published as a conference paper at ICLR 2025
RPMMCDA vs. MGDA: Otecttve-uise Performance
Effect Sparsity Variable Merging
Log Scale Offfrrenee
Oljective Ind0x
Density (96)
Figure 4: Experiments on randomly generated sparse adjacency matrices. Left: [20 x 100 matrix]. The bar chart compares the solution from MGDA with that post-processed by RP-MGDA. Red bars indicate the magnitude by which RP-MGDA outperforms MGDA in objective value, while green bars (if any) indicate the opposite. Right: [100 100 matrices]. The impact adjacency matrix density variable merging in REFINED. PARTITION, where y-axis shows the final number of variable blocks returned. A value indicates all variables are merged into a single block, and a value of 100 (represented 10 the square root scale) indicates that all variables are fully separated.
Wg
W
W2
W3
W4
W1
W2
W3
W1
W2
W3
fi
*
*
fi
f1
*
f2
*
*
f2
*
*
f2
*
*
f3
W
fs
f4
f4
Figure 5: Different function-variable dependency structures for experiments benchmark datasets.
Left: Personalized federated learning; Middle: Hierarchical classification; Right: Multi-objective learning with partial information.
generate refined partitions, especially for larger adjacency matrices (e.g. 100 100) where manual partitioning becomes cumbersome. Details of the setup be found in Appendix B.2.
Results. From Figure 4 (Left) we observe that by post post-processing the outputs of MGDA, i.e., using them to initialize RP-MGDA, can improve the solutions Pareto dominate the original ones. Conversely, we point out that MGDA cannot improve the stationary solutions of RP-MGDA, due to Theorem 1. In the demonstration with 100 X 100 matrix (Figure 4, Right), note that the number of final blocks returned by REHNND,, PARTITION decreases as the density increases, starting at 1.5%, where all variables separated, and eventually merging all variables into single block when the density reaches 7%. We also empirically verified Theorem in Appendix B.2.
7.2 MI. BENCHMARK DATASETS
We examine three problems with different funetion-variable dependency structures derived from real-world application scenarios. These examples also serve as 'proof of concept' for applying refined partitioning realistic ML problems. The structures and their corresponding refined partitions are illustrated in Figure 5.
7.2.
PERSONALIZED FEDERATED LEARNING ('MTL' STRUCTURE)
Setup. We consider a personalized federated learning setting with m = 4 clients, each holding distinct non-i.i.d. data D, sampled from the training dataset (MNIST/CIFAR--O)) The objectives fi are defined as empirical cross-entropy losses over the clients' data distributions. As in standard federated learning, we have shared global model with learnable parameters wo- To handle data heterogeneity and enable personalization, instead of directly feeding inputs (c.g., images) into the global model Wo, each client has local personalized network, parameterized by w,, which extracts
8

---

Published as a conference paper at ICLR 2025
MNIST
CIFAR10
15
A8
1.0
6.5
02
4
MGDA
4
RPMGDA
Figure 6: Radar graph of final cross-entropy losses Si in the personalized federated learning setting, using MGDA and RP-MGDA respectively. Lower is better.
client-specific representations. These representations are then forwarded to the global model for prediction (e.g.. Liang et al., 2020). Formally, f. (Wu, w.) = Ex~D; [e(NN(NN(x, w,); wo))], thus having the dependency structure illustrated in Figure (Left), which is also commonly seen in multi-task learning (MTL), see e.g., Sener and Koltun (2018).
Refined Partition. For this 'MTL' dependency structure, the optimal refined partition is {[wo), [Wa].-.. ..... [W.]}. Consequently, at each iteration, RP-MGDA updates Wo by descending along the minimum- direction, while w; (for E [m)] updated with gradient descent simulta- neously. This partitioning (a) simplifies the dual sub-problem by reducing its dimensionality and (b) allows for more flexible updates to the personalized networks.
Results. As shown in Figure 6 and Appendix B.3.2, we observe that RP-MGDA converges faster and reaches better solutions than MGDA, particularly for f2, fa and fs. while for f1. the performances similar. Further details are provided in Appendix B.3.
7.2.2 HIERARCHICAL CLASSIFICATION ('LADDER' STRUCTURE)
Setup. We consider multi-objective hierarchical classification problem with m 3 levels of objectives that predict image categories, from coarse to fine labels, on the CIFAR-10 dataset, using a network structure similar Branch-CNN (Zhu and Bain, 2017). Here, WT, W2 and W3 represent the network weights of feature extraction layers 1, 2 and 3, respectively. The three objectives, f1, fz and fa. are all cross-entropy losses but defined for different prediction tasks. The first task is binary classification, categorizing images 'living' or 'non-living,' using only the representations from feature extraction layer 1, and thus depending solely on w1. The second task classifies images into four categories: 'ground vehicle," 'non-ground vehicle," 'land animal,' representations from layers and 2, and thus depending on W and W2. The third task classifies images into the original CIFAR-10 categories, using representations from all three layers, and thus depending on WT, W2, and W3. This hierarchical structure allows for progressively more complex predictions as we move from coarse to fine labels.
'non-land animal,' using
Refined Partition. The corresponding dependency structure in Figure 5 (Middle) features an optimal refindd partition of ((w1 w2). (w3)). where RP-MGDA optimizes Wy using gradient descent and the block [w1 w2} using MGDA. This partitioning should be advantageous for Objective 3, as it allows for more flexible updates to W3 compared to MGDA.
Results. Indeed, we observe that the training loss curves for Objectives and 2 are nearly indis- tinguishable; however, RP-MGDA demonstrates faster and better convergence for Objective as illustrated in Figure
After 'branching out,' an additional linear classification layer is used for the final prediction, which can either be fixed or updated separately. We omit these 'off-ramps' from the discussion, they do not affect the dependency structure of the feature extraction layers, which the focus here.

---

Published as a conference paper at ICLR 2025
Binary classifictioo (Objective
d-da dissification (Objective
cascificatioo (Oojoctive
MGDA RPMGDA
MGDA RPMGDA
MGDDA
0.5
175
RPMGDA
0.4
1:2
0.3-
0.2
0.4
0.15
Eoochs
Epachs
Epochs
Figure 7: Loss curves of MGDA and RP-MGDA for the three objectives in hierarchical classification.
7.2.3 MULTI-OBIECTIVE LEARNING WITH PARTIAL INFORMATION ('CHAIN' STRUCTURE)
Setup. We simulate a scenario inspired by vertical federated learning (Liu et al., 2024) where each party holds different feature sets for the same instances, akin multiple institutions possessing various attributes for the same users. In particular, we explore the setting where each party only has access to consecutive variables, e.g., a company in supply chain having only adjacent upstream and downstream data. In this context, clients with heterogeneous data collaborate to learn stronger model without directly sharing sensitive user data. Specifically, we consider an m 4-objective learning problem on the California housing dataset (Pace and Barry, 1997), where we employ linear model to predict the median house value. The original features are grouped into sets", each associated with linear regression weights W1, W2, W3. The objectives S; represent the mean-squared error (MSE) for different parties, all trained on the same dataset but with each objective depending on different subsets of features, as illustrated in Figure 5 (Right).
Refined Partition. For this 'chain" dependency structure, the optimal refined partition is [w1), [w2), {wy]), allowing RP-MGDA apply block-wise MGDA to W1, Wa and Wa sep- arately. This results in simpler dual aub-problems and improved convergence.
Results. As shown in Figure 8, RP-MGDA demonstrates greater stability and lower average losses across the 20 trials. We also observe that the stationary solutions of MGDA can be improved by post-processing with RP-MGDA, in 18 out of 20 trials. Additionally, the conditions of Theorem 2 are met in this setup, ensuring that RP-MGDA achieves Pareto optimality.
MCDA
MGDA RPSEDA
MCDA
MIDA
RAVODA
RPMCD4
RPMODA
300
MISE
05
Blerston
Beertion
Iteration
Iteration
Figure 8: We calculate the mean and standard deviation of the 4 losses across 20 ramdom trials (dif- ferent seeds) for both MGDA and RP-MGDA, and plot the means, with shaded regions representing the standard deviation.
CONCLUSION AND DISCUSSION
In this work, we introduced Refined Pareto Stationarity (RPS) with an efficient partitioning procedure (REFINED PAPT_PTARROTT to address limitations of Pareto stationarity in multi-objective optimization (MOO). We proposed RP-MGDA a novel MOO algorithm based on refined partitioning that con- verges to RPS, supported by both theoretical and empirical justification. Future work may explore applying our idea to other MOO algorithms and demonstrate the superior performance on other real problems with (sparse) dependency structures.
Details on feature grouping are provided in Appendix B.5.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
We thank the reviewers and the area chair for their constructive comments that have improved the presentation of this work. Zeou Hu would like to thank Dihong Jiang and Haoye Lu for helpful discussions. YY gratefully acknowledges CIFAR and NSERC for funding support.
REFERENCES
Albuquerque, I., J. Monteiro, T. Doan, B. Considine, T. Falk, and I. Mitliagkas (2019). "Multi- objective training of Generative Adversarial Networks with multiple discriminators". In: Proceed- ings of the 36th International Conference on Machine Learning.
Assunção, P., P. P. Ferreira, and L. Prudente (2021). "Conditional gradient method for multiobjective optimization". Computational Optimization and Applications, vol. 78, no. 3, pp. 741-768.
Ban, H. and K. (2024). "Fair Resource Allocation in Multi-Tast Learning". In: Proceedings of the st International Conference Machine Learning, pp. 2715-2731.
Chen, L., H. Fernando, Y. Ying, and T. Chen (2023). Tha Trade-Off in Multi-Object Objective Learn- ing: Optimization, Generalization and Condiic--vvidancee" In: Advances in Neural Information Processing Systems, pp. 70045-70093.
Cormen, H., C. E. Leiserson, R. L. Rivest, and C. Stein (2009). "Introduction to Algorithms". 3rd. The MIT Press.
Deb, K., A. Pratap, S. Agarwal, and T. Meyarivan (2002). "A fast and elitist multiobjective genetic algorithm: NSGA-II", IEEE Transactions on Evolutionary Computation, vol. no. pp. 182-197.
Désidéri, J.-A. (2012). "Multiple gradient descent algorithm (MGDA) for multiobjective optimiza- tion". Comptes Rendus Mathematique, vol. 350, no. 5, pp. 313-318.
Fernando, H. D., H. Shen, M. Liu, S. Chaudhury, K. Murugesan, and T. Chen (2023). "Mitigating Gradient Bias Multi-objective Learning: A Provably Convergent Approach", In: International Conference Learning Representations.
Fliege, J., L. G. Drummond, and B. F. Svaiter (2009). "Newton's method for multiobjective optimiza- tion". SIAM Journal on Optimization, vol. 20, no. pp. 602-626.
Fliege. J. and B. F. Svaiter (2000). "Steepest descent methods for multicriteria optimization". Mathe- matical Methods of Operations Research, vol. 51, no. pp. 479-49444
Fliege, J., A. F. Vaz, and L. N. Vicente (2019). "Complexity of gradient descent for multiobjective optimization". Optimization Methods and Software, vol. 34, no. 5, pp. 949-959.
Hu, Z., K. Shaloudegi, G. Zhang, and Y. Yu (2022). "Federated learning meets multi-objective optimization". IEEE Transactions on Network Science and Engineering, vol. 9, no. 4, pp. 2039- 2051.
Kamishima, T. S. Akaho, and J. Sakuma (2011). "Fairness-aware Learning through Regularization Approach". In: IEEE 11th International Conference on Data Mining Workshops, pp. 643-650.
Kleinberg, J., S. Mullainathan, and M. Raghavan (2017). "Inherent trade-offs in the fair determination of risk scores". In: Innovations Theoretical Computer Science (ITCS), 43:1-43:23.
Liang, P. P., Liu, L. Ziyin, N. B. Allen, R. Auerbach, D. Brent, R. Salakhutdinov, and L.-P. Morency (2020). "Think locally, act globally: Federated learning with local and global representa- tions". In: NeurlPS Workshop on Federated Learning.
Lin, X., H.-L. Zhen, Z. Li, Q.F. Zhang, and S. Kwong (2019). "Pareto Multi-Task Learning", In: Advances in Neural Information Processing Systems.
11

---

Published as a conference paper at ICLR 2025
Liu, B., X. Liu, X. Jin, P. Stone, and Q. Liu (2021a). "Conflict-averse gradient descent for multi-task learning". In: Advances in Neural Information Processing Systems, pp. 18878-18899
Liu, L., Y. Li, Z. Kuang, J.-H. Xue, Y. Chen, W. Yang, Q. Liao, and W. Zhang (2021b). "Towards Impartial Multi-task Learning". In: International Conference on Learning Representations.
Liu, S. and L. N. Vicente (2021). "The stochastic multi-gradien algorithm for multi-objective optimization and its application to supervised machine learning". Annals of Operations Research, vol. 339, pp. 1119-1148.
Liu, Y., Y. Kang, T. Zou, Y. Pu, Y. He, X. Ye, Y. Ouyang, Y.-Q. Zhang, and Q. Yang (2024). "Vertical federated learning: Concepts, advances, and challenges". IEEE Transactions on Knowledge and Data Engineering, vol. 36, no. 7, pp. 3615-3634.
McMahan, B., E. Moore, D. Ramage, S. Hampson, and B. A. Arcas (2017). "Communication- Efficient Learning of Deep Networks from Decentralized Data". In: Proceedings of the 20th International Conference on Artificial Intelligence and Statisties (AISTATS), pp. 2773-188..
Mercier, Q., Poirion, and J.-A. Désidéri (2018). "A stochastic multiple gradient descent algorithm". European Journal of Operational Research, vol. 271, no. 3, pp. 808-817 -17.
Mukai, H. (1980). "Algorithms for multicriterion optimization". IEEE Transactions on Automatic Control, vol. 25, no. pp. 177-186.
Navon, A., A. Shamsian, I. Achituve, H. Maron, K. Kawaguchi, G. Chechik, and E. Fetaya (2022). "Multi-Tare Learning Bargaining Game". In: Proceedings the 39th International Conference on Machine Learning.
Nesterov, Y. (2018). "Lectures on Convex Optimization". 2nd. Springer.
O. Montonen, N. K. and M. M. Mäkelä (2018). "Multiple subgradient descent bundle method for convex nonsmooth multiobjective optimization". Optimization, vol. 67, no. 1, pp. 139-158.
Pace, R. K. and R. Barry (1997). "California Housing Dataset". Accessed through scikit-learn library.
Padh, K., D. Antognini, E. Lejal-Glaude, B. Faltings, and C. Musat (2021). "Addressing faimeess in classification with a model- aggossic multi-objective algorithm". In: Uncertainty Artificial Intelligence, pp. 600-609.
Sener, and V. Koltun (2018). "Multi-Tas Learning as Multi-Ohjective Optimization". In: Advances in Neural Information Processing Systems.
Tanabe, H., E. H. Fukuda, and N. Yamashita (2019). "Proximal gradient methods for multiobjective optimization and their applications". Computational Optimization and Applications, vol. 72, pp. 339-361.
(2023). "An accelerated proximal gradient method for multiobjective optimization". Computational Optimization and Applications, vol. 86, pp. 421 425-455.
Xiao, P., H. Ban, and K. Ji (2023). "Direction-oriented Multi-objective Learning: Simple and Provable Stochastic Algorithms". In: Advances in Neural Information Processing Systems. pp. 4509-4533.
Yu, T., S. Kumar, A. Gupta, S. Levine, K. Hausman, and C. Finn (2020). "Gradient surgery for multi-task learning". In: Advances in Neural Information Processing Systems, pp. 5824-5836.
Zhou, S., W. Zhang, J. Jiang, W. Zhong, J. GU, and W. Zhu (2022). "On the Convergence of Stochas- tic Multi-Objective Gradient Manipulation and Beyond". In: Advances in Neural Information Processing Systems.
Zhu, X. and M. Bain (2017). "B-CNN: branch convolutional neural network for hierarchical classifi- cation".
12

---

Published as a conference paper at ICLR 2025
A PROOFS AND PSEUDO-CODE OMITTED FROM THE MAIN TEXT
Lemma 2. Any Pareto optimal solution is Pareto stationary w.r.t. any partition.
Proof. Let w be Pareto optimal w.r.t. f. Consider the function g(z) == f (z, Wp...... W Clearly, W is Pareto optimal w.r.t. g. Applying Lemma 1 we know 0 conv Vg(wA)) conv V wp, ff (w")}. Iterating the argument proves (11).
Theorem 1. Let P = REFINED PARTITION(A) where A is defined in (12). Then, any w. that is Pareto stationary w.E.t P, which we call refined Pareto stationary from now, is Pareto stationary.
Proof. For each [kt] let us define
Fj = {i E [m] fi is connected to Pj in the final graph).
(13)
namely, the set of functions that the variable set Pj "sees." We claim that for all + 1,
Fg n Fil 1.
(14)
Suppose not, let + b E F3 n Fi. Then, in our final graph, fa and fo are connected to both P3 and Pt, creating a cycle 4 and hence contradicting to the fact that P3 and Pt were not merged.
Since w. Pareto stationary w.r.t. P, for each j E [A:] there exists X E A such that
Vwp, f(w.): X 0, where
X = i & Eg.
(15)
Our goal is to construct À A (independent of the index j) such that Vf(w.) A = 0, iee, w. is Pareto stationary.
W.l.o.g. we make the following assumptions:
1. The graph is connected, as we can consider each connected component separately.
2. The variable sets are rearranged according their distance to Pi (ties broken arbitrarily).
3. (positivity) X/ 0 if and only if i Fy; we will see how to reduce to this case later.
For each j E [k:), consider any n 2 j + such that there exists a (unique) in E Fy F Fn, and perform the rescaling
A" x
(16)
where we note that X, # due the positivity assumption. Importantly, rescaling (by positive number) does not affect any of the stationary conditions in (15), other than the normalization constraint 1 = 1, which we will take care of the end.
We claim that each A is rescaled at most once. Suppose not so there exist j1 < f2 < and in E Fn F, and i/z E F22 n Fn, i.e., we have the edges shown on Figure (left). Due to their appearance order, we must have
dist(P,, P1) & dist(P Pt) S dist(Pa,
(17)
Noting the edges from in to Pj and P.. and from i to P22 and P... we must have
dist (P), Pi) dist(Pp;, Pi) < dist((.... Pi):
(18)
for otherwise there will be cycle (due to back edge, see Cormen et al., 2009). We can now trace back the ancestors of P, and P/2 until we finally arrive at the same variable set P (since only P1 has 0 distance to Pi) that intersects both P3 and P (here prime denotes the final ancestor pair). But this creates a cycle (see Figure 9, right), contradiction.
Lastly, take component wise maximum to construct
A
(19)
13

---

Published as a conference paper at ICLR 2025
P
Pj
P/
32
Pj
j2
P32
P/
Pr
Ps
Figure 9: Illustration of the claim that cach X is rescaled at most once.
Clearly, + 0 so we may normalize it so that X E A. Since each X is re-scaled at most once (and
nonzero entries of different X and A intersect at most once, see (14)), for any j and X * 0, we have
X
(20)
Since (15) holds for any j (other than the normalization constraint), it follows that Vf(w.) À 0. We are left justify the positivity assumption. Consider the "adjacency" matrix
A
A
X2
A4
(21)
where we put an edge between f; and Pj if the corresponding X; value nonzero. Suppose A/ = for some E Fj. Then, for all variable subsets P,, other than P,. that can be reached by f.. we set their X' (namely entire columns in A) and Fi 0. Note that do not change X (for if we reach P, from but not through the edge {í. P3], we will have a cycle) so A remains nonzero after our operation. Moreover, the stationary conditions (15), other than the normalization constraint, are maintained. Thus, we may repeat this process until the positivity assumption holds.
The proof is complete.
We point out that REFINED PARTITION(A) A) returns unique solution (irrespective of the order of the cycles we contract). Indeed, when we merge the variables and contract the graph, any existing cycle (other than the to think of contracting a cycle as replacing it with a complete bipartite subgraph.
Remark 1.
contracting) will remain
cycle. Another way see this
Remark We note that Theorem continues hold if we replace P by any of coarser partition
Q (i.e., for any P E P there exists Q Q such that P C Q). In particular, setting Q [d] recover Pareto stationarity in Definition 3.
We will need the following elementary result: Lemma 3. If g(w, u) and hiw,, v) are both strictly convex in (w, u) and (w, v), respectively, then f(w, u, v) == g(w, + h(w, v) strictly convex in (w, u, v).
Proof. Indeed, consider (Wo, Ug, vo) * (W1, u1, v1). For any E (0, 1), denote WA = A)wo + Awi and similarly for uy and Vx. we have
g( W/ ux) < (1 A)g(wo, uo) + Ag(wi, h(wx. vx) < (1 A)h(wo, vo) + Xh(Wi, v1).
(22)
(23)
where at least one the inequalities is strict. Thus, f(wA, uy v.) < (1 A)f(Wn: Up Vo) A(W1, U1, v1).
14

---

Published as a conference paper at ICLR 2025
Theorem 2.
Let =PI..... Po) be returedd by REFINED PARTITION. Suppose each fa is strictly convex in WI, where 1, C P is the set of blocks of variables that ft depends on. Then, any refined Pareto stationary solution (W.r.. P) is Pareto optimal.
Proof. Let w be an arbitrary refined Pareto stationary solution w.I.t P. For the sake of contradiction, consider any Pareto optimal solution z that dominates w', i.e., f(z) $ f(w").
Applying Theorem we know w' is Pareto stationary, Le.,, there exists some À A such that
Σ [(") = O.
(24)
Restricting to the subset F == {i A + 0} G, we know from Lemma 3 that the function h(w) = Eier- (ef((w) is strictly convex in WI, that it depends on (where In S P). Since h(z)= & h(w"), we necessarily have
ZUI
(25)
We are now ready to reduce. We fix Wit, and remove all blocks of variables in I (and the corresponding edges in our bipartite graph). Clearly, the bipartite graph remains acyclic and Wyy,, remains to be refined Pareto stationary w.r.t the reduced problem. Iterating the argument in the previous paragraph. we deduce that z agrees with w in least one more block of variables. Since there are only & blocks in total, after at most l iterations we must have z = w", which contradicts to the assumption f(z) $ f(w"). Thus, w is Pareto optimal and the proof is complete.
Remark 3. Since Theorem I also holds for any partition Q that is coarser than P, the same is true for Theorem 2. In particular, choosing Q = [m)) refined Pareto stationarity reduces to Pureto stationarity and Theorem reduces to the well-known result in MOO (see Lemma 1).
Example 3 (Personalized federated learning). Let us give an example where Theorem strictly improves Lemma 1. Consider the personalized federated learning setting with Je(Wo, w:), i E [m]] is clear that none of the functions fa strictly convex w.r.f. (Wa: Wi...., W. Thus, Lemma I not applicable and not every Pareto stationary solution is Pareto optimal.
On the other hand, REFINED PARTITION returns P = [[Wo): [wi]...., {wo) }} and is possible for each function Is to be strictly convex w.r.t. the (blocks of) variables (Wo, w.) that it depends on. (This can also be uchieved by regularizing euch function fa.) Therefore, Theorem 2 is applicable. In fact, can apply Theorem 2 to both our Example I and Example 2 in the main text and conclude that the refined Pareto stationary solution indeed coincides with the unique Pareto optimal solution.
DERRIIEDNARTITIONN
To be more concrete, consider
Si (wo, W1, W2, w3) = 2 + w/
(26)
f2( f2(o W1, W2, Wy) (wo 1)2 + w2 2
(27)
fa(wo: W1; W2, w2, ws) (wo - 2) + wz-
(28)
We run simulations with step size n = 0.01 and 1000 iterations. With initialization w
(1.5, 1, 0,0.1,0.1), MGDA converges w 1000
(1.5, 1, with function values f(w01000
13 1 1), which is not Pareto optimal since it is dominated by f- = (2_ 2) achieved at w (1.5, 0, 0) In contrast, under the same setting, RP-MGDA converges the Pareto op-
$ 1'
timal solution w" = (1.5, 0, 0,0).
From Theorem 2, we also see how MGDA fails reach the Pareto optimal solution in this example, When MGDA converges to w 10000 = (1.5, 1, O, 0), the corresponding X; = 0 while fi wt) + which means MGDA stops even though there is a descent direction along wi.
Theorem 3. Suppose the functions f; are bounded from below and Lipschitz smooth with constant L3 Set 13 = 17 S min, 1. Then, minicesT ||d < <0 )
L
Proof. Denote
I : (j depends P,}
(29)
15

---

d' argmin max Published as a conference paper at ICLR 2025
and apply smoothness to upper bound the i-th objective as (for step size 1f Lipschitz constant of fi):
I,² L; being the
1.
1 S fi(w") + V.((ww)) -(w -w') + 1
f((w
|| w'l1?
(30)
2n
= -i(w') + Σn 11 (P,,(((')) dr, +blld?,
(31)
JEL,
S fi(w") - Σ 2 ||d l2.
(32)
jEL.
where the last inequality follows from the definition of dz.; VP,fe(w") de, 11 dr, iEF
(33)
Indeed, we note that the objective above 1-strongly convex in dr,. so setting dr, and de, d'p we obtain from e.g. Nesterov (2018, Corollary 3.2.3, p. 210):
max
Vr,J((w") dj, + + 31ld%,
+ + 1l-o-,,.1
d'p
(34)
iFF;
Rearranging and summing over we obtain:
ΣΣ Id' 122 - 2 [1f((w') f((w" [+W
(35)
Dividing both sides by we obtain:
min
Σ dd
Σ
1
(i(w") -
(36)
JEL.
t= jEA
Finally, we sum over any subset F (e.g., F = [m]) of functions that together depend on all variables:
T
T
Eii(w') -
f f((T+
ldd
- a|
(37)
YEF
t= SEl:
j=1
Dividing both sides by T we obtain:
T min ||d'
IIA(w") - f((TT)))
Σ
|
(38)
n!
YEF
Since all functions are assumed to be bounded from below, the claim is proved.
A.1 PSEUDO-CODE FOR REFINED PARTITION
In the pseudocode below, cycle C' a collection of column indices (i.e. variable indices) of the adjacency matrix A E Rmxx We can use depth-first search (DFS) or networkx for detect_cycle. The loop can continue for most iterations, with each iteration costing O(m + d).
Algorithm 2:
Input: Adjacency matrix A representing the function- dependencies (bipartite graph) Output: Refined partition P of variables Initialize P + (fw1), ), (u2),...,(wa)))
// each variable in its own group
while there exists a cycle do
C detect_cycle(A)
1/ e e.g., use networkx package or DFS // merge variables in the cycle // update the edges // contract the graph // update the partition
P + UjecPj
Veec A.j
Ac + I, A [A,a]
Po + I, P P PU(P)
return P
16

---

Published as a conference paper at ICLR 2025
B EXPERIMENT DETAILS
B. SYNTHETIC EXAMPLES
MCDA
RPMEDA
MGDA
RP-MDDA
Figure 10: Comparisons of stationary solution fronts generated by MGDA and RPMGDA. (1) and (2) for the quadratic example, (3) and (4) for the non-strictly convex example.
Two-objective toy examples. We examine two examples with the same underlying function-variable dependency structure but different convexity conditions. The quadratic one given by: [1 (w)
wi + w². /2(w) (w2 - 1)2 + (w² 1) The non-strictly convex one is: Si [i(w)
w + |w2).
fe(w) = Iu22 1 + (w's - 1)a. Initialized with a grid search over [-1, 1
s we plot the solution
fronts in terms of function values [ww), f2(w") for MGDA and RP-MGDA in Figure 10.
We observe that RP-MGDA always reaches Pareto optimal solutions regardless of initialization, while MGDA may converge to sub-optimal PS solutions (i.e., those with fi 0, > and fi > f2 = 0).6 Moreover, by post- post-processing the sub-optimal solutions MGDA with RP- MGDA,
refine these solutions and bring them to the Pareto front.
Adding regularization induce strict convexity. We have discussed in Section 4 the importance of joint strict convexity for the performance of Pareto stationary solutions, particularly as highlighted in the second part of Lemma We note that the functions in the two-objective toy example setting in Appendix B.1 are not strictly convex w.r.t. w, though they are strictly convex with respect to their dependent variables (in the quadratic case). One natural attempt is to add regularization to the objectives to induce strict (indeed strong) convexity. For the two-objective toy example setting in Appendix B.I, we regularize the objectives with L2-norm on w = (Wi, W2, W3) with different magnitudes of regularization ", and examine the stationary solution fronts generated by MGDA. /t///////
Specifically, we consider fi (w) == wi + w3 + > /// (w) = (w2 - 1)2 + (wys - 1)2 + + /
We observe in Figure 11 that bigger regularization yields solutions that further away from Pareto front; while smaller regularization gradually recover the previous (undesired) stationary solution set of MGDA (as in Figure 10), thus still having those inferior weakly Pareto solutions (i.e., those on the tails). To summarize, adding a regularization term, whether large or small, to induce strong convexity, does not alleviate the issues with MGDA, further highlighting the effectiveness of our refined partitioning for MGDA.
0.01
2.5
MGDA
2.3
MGDA
MGDA
Pareto front
Pareto front
Pareto front
2.0
1.5.
1.5-
1.0
1.0
0.0
0.0
0.2
0.2
0.4
0.6
0.0
0.2
0.4
0.00 0.25 0.50
0.75
1.25
3.50
1.75
Figure 11: Stationary solution fronts of MGDA with regularized objectives, compared to the true Pareto front (red). From left to right: regularization magnitude ? = 1,0.1 and 0.01.
For MGDA, 372/512 initializations converge sub-optimal PS solutions in the strictly convex example.
17

---

Published as a conference paper at ICLR 2025
B.2 RANDOMLY GENERATED SPARSE ADJACENCY MATRIX
Setup. The problem is formulated by first generating random sparse adjacency matrix of m x d, with density p. In detail, we do this by randomly assigning mdp (rounded integer) non-zero entries to zero m x matrix. Afterwards, we define our objectives Si = Ew,,v(t.) (wy i) E [m]] where v(ft) is the set of variables that depends on.
More results. We compare the solution of MGDA and RP-MGDA with the same random initialization Wo (see Figure 12 Left), and notice that RP-MGDA outperforms MGDA in most objectives. Although RP-MGDA is theoretically superior, their different update rules can lead to incomparable solutions, even when the solution of RP-MGDA is Pareto optimal and MGDA is not.
We track the norm |[d]] of RP-MGDA and MGDA during optimization, and observe that both converge to zero. Note that the gradient norm ||]]| of RP-MGDA is much larger than MGDA in the beginning. which is not surprising since MGDA finds the overall min-norm element. Moreover, descent direction d' with larger norm generally indicates greater improvement for each update.
RP-MGDA vs. MOON Objective-wse Performance
Gradient Norm vs. Iteration (RP-NGD4)
APMGOA
NODA
Scale offleettoot
Oc Indox
Frestion
Figure 12: Left: compare MGDA and RP-MGDA solution, with same random initialization Wo- Right: The norm of d' over time converges to zero, empirically verifying Theorem 3.
We also present x 5 toy example below, which maybe useful for readers.
Toy 5 x 5 dependency matrix. Here we consider the quadratic objectives: f. = Eu (v)
i) E (5). where v(fs) is the set of variables that f, depends on. The variable dependency structure is given in Figure 32, Appendix B.7. The refined partition for this problem is {wi, W2, [wo my wg]}. where RP-MGDA is performing (8) w.r.t. w' = (w3, W4, Ws) and gradient descent w.r. wa and w2. We observe from Figure 13 that the solutions of RP-MGDA dominate those of MGDA, although all being Pareto stationary (with corresponding convex combination coefficients plotted).
18

---

Published as a conference paper at ICLR 2025
30
MCDA BI-MGIIA
1.0
1.0
25-
RP-NGDA
0.6
compupo nin ameed
20
20
2.4
-34
IIPRGGDA
0.2
RPMGGAA MCDA
MCDIA
0.6
0
MGDA RP-MFDA
MGDA
14
15.0
RP- NR-MAAA
12-
0.5
12.5
3.6
2.8
10.5
3.6
1053
8-
7.5
5.0-
02
32
Figure 13: Comparison of MGDA and RP-MGDA solutions, with different initializations. (1) Colored lines connect the final objective values of each fi. where blue represents RP-MGDA, and orange represents MGDA. (ii) Red markers (with values on the right y-axis) are the corresponding dual coefficients X; of the solutions, showing the differences of solutions from dual perspective.
B.3 PERSONALIZED FEDERATED LEARNING (THE 'MTL' STRUCTURE)
In this section, we present detailed experiment setup and more results regarding the personalized federated learning (PFL) experiments.
B.3.1 DETAILED EXPERIMENT SETUP
Data. For the PFL setting, we conducted experiments on both MNIST and CIFAR-10 dataset. In order create non-i.i.d. dataset, we follow similar sampling procedure as in McMahan al. (2017): First we sort all data points according to their classes. Then, they are split consecutively into shards (300 shards for MNIST, 250 shards for CIFAR-1O), with 200 images per shard, each shard contains images from only one class. Each client is randomly assigned 10 different shards, totaling 2000 instances per client. The data distribution for each client varies, with each having access to different subsets of class labels. For example, client 1 data includes class labels ['0' *2" '4' '6" '7' *8" '9'J, while lacking data from class labels $1", '"'"3' and '5'.
Model. For MNIST, we use Multi-Layer Perceptrons (MLP) for both the lower personalized networks and the top global network. For CIFAR-10, 10, the lower personalized networks are Convolutional Neural Networks (CNNs), while the top global network remains MLP. Input data first passes through the lower personalized networks, and the resulting representations are then forwarded to the top global model for predictions. See Table 1 and 2 for configurations.
Misc. We adopt a warmstart procedure by first rumning RP-MGDA for 50 epochs on a given random initialization, using the resulting weights the starting point for both MGDA and RP-MGDA training. This approach helps improve stability in some cases while still ensuring a fair comparison. We also employ periodic exponential decay learning rate scheme for the CIFAR-10 experiments.
19

---

Published as a conference paper at ICLR 2025
Table I: Network architecture for PFL MNIST experiments.
Network
Input Dim Hidden Dim Output Dim
Lower Personalized MLP
img size
256
128
Top Global MLP
128
128
10
Table 2: Network architecture for PFL CIFAR-10 experiments.
Layer Type
Configuration
Activation
Lower Personalized CNN Network
Conv2D
x 32, kernel size
ReLU
BatchNorm22
32 channels
MaxPool2D
kernel size 2, stride 2
Conv2l
32 x 32, kernel size 5 ReLU
BatchNorm21
32 channels
MaxPool2D
kernel size stride 2 32 + 384
Fully Connected
ReLU
Top Global MIP Network
Fully Connected
384 -> 192
ReLU
Fully Connected
192 + 10
B.3.2
MORE RESULTS
Objective
Objective
MCDA RF-GDA
NGOM RF-G33
2.00
1.75
1.75
150
1.25
1.00
0.75
0.75
050
0.25
0.25
600
600
BC0
1000
200
400
800
1000
Objective
RMACDDA
2.00
1.75
1.50
1.0
0.75
0.50
100
600
BC0
200
1000
Epochs
Epochs
Figure 14: Personalized federated learning problem on MNIST. Comparing objectives using RP. MGDA and MGDA. Random seed 1.
20

---

Published as a conference paper at ICLR 2025
Objective
Objective
NCDA RP-NG3A
RP-MGDA
2.00
2.00
1.75
175
150
1.25
1.00
0.75
0.75
0.90
200
400
620
800
1000
200
400
620
900
1200
Objective
Objective
2.25
2:25
PP-MGDA
2.00
1.75
1.00
0.75
0.0
145AA
200
400
600
800
1000
200
400
600
800
1200
Epochs
Epochs
Figure 15: Personalized federated learning problem on MNIST. Comparing objectives using RP. MGDA and MGDA. Random seed 2.
Objective
Objective
2.00
MGDA RA-ADDA
2.50
MGD4
RKAYDAA
1.75
1.50
0.50
0.75
0.25
1000
7000
3000
400n
5000
1000
2000
3000
4000
5200
Objective
Objective
2.00
RUAADDA
2.00
1.75
1.50
1.25
3
1.00
0.75
0.50
030
0.25
0.5
1000
2000
3000
4000
1000
2000
4000
5000
Epochs
Epochs
Figure 16: Personalized federated learning problem on CIFARIO. Comparing objectives using RP-MGDA and MGDA. First random seed.
21

---

Published as a conference paper at ICLR 2025
Objective
Objective
2.00
175
MIDDA
2,00
MGDA
155
1.75
1.25
1.00
1.25
1.00
0.50
0.25
0.50
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Objective
Objective
2.00
RP MGDA
2.00
1.75
1.75
1.50
1.50
1.25
1.25
0.50
0.50
NGDA
0.25
0.25
1000
2000
3000
4000
S000
1000
2000
3000
4000
5000
Epochs
Epochs
Figure 17: Personalized federated learning problem on CIFAR1O. Comparing objectives using RP-MGDA and MGDA. Random seed 2.
B.3.3 ELU ACTIVATION
The purpose these experiments is to verify whether replacing ReLU with differentiable ELU activations yields similar results and conclusions. We observed that the performance of both RP- MGDA and MGDA remains consistent with their performance when using ReLU, with RP-MGDA still outperforming MGDA.
MNIST f
CIFAR10 f
1.
C6 0.8
B5
f
MGDA
f4
RPMGDA
Figure 18: With ELU activation. Radar graph of final cross-entropy losses fi in the personalized federated learning setting, using MGDA and RP-MGDA respectively. Lower is better.
22

---

Published as a conference paper at ICLR 2025
Objective
Objective
2.00
RP-MGDA
RP-NG3A
1.75
1.75
150-
1.25
1.00
0.75
0.50
0.25
200
400
620
800
1000
200
400
620
900
1200
Objective
Objective
2.00
MGDA
2.00
1.75
1.00
0.75
050
145AA
0.2
6AMGDA
0
200
400
600
800
1000
200
400
600
800
1200
Epochs
Epochs
Figure 19: Personalized federated learning problem on MNIST. Comparing objectives using RP. MGDA and MGDA. ELU activation.
Objective
MGDA
2.0
NGDM
1.4
MP-MDAA
1.0
RPAYDAA
1.2
1.4
1.0
1.2
0.8
0.6
0.4
0.6
0.2
0.4
1000
2000
4000
5000
100C
2000
3000
4000
5200
Objective
1.8
MSDM IA-ACAA
NCDA
1.6
RNAADA
1.50
1.2
1.0
1.00
0.6
6.4
0.50
1000
2000
4000
5000
1000
1000
5000
Epachs
Figure 20: Personalized federated learning problem on CIFAR-10. Comparing objectives using RP-MGDA and MGDA. ELU activation.
23

---

Published as a conference paper at ICLR 2025
B.3.4 STOCHASTIC GRADIENTS
We evaluate both RP-MGDA and MGDA the stochastic setting, where only stochastic gradients are available due to mini- mini-batch training. The experiments are run for 500 epochs, with each epoch corresponding to a full pass through the dataset. Mini-batch size= 200. For each epoch, we report the loss at the start of the epoch. For radar graph, we report the loss averaged across mini-batches of the last epoch.
We observe that RP-MGDA continues to outperform MGDA in performance. However, neither algorithm guarantees descent in every iteration, and the performance both methods drops slightly, potentially due to bias in the descent direction.
MNIST
CIFAR10
15
15
100
96
02
f
MGDA
4
RPMGDA
Figure 21: Stochastic gradients. Radar graph of final cross-entropy losses fi in the personalized federated learning setting, using MGDA and RP-MGDA respectively. Lower is better.
Objective
MGDA
MGDA
2.0
RF-GOA
RP M-DA
1.5-
0.5
100
700
300
400
500
700
300
400
500
Objectivve
Objectivee
R1P RM-MDA
0.5
100
20c
300
000
400
500
Epochs
Figure 22: Personalized federated learning problem on MNIST. Comparing 4 objectives using stochastic RP-MGDA and stochastic MGDA. Report loss the start of each epoch.
24

---

Published as a conference paper at ICLR 2025
Objective
Objective
MCDA RP-NGDA
2.00
MGDA
1.75
140
0.25
100
200
300
400
500
100
200
300
400
500
Objective
Objective
2.25
MGDA NGDA
RP MEDA
1.50
1.25
1.25
1.00
1.00
0.75
0.75
0.50
0.25
100
200
300
400
500
100
200
300
400
500
Epochs
Epochs
Figure 23: Personalized federated learning problem on MNIST. Comparing 4 objectives using stochastic RP-MGDA and stochastic MGDA. Report loss at the start of each epoch.
B.3.5 PCGRAD+ AND RP- PCGGAD
In this section, we further validate the effectiveness of experiments on the PCGrad+ algorithm, both with and without RP, in the PFL setting. PCGr is a looped version of the PCGrad algorithm (Yu et al., 2020), where the iterative projection and correction step (Lines 4-7 in Algorithm of (Yu et al., 2020)) is repeated until the 'surgery' gradient g." achieves a nog-nveat inner product with all other gradients. This modification ensures that PCGrad+ is common descent algorithm for all objectives even when m 3.
(RP) by conducting
For MNIST, we run 1000 epochs with 1r=0.1 for both algorithms; for CIFAR-10, we run 5000 epochs with Ir=0.05 and a step decay of 0.9 every 200 epochs for both algorithms. Other settings follow those of MGDA and RP-MGDA. We observe that RP-PCGrad+ outperforms PCGrad+.
MNIST f
CIFAR10 f
03 0.4
f
PCGrad+
f4
RP-PCGRad+
Figure 24: Radar graph of final cross-entropy losses fo in the personalized federated learning setting, using PCGrad+ and RP-PCGrade respectively. Lower is better.
25

---

Published as a conference paper at ICLR 2025
Objective
Objective
2.25
PCGrade RP-PCGRad+
225
PColldd
2.00
2.00
1.75
1.75
1.30
5 122
1.00
1.00
0.75
0.75
0.30
0.0
0.75
200
400
600
800
1000
200
400
620
900
1200
Objective
Objective
P
ICGRad+
RP #CdRdd+
2.00
RP FCORad
0
200
400
600
800
1000
200
400
600
800
1200
Epochs
Epochs
Figure 25: Personalized federated learning problem on MNIST. Comparing objectives using RP. PCGrad+ and PCGrad+.
Objestive
Objective
KcGrad
ICGluds
1.2
3p PCGRad+
RP PCGGCa
1.25
0.8
1.00
0.6
0.75
0.25
0.0
0.00
1000
5000
1000
4000
5200
Obiestive
Objective
1.4
3P #CGRad+
KCGRad+
RP PCGRad
ICGRad+
1.2
1.2
1.0
1.0
0.8
0.2
0.0
0.0
1000
2000
4000
5000
1000
4000
5000
Epochs
Figure 26: Personalized federated learning problem on CIFAR-10. Comparing objectives using RP-PCGrad+ and PCGrad+
26

---

Published as a conference paper at ICLR 2025
B.4 HIERARCHICAL CLASSIFICATION (THE 'LADDER' STRUCTURE)
In this section, we present detailed experiment setup.
Data. In addition the original 10 classes in the CIFAR-I0 dataset, we define broader categories with binary labels: I'non-living', 'living'], J. as well as mid-level categories: ['ground-vchick 'non- ground-vehicle', 'land-animal', 'non-land-animal]] These serve as coarser labels for the original classes, which include ['plane", "car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck'], ]. Consequently, each image instance in the dataset with an original label is also assigned binary label and mid-level label for the tasks of binary classification (f1) and four-class classification (/2), respectively. For instance, a 'plane' labeled as 'non-live 'non-living' 'non- ground vehicle" while 'deer' is labeled as 'living' 'land-animal We take smaller subset of the original CIFAR- 10 dataset training set.
Model. We employ CNN architecture similar in spirit to Branch-CNi (Zhu and Bain, 2017), featuring three layers for feature extraction and three 'off-ramp" linear classifiers that branch out after the first, second, and third feature extraction layers, respectively. The first task, fi, processes input through the shared feature extraction layer followed by classifier 1. The second task, /2, processes input through the shared feature extraction layers and 2, followed by classifier 2. The third task, fa. processes input through the shared feature extraction layers and 2, then through the non-shared feature extraction layer 3, and finally classifier 3. See Table 3.
Misc. We adopt a warmstart procedure similar to the previous section by first running RP-MGDA for epochs. We also employ a periodic exponential decay learning rate scheme for the experiments.
Table 3: Network architecture for hierarchical classification experiments.
Layer Type
Configuration
Activation
First Feature Extraction Layer
Conv2D
32, kernel size
ReLU
BatchNorm2D
32 channels
MaxPool2D
Kernl size 2, stride 2
Conv2l)
32 32, kernel size 5 ReLU
BatchNorm2D
32 channels
MaxPool2D
Kernl size 2, stride 2
Second Feature Extraction Layer
Fully Connected (FC)
32 x 5 x 5 + 384
ReLU
Third Feature Extraction Layer
Fully Connected (FC)
384 + 192
ReLU
First Classifier
Fully Connected (FC)
32 x 5 x 5 + 2
Second Classifier
Fully Connected (FC)
384 -
Third Classifier
Fully Connected (FC)
192 - 10
B.5 MULTII-R/ECTIVV LEARNING WITH PARTIAL. INFORMATION (THE 'CHAIN' STRUCTURE)
In this section, we present detailed experiment setup.
27

---

Published as a conference paper at ICLR 2025
Data. We conduct experiments the California housing dataset, which consists of 20,640 sam- ples from the 1990 U.S. Census, aiming to predict median house values. The dataset includes features, ['Longitude', 'Latitude', 'AveOccup', 'Population', 'MedIne', 'HouseAge', 'AveRooms', 'AveBedrms'J. We group 'Longitude" and 'Latitude" as w1; AveOOccp', "Population" and 'MedInc' W2; 'HouseAge', 'AveRooms" and 'AveBedrms' W3- To implement the function-variable dependency structure, we use feature masks on X during training.
Model. We consider linear model with 8 weights, each corresponding one of the 8 features in the dataset. We set the bias b to be the mean of Y train.
Misc. We standardize each feature to have mean and unit variance improve training.
2.0
RRMGDA
2.5
RAMGDA
1.8-
2.0
1.4
1.5
1.2
1.0%
0.5
100
200
300
400
500
100
200
400
500
lteration
Iteration
MGDA RAMGDA
MGDA
3.0
RAMGDA
2.5
2.25
2.00
2.0
1.75
1.30
1.00
0
100
200
300
400
500
0 100
200
300
400
500
lleration
Iteration
Figure We calculate the mean and standard deviation of the 4 losses across the 20 trials (different seeds) for both MGDA and RP-MGDA, and plot the means, with shaded regions representing the standard deviations. Although the solution of RP-MGDA for a single trial does not dominate MGDA's. RP-MGDA achieves lower average losses for all 4 objectives and has much smaller deviations.
B.6 JACOBI VS. GAUSS-SEIDEL UPDATE
In Section 6, we discussed the approach of cycling through the blocks of variable identified by REFINED PARTITION for updates, also known the "Gauss-Seidel" update. The main RP-MGDA algorithm presented in Algorithm I, which updates all blocks simultancously, is referred to as the 'Jacobi' update.
In this section we empirically compare the Jacobi (default) and Gauss- Seidel versions of RP-MGDA updates, using refined partition of blocks for the PFL setting on both the MNIST and CIFAR-10 10 dataset. We find no significant difference overall when the number variable updates is kept the same.
28

---

Published as a conference paper at ICLR 2025
Objective
Objective
RPMGDA RPWGDA-CO GS
2.05
RFNG24-05
1.-
2.00
1.95
1.6
1.5
1.25
144
1.80
1.75
1.3
1.70
1.2
20
40
60
80
100
20
40
60
80
100
Objective
Objective
1.9
RFNGD4-JO RFM0226-0
RPAGDAIGSS
188
17-
14-
1.5
1.4
0
20
40
60
80
100
0
20
40
60
80
100
Epochs
Epociss
Figure 28: look at the first 100 epochs. Gauss-Seidel update exhibits some 'zig-zags' and converges slower in terms of pure number of epochs. CIFAR-10 dataset.
Objective 1
Objective 2
1.8
RPMGDDM-Cc APMEDAA-S
RPMGON APMADA
1.2
1.4
1.
1.2
1.0
1.-
0.8
1.0
0.6
0.4
200
1000
200
600
800
1000
Objective 3
Objective
2.0
RPMGDAA-jch
RPMIGDA-Jch RPMISDA
1.8
RPMEDA G5
1.6
1.4
5
0.6
200
600
800
1000
200
400
600
800
1000
Epochs
Epochs
Figure 29: Overall convergence trends are similar if we plot the loss of Gauss-Seidel update every 5 epochs instead, to ensure the total number of variable updates are the same for Jacobi and Gauss- Seidel at each time stamp in the plot. CIFAR-10 10 dataset.
29

---

Published as a conference paper at ICLR 2025
Objective
Objective
2.26
2.2-
2224
2.20
2.30
2.16
2.10
RPM60A-J0
20
60
80
100
20
40
60
80
100
Objective
Objective
2.76
2.20
2.24
2.20
3
2.22
2.30
2.18
APMGDA-JO
2.14
2:16
20
40
30
100
20
40
60
800
100
Epochs
Epochs
Figure 30: look at the first 100 epochs. MNIST dataset, PFL setting.
Objective 1
Objective 2
2.25
RPMKDDN-jC APMIDDA-GS
2:25
RPINGON-JEb APAADA
2.00
2.00
1.50
1.25
1.25
1.00
0.75
0.50
0.25
600
BC0
1000
200
600
BCB
1000
Objective
Objective 4
2.25
SPMSDAN-CC
2.25
RPMAGDA-CC
2.00
2.00
1.75
1.75
1.50
150
1.25
1.25
1.00
0.75
0.50
600
BC0
1.000
200
600
BC0
1000
Epochs
Epochs
Figure 31: Overall convergence in 1000 epochs, with Gauss-Seide update plotted every epochs to ensure the total number of variable updates are the same. MNIST dataset, PFL setting.
30

---

Published as a conference paper at ICLR 2025
B.7 Misc
01
0
03
04
0,
V
f2
0
2
0g
f3
f4
f2
fs
Figure 32: Variable dependency structures of synthetic toy examples in $B.1 and BB.2.
31


Reviews:
[{"review_id": "ozRdEsruUA", "reviewer": "Reviewer_MUMM", "summary": "By leveraging refined variable partitioning, this work introduces a novel solution concept, Refined Pareto Stationarity (RPS), and a variant of the Multiple Gradient Descent Algorithm (MGDA), termed RP-MGDA, to address limitations of Pareto stationarity and MGDA in multi-objective optimization. RPS provides a sharper characterization than Pareto stationarity, and RP-MGDA is proven to converge to RPS. Comprehensive experiments demonstrate the superior performance of RP-MGDA over vanilla MGDA.", "questions": "Apart from the questions raised in the Weaknesses section, I have a few additional questions:\n\n$\\textbf{Q1:}$ In Theorem 3, it appears that $\\eta \\leq \\min_i \\frac{1}{L_i}$ may be insufficient, as it seems that (32) cannot be derived directly from (31) using (33). Could you please verify (32) in the proof of Theorem 3 on Page 16? If my observation is correct, one alternative might be to set $\\eta \\leq \\min_i \\frac{1}{2L_i}$ in Theorem 3 and adjust the proof accordingly. \n\n$\\textbf{Q2:}$ In the experiments of Section 7.2, is a stochastic variant of RP-MGDA used? Additionally, when ReLU is applied, what type of derivative is used in the implementation of RP-MGDA? Could this method be extended to a stochastic setting, and what significant challenges might arise in making such an extension?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "$\\textbf{S1:}$ This work reveals limitations of Pareto stationarity and  Multiple Gradient Descent Algorithm (MGDA), commonly used in multi-objective optimization, particularly when the function-variable dependency structure is sparse. The authors provide illustrative examples showing that a variable partitioning scheme is crucial for addressing these limitations.\n\n$\\textbf{S2:}$ Building on this insight, the authors introduce a novel solution concept, Refined Pareto Stationarity (RPS), which corresponds to the finest (or refined) variable partition aligned with the function-variable dependency structure. RPS is shown to be a sharper characterization than Pareto stationarity, from both the necessary and sufficient conditions perspective for Pareto optimality.  \n\n$\\textbf{S3:}$ Utilizing this refined variable partitioning, the authors propose a variant of MGDA, termed RP-MGDA, which converges to RPS and is theoretically more efficient. Empirical results further demonstrate the superior performance of RP-MGDA compared to vanilla MGDA.", "weaknesses": "$\\textbf{W1:}$ If the full gradient is used in (11) of Definition 4 (Generalized Pareto Stationarity), then any Pareto stationary point with respect to any variable partition would also be Pareto stationary with respect to the trivial partition. This suggests that the current version of Definition 4 is not consistent with the motivation behind RPS or Algorithm 1 (RP-MGDA). It seems that replacing the full gradient $\\nabla \\bf{f}^{P_j}$ with the partial gradient $\\nabla_{\\bf{w}_{P_j}} \\bf{f}^{P_j}$ could address this issue. Please let me know if my understanding is incorrect, as I may adjust my ratings based on your response.   \n\n$\\textbf{W2:}$ Since RP-MGDA and the vanilla MGDA have a similar convergence rate, the authors discuss the computational complexity of RP-MGDA at the end of Section 6 and state that RP-MGDA is theoretically cheaper than the vanilla MGDA, aside from the one-time overhead in line 1. However, the supporting argument lacks detail. A more thorough complexity analysis, including explicit computational cost comparisons for solving the dual subproblem in both algorithms, would be beneficial in clarifying the computational savings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Z779elfzK2", "reviewer": "Reviewer_EgBd", "summary": "This paper studies the multi-objective optimization problem and reveals the limitation of the widely used metric, Pareto stationarity. Accordingly, the authors propose the refined Pareto stationarity sandwiched between Pareto stationarity and Pareto optimality. Then, the authors verify the benefit of their RP-MGDA empirically and theoretically.", "questions": "Please check the weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This paper has a solid standing point that Pareto stationarity could be short in complex and sparse settings.\n2. Experiments explore multiple variable dependency structures.", "weaknesses": "1. Some important parts are confusing in the paper. 1) How can we get the function-variable dependency structure? This is important because the dependency structures vary in different settings. 2) Algorithm REFINED_PARTITION is not clear. A more detailed explanation of it should be added. In the current version, I cannot say I fully understand it.\n2. Since I did not fully understand the partition, what does \"finer\" or \"coarser\" partition mean? \n3. According to the illustration of the function-variable dependency structure and the experimental setup in lines 467-468, I understand this function-variable dependency structure as a dependency between objectives and \"specific layers\" in the model. However, I do not feel this setup fits my sense. From my point of view, a dependency should be between objectives and some part of weights in each layer if the model is sparse (Correct me if I am wrong). A simple example would be this: suppose we have m objectives and the model is a n-layer neural network. Then the objective $i$ is dependent on weights $[w_{1, i},..., w_{n,i}]$ where the first index of weights represents the layer index and the second index of weight represents the objective index. Why do the authors consider the dependency in your way? Also, if consider my settings, how to do the partition?\n4. Though this paper has considered multiple dependency structures in the experiments, tasks, and datasets are a bit easy. Previous related papers compare the performance of Cityscapes, NYU-v2, CelebA, etc. Do authors consider checking these experiments? In addition, this paper only compares MGDA and RP-MGDA, which is short in the number of methods. Lastly, can the partition be added to other MGDA-based methods?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y0NSCvkZoI", "reviewer": "Reviewer_Vj3K", "summary": "This work highlights the limitations of Pareto stationarity when dealing with sparse function-variable structures, offering compelling examples to illustrate these constraints. To overcome these challenges, they introduce a new solution concept called Refined Pareto Stationarity (RPS) and present an efficient partitioning algorithm to automatically uncover function-variable dependencies.", "questions": "1.Lack of practical examples. Could you provide some real-world examples of sparse function-variable structures? For instance, cases that exist in multi-objective federated learning or reinforcement learning.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This work is presented with good writing style, where the summarized problems with detailed explanations make it easy for readers to understand the problem addressed in this article. \n\n2. The set defined by Pareto stationarity is broader than that defined by Pareto optimal, a detail that previous algorithms based on Pareto stationarity have overlooked. This paper faces this gap and introduces algorithms to overcome this limitation, representing a significant improvement.\n\n3.Theorems 1 and 2 provide a detailed discussion on the relationships among Refined Pareto Stationarity, Pareto optimality, and Pareto stationary points. Additionally, Theorems 3 and Corollary 1 offer theoretical guarantees for the specific convergence rate of RP-MGDA.\nThe proof seems solid but I have not carefully checked the whole Appendix.\n\n4.The performance of MGDA and RP-MGDA was compared across various scenarios, demonstrating the effectiveness and versatility of RP-MGDA.", "weaknesses": "1.Computational Cost.  Neither MGDA nor RP-MGDA seems well-suited to large-scale machine learning problems, as stochastic variants (e.g. MOCO, MODO) are often more computationally efficient in practice. Can the RP-MGDA algorithm be adapted into a corresponding stochastic variant, and if so, would it still handle sparse parameter issues effectively after randomization?\n\n2.Theoretical challenges. Compared to the RPS concept proposed in this paper, Pareto stationary points appear to be a clearer optimization target. What changes does the Refined Pareto Stationarity bring to the theoretical proof? What challenges arise from these changes, and how are you addressed?\n\n3.Illustrations on Pareto front. The paper could provide a more in-depth analysis of Pareto optimal, Pareto stationarity, and Refined Pareto Stationarity. For example, the experiments could visualize the fronts corresponding to each of these concepts. Additionally, plotting the convergence trajectories of MGDA and RP-MGDA would further emphasize the effectiveness of RP-MGDA.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TP3707xGLV", "reviewer": "Reviewer_h4fS", "summary": "Multi-objective optimization (MOO) have many applications in machine learning. Multiple Gradient Descent Algorithm (MGDA) is essential to solve MOO, converging to a Pareto stationary solution, which serves as a first-order necessary condition for Pareto optimality. This work demonstrates that the Pareto Stationarity (PS) has limitations when sparse function-variable dependencies exist, and to address it, they propose a concept named Refined Pareto Stationarity (RPS). With a suitable designed partitioning procedure, they propose an optimization algorithm RP-MGDA, which is effective in both the theory and experiments.", "questions": "Is variable sparsity a common phenomenon in MOO?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The contributions of this paper are very clear. They provide a refined concept, and based on this, they propose a novel MOO algorithm.\n\n- Under some convexity, they prove RPS reduces exactly to Pareto optimality, whereas the widely-used PS does not, suggesting that the new solution concept is more superior.\n\n- A more powerful algorithm is proposed, and the advantages are supported in both the convergence and the experiments.", "weaknesses": "- The aim of the partition of variables should be clearly interpreted in the Introduction.\n\n- I apologize that I am not very familiar with this topic and the relevant references. I will carefully refer to the comments of other reviewers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)