Federated Multi-Objective Learning
Authors: Haibo Yang
Zhuqing Liu
Jia Liu
Chaosheng Dong
Michinari Momma
Venue: NeurIPS 2023 poster (2023)
Keywords: Multi-Objective Learning
Federated Learning

Abstract: In recent years, multi-objective optimization (MOO) emerges as a foundational problem underpinning many multi-agent multi-task learning applications. However, existing algorithms in MOO literature remain limited to centralized learning settings, which do not satisfy the distributed nature and data privacy needs of such multi-agent multi-task learning applications. This motivates us to propose a new federated multi-objective learning (FMOL) framework with multiple clients distributively and collaboratively solving an MOO problem while keeping their training data private. Notably, our FMOL framework allows a different set of objective functions across different clients to support a wide range of applications, which advances and generalizes the MOO formulation to the federated learning paradigm for the first time. For this FMOL framework, we propose two new federated multi-objective optimization (FMOO) algorithms called federated multi-gradient descent averaging (FMGDA) and federated stochastic multi-gradient descent averaging (FSMGDA). Both algorithms allow local updates to significantly reduce communication costs, while achieving the {\em same} convergence rates as those of their algorithmic counterparts in the single-objective federated learning. Our extensive experiments also corroborate the efficacy of our proposed FMOO algorithms.

Federated Multi-Objective Learning
Haibo Yang
Zhuqing Liu Dept. of ECE
Jia Liu Dept. of ECE
Dept. Comput. & Info. Sci. Rochester Institute of Technology Rochester, NY 14623 hbycis@rit.ech edu
The Ohio State University Columbus, OH 43210
The Ohio State University Columbus, 43210 liu@ece. osu. edu
A3u.93840ss..o edu
Chaosheng Dong Amazon.com Inc. Seattle, WA 98109 chaosd@amazon.c com
Michinari Momma
Amazon.com Inc. Seattle, WA 98109 mi achi@amazon.comm com
Abstract
In recent years, multi-objective optimization (MOO) emerges as foundational problem underpinning many multi-agent multi-task learning applications. How- ever, existing algorithms in MOO literature remain limited to centralized learning settings, which do not satisfy the distributed nature and data privacy needs of such multi-agent multi-task learning applications. This motivates us to propose a new federated multi- objeei-o learning (FMOL) framework with multiple clients distributively and collaboratively solving an MOO problem while keeping their training data private. Notably, our FMOL framework allows a different set of objec- tive functions across different clients to support a wide range of applications, which advances and generalizes the MOO formulation the federated learning paradigm for the first time. For this FMOL framework, we propose two new federated multi-objective optimization (FMOO) algorithms called federated mulli-gradient descent averaging (FMGDA) and federated stochastic multi-gradien descent av- eraging (FSMGDA). Both algorithms allow local updates to significantly reduce communication costs, while achieving the same convergence rates as those of their algorithmic counterparts in the singlc-objective federated learning. Our extensive experiments also corroborate the efficacy of our proposed FMOO algorithms.
Introduction
In recent years, multi-objective optimization (MOO) has emerged as foundational problem underpin- ning many multi-agent multi-task learning applications, such training neural networks for multiple tasks [1. hydrocarbon production optimization [2), recommendation system 3, tissue engineering [4, and learning-to-He to-nnkkk (5] 6 7). MOO aims optimizing multiple objectives simultaneously, which can be mathematically cast as:
min F(x) = (x), ... ,f((x)), xED
(I)
where x E D C 2d is the model parameter, and f. Rd + R. s E [S] is one of the objective functions. Compared to conventional single-objective optimization, coupling and potential conflicts between different objective functions. As a result, there may not exist common x-solution that minimizes all objective functions. Rather, the goal in MOO is to find Pareto stationary solution that is not improvable for all objectives without sacrificing some objectives. For example, in recommender system designs for e-commerce, the platform needs consider different
key difference in MOO is the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

customers with substantially conflicting shopping objectives (price, brand preferences, delivery speed, etc.). Therefore, the platform's 's best interest is often find Pareto-stationary solution, where one cannot deviate to favor one consumer group further without hurting any other group. MOO with conflicting objectives also has natural incarnations in many competitive game-theoretic problems, where the goal is to determine an equilibrium among the conflicting agents in the Pareto sense.
Since its inception dating back the 1950s, MOO algorithm design has evolved into two major categories: gradient-free and gradient-based methods, with the latter garnering increasing attention in the learning community in recent years due to their better performances (see Section 2 for more detailed discussions). However, despite these advances, all existing algorithms in the current MOO literature remain limited to centralized settings (i.e.. training data are aggregated and accessible to a centralized learning algorithm). Somewhat ironically, such centralized settings do not satisfy the distributed nature and data privacy needs of many multi-agent multi-task learning applications, which motivates application of MOO in the first place. This gap between the existing MOO approaches and the rapidly growing importance of distributed MOO motivates us to make the first attempt to pursue a new federated multi-objective learning (FMOL) framework, with the aim to enable multiple clients to distributively solve MOO problems while keeping their computation and training data private.
So far, however, developing distributed optimization algorithms for FMOL with provable Pareto- stationary convergence remains uncharted territory. There are several key technical challenges that render FMOL far from being straightforward extension of centralized MOO problems. First of all. due to the distributed nature of FMOL problems, one has to consider and model the objective heterogeneity (i.e., different clients could have different sets of objective functions) that is unseen in centralized MOO. Moreover, with local and private datasets being a defining feature in FMOL, the impacts of data heterogeneity (i.e., datasets are non-i.i.d. distributed across clients) also need to be mitigated in FMOL algorithm design. Last but not least, under the combined influence of objective and data heterogeneity, FMOL algorithms could be extremely sensitive to small perturbations in the determination of common descent direction among all objectives. This makes the FMOL algorithm design and the associated convergence analysis far more complicated than those of the centralized MOO. Toward this end, a fundamental question naturally arises:
Under both objective and data heterogeneity in FMOL, is it possible to design effective and efficient algorithms with Pareto- staeto-statinaay convergence guarantees?
In this paper, we give an affirmative answer to the above question. Our key contribution is that propose new FMOL framework that captures both objective and data heterogeneity, based on which we develop two gradient-based based algorithms with provable Pareto-stationary convergence rate guarantees. To our knowledge, our work is the first systematic attempt bridge the gap between federated learning and MOO. Our main results and contributions are summarized as follows:
We formalize the first federated multi- objective learning (FMOL) framework that supports both objective and data heterogeneity across clients, which significantly advances and generalizes the MOO formulation to the federated learning paradigm. As result, our FMOL framework becomes a generic model that covers existing MOO models and various applications as special cases (see Section 3.2 for further details). This new FMOL framework lays the foundation to enable us to systematically develop FMOO algorithms with provable Pareto-stationary convergence guarantees.
For the proposed FMOL framework, we first propose a federated multi-gradient descent averaging (FMGDA) algorithm based on the use of local full gradient evaluation at each client. Our analysis reveals that FMGDA achieves linear (cxp(-xxT)) and a sublinear O (1//T) Pareto- -tationnny convergence rates for μ-stroogly convex and non non-convex settings, respectively. Also, FMGDA employs a two-sided learning rates strategy to significantly lower communication costs (a key concern in the federated learning paradigm). It is worth pointing out that, in the single-machine special case where FMOL degenerates to a centralized MOO problem and FMGDA reduces to the traditional MGD method the restrictive assumptions on the linear search of learning rate and extra sequence convergence. Thus, our results also advance the state of the art in general MOO theory.
B. our results improve the state-of-the-ar art analysis of MGD by eliminating
To alleviate the cost of full gradient evaluation in the large dataset regime, we further propose a federated stochastic multi-gradien descent averaging (FSMGDA) algorithm based on the use of stochastic gradient evaluations at each client. We show that FSMGDA achieves Õ(1/T) and ((1/VT) Pareto -tationstato convergence rate for j-strooggyy convex and non-convex settings, re- spectively. We establish our convergence proof by proposing new (a, Lipsschit continuous
2

---

Table 1: Convergence rate results (shaded parts results) comparisons.
Strongly Convex
Non-comvex
Methods
Rate
Assumption"
Rate
Assumption"
MGD
((r") #
Linear search & sequence convergence
((1/T)
Linear search & sequence convergence
SMGD 9
First momeat bound Lipschitz continuity X
Not provided
Not provided
((1/2)
FMGDA
((exp(-piD)
needed
O(1/2)
Not needed
FSMGDA
Ó(1/))
(a. B)--Lpscchittz continuous
stechastic gradient
0(1/T))
(a, fJ--ipschitzz continuous stnchustic gradient
Notes constants: μ the strong convexity modulus; is constant depends on Jr, s.I., r (0, 1).
Assumption short-hands: "Linear search": learning rate linear search [8] "Sequence conver-
gence": [xi] converges to x" []; "First moment bound" (Asm. 5.2(b) [9] ) /(IV)(
fx(x)]]] I n(a + "Liisscct continuity of X" (Asm. 5,4 ()::
|| - Xcl <
8
(x))) V(((x)))) ..... (V]s(x)) V]]s(x)))]]I:: "(ax, 3)-Lipschitz continuous stochastic gradi-
ent": see Asm. 4
stochastic gradient assumption (cf. Assumption 4. which relaxes the strong assumptions on first moment bound and Lipschitz continuity on common descent directions in [9] We note that this new (a, 3)-Lipschitz continuous stochastic gradient assumption can be viewed as natural extension of the classical Lipschitz-continuon gradient assumption and could be of independent interest.
The rest of the paper organized follows. In Section 2 we review related works. In Section 3 we introduce our FMOL framework and two gradient-based algorithms (FMGDA and FSMGDA). which are followed by their convergence analyses in Section [ We present the numerical results in Section and conclude the work in Section 6 Due to space limitations, we relegate all proofs and some ex experiments to supplementary material.
2 Related work
In this section, we will provide an overview algorithm designs for MOO and federated learning (FL), thereby placing our work in a comparative perspective to highlight our contributions and novelty.
1) Multi-objective Optimization (MO0): As mentioned in Section since fedderate/ddistribteed MOO has not been studied in the literature, all existing works we review below are centralized MOO algorithms. Roughly speaking, MOO algorithms can be grouped into two main categories. The first line of works are gradient-free methods (e.g., evolutionary MOO algorithms and Bayesian MOO algorithms [10 11 ). These methods are more suitable for small-scale problems but less practical for high-dimensional MOO models (e.g., deep neural networks). The second line of works focus on gradient-bass approaches [14 15 16 9 which are more practical for high-dimensional MOO problems. However, while having received increasing attention from the community in recent years, Parcto-stationary convergence analysis of these gradient-baser MOO methods remains in its infancy.
Existing gradient-basee based MOO methods can be further categorized as i) multi-gradient descent (MGD) algorithms with full gradients and ii) stochastic multi-gradien descent (SMGD) algorithms. It has been shown in [8] that MGD methods achieve Orr for some E (0, 1) and O(1/T) Pareto- stationary convergence rates for j-strongly convex and non-convex functions, respectively. However, these results are established under the unconventional linear search of learning rate and sequence convergence assumptions, which are difficult to verify in practice. In comparison, FMGDA achieves a linear rate without needing such assumptions. For SMGD methods, the Pareto-stationary convergence analysis is further complicated by the stochastic gradient noise. Toward this end, an O(1/T) rate analysis for SMGD provided in [9] based on rather strong assumptions and Lipschtiz continuity of common descent direction. As a negative result, it was shown in [9] and (18] that the common descent direction needed in the SMGD method is likely to be biased estimation, which may cause divergence issues.
first-moment bound
In contrast, our FSMGDA achieves state-of-the-art Õ(I/T) and O(1/VT) convergence rates for strongly-convex and non-convex settings, respectively, under a much milder assumption on Lipschtiz continuous stochastic gradients. For easy comparisons, we summarize our results and the existing
works in Table I It is worth noting recent works [18 19 20 established faster convergence rates in
3

---

the centralized MOO setting by using acceleration techniques, such as momentum, regularization and bi-level formulation. However, due to different settings and focuses, these results are orthogonal to ours and thus not directly comparable. Also, since acceleration itself is a non-trivial topic and could be quite brittle not done right, in this paper, we focus on the basic and more robust stochastic gradient approach in FMOL. But for a comprehensive comparison on assumptions and main results of accelerated centralized MOO, we refer readers to Appendix [ for further details.
Federated Learning (FL): Since the seminal work by [21. FL has emerged as a popular distributed learning paradigm. Traditional FL aims at solving singleobjective minimization problems with a large number of clients with decentralized data. Recent FL algorithms enjoy both high communication efficiency and good generalization performance [21] 22 [23] 24 [5 26]. Theoretically, many FL methods have the same convergence rates as their centralized counterparts under different FL
settings (27 28 29 30 Recent works have also considered Fl. problems with more sophisticated
problem structures, such as min-max learning [3 322, reinforcement learning [3] multi-armed bandits (34. and bilevel and compositional optimization [35]. Although not directly related, classic FL has been reformulated in the form of (3) which allows the use of MGD-type algorithm instead of vanilla local SGD to solve the standard FL problem. We will show later that this MOO reformulation is special case of our FMOL framework. So far, despite wide range of applications (see Section 3.2 for examples), there remains a lack of a general FL framework for MOO. This motivates to bridge the gap by proposing general FMOL framework and designing gradient- basse methods with provable Pareto staatooaaa convergence rates.
3. Federated multi-objective learning
3.1 Multi-objective optimization: A primer
As mentioned in Section [ due to potential conflicts among the objective functions in MOO problem in ①.. MOO problems adopt the the notion of Pareto optimality:
Definition 1 ((Weak) Pareto Optimality), For any two solutions x and y, we say x dominates if and only if fx(x) < [sly), Vs E [S] and [s(x) < <f,(y) As E [S]. A solution x is Pareto optimal if it is not dominated by any other solution. One solution x is weakly Pareto optimal if there does not exist a solution y such that fx(x) fs(y), Vs E (S).
Similar solving single-objective non-convex optimization problems. finding a Pareto-optimal solution in MOO is NP-Hard in general. As a result, it is often of practical interest to find solution satisfying Pareto steetossttionnarity (a necessary condition for Pareto optimality) stated as follows [4
Definition 2 (Pareto Stationarity). A solution x is said to be Pareto stationary if there is no common descent direction d E _dd such that fx() d < 0, Vs E [S].
Note that for strongly convex functions, Pareto stationary solutions are also Pareto optimal. Following Definition 2 gradient-based MOO algorithms typically search for common descent direction
E gd such that (x) d < 0, Vs E [S]. If no such a common descent direction exists at x,
then x is Pareto stationary solution. For example, MGD [15] searches for optimal weight
X of gradients (x & (Vf Ys E [$]} by solving X (x) = argminxec | V [x) 2|2.
Then, common descent direction can be chosen as: d X (x MGD performs the iterative update rule: x + x - 7/d until a Pareto stationary point is reached, where is learning rate. SMGD (9] also follows the same process except for replacing full gradients by stochastic gradients. For MGD and SMGD methods,
shown in [ and [8] show that || X VF(x)]] = 0 for some A {y E 1Js, >. V/- = 1}. then X is a Pareto stationary solution. Thus,
E C, where C'
|||l = || V
x)
2 can be used as metric to measure the convergence of non-convex MOO
algorithms &
19 On the other hand, for more tractable strongly convex MOO problems, the 18
ESels X. [x) fa(x*) ] is typically used as the metric to measure the convergence of an algorithm 19, where x" denotes the Pareto optimal point. We summarize and compare different convergence metries as well as assumptions in MOO, detailed in Appendix A
optimality gap Σ

---

3.2 A general federated multi-objective learning framework
With the MOO preliminaries in Section 3.1 we now formalize our general federated multi-objective learning (FMOL) framework. For system with M clients and S tasks (objectives), our FMOL framework can be written as:
min
Diag(FA (FA
(2)
x
fi ... fL. F P
11,1
11,M
.
A
fs, fs.M
9xM
0S,1 a
SxM
where matrix F groups all potential objectives (x) for each task at each client i, and A {0, 1) 1)SxM is binary objective indicator matrix, with each element Oz.i = if task is of client i's interest and as = otherwise. For each task s E [S]. the global objective function (x(x the average of local objectives over all related clients, i.e., fx(x) - [.. EiER, (x,,(x), where
Rg {i as 1, [M]}. Note that, for notation simplicity, here which corresponds to the balanced dataset setting. Our FMLO framework can be directly extended to imbalanced dataset settings by using weighted average proportional dataset sizes of related clients. For a client i E MM. its objectives of interest are (xs,(x)::.. = -1, [S]], which is a subset of [S].
simple average in fx(x,,
We note that FMOL generalizes MOO to the FL paradigm, which includes many existing MOO problems as special cases and corresponds to a wide range of applications.
If each client has only one distinct objective, i.e., A -.. S M, then Diag(FA7) [x)........ ...., ((xx).....s(x [s(x)]
where each objective fx(x), E [S] optimized only by client This special FMOL setting corresponds to the conventional multi-task learning and federated learning. Indeed, [ and [X formulated multi-task learning problem as MOO and considered Pareto optimal solutions with various trade-offs. (36) also formulated FI. as distributed MOO problems. Other examples of this setting include bi-objective formulation of offline reinforcement learning (39 and decentralized MOO [40].
If all clients share the same S objectives, i... A is all-one matrix, then Diag [FA T)
M EiE[M] fx,,(x), .... 37 EiE[M] [s..(x)] T_ In this case, FMOL reduces to federated MOO
problems with decentralized data that jointly optimizing fairness, privacy, and accuracy [4] 42 43 well as MOO with decentralized data under privacy constraints (e.g.. machine reassignment
among data centres 44) and engineering problems 45 46 47 (8)).
If each client has a different subset of objectives (i.e., objective heterogeneity), FMLO allows distinct preferences at each client. For example, each customer group on recommender system in e-commerce platforms might have different combinations of shopping preferences, such as product price, brand, delivery speed, etc.
3.3 Federated Multi-Objective Learning Algorithms
Upon formalizing our FMOL framework, our next goal is to develop gradient- based algorithms for solving large-scale high-dimensional FMOL problems with provable Pareto stationary convergence guarantees and low communication costs. To this end, we propose two FMOL algorithms, namely federated multiple gradient descent averaging (FMGDA) and federated stochastic multiple gradient descent averaging (FSMGDA) as shown in Algorithm I We summarize our key notation in Table in Appendix allow easy references for readers.
As shown in Algorithm 1. in each communication round t E [T], cach client synchronizes its local model with the current global model x, from the server (cf. Step 1). Then each client runs K local steps based on local data for all effective objectives (cf. Step 2) with two options: i) for FMGDA.
each local step performs local full gradient descent, i.e., x t.k+1 =
ril x M). V...(((x 1. Vs E 1,b
1.++1 x, 2,1)
S; ii) For FSMGDA, the local step performs stochastic gradient descent, i.e., x s.2
x
VL fx,,((''. (x.,,) <f V, S; where < denotes random sample in local step and round client Upon finishing local updates, each client returns the accumulated update A for each effective objective to the server (cf. Step 3). Then, the server aggregates all returned A-updates from
5

---

Algorithm Federated (Stochastic) Multiple Gradient Descent Averaging (FMGDA/FSMGGD))
At Each Client i:
1. Synchronize local models S,
X,, Vs E S
2. Local updates: for all E S₁, for lo = 1....,K K,
(FMGDA): x f.R f,k- x.
TLL fa (x,,) (x)))-))
L.k t.k-1 Tu V fa, (x dakml ,5: -.. 3. Return accumulated updates to server (A E S
(FSMGDA): X x.i
(FMGDA): D',, Ene(K] (x..)
(FSMGDA): Ab,; EkE(K) (x 4
At the Server:
4. Receive accumulated updates (A AsE ViE [M]}
5. Compute A [T..] LiER, A Vs E [S], where R. = {i: 0,,3 = 1, [M]]
6. Compute X; E [0, 1] by solving
Σ E.els) XA:lI² s.t. Σ SE(s) N1
min 2
(3)
7. Let d; = EeE(s] X A and update the global model as: X(+1 = X; - m.d, with global learning rate 1).-
clients to obtain the overall updates A for each objective & E [S] (cf. Steps 5), which will be used in solving convex quadratic optimization problem with linear constraints obtain an approximate common descent direction d, (ef. Step 6). Lastly, the global model updated following the direction d, with global learning rate 7). (ef. Step 7).
Two remarks on Algorithm [ are in order. First, we note that a two-sided learning rates strategy is used in Algorithm | which decouples the update schedules of local and global model parameters at clients and server, respectively. As shown Section 4 later, this two-sided learning rates strategy enables better convergence rates by choosing appropriate learning rates. Second, to achieve low communication costs, Jelverages
local updates at each client and infrequent periodic communications between each client and the server. By adjusting the two-sided learning rates appropriately, the K-value can be made large to further reduce communication costs.
Pareto stationary convergence analysis
In this section, we analyze the Pareto stationary convergence performance for our FMGDA and FSMGDA algorithms in Sections 4.1 and 4.2. respectively, each of which include non-convex and strongly convex settings.
4.1 Pareto stationary convergence of FMGDA
In what follows, show FMGDA enjoys linear rate Ō(cxp(-1(T) for p-strongly convex functions and sub-linear rate ( ) for non-convex functions.
1) FMGDA: The Non-convex Setting, Before presenting our Pareto stationary convergence results for FMGDA, we first state serveral assumptions as follows:
Assumption 1. (L-Lipschitz continuous) There exists constant L > 0 such that f.)) Vf.(y)) & L||x - yll, Vx, E Rd E [S].
Assumption 2. (Bounded Gradient) The gradient of each objective at any client is bounded, i.e.,
there exists constant G such that [x)]]( S G2, Vs E [S], [M].
With the assumptions above, we state the Pareto stationary convergence of FMGDA for non-convex FMOL follows:

---

Theorem (FMGDA for Non-convex FMOL). Let nr 17 S 2(1+L) Under Assumptions 7 aadd
3
if at least one function fe s E [S] is bounded from below by sami, then the sequence {xt} output by
FMGDA satisfies: min ||d,|| I Tn + where 8 A 16n K² L 6
"
In non-convex functions, we use ||ā,]| as the metrics for FMOO, where d, X (Diag (FA ))
and X is calculated by the quadratic programming problem Basse on accumulated (stochastic) gradients D. We compare different metrics for MOO in Appendix [ The convergence bound in Theorem D contains two parts. The first part is optimization error, which depends on the initial point and vanishes as T increases. The second part is due to local update steps K and data heterogeneity G, which can be mitigated by carefully choosing the local learning rate nz. Specifically, the following Pareto stationary convergence rate of FMGDA follows immediately from Theorem with appropriate choice of local learning rate MT.
Corollary 2. With a constant global learning rate T)t = VI, and a local learning rate V)r = O(1/VT), the Pareto stationary convergence rate of FMGDA is (1/T)
Several interesting insights of Theorem | and Corollary 2 are worth pointing out: 1) We note that FMGDA achieves a Pareto stationary convergence rate (I/T") for non-convex FMOL, which is the same as the Pareto stationary rate of MGD for centralized MOO and the same convergence rate of gradient descent (GD) for single objective problems. This is somewhat surprising because FMGDA needs to handle more complex objective and data heterogeneity under FMOL; 2) The two-sided learning rates strategy decouples the operation of clients and server by utilizing different learning rate schedules, thus better controlling the errors from local updates due to data heterogeneity: 3) Note that in the single-client special case, FMGDA degenerates the basic MGD algorithm. Hence, Theorem T directly implies a Pareto stationary convergence bound for MGD by setting 5 = O due to local updates in centralized MOO. This convergence rate bound is consistent with that in 8 However, we note that our result is achieved without using the linear search step for learning rate [8] which is much easier to implement in practice (especially for deep learning models); 4) Our proof is based on standard assumptions in first-order optimization, while previous works require strong and unconventional assumptions. For example, a convergence of x-sequence is assumed in g.
The Strongly Convex Setting. Now, we consider the strongly convex setting for FMOL, which is more tractable but still of interest in many learning problems in practice. In the strongly convex setting, we have the following additional assumption:
2) FMGDA:
Assumption 3. (μ-Strrongyy Convex Function) Each objective fx(x), E [S] is a p--strongly convex function, ie., fs(y)= 2 [x(x) + V (x) x) + Ill x|| for some μ >> 0.
For more tractable strongly-come FMOL problems, we show that FMGDA achieves a stronger Pareto stationary convergence performance as follows:
Theorem 3 (FMGDA for y-Strongly Convex FMOL). Let т) 1 such that 1) S 2(1-L)' 7. 21+2 and 1) 2 1 HT. Under Assumptions
3
1 pick Xt as the final output of the FMGDA algorithm with
weights We = (1 = Then, it holds that EJ E[A']] Σ l|xo - x. 1/11/110001 1/ nyT + 6, where
2/ A ExE[s] 21" (x.) fx.] and d = Bq x² G² 2n L22
Theorem
3 immediately implies following Pareto stationary convergence rate for FMGDA with a proper choice of local learning rate:
Corollary 4. If n is chosen sufficiently small such that 5 = O (x(_exp(_xrT) then the Pareto stationary convergence rate of FMGDA is |[A = ((ueep((ppi)) p()))
Again, several interesting insights can be drawn from Theorem and Corollary 4 First, for strongly convex FMOL, FMGDA achieves linear convergence rate O exp(-u(")). which again matches those of MGD for centralized MOO and GD for single-objective problems. Second, compared with the non-convex case, the convergence bounds suggest FMGDA could use larger local learning rate for non-convex functions thanks to our two-sided learning rates design. A novel feature of FMGDA for strongly convex FMOL is the randomly chosen output x, with weight w, from the xt-traeectory, which is inspired by the classical work in stochastic gradient descent (SGD) [9]. Note that, for implementation in practice, one does not need to store all x,-values. Instead, the algorithm can be implemented by using random clock for stopping [9
7

---

4.2 Pareto stationary convergence of FSMGDA
While enjoying strong performances. FMGDA uses local full gradients at each client, which could be costly in the large dataset regime. Thus, it is of theoretical and practical importance to consider the stochastic version of FMGDA, i.e., federated stochastic multi muati-gradieet descent averaging (FSMGDA).
1) ESMGDA:
The Non-convex Setting. A fundamental challenge in analyzing the Pareto stationarity convergence of FSMGDA and other stochastic multi-gradien descent (SMGD) methods stems from bounding the error of the common descent direction estimation, which is affected by both X; (obtained by solving a quadratic programming problem) and the stochastic gradient variance. In fact, it is shown in [9] and [18) that the stochastic common descent direction in SMGD-type methods could be biased, leading divergence issues. To address these challenges, in this paper, we propose to use new assumption on the stochastic gradients, which is stated as follows:
Assumption 4 ((a, 3)Lipschitz Continuous Stochastic Gradient). A function f has (a,, B)-Liischhitz continuous stochastic gradients if there exist two constants a. 3 > O such that, for any two indepen- dent training samples & andd E [|I E) - Vy < )|2] S al| - -y12 + +3²
In plain language, Assumption 4 says that the stochastic gradient estimation of an objective does not change too rapidly. We note that the (a, 3)-Lipschitz continuous stochastic gradient assumption is a natural extension of the classic L-Lipschitz continuous gradient assumption (cf. Assumption [T] and generalizes several assumptions of SMGD convergence analysis in previous works. We note that Assumption D is not necessarily too hard to satisfy in practice. For example, when the underlying distribution of training samples & has a bounded support (typically safe assumption for most applications in practice due to the finite representation limit of computing systems), suppose that Assumption holds (also a common assumption in the optimization literature), then for any given x and y. the left-hand-side of the inequality in Assumption 4 is bounded due to the L-smoothness in Assumption] [ In this case, there always exist a sufficiently large a and a 3 such that the right- hand-side of the inequality in Assumption [ holds. Please see Appendix A for further details. In addition, we need the following assumptions for the stochastic gradients, which are commonly used in standard (GD-based analyses [49, 550 51 52..
Assumption 5. (Unbiased Stochastic Estimation) The stochastic gradient estimation unbiased for each objective among clients, i.e., E (x, <)] = (x,, Vs E [5]. E [M].
Assumption 6. (Bounded Stochastic Gradient) The stochastic gradients satisfiy B[]l V (x. E)]] s
D2, Vs [$], E [M] for some constant D >
With the assumptions above, we now state the Pareto stationarity convergence of FSMGDA as follows:
Theorem (FSMGDA for Non-convex FMOL). Let nt = . X[+EJ. Under Assumptions 4 if an objective fo is bounded from below by frin, then the sequence {x,} output by FSMGDA satisfies:
mintety [
m.m 8 8(1
n1 + 8, where ō = (2S + (om) K2 D2 + (302).
Theorem immediately implies an O(I/VT) convergence rate of FSMGDA for non-convex FMOL:
Corollary 6. With a constant global learning rate = = OLIVVT), Vt and a local learning rate T/r,- O (1/T1/4), and if = O()), the Pareto stationarity convergence rate of FSMGDA is min 1| O(I/VT)
2) The Strongly Convex Setting: For more tractable strongly convex FMOL problems, we can show that FSMGDA achieve stronger convergence results as follows:
Theorem 7 (FSMGDA for p-Strongly Convex FMOL). Let n) = n = 2 )- Under Assumptions
and 6 pick x4 as the final output of the FSMGDA algorithm with weight We = (1 2 Then,
it holds that: 2 < ||x0
x. x (TT + 5, where S'S Exees]] X:" [xi - fx.
and 8- 52 (om K2 D2 + 3022 + n
The following Pareto station convergence rate of FSMGDA follows immediately from Theorem
Corollary 8. Choose Mr. = (( and = O log(max(1.,) If B = O(n), then the Pareto
stationary convergence rate of FSMGDA is E E - ((IT)).
8

---

Corollary 8 says that, With proper learning rates, FSMGDA achieves (1/TT) Pareto stationary convergence rate (i.e., ignoring logarithmic factors) for strongly convex FMOL. Also, in the single- client special case with no local updates, FSMGDA reduces to the SMGD algorithm and
4 0z + n² in this case. Then, Theorem implies an O(}) Pateto stationarity convergence rate for SMGD for strongly convex MOO problems, which consistent with previous works (9] However, our convergence rate proof uses a more conventional (a, 3) )-ppisccci stochastic gradient assumption, rather than the unconventional assumptions on the first moment bound and Lipschitz continuity of common descent directions in [9]
2
5 Numerical results
In this section, we show the main numerical experiments of our FMGDA and FSMGDA algorithms in different datasets, while relegating the experimental settings and details to the appendix.
task
MALL
Ex
10
rounds
Communcction rounzs
Communication rounds
Cormunicat rounds
(a) Training loss convergence in terms of communica- (b) The impacts local update number K on train- tion rounds with different batch-sizes under non-i.i.d. ing loss convergence terms communication rounds.
data partition in MultiMNIST.
Figure Training loss convergence comparison.
1) Ablation Experiments on Two-Tasks FMOL: l-a) Impacts of Batch Size on Convergence: First, compare the convergence results in terms of the number of communication rounds using the "MultiMNIST"" dataset [53] with two tasks (L and R) as objectives. We test our algorithms with four different cases with batch sizes being [16, 64, 1 128, 256]. To reduce computational costs in this experiment, the dataset size for each client is limited to 256. Hence, the batch size 256 corresponds to FMGDA and all other batch sizes correspond FSMGDA. As shown in Fig. [[a] under non-i.i.d. data partition, both FMGDA and FSMGDA algorithms converge. Also, the convergence speed of the FSMGDA algorithm increases the batch size gets larger. These results consistent with thcoretical analyses as outlined in Theorems D and
1 1-b) Impacts of Local Update Steps Convergence: Next, we evaluate our algorithms with different numbers of local update steps K. As shown in Fig. [(b) and Table 2, both algorithms converge faster the number of the local steps K increases. This because both algorithms effectively run more iterative updates as K gets large.
1-c) Comparisons between FMOL and Centralized MOO: Since this work is the first that investigates FMOL, it is also interesting to empirically compare the differences between FMOL and centralized MOO methods. In Fig. 2(a) we compare the training loss of FMGDA and FSMGDA with those of the centralized MGD and SMGD methods after 100 communication rounds. For fair comparisons,
the centralized MGD and SMGD methods use Σ |.S] batch-sizes and run K x T iterations. Our results indicate that FMGDA and MGD produce similar results, while the performance of FSMGDA is slightly worse than that of SMGD due to FSMGDA's sensitivity to objective and data heterogeneity in stochastic settings. These numerical results confirm our theoretical convergence analysis.
Table 2: Communication rounds needed for 10 2 loss.
i.i.d.
non non-i.i.d.
Task L
Task R
Task
Task R
K =
82
84
96
82
= 5
18(4.6x)
20(4.2x)
24(4.0x)
20(4.1x)
K = 10
10(8.2x)
9(.33x)
13(7.4x)
10(8.2x)
K = 20
5(16.4x)
5(16.8x)
6(16.0x)
5(16.4x)

---

FMGGD
FSMGDA
Nemalaan
6010
1452
0:12
ta3k
100 communication rounds with various local steps K, corresponding federated and centralized set- tings share the same marker shape.
Normalized loss with the River Flow datasets.
Figure 2: Training losses comparison
2) Experiments Larger FMOL: We further test our algorithms on FMOL problems of larger sizes. In this experiment, we use the River Flow [Staset which contains eight tasks in this problem. To better visualize 8 different tasks, we illustrate the normalized loss in radar charts in Fig. 2(b). In this 8-task setting, we can again verify that more local steps K and larger training batch size lead faster convergence. In the appendix, we also verify the effectiveness of our FMGDA and FSMGDA algorithms in CelebA [55] (40 tasks), alongside with other hyperparmeter tuning results.
6 Conclusion and discussions
In this paper, we proposed the first general framework to extend multi-objective optimization to federated learning paradigm, which considers both objective and data heterogeneity. We showed that, even under objective and data heterogeneity, both of our proposed algorithms enjoy the same Pareto stationary convergence rate their centralized counterparts. In our future work, will go beyond the limitation the analysis MOO that an extra assumption on the stochastic gradients (and A). In this paper, have proposed weaker assumption (Assumption 4 We conjecture that using acceleration techniques, e.g., momentum, variance reduction, and regularization, could relax such assumption and achieve better convergence rate, which is promising direction for future works. In addition, MOO in distributed learning gives rise to substantially expensive communication costs, which scales linearly with the number of clients and the number of objectives in each client. Developing communication-effiieen MOO beyond typical gradient compression methods for distributed learning also a promising direction for future works.
Acknowledgments and Disclosure of Funding
This work has been supported in part by NSF grants CAREER CNS-21 200259 and CNS-21 12471.
10

---

References
[1] O. Sener and V. Koltun, "Multi-task learning multi-objective optimization," Advances in neural information processing systems, vol. 31, 2018.
[2] You, W. Ampomah, and Q. Sun, "Development and application of machine learning based multi-objective optimization workflow for co2-eor projects," Fuel, vol. 264, p. 116758, 2020.
[3] T. Zhou, M. Momma, C. Dong, F. Yang, C. Guo, J. Shang, and J. K. Liu, "Multi-task learning on heterogeneous graph neural network for substitute recommendation," in 19th International Workshop on Mining and Learning with Graphs, 2023.
[4] J. Shi, J. Song, B. Song, and W. Lu, "Multi-objective optimization design through machine learning for drop-on- on-demand bioprinting," Engineering, vol. 5, no. 3, pp. 586-593, 2019.
[5] D. Mahapatra, C. Dong, Y. Chen, and M. Momma, "Multi-label learning to rank through multi- objective optimization." in Proceedings of the 29th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2023.
[6] D. Mahapatra, C. Dong, and M. Momma, "Querywise fair learning to rank through multi- objective optimization," in Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023.
[7] M. Momma, A. Bagheri Garakani, N. Ma, and Y. Sun, "Multi-objective ranking via constrained optimization," in Companion Proceedings of the Web Conference 2020, 2020, pp. 111-112.
[8] J. Fliege, A. F. Vaz, and L. N. Vicente, "Complexity of gradient descent for multiobjective optimization," Optimization Methods and Software, vol. 34, no. 5, pp. 949-959, 2019.
[9] S. Liu and L. N. Vicente, "The stochastic multi-gradient algorithm for multi-objective optimiza- tion and its application to supervised machine learning," " Annals of Operations Research, pp-
1 1-30, 2021.
[10] Q. Zhang and H. Li, "Moea/d: A multiobjective evolutionary algorithm based on decomposition." IEEE Transactions on evolutionary computation, vol. 11, no. 6, pp. 712-731, 2007.
[11] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: Nsga-ii," IEEE transactions on evolutionary computation, vol. 6, no. 2, pp. 182-197, 2002.
[12] S. Belakaria, A. Deshwal, N. K. Jayakodi, and J. R. Doppa, "Uncertainty-aware search frame- work for multi-objective bayesian optimization," Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, 2020, pp. 044--10052.
[13] M. Laumanns and J. Ocenasek, "Bayesian optimization algorithms for multi-objectin optimiza- tion." in International Conference on Parallel Problem Solving from Nature. Springer, 2002, pp. 298-307.
[14] J. Fliege and B. F. Svaiter, "Steepest descent methods for multicriteria optimization," Mathemat- ical methods of operations research, vol. 51, no. pp. 479-494, 2000.
[15] J. Désidéri, Mhultiple-gradienn descent algorithm (mgda) for multiobjective optimization," Comptes Rendus Mathematique, vol. 350, no. 5-6, pp. 313-318, 2012.
[16] S. Peitz and M. Dellnitz, "Gradient-based multiobjective optimization with uncertainties," in NEO 2016. Springer, 2018, pp. 159-182.
[17] M. Momma, C. Dong, and J. Liu, "A multi-objective multi-task learning framework induced by pareto stationarity." in Proceedings of the 39th International Conference on Machine Learning, 2022.
[18] Zhou, W. Zhang, Jiang, W. Zhong, J. GU, and W. Zhu, "On the convergence of stochastic multi-objective gradient manipulation and beyond," in Advances in Neural Information Processing Systems, A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, Eds., 2022. [Online].
Available:
[19] H. Fernando, H. Shen, M. Liu, S. Chaudhury, K. Murugesan, and T. Chen, "Mitigating gradient bias in multi-objective learning: provably convergent stochastic approach." arXiv preprint 2r /2644 2022.
[20] Xiao, H. Ban, and K. Ji, "Direction-oriented multi-objective learning: Simple and provable stochastic algorithms," arXiv preprint 230...2300...009 2023.

---

[21] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, "Communication-efiooe learning of deep networks from decentralized data," " in Artificial intelligence and statistics. PMLR, 2017, pp. 1273-1282.
[22] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, "Federated optimization in heterogeneous networks," in Proceedings of Machine Learning and Systems, I. Dhillon, D. Papailiopoulos. and V. Sze, Eds., vol. 2, 2020, pp. 429-450.
[23] D. A. E. Acar, Y. Zhao, R. M. Navarro, M. Mattina, P. N. Whatmough, and V. Saligrama. "Federated learning based on dynamic regularization," in International Conference on Learning Representations, 2021.
[24] J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor, "Tackling the objective inconsistency problem in heterogeneous federated optimization," " Advances in Neural Information Processing Systems, vol. 33, 2020.
[25] T. Lin, S. U. Stich, K. K. Patel, and M. Jaggi, "Don't use large mini-batches, use local sgd," in International Conference on Learning Representations, 2020. [Online]. Available: http://openncviee..e/ffoumu hiwp://woeeoooommiiidillllllll
[26] H. Yang, P. Qiu, and J. Liu, "Taming fat-tailed ("heavier-tailed" with potentially infinite variance) noise in federated learning," in Advances in Neural Information Processing Systems, A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, Eds., 2022. [Online]. Available: https://openeviiewne/////ooo mwtt://fooommmiddSSSioooa..
[27] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich,, and A. T. Suresh, "SCAFFOLD: Stochastic controlled averaging for federated learning," in Proceedings of the 37th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, H. D. III and A. Singh, Eds., vol. 119. PMLR, 13-18 Jul 2020, pp. 5132-5143.
[28] H. Yang, M. Fang, and J. Liu, "Achieving linear speedup with partial worker participation in non-III federated learning." " in International Conference on Learning Representations, 2021.
[29] H. Yang, X. Zhang, P. Khanduri, and J. Liu, "Anarchic federated learning." in International Conference on Machine Learning. PMLR, 2022, pp. 25 251-1125 363.
[30] X. Zhang, M. Fang, Z. Liu, H. Yang. J. Liu, and Z. Zhu, "Net-fleet: achieving linear convergence speedup for fully decentralized federated learning with heterogeneous data," Proceedings of the Twenty- Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, 2022.
[31] H. Yang, Z. Liu, X. Zhang, and J. Liu, "SAGDA: Achieving ((E-2) communication complexity in federated min-max learning." in Advances in Neural Information Processing Systems, A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, Eds., 2022. [Online]. Available: https://openreviewwee////o/ TTw.://ruummdddww./gg..//
[32] P. Sharma, R. Panda, G. Joshi, and P. Varshney, "Federated minimax optimization: Improved convergence analyses and algorithms," in International Conference on Machine Learning. PMLR, 2022, pp. 19 686-197770
[33] S. Khodadadian, P. Sharma, G. Joshi, and S. T. Maguluri, "Federated reinforcement learning: Linear speedup under markovian sampling." in International Conference on Machine Learning. PMLR, 2022, pp. 10 9099-111057 057.
[34] C. Shi, C. Shen, and J. Yang, "Federated multi-armed bandits with personalization." in Interna- tional Conference on Artificial Intelligence and Statistics. PMLR, 2021, pp. 2917-2925.
[35] D. A. Tarzanagh, M. Li. C. Thrampoulidis, and S. Oymak, "FedNest: Federated bilevel, minimax, and compositional optimization," in Proceedings of the 39th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, Eds., vol. 162. PMLR, 17-23 Jul 2022, pp. 21 146 22 179.
[36] Z. Hu, K. Shaloudegi, G. Zhang, and Y. Yu, "Federated learning meets multi-objective optimiza- tion," IEEE Transactions on Network Science and Engineering, 2022.
[37] K. Miettinen, Nonlinear multiobjectivv optimization. Springer Science & Business Media, 2012, vol. 12.
[38] X. Lin, H.-I.. Zhen, 7. Li, Q.-P. Zhang, and S. Kwong, "Pareto multi-task learning," Advances in neural information processing systems, vol. 32, 2019.
12

---

[39] Y. Yang, J. Jiang, T. Zhou, J. Ma, and Y. Shi, "Pareto policy pool for model-based offline reinforcement learning," " in International Conference on Learning Representations, 2022.
[Online]. Available:
[40] M. J. Blondin and M. Hale, "A decentralized multi-objective optimization algorithm," Journal of Optimization Theory and Applications, vol. 189, no. 2, pp. 458 485, 2021.
[41] L. T. Bui, H. A. Abbass, and D. Essam, "Local models- approach distributed multi- objective optimization," Computational Optimization and Applications, vol. 42, no. 1, pp. 105-139, 2009.
[42] S. Cui, W. Pan, J. Liang, C. 7hang, and F. Wang, "Addressing algorithmic disparity and performance inconsistency in federated learning," Advances Neural Information Processing Systems, vol. 34, pp. 26 091-26 102, 2021.
[43] N. Mchrabi, C. de Lichy, J. McKay, C. He, and W. Campbell. "Towards multi-objecctvv statistically fair federated learning." arXiv preprint orXiv:2201.09911 2022.
[44] T. Saber, X. Gandibleux, M. O'Neill, L. Murphy, and A. Ventresque, "A comparative study of multi-objective machine reassignment algorithms for data centres," Journal of Heuristies, vol. 26, no. 1, pp. 119-150, 2020.
[45] I.. Yin, T. Wang, and B. Zheng, "Analytical adaptive distributed multi-objective optimization algorithm for optimal power flow problems," Energy, vol. 216, p. 119245, 2021.
[46] Y. Jin, Multi-objective machine learning. Springer Science & Business Media, 2006, vol. 16.
[47] A. Mansoor, X. Diao, and C. Smidts, "A method for backward failure propagation in conceptual system design," Nuclear Science and Engineering, 2023.
[48] A. Mansoor, Diao, and Smidts, "Backward failure propagation for conceptual system design using isfa," 11 2021.
[49] S. Ghadimi and G. Lan, "Stochastic first-and zeroth-order methods for nonconvex stochastic programming." " SIAM Journal on Optimization, vol. 23, no. pp. 2341-2368, 2013.
[50] I.. Bottou, F. F. Curtis, and J. Nocedal, "Optimization methods for large-scale machine learning," Siam Review, vol. 60, no. 2, pp. 223-311, 2018.
[51] H. B. McMahan el al., "Advances and open problems federated learning." Foundations and Trends@ in Machine Learning, vol. 14, no. 1, 2021.
[52] J. Wang, Z. Charles, Z. Xu, G. Joshi, H. B. McMahan, M. Al-Shedivat, G. Andrew, S. Aves- timehr, K. Daly, D. Data et al., "A field guide federated optimization," arXiv preprint arXiv:2107.06917, 2021.
[53] S. Sabour, N. Frosst, and G. E. Hinton, "Dynamic routing between capsules," Advances in neural information processing systems, vol. 30, 2017.
[54] L. Nie, K. Wang. W. Kang, and Y. Gao, "Image retrieval with attributeasssociated auxiliary references," " in 2017 International Conference on Digital Image Computing: Techniques and Applications (DICTA). IEEE, 2017, pp. 1-6.
[55] Z. Liu, P. Luo, X. Wang, and X. Tang, "Deep learning face attributes in the wild," in Proceedings of the IEEE international conference on computer vision, 2015, pp. 3730-3738.
[56] Q Mereier, F. Poirion, and J.-A. Désidéri, "A stochastic multiple gradient descent algorithm." European Journal of Operational Research, vol. 271, no. 3, pp. 808-817, 2018.
[57] Y. LeCun, C. Cortes, and C. Burges, "Mnist handwritten digit database," Available: http://yann. lecun. com/exdb/mnnsst, 1998.
[58] K. He, X. Zhang. S. Ren, and J. Sun, "Deep residual learning for image recognition. cvpr.. 2016." arXiv preprint arXiv: 15 122.03385 2016.
13

---

A Gradient-based methods in MOO
(Stochastic) Gradient-based methods in MOO have attracted much attention owing to simple update rules and less intensive computation recently, thus rendering them perfect candidates to underpin MOO applications in deep learning under first-oracle. However, their theoretical understandings remain less explored relative to their counterparts of single objective optimization. Hence, we highlight the existing works and corresponding assumptions alongside with convergence metrics.
Existing Works. Various works managed to explore the convergence rates under different assump- tions in strongly-convex, convex, and non-convex functions as listed in Table Using full gradient, MGD 8 could achieve tight convergence rates in strongly-convex and non-conved cases, i.e., linear rate ),r"),r E (0, and sub-linear rate O ++) However, it requires linear search of learning rate in the algorithm and sequence convergence (xx,) converges to x.). The linear search learning rate is a classic technique, but does not fits in gradient-based algorithms in deep learning. Moreover, sequence convergence assumption is a too strong assumption. With no local step, our FMGDA degenerates MGD. As result, our analysis also provide the same order convergence rates in both strongly-convex and non-convex functions while avoiding strong and unpractical assumptions. If using stochastic gradient, SMGD methods makes further complicated case. The stochastic gradient noise would complicate the analysis and thus it is still unclear whether SMGD is guaranteed to converge. [9] provided convergence rate for SMGD but extra assumptions and/or unreasonably large batch requirements were needed. On the other hand, [9] and [88 showed that the common descent direction provided by SMGD method is likely be a biased estimation, rendering non-convergence issues. Recently, by utilizing momentum, MoCo [19] and CR-MOGM [18] were proposed with corre- sponding convergence guarantees. (20) utilized direction-oriented approach by preference direction. However, these analyses do not shed light on pure SMGD despite its widespread application.
Assumptions. When applying stochastic gradient to MOO, common descent direction estimation (x). fs fx)) is biased estimation and thus rendering potential non- convergence issues 18]. This is a limitation for SMGD. However, SMGD does work well with wide range of applications in practice. Understanding under what conditions SMGD have convergence guarantee is thus an important problem. (56) assumes convexity property(HS): f(x, {)
X (x) <) (F(x)
f(x", 2 x 122 almost sure. (9] utilizes weaker assumptions but still needs first moment bound (A (Assumption 5.2(b)): B[I f(x E) [V((i)]] S niaa + bb (xx))) I]) and Lipschitz continuity of x (Assumption 5.4): | - Aell S 3 (x)s - V.i
...,, (V - fs (xx)))
In this paper, we use (a, -ipsschhit continuous stochastic gradient (Assumption 4. In essence, we need the stochastic gradient estimation satisfying E[|l fx,, V f(y, ( for any two independent samples & and E' For the incquality E|l < y| 3
vfy, [ <
a|Ix - y2 + 30 in Assumption 4, the notation o² just represents a general positive constant. This o² does not denote the variance of the stochastic gradient variance. Thus, this inequality does not
Table 3: List of key notation.
Notation
Definition
i
Client index
M
Total number of clients
8
Objective/task index
S
Total number of Objectives/tasks
S
Number of objectives/tasks of client i's interest
k
Local step index
K
Total number of local steps
t
Communication round index
T
Total number of communication rounds
X
E Rd
Global model parameters of FMOL in Problem (2)
Xo E Rd
Initial solution of FMOL in Problem (2)
X. E Ipd
A Pareto optimal solution of FMOL in Problem 2
The learning rate on the client side
n1
The learning rate on the server side in round
14

---

depend on the batch size of the stochastic gradient. More specifically, unlike the assumption in [9] that characterizes the difference between a stochastic gradient and its full gradient (hence depending on the batch size), our Assumption 4 only measures the average norm square of two stochastic gradient difference () V fyy <') given any two points x and y and any two samples & and E In other words, Assumption 4 does not involve any full gradient, and hence no dependence batch size.
It is natural extension of the classic Lipschitz continuous gradient assumption and could generalize existing assumptions.
If & and E' are the whole dataset, by setting a L and 0, (a, 3)-Liscchizz continuous stochastic gradient condition generalizes the traditional Lipschitz continuous gradient assumption [[V fyyll S L|[x -yll-
2. If E is one data sample, g' are the whole dataset and x = y, by setting a 0 and 3 (a, L--ipchccs continuous stochastic gradient condition generalizes the traditional bounded variance assumption [ <) fx)) - o².
3. If & is one data sample, g are the whole dataset and x y, by setting 3 = acg, (a, Jy-Lischhizz continuous stochastic gradient condition generalizes the bound on the first moment assumption (assumption 5.2(b)) and bounded sets assumption (assumption 5.3) p (EIIV [xx)]]] s on (n:(C; + (xx=))(())))))))) and [[((x)] S My + I.)).
Metries. For strongly-convex functions, we use 4/2 = -ESE(s) A1*
- fx as
the metrics. We note similar metrics are used in other works. For example, 99] uses min;=1...., EEEss) [X (xx,) (x.)) where dy by the quadratic programming problemB stochastic gradients. Rigorously speaking, the left-hand side is not guaranteed to be positive. But if we impose stronger assumptions as shown in ( [66, we can have the same convergence metric as that in single objective optimization as an direct extension.
EL Here X1** is calculated
In non-convex functions, ||d.]l are used as the metrics for FMOO, where d, > VF(x)) and A is calculated based on accumulated (stochastic) gradients A. We note, directly extended from
MOO 18 19 d = --" Vx(x)) could also be used as the metries in FMOO, where X is calculated based on full gradients (xx). However, we prefer d, for the following reasons: i). For applying gradient descent with no local steps, d, degenerates to d; ii). Clearly, || 2 ||d;]| as X; is calculated based gradients Fx()).. Hence, ||d.]] is stronger convergence measure for FMOO. iii). A calculated in the algorithm and thus being more practical to use in practice, while X; is unknown. Also, the convergence of d, implicitly indicates A converges to X
B Proof of gradient descent type methods
For gradient descent type methods, each step utilizes full gradient to update and the corresponding parameter À is deterministic. For clarity of notation, we drop for X, that is, we use X; to represent the solution of quadratic problem (Step the algorithm) for task s in the 1-th round.
Lemma 1. Under bounded gradient assumption, the local model updates for any client could be bounded
Ght²k |x xx112 < K2
(4)
H1. (x.))x) -31 -
< K22
(5)
Proof. For one task s [S] and one client E R,, the local update bounded.
1.k Xx x,
could be further
X1
1:ke 2 x
= X,
lkk1
+ mr. V V. (x
1 l
0.1
(6)
$ (1
1 1 1|xc
x
1 2
+ ni K
V (
(7)
15

---

Table 4: Convergence rate (shaded parts are our results) for strongly-convex and non-convex functions, respectively:
Methods
Rate
Assumption
Setting
Algorithm
SC
NC
MGD 8
O(r"), E (0,1)
O
Sequence convergence
MGD
Olexp( -pT))
SMGD 19
(
Lipschitz continuity of À
Vanilla Gradient
SMGD [56
((+)
Convexity property
SMGD 39
0
Given exact solution X*
SMGD
O(+)
0
Asm.
MoCo [9
0
Momentum
CR-MOGM [18
0
FMGDA
Olerpl nT))
((+)
Federated Settings
FSMGDA
OG7)
O
Asm.
Assumptions. Linear search 8 stepsize linear search; sequence convergence
{x}
converges to X=: first moment bound (Asm. 5,2(b) 19)::
f(x))((x())
fx)
a(a + b fxx]ll)) Lipschitz continuity of À (Asm.
5.4
X,
8 [[[((()((x)) (x(())) ....., (V.., V. (x:))
convexity property(H5)
[56]
[xx <) [(x" g||x x=1 almost sure; (a,, B)-iishhtt continuous stochastic gradient (Asm.
(1 +
|xx,
x
x
+ KG
(8)
KG?) (1 ( --
S Σ
(9)
rE(k-1)
-1 (1+x-1)
1 K
s (K 1)
(nk
(10)
s 4n G²
(11)
where the first inequality comes from Young's 's inequality, the second inequality follows from bounded gradient assumption, and the last inequality follows if (1 - K
-1 4 for K 1.
We have the bound for local update for each task 8, He,s, as follows:
H = [V - 112
(12)
fx.
(13)
R
kE[K]
R.
VSa,i(x:)
S...
(14)
K
R
k
SER.
$ マ 2
Σ
X
x
1.k
(15)
R.
kE[K]
EE
- K
(16)
0
Lemma 2. For general L-soooth functions {fss s [S]]. choose the learning rate nh s.t. 7) <
2(14E the update d, of the algorithm satisfies:
3
T)t d < (xx())))) fa(x)) + K2
(17)
16

---

Proof.
fx(x(+1) S (x()) + (Vff(x)) -dd)) + 2 d.
(18)
(x.)) + (V))(x)) A. -mdd) - n (A di) + 1
(19)
2 fx.)) + (V)(()) A. -mdd) - nelld.11 1
2 =
(20)
S (x))) + 2 (x, - A3I + =nilld112 - - + 1
2 Lnblldel dell
(21)
fx(x)) + 1
1
2/2 [x,(xx) - 2 1) 1 - 2 Lone
|d ||
(22)
S.(x)) + 2n 12 1/8 2 //1
Lmp ||d.1?
(23)
The third inequality follows from (A.. d,) 2 ||d 12 since d, a general solution in the convex hull of the family of vectors fAs E [S]} (see Lemma 2.1 [15]). Here d, Eve(s] A and A is calculated by A, but we drop the of À for simplicity.
By setting (1 2 {Lm)
2 1. that is, ne I 2[442 we have
/ || (a((x))) + +2)
(24)
4
B.1 Strongly Convex Functions
Theorem (FMGDA for y-Strongly Convex FMOL). Let mJ r7 such that 1) S zn- nf S 2Lty and 1 Z NT Under Assumptions
[ 3 pick X₁ the final oulput of the FMGDA algorithm with
TkT 222222222222 + 6, where weights wi (1 ) Then, it holds that E 1 I I|xo - x. 1 peppp
Sn K22 G
A/4 A Exels] N [x((x)) [a(xx)] and δ
2n 12
Proof.
fx(x+1)) fxx))) + (V.), mn) + L 1ll
(25)
S (x.))) + (V xxxx.)
/ ||xe-x111
(26)
2
+ (x)) - -.)) + [ll
(27)
where the first inequality is due to L-smoothness, the second inequality follows from p-strongly convex.
Σ SE|S
X - fx((x)
(28)
(x))xxx) x,
# xx x, 1|
Σ
+
1
L
1l l|
2
2
[E(S]
[eE[S]
(29)
X (x)x -e
1
|x
12
Lllndde11
(30)
2
[EE[S]
1 11
= (de, X - -x. mdd - - 11x: x.
2 Lllmddb11
{xx.((x)) -d,, X, n.
[E([
(31)
17

---

(dd,, Xt - xx) -nelld;12 -
P 11xc
x, 1 1
1nn 112 +
M Vxxx((x)) - dr, Xx+1 X+
2
[eE[s]
(32)
$ 217
1
(1|x;- - x.112 - ||x(+1 - -x,113) - 2" ///ld/1l"
1
11
||x; - xx11 22 + 2 Lm ||d?l?
(33)
2
|2
1
+
Σ (xx,) de
+c [c||xx+1 - xx.1²
(34)
4e
H.
1
(I|x: x.112 - ||xc+1 - -x.113)
1 2/1 //.ld.112
2
1 ||x; - xx.12+ Ln 1
(35)
277t
+ 4e
H1 +
(2) 1|2x + |d, 122
(36)
1
(11
1 m1)) ||x xx11² ||x+11 x, x.11²) - 1 2 1 In 1 ||del 12 + H
2
217
p
(37)
where ||x: - x.11² -||x++1 -X, - /|: last inequality.
2 (n, X xx), and we choose e - _/4 in the
From Lemma it is clear that
[fs((e+1)- - ff((x)) S 12n
4 ||d:11?
Th
(38)
S 2 + Ttt
4 ||del?
(39)
A/- Σ M (xx(() - [xxx)) Σ (1)=(x++))-fa6f) - fx(x.)] + (fa((x(+1) - fx(xx)
(40)
RE[S]
#E|Si
1
(11 (1- u (1- - 1-11-11x: -x11²) - (7 1 In 112 ||d.11 ++ 2
1
H. + 2n K22K211 C??
217
11
(41)
11
Σ f - de
(42)
RE[S]
S S Σ (2:)
(43)
*E[S]
< Anj
(44)
By setting ni S
1 we have
2L+H*
A/2
Σ [a((x(11 sx(xx)]
(45)
+E[S]
$ 2np
1
(11-110 2
H
-xxx,xx,, x,112 -x,11 1x441-x,11]
L 2
(46)
P
Averaging using weight w. = (1- (1-1711- and using such weight to pick output x. By using Lemma 1 in (27 with ait. ahve
MuT
E E S ||xo - x. pxpp
) + 8
(47)
2
18

---

Ou + O(6).
(48)
If set n sufficiently small such that 5 ([juep((pPT)), then have the convergence rate
[[Aq] = (0(xxp((pxT))
B.2 Non-Convex Functions
Theorem (FMGDA for Non-convex FMOL), Let = 17 3
2(1LL) Under Assumptions and
if at least one function fex s E [S] is bounded from below by fa then the sequence {x+} output by
|dd]| 16(f2-1.'") + where 2 16nî K2 (2+5(1
FMGDA satisfies: min
Tn
Proof. From Lemma we have
4 I|, - ff((x))))) + fa(x))
2n,
(49)
With constant learning rate n) 1)+
4(
pmmn
KnLK2
d.ll
S
(50)
T
Tn
EE
Note that d 2 used as the metrics for FMOO, where d, X (DDia((FFA)) and X is calculated based on accumulated (stochastic) gradients Å, Then we have
| s 2
x fxxx((x)) de Σ +E|S|
2 |d
(51)
Thus,
16(
sm)))
(1
Σ
|
(52)
T KE[T]
Tn
1
With constant learning rate r and local learning rate f)1. = 0
VTKLGS ) we have
Σ | < (
(53)
T
EE|T]
C Proof of stochastic gradient descent type methods
For stochastic gradient descent type methods, each step utilizes stochastic gradient to update and the corresponding parameter À is stochastic, depending on the random samples in each client. For clarity of notation, we drop * for that is, we use Xē to represent the solution of quadratic problem (Step 6 in the algorithm) for task s in the t-th round.
Lemma Under bounded stochastic gradient assumption, the local model updates could bounded
Gr. 5,
ElIx
EE
t.k
xel12
S $61f [
(54)
E
Σ
A
< S²D
(55)
(E(S)
Further with assumption
we have
H E EllVfs((x..))
A amm -B02.
(56)
19

---

Proof. For one task E [S] and one client E Rg the local update bounded.
Xx
x 1.k x.i
could be further
G
E
X
x
1.
(57)
E
Σ
72 V fo. $5:3)
(58)
rE(K]
S 1/2 k2 D>2
(59)
E
Σ X
S Σ
E
(A)) ||-31]]]
(60)
SE
SE|Si
S S Σ
E
||A:1|]]
(61)
*E|S|
S8 Σ
E
1
Σ
(62)
Rs
+E|S|
iER,
rE[K]
S Σ
Σ
(63)
RA
K
SE|Si
EER.
TE|K]
< D?.
(64)
H = E VI.
E (x,, {.) - -
(65)
E
fx, 81) - fa,
(x lik ct.k)
58,1
(66)
K
kE[K]
<
1
Σ
E
V (x,s(xe, V., 8,11
ctice
(67)
K
Ra
kE[R]
VER,
<
1
Σ
1
aE aEE||x
x + -002)
(68)
K
R.
kE|K]
iE
< am K2 D² + 3
(69)
C.1 Strongly Convex Functions
Theorem 7 (FSMGDA for y-Sttongly Convex FMOL). Let n. = = 52 )T) Under Assumptions
5 and o pick xt the final output of the FSMGDA algorithm with weight Wi (1 2 Then,
it holds that: E ||2O xx
pTT) xx (IT + 5, where A/2- =.eess] X:" [fo(x))) fx.))
and 6 1 52 (an x2 D2 30²) + n²
i
Proof. Taking expectation over random samples conditioning on x,, we have
E X|x++1 - x. 12 E
X2 77 Σ
XA
F.
(70)
SE(S]
20

---

= -|x; x,11 E
X x,: 207e
Σ X
+
The Σ
(71)
sE(s]
RE(S]
=
=|[x= - X,1 11 E
Xx X 277
Σ
X (x,,
(72)
sE|S]
+ X1 x,, 21)
Σ
(x Ex) Ab))
+E
The Σ XA
(73)
+E|S!
RE(S]
=
=|[x; -x,12
X1 x,, 2m
Σ
(74)
sE|91
+
X1 x., 2716
Σ
X (xx,)(( -b:)
+
T1e Σ X
(75)
sE|S]
#E|S]
$ ||x: - x.11
277e
11
Xt x.112+ + Σ
B[A - [s(x,))
+ +c|1x,-xx
-
(76)
2
.E(S]
+
1
4m²BBB B
Σ
fo(Vfo(Xo Et) - A3)
+ 1121LE
Σ بحا
(77)
4e
.E((S]
SELS!
< [x - Xx1 112
2n11
- x2 +
2
(f - fx())))
+ + x,11 (78)
+
1 4 Σ
E
(1:)²
- -(,))) + nF
Σ محاا
(79)
4c xE(S]
+EIS)
< ||x; x.11² 12 - 21p
2 1xx x11 Σ ([AI(A(())) [s(x,))
+ +e|1x,- x.|1
(80)
-E|S]
+
1 4mt S Σ
E V. Ex) -511 + +n,'
Σ xح
(81)
4e #E[S]
NE|S]
< ||x: - x,11² - 2776
121 1Ix: 12 Σ (f,( - sa(x5.)) + +c||x, - xx11
11
(82)
(E(S]
1 An 52 (anj T222 B002 + 5 52 D2
+ 4e
(83)
< (1
nefl ||xe -x.12-210
([N - fa(x))) +E[S]
Σ
(84)
2
+
S (an D2 + 000000++000)) + DD
(85)
where the first equality is due to strongly-convex objective functions, and we set
E[A]((((x) - f((x)) S 2m
1 (1
null ||,
x,122
|xx+1 - 11
(86)
2
21)
*E(S]
21

---

52
D2
+ s Kan D2 + B0²)
(87)
2
Averaging using weight wy = (1- ) )- 1 and using such weight to pick output By using Lemma
1 in 27 with constant learning rate 1/t 1j 22( pTr have
E E|Aq] - Xo x.11 pexpp-
" 2 + 0
0(0)
(88)
2
where 8 == 1 5 (an), 2
By letting 5 17. 1LL 0
and O
(mxx 1,1
vT
E
A S 0
O( T
1
(89)
n
C.2 Non-convex Functions
Theorem 5 (FSMGDA for Non-convex FMOL). Let Ttt 1) 2(14)) Under Assumptions 1 if from an objective fa is bounded from below by famin then the sequence {x,) output by FSMGDA satisfies:
mineery E | 8(f2-1." 8, where å = (25 () K2 + Ba²).
Proof. Similar to Lemma
2
and taking expectation the random data samples conditioning X
we have
Bfa(x(11) S (xx) + (xx)),)) m.d,) T. |.
(90)
= fx((x) (x,)) A,, 1E (A d,) + LBllddde
(91)
1
fx(x)) + E (x,) A m.d
d, d 2
I. d. 11
(92)
2
$ fx,,) + E V La x1) ) 11 [l
-
7/ 1.
+
LEn d
(93)
2
1
fx)) + E V f. (x) - 1
(1-2") -" 2 Lm E
(94)
where d, = Eess)) X A and " is calculated by the accumulated stochastic gradients 4 E [S]. but drop the of À for simplicity.
With V/ S 2[++) we have
2 (fa(x(+)) + fx(x)) E V - 1!12
(95)
4
S - + fx(x)) + (am K2 B0²2)
(96)
With constant learning rate 7) = 1)+
1
Σ 1E[21
d, 2
4 (fx(x)) Eff(x++1))
+ +2(nn Bo²
(97)
T
nT
Note that we want to use | are used as the metrics, where d, X ((Dia((FA)) and X is calculated based on accumulated (stochastic) gradients A.. Then we have
| | < 2
Σ sE]S]
xxV((( d:
+2 +2
(98)
22

---

With constant learning rate 7) = 1) and averaging from T communication rounds, we have
Σ
Elāe
Σ
2E
Σ
i
f d:
+ T
2E
||:
(99)
T [E|T]
(E(T]
sE|S)
tE[T]
1
- T 1E[2]
Σ 2SE Σ
(xx(V]s(x)) - 13)l
21 d,
(100)
T
SE[S]
BE(2]
8 (f((x1)
Ef (x((x)+1)
+ (25 + +)) K B022
(101)
nfT
With constant learning rate 1) = 1
VT
local learning rate n)s. = 0 7774
and _ = 17.
1 = 01
(102)
T 1ET
VT
D Further Experiments and Additional Results
In the following, we provide the detailed machine learning models for our experiments:
1) MultiMNIST Datasets and Learning Tasks: We test the convergence performance of our algorithms using the "MultiMNIST" dataset [53]. which multi-task learning version of the MNIST dataset (57) from LIBSVM repository. Specifically, to convert the hand-written classification problem into a multi-task problem, we randomly chose 60000 images and divided them into M agents. Each agent has two tasks, where each task has = 60000/ (2 M) samples. Due to space limitations, we only present the convergence results for the case of non-i.i.d. data partition (i.c., data heterogeneity) and relegate the results of the i.i.d. data case to the appendix. For the non-i.i.d. data partition, we use the same data partition strategy as in (28), where each client can access data with most two labels. In experiments, group of images is positioned in the top left corner, while another group of images is positioned in the bottom right. The two tasks are task "L" (to categorize the tep-left digit) and task "R" (to classify the bottom-right digit). The overall problem is to classify the images of different tasks at different agents. All algorithms use the same randomly generated initial point. Here, present experiments with M 10 agents, where each agent has two tasks (i.e., A E IR x2 is an all-one matrix). We set the local update rounds K = 10. Experiments with a larger number of agents (M 5, 10, 30) are provided here. The learning rates are chosen as Vi 0.1 and = 0.1, Vt.
2): River Flow Dataset and Learning Tasks: larger sizes. In this experiment, we use the River Flow dataset which is for flow prediction flow at eight locations within the Mississippi River network. Thus, there are eight tasks in this problem. In this experiment, we set 7 = 0.001, 7/8 = 0.1, M = 10, and keep the batch size = 256 while comparing K, and keep K 30 while comparing the batch size. To better visualize different tasks, we illustrate the normalized loss in radar charts in Fig. 2(b) We again verify that utilizing a larger training batch size and conducting additional local steps K results in accelerated convergence.
We further test algorithms on FMOL problems of
3): CelebA Dataset and Learning Tasks: We utilize the CelebA dataset (55], consisting of 200K facial images annotated with 40 attributes. We approach each attribute a binary classification task, resulting in a 40-way multi-takk learning (MTL) problem. To create a shared representation function, we implement ResNet-18 (58) without the final layer, attaching linear layer to each attribute for classification. In this experiment, we set πu = 0.0005, 7 = 0.1, M = 10, and K = 10. Figure 3 displays radar chart depicting the loss value of each binary classification task. In Figure 3 demonstrate the efficacy of our FMGDA and FSMGDA algorithms in both i.i.d. case and non-i.i.d.
case.
Experiments on i.i.d. data: First, we compare the convergence results with the same experimental settings in our Section. 5 tested on the i.id data. As shown in Fig. both FMGDA and FSMGDA
23

---

0
22
36R
23
37
16
15
25
15
25
35
13
33
13
12
10
30
11
24
31
(a) Non-i.i.d, case.
(b) i.i.d case.
Figure 3: Experiments CelebA dataset.
Cook
Busk
10
Derations
Iivection
(a) Loss v.s. Communication rounds.
(b) Loss v.s. Local update rounds.
Figure 4: Experiments on i..dd data.
successfully converged in i.i.d. data, and the algorithm with a larger training batch size and more local updates K may converge faster.
Impact of the number of clients: In this experiment, we choose the different number of clients from the discrete set (5, 10, 30) and fix learning rates at 0.1 and local update rounds at 10. As shown in Fig. [5) a larger number of workers leads faster convergence rates of our proposed algorithms both in i.i.d. case and non-i.i.d. case; this is mainly because more samples have been used while training while having more workers.
Beck
0.025
0.000
00338
6.0130
1:00
1.0
00175
17
60125
M-30
0.013
00150
00125
6.0055
00000
8.005
0.00
0.00
0.05
028155
00100
00858
00825
20
40
100
411
30
160
20
30
100
26
40
60
80
100
Iterations
Iterations
Iteratio ms
Iterations
(a) i.i.d. case.
(b) Non-i.i.d. case.
Figure 5: Loss value comparisons of algorithms on a different numbers of clients M.
0525
8.035
0.0215
Dic
0JXZ5
0.000
0.006
0.0075
0515
8.000
0.6125
0.0050
03120-
0.000
0,0155
00000
0106
5.005
0.0850
28
40
60
30
Barations
Hoa Mlrrations
Dar aaarrt
(a) FMGDA.
(b) FSGMDA.
Figure 6: Comparisons of different step-sizes.
Impact of the Step-size: In this experiment, we choose the value of the learning rate yJr. from the discrete set (0.05, 0.01, 0.13 and fix worker number at 5, local update rounds at 10. As shown in Fig. (, larger local step-sizes lead to faster convergence rates on both FMGDA algorithm and FSMGDA algorithm.
24


Reviews:
[{"review_id": "O4MY9kS3Ug", "reviewer": "Reviewer_8EfV", "summary": "In this paper, the authors present a new distributed optimization problem named Federated Multi-Objective Optimization (FMOO) along with its corresponding algorithms. The idea behind FMOO is to reformulate the classical Multi-Objective Optimization (MOO) problem into a federated learning framework, where each client holds a specific subset of objectives. This formulation encompasses both existing centralized and federated MOO problems as special cases. In the proposed Multiple Gradient Descent Averaging strategy, each client calculates local updates for its respective objectives and transmits them to the server. The server, in turn, uniformly aggregates these local updates for each objective and subsequently constructs a combined set of updates that span across different objectives. This combination is achieved by solving a quadratic optimization problem.\n\nThe authors instantiate the strategy in the form of two algorithms: The Federated Multi-Gradient Descent Averaging (FMGDA) algorithm involves complete gradient evaluations within each client, and the Federated Stochastic Multi-Gradient Descent Averaging (FSMGDA) algorithm employs stochastic sampling. The authors provide a convergence analysis for both FMGDA and FSMGDA, encompassing scenarios with strongly-convex and non-convex objectives.\n", "questions": "The current reviewer was wondering whether the parameter combination across objectives (as in Step 6 of the proposed algorithm) can be performed within each client, effectively reducing the communication cost per training iteration to O(M).", "limitations": "It would be beneficial if the authors added a paragraph explicitly discussing the limitations of the present study.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Multi-objective optimization is a rapidly developing research area. The proposed approach extends the applicability and scope of federated learning, opening new possibilities for solving complex optimization tasks.\n- The proposed algorithms are commendable for its simplicity and apparent straightforwardness of implementation.\n- The authors provide theoretical convergence guarantees enhancing the significance of their work. The convergence analysis not only covers the proposed problem setting but also provides good insights into classical central MOO scenarios.\n- The paper is generally well-written, although I have not thoroughly examined the proof. Including an appendix that addresses MOO challenges without heavily relying on external references is good.\n", "weaknesses": "- The communication cost per training interaction appears to be high for the proposed FMGDA algorithm, with a complexity of O(M x S) (M: number of clients, S: number of objectives). This cost could be a limiting factor, especially in scenarios with a large number of objectives and clients.\n- Replicating the experiments in section 5 might be challenging based solely on the information provided in the main paper. Important details, including baseline learning algorithm specifics, are only available in the supplemental materials. Consolidating all important information in the main paper would improve accessibility.\n- Minor comment: Table 3 might be better placed in the main paper. Additionally, it would be helpful to explicitly define $S_i$ before its usage (defined in the table).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the review and the constructive comments. We believe the valuable suggestions from the reviewer have helped us significantly improve the quality of this paper. The detailed point-by-point responses are as follows:\n> 1. The communication cost per training interaction appears to be high for the proposed FMGDA algorithm, with a complexity of O(M x S) (M: number of clients, S: number of objectives). This cost could be a limiting factor, especially in scenarios with a large number of objectives and clients.\n\n**Our Response:** Thanks for your insightful comments. Communication cost is one of the major concerns in distributed learning systems. By reducing the communication frequency (i.e., utilizing local update steps), our FMOO algorithms can already reduce the total number of communication rounds by a factor of $K$, where $K$ is the local update steps. \n\nIn terms of the communicaion cost per round, we agree with the reviewer that the per-round communication cost could be high with a large number of objectives and clients. However, such a high per-round communication cost is primarily due to the nature of the underlying FMOO learning system, rather than a limitation of our proposed algorithm for FMOO. In this paper, we focus on developing the first federated learning algorithm for FMOO with convergence guarantee. We will further consider communication-efficient FMOO in our future studies, which deserves an independent paper but beyond the scope of this work.\n\n> 2. Replicating the experiments in section 5 might be challenging based solely on the information provided in the main paper. Important details, including baseline learning algorithm specifics, are only available in the supplemental materials. Consolidating all important information in the main paper would improve accessibility.\n\n**Our Response:** Thanks for your comments. As you suggested, we will relocate the experimental description along with important details from the appendix to the main paper for a clear and accessible presentation in the revised version.\n\n> 3. Minor comment: Table 3 might be better placed in the main paper. Additionally, it would be helpful to explicitly define $S_i$ before its usage (defined in the table).\n\n**Our response:** Thanks for your suggestions. We will move Table 3 from the Appendix to the main paper and define $S_i$ before its first usage for a clear presentation of notations.\n\n> 4. The current reviewer was wondering whether the parameter combination across objectives (as in Step 6 of the proposed algorithm) can be performed within each client, effectively reducing the communication cost per training iteration to O(M).\n\n**Our response:** Thanks for your comments. We believe the problem of reducing the per-round communication cost to $O(M)$ is an interesting and promising topic for future exploration. However, we outline several challenges in pursuing this direction:\n\n1. In our general FMOL framework, achieving $O(M)$ per-round communication cost is challenging. The challenges arise from the inherent *data heterogeneity* and *objective heterogeneity*, two characterize in FMOL problems. Specifically, due to data heterogeneity, each client $i$ can only possess an estimation of the local objective function $f_{s, i}$ corresponding to its local data, rather than the global function $f_s$ for each objective $s$. Consequently, this restricts the computation operation of parameter combinations to the set of objectives at each client. Specifically, each client can only obtain a shared descent direction for local objectives at each client ($f_{s, i}, \\forall s \\in [S]$, rather than $f_{s}, \\forall s \\in [S]$). Given the nonlinear nature of this process, the aggregation of these parameter combinations across multiple clients might need completely new approaches, obviously beyong simple averaging.\n\n2. This challenge is compounded by situations in which distinct clients pursue varying sets of objectives, stemming from *objective heterogeneity*. That is, the parameter combinations across clients are the estimations of common descent directions for different objectives sets. In these cases, achieving a reduction in communication costs becomes even more challenging.\n\nWhile addressing the challenges above goes beyond the scope of our current paper, we appreciate the valuable insights from the reviewer, which could lead to new algorithms with low per-round communication cost different from traditional algorithm-agnostic approaches, such as gradient quantization and sparsification. \n\n> 5. It would be beneficial if the authors added a paragraph explicitly discussing the limitations of the present study.\n\n**Our response:** Thanks for the suggestion. We will add one paragraph to discuss the limitations in the revision."}, {"review_id": "bLHWEPLH3X", "reviewer": "Reviewer_kXdB", "summary": "The paper tackles the problem of Multi Objective Optimization in the Federated Learning Setting, which is a practically relevant problem. The proposed algorithms have same order of convergence rates to the single objective counterpart. ", "questions": "1. There is significant emphasis on client objective heterogenity, however the only occurence of this seems to be the range of the function f_s in the Theorem 1, which seems like very standard convergence rate analysis. Was there some investigation on how the constant factors in the rate deteriorate depending on the heterogenity of the client objectives, tham just the range of f_s?\n2. Although the order of convergence is much better than the baselines presented in Table 1, I wonder why they were not compared against in the experiments? It would be a good check on the practicality of the constants in the bound in Theorem 1. ", "limitations": "The work is technically solid and has no major limitations. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The motivation and related work is very well written. \n2. A variety of experiment settings are considered which complements the theory very well.\n3. It is interesting to see the convergence bounds are the same as the single objective counterpart.", "weaknesses": "There seem to be no major weaknesses of the paper. However, it would be good to highlight the non-trivial (if any) proof techniques needed to deduce the results. Also, refer to the questions. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the review and the constructive comments. We believe the valuable suggestions from the reviewer have helped us significantly improve the quality of this paper. The detailed point-by-point responses are as follows:\n\n**General response about the constants in our results:** To assess the impact of the constants in our theorems, we conducted an ablation study encompassing various elements of the learning setting. This encompassed crucial parameters such as the number of local update steps ($K$), batch size, task number, data heterogeneity, number of clients, and learning rate. However, we note that certain constants tied to the objective functions, such as the Lipschitz constant, strongly-convex constant $\\mu$, minimal function value $f_s^{min}$ and full gradient bound $G$, present challenges in quantification. More importantly, these constants are inherently tailored to the intricacies of each unique problem, rendering their interpretation less straightforward and less readily meaningful.\n\n> 1. There is significant emphasis on client objective heterogenity, however the only occurence of this seems to be the range of the function f_s in the Theorem 1, which seems like very standard convergence rate analysis. Was there some investigation on how the constant factors in the rate deteriorate depending on the heterogenity of the client objectives, than just the range of f_s?\n\n**Our response:** Thanks for your comments. The objective heterogeneity is not only about the function range of $f_s$, but also how each objective function $f_s$ is distributed accross clients by $f_{s, i}$ and its property with local dataset such as full gradient bound $G$. Due to these complications, it is hard to quantify the objective heterogeneity in a straightforward manner and then study its effect. To address this challenge, we provide ablation studies of all elements that could have direct impact on the objective heterogeneity, such as task number (different datasets), data heterogeneity (i.i.d. vs non-i.i.d. data), and number of clients.\n\n> 2. Although the order of convergence is much better than the baselines presented in Table 1, I wonder why they were not compared against in the experiments? It would be a good check on the practicality of the constants in the bound in Theorem 1.\n\n**Our response:** Thanks for your comments. In Table 1, the baselines were all designed for the centralized learning setting. First, we had an direct comparison with these baselines, as shown in Lines 379-386, Sec. 5 1-c. Moreover, it is worth noting that distributed version of these baselines can be interpreted as special cases of our FMGDA and FSMGDA algorithms with $K=1$ (no local update). So through the ablation studies of local udpate steps and data heterogeneity, the distributed version of the these baselines were also compared. See, e.g., Sec. 5 1-b, Table 2, and Fig 4(b) in the Appendix. According to these results, our algorithms have faster convergence than these baselines in different datasets. "}, {"review_id": "DfOLvGjJTL", "reviewer": "Reviewer_gLj4", "summary": "This paper generalizes multi-objective optimization to the federated learning paradigm, and proposes an algorithm for both full-batch and stochastic settings. Theoretical analysis shows same convergence rates as those of their algorithmic counterparts in the single-objective federated learning.", "questions": "1. What is the direction bias in FSMGDA after having assumption 4? (Lemma 2 in [1])\n\n[1] Fernando et al. Mitigating gradient bias in multi-objective learning: A provably convergent approach. ICLR 2023\n", "limitations": "No", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper studies an important and unsolved problem. The proposed setting is meaningful for many practical usages.\n\n2. The idea to use $(\\alpha,\\beta)$-Lipshitzness to eschew incorrect assumption in SMGD is insightful. Though I am not very convinced, it provides a different way to consider this problem.", "weaknesses": "1. Since [1] has shown that SMGD will not converge to Pareto optimal for some stochastic cases due to the incorrect assumption on Lipschitz continuity of $\\lambda$, I am not convinced how the $(\\alpha,\\beta)$-Lipshitzness can help the algorithm to converge, as the paper claims that Algorithm 1 can reduce to SMGD. Does Assumption 1 can lead to Lipschitz continuity of $\\lambda$?\n\n2. (Similar to point 1) The appendix provides further analysis for SMGD under assumption 4. After I checked the appendix in [1], I found an empirical test with Gaussian stochastic noise more aligned with practical cases (figure 5). The results show that SMGD will not converge to Pareto optimal. This conclusion is contradictory to the claim in this paper, so I am concerned about whether the assumption is still not natural or the proof is wrong. Given that I think Gaussian stochastic noise cases satisfy Assumption 4 (not carefully checked), I suspect some proof details are incorrect.\n\n[1] On the Convergence of Stochastic Multi-Objective Gradient Manipulation and Beyond. NeurIPS 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and constructive comments. We believe the valuable suggestions have helped us significantly improve the quality of this paper. The detailed point-by-point responses are as follows:\n\n> 1. Since [R1] has shown that SMGD will not converge to Pareto optimal for some stochastic cases due to the incorrect assumption on Lipschitz continuity of $\\lambda$, I am not convinced how the $(\\alpha, \\beta)$-Lipshitzness can help the algorithm to converge, as the paper claims that Algorithm 1 can reduce to SMGD. Does Assumption 1 can lead to Lipschitz continuity of $\\lambda$?\n\n**Our response:** Thanks for your comments. There appears to be some misunderstandings on the assumptions used in this paper, and there is no contradiction with the claims in [R1]. Since the reviewer's questions are relatively complicated, we structure our responses in three parts as follows:\n\n1. Our Assumption 1, $L$-Lipschitz continuous gradient assumption, is a standard assumption in optimization that characterizes the smoothness of a function. It is important to note that this assumption is completely different from the $\\lambda$-Lipschitz continuity assumption, which focuses on the properties of $\\lambda$, which is an implicit function of the stochastic gradient updates. Also, our $(\\alpha, \\beta)$-Lipschitz continuous stochastic gradient assumption (Assumption 4) is also completely different from the $\\lambda$-Lipschitz continuity assumption (see below for further details). Thus, our Assumptions 1 and 4 do *not* imply or lead to the $\\lambda$-Lipschitz continuity mentioned in [R1]. \n\n2. The $\\lambda$-Lipschitz continuity is never used in our paper. Instead, we propose a new $(\\alpha, \\beta)$-Lipschitz continuous stochastic gradient assumption in Assumption 4. The intuition behind Assumption 4 is that the rate of change of the stochastic gradient estimation stays within reasonable bounds and retains a satisfactory level of accuracy across any two independent samples. Thanks to this new assumption, our proofs will not run into any incorrect use of the $\\lambda$-Liptschitzness assumption, even when the our algorithm reduces to SMGD in special cases.\n\n3. We note that the case with a large variance in stochastic gradients as shown in [R1] does not apply in this work. Specifically, our assumptions introduces a modest criterion for the stochastic gradient estimation that preclude cases with large variance in stochastic gradients. To see why this is the case and for a deeper understanding of our assumptions, please see our detailed discussions outlined in Lines 315-327, the systematic comparative analysis with other assumptions in Lines 556-599 in the Appendix, and our response to the reviewer's Comment 2.\n\n> 2. (Similar to point 1) The appendix provides further analysis for SMGD under assumption 4. After I checked the appendix in [R1], I found an empirical test with Gaussian stochastic noise more aligned with practical cases (figure 5). The results show that SMGD will not converge to Pareto optimal. This conclusion is contradictory to the claim in this paper, so I am concerned about whether the assumption is still not natural or the proof is wrong. Given that I think Gaussian stochastic noise cases satisfy Assumption 4 (not carefully checked), I suspect some proof details are incorrect.\n\n**Our response:** Thanks for your comments. Again, we remark that there is actually no contradiction with the claims in [R1], and there is no issue in our proof and anaysis. Note that [R1] showed that stochastic gradient manipulation techniques, such as SMGD [R2], PCGrad [R3], and CAGrad [R4], fail to converge when the given samples contain Gaussian stochastic noise. However, it is important to note that the example in [R1] does *not* disprove the theoretical results in [R2, R3, R4]. This is due to the simple logical fact that the example in [R1] does *not* satisfy the respective sufficient conditions in [R1, R2, R3] for their theoretical convergence results to hold. \n\nThe situation is also the same when comparing our results with [R1], i.e., the example in [R1] does not satisfy the sufficient conditions in our theoretical results. Specifically, in order to ensure Pareto stationary convergence in non-convex functions, Corollary 6 requires a sufficient condition that $\\beta = \\mathcal{O}(\\eta)$. Applying this sufficient condition in the experiment settings in [R1], we have $\\beta = \\mathcal{O}(0.006/\\sqrt{T})$. However, the large variance setting in Gaussian stochastic noise for the example in [R1] leads to $\\beta = \\Omega(1)$, which clearly violates our sufficient condition. Hence, there is no logical contradiction between our work and [R1], and the example constructed in [R1] cannot be used to disprove our theoretical results.\n\n[R1] Zhou, Shiji, et al. \"On the convergence of stochastic multi-objective gradient manipulation and beyond.\" Advances in Neural Information Processing Systems 35 (2022): 38103-38115.\n\n[R2] Sener, Ozan, and Vladlen Koltun. \"Multi-task learning as multi-objective optimization.\" Advances in neural information processing systems 31 (2018).\n\n[R3] Yu, Tianhe, et al. \"Gradient surgery for multi-task learning.\" Advances in Neural Information Processing Systems 33 (2020): 5824-5836.\n\n[R4] Liu, Bo, et al. \"Conflict-averse gradient descent for multi-task learning.\" Advances in Neural Information Processing Systems 34 (2021): 18878-18890.\n\n\n> 3. What is the direction bias in FSMGDA after having assumption 4? (Lemma 2 in [R5])\n\n**Our response:** Thanks for your comment. The direction bias between the stochastic gradient and common descent gradient in FSMGDA is $H_{t, s} = \\mathbb{E} \\left\\| \\nabla f_s(x_t, \\xi_t) - \\Delta^t_s \\right\\|^2 \\leq \\alpha \\eta_L^2 K^2 D^2 + \\beta \\sigma^2$ as shown in Lemma 3 (Line 647).\n\n\n[R5] Fernando, Heshan Devaka, et al. \"Mitigating gradient bias in multi-objective learning: A provably convergent approach.\" The Eleventh International Conference on Learning Representations. 2022."}, {"review_id": "WtGT6zator", "reviewer": "Reviewer_TvWz", "summary": "The authors  propose a federated multi-objective learning (FMOL) framework with multiple clients distributively and collaboratively solving an MOO problem while keeping their training data private. Notably, their FMOL framework allows a different set of objective functions across different clients to support a wide range of applications, which advances and generalizes the MOO formulation to the federated learning paradigm. \n\nFor this FMOL framework, they propose two new federated multi-objective optimization (FMOO) algorithms called federated multi-gradient descent averaging (FMGDA) and federated stochastic multi-gradient descent averaging (FSMGDA). Both algorithms allow local updates to significantly reduce communication costs, while achieving the same convergence rates as those of the their algorithmic counterparts in the single-objective federated learning. ", "questions": " - Line 52-54, what this challenge means? What means \"FMOL algorithms could be extremely sensitive to small perturbations in the determination of common descent direction among all objectives\"? Can the authors give a more detailed explanation?\n - Since each client may perform different tasks, how can the authors guarantee the network used in each client is the same?", "limitations": "See Weaknesses and Questions.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": " - The motivation is clear and this paper is well written.\n - The theoretical analysis of this paper is sufficient.", "weaknesses": "- How does the algorithm proposed in this paper solve the problem of data heterogeneity? In Algorithm 1, there is no design to solve data heterogeneity.\n- Experimental results compared with FedMGDA+ [1] are lacking. FedMGDA+ is also suitable for the experimental setting in this paper. \n- Experiments with different tasks for each client are missing. In the experiments of this work, each client has the same task. Since the authors claim that they are a generic algorithm that can deal with different setting, the experiments should be more comprehensive.\n\n\n\n\n[1] Z. Hu, K. Shaloudegi, G. Zhang, and Y. Yu, “Federated learning meets multi-objective optimization,” IEEE Transactions on Network Science and Engineering, 2022.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the review and the constructive comments. We believe the valuable suggestions from the reviewer have helped us significantly improve the quality of this paper. The detailed point-by-point responses are as follows:\n\n> 1. How does the algorithm proposed in this paper solve the problem of data heterogeneity? In Algorithm 1, there is no design to solve data heterogeneity.\n\n**Our response:** Thanks for your comment. In Algorithm 1, our basic idea and key technique to mitigate data heterogeneity is the use of a *two-sided learning rates*, where a local learning rate $\\eta_L$ is used for local update (Step 2 in Algorithm 1) and a global learning rate $\\eta_t$ is used for global update (Step 7 in Algorithm 1). With this two-sided learning rate approach, we can set a relatively small local learning rate $\\eta_L$ to allow more local steps without local models drifting too far across clients. Also, we can set a relatively large global learning rate $\\eta_t$ to ensure sufficiently fast convergence progress. By doing so, the \"model drift\" problem due to data heterogeneity could be properly controlled.\n\n> 2. Experimental results compared with FedMGDA+ [R1] are lacking. FedMGDA+ is also suitable for the experimental setting in this paper.\n\n**Our response:** Thanks for your comment. Our paper formulates a general federated multi-objective learning (FMOL) framework that is different from the setting in [R1]. Thus, our algorithms are *not* directly comparable to FedMGDA+. Specifically, we consider a FL system with $M$ clients and each client targets at $S$ tasks/objectives. In contrast, Ref. [R1] *reformulates* the classic single-objective FL as a multi-objective optimization problem, where each client has one distinctive objective. Under our experimental setting, it is unclear how to modify FedMGDA+ to allow multiple objectives at each client. \n\n[R1] Z. Hu, K. Shaloudegi, G. Zhang, and Y. Yu, “Federated learning meets multi-objective optimization,” IEEE Transactions on Network Science and Engineering, 2022.\n\n> 3. Experiments with different tasks for each client are missing. In the experiments of this work, each client has the same task. Since the authors claim that they are a generic algorithm that can deal with different setting, the experiments should be more comprehensive.\n\n**Our response:** Thanks for your comment. There appears to be some misunderstandings on our experiments. In our experiments, each client has the *same set of multiple tasks* rather a single same task. For example, each client has two tasks for the MultiMNIST dataset, eight tasks for the River dataset, and 40 tasks for the CelebA dataset. Also, these could be different across clients. Thus, our experiments already considered the *generic* settings consistent with our the FMOL formulation in Sec. 3.2. \n\n> 4. Line 52-54, what this challenge means? What means \"FMOL algorithms could be extremely sensitive to small perturbations in the determination of common descent direction among all objectives\"? Can the authors give a more detailed explanation?\n\n**Our response:** Thanks for your comment. One of the key challenges for gradient-based multi-objective optimization (MOO) is to compute an accurate common descent direction that can decrease all the objectives at the same time, given each objective's stochastic gradients. The common descent direction can be determined by solving a *quadratic programming* (cf. Step 7 in our Algorithm 1). However, the process of solving this quadratic programming to find a common descent direction is sensitive to each objective's stochastic gradient estimation. When such estimation is perturbed by noise, the common descent direction obtained from solving the quadratic programming could be biased and even lead to divergence issues. For example, even in centralized MOO, when the stochastic gradient has large Gaussian noise, divergence problems of many algorithms have been observed [5,13]. This situation is further excerbated by the data heterogeneity and objective heterogeneity as described in Line 45-52, which could inject additional bias in the evaluation of each objective's gradient estimation. As a result, FMOL algorithms could be extremely sensitive to perturbations and noises in the determination of common descent direction among all objectives.\n\n> 5. Since each client may perform different tasks, how can the authors guarantee the network used in each client is the same?\n\n**Our response:** Thanks for your comment. There appears to be some confusion between tasks (i.e., the $f(\\cdot)$) and network (i.e., the $\\mathbf{x}$-parameters) in our FMOL. To clarify, we start with the traditional multi-objective optimization (MOO). In MOO, the goal is to simultaneously optimize multiple objective functions (i.e., tasks) denoted as $\\min_{x} (f_1(x), f_2(x), \\cdots, f_S(x))$. That is, MOO seeks to find a *common solution* $\\mathbf{x}$ (i.e., the network parameters) for the *entire set of objectives/tasks*. In other words, the network/model $\\mathbf{x}$ is the same across all tasks. Following the same token, our FMOL extends the MOO problem setting to the federated learning paragdigm, where each client maintains a local copy of the same global network/model parameters (i.e., $\\mathbf{x}$) for all tasks across the federated learning system. Thus, the network used in each client is the same *by design*."}, {"review_id": "nwUy1l845w", "reviewer": "Reviewer_nQxG", "summary": "The paper proposes a new federated multi-objective learning (FMOL) framework where multiple clients can collaboratively solve an MOO problem while keeping their training data private. The authors propose two new federated multi-objective optimization (FMOO) algorithms called federated multi-gradient descent averaging (FMGDA) and federated stochastic multi-gradient descent averaging (FSMGDA) that allow local updates to reduce communication costs while achieving the same convergence rates as those of their algorithmic counterparts in the single-objective federated learning. The authors claim that their work is the first systematic attempt to bridge the gap between federated learning and MOO.", "questions": "No.", "limitations": "Yes, limitations are addressed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper addresses an important and timely problem of extending multi-objective optimization to the federated learning paradigm, considering both objective and data heterogeneity.\n\nThe paper proposes two new FMOO algorithms, FMGDA and FSMGDA, with provable Pareto-stationary convergence rate guarantees. Theoretical analysis of convergence rates looks reasonable.\n\nThe effectiveness of the algorithms is supported with comprehensive experimental results.", "weaknesses": "I find no big issues. Maybe assumption 4 is not so common.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the positive review and the constructive comments.\n\n> I find no big issues. Maybe assumption 4 is not so common.\n\n**Our response:** Thanks for the positive review. The fact that our $(\\alpha, \\beta)$-Lipschitz continuous stochastic gradient assumption (Assumption 4) being uncommon is one of the novelties for our paper. Assumption 4 is an natural generalization of previous assumptions in MOO. The intuition behind Assumption 4 is that the rate of change of the stochastic gradient estimation stays within reasonable bounds and retains a satisfactory level of accuracy across any two independent samples. Thanks to this new assumption, we can provide the theoretical analyses in FMOO with data heterogeneity and objective heterogeneity."}]

Author rebuttal:

Meta-review: This paper presents a formulation of a new problem, federated multi-objective learning, and proposes a method to solve the problem for the first time. This is a borderline case because the average score is close to the threshold and the review scores are significantly diverging, from 3 to 7. However, I believe that the formulation of a new problem can be regarded as an important contribution of this work although the formulation is kind of an extension to federated learning and the problem setting is not very realistic. The methodology to solve the problem is reasonable and shows its effectiveness, but it is also true that it has known limitations such as large communication costs. After rebuttal, a large portion of concerns appear to be addressed but there exists a remaining concern on the theoretical side. Considering all these facts, I would recommend accepting this paper to motivate the research community in federated learning towards this new problem besides acknowledging the technical contributions of this work.
Decision: Accept (poster)