Learning to Collaborate
Authors: Sen Cui
Jian Liang
Weishen Pan
Kun Chen
Changshui Zhang
Fei Wang
Venue: ICLR 2022 Submitted (2022)
Keywords: collaboration equilibrium

Abstract: In this paper, we focus on effective learning over a collaborative research network involving multiple clients. Each client has its own sample population which may not be shared with other clients due to privacy concerns. The goal is to learn a model for each client, which behaves better than the one learned from its own data, through secure collaborations with other clients in the network. Due to the discrepancies of the sample distributions across different clients, it is not necessarily that collaborating with everyone will lead to the best local models. We propose a learning to collaborate framework, where each client can choose to collaborate with certain members in the network to achieve a ``collaboration equilibrium", where smaller collaboration coalitions are formed within the network so that each client can obtain the model with the best utility. We propose the concept of benefit graph which describes how each client can benefit from collaborating with other clients and develop a Pareto optimization approach to obtain it. Finally the collaboration coalitions can be derived from it based on graph operations. Our framework provides a new way of setting up collaborations in a research network. Experiments on both synthetic and real world data sets are provided to demonstrate the effectiveness of our method.

Under review as a conference paper at ICLR 2022
LEARNING TO COLLABORATE
Anonymous authors
Paper under double-blind review
ABSTRACT
In this paper, we focus on effective learning over a collaborative research network involving multiple clients. Each client has its own sample population which may not be shared with other clients due to privacy concerns. The goal is to learn a model for each client, which behaves better than the one learned from its own data, through secure collaborations with other clients in the network. Due to the discrepancies of the sample distributions across different clients, it not necessarily that collaborating with everyone will lead to the best local models. We propose learning to collaborate framework, where each client can choose collaborate with certain members in the network to achieve a "collaboration equilibrium", where smaller collaboration coalitions are formed within the network so that each client can obtain the model with the best utility. We propose the concept of benefit graph which describes how each client can benefit from collaborating with other clients and develop a Pareto optimization approach to obtain it. Finally the collaboration coalitions can be derived from it based on graph operations. Our framework provides new way of setting up collaborations in a research network. Experiments on both synthetic and real world data sets are provided to demonstrate the effectiveness of our method.
INTRODUCTION
Effective learning of machine learning models over a collaborative network of data clients has drawn considerable interest in recent years. Frequently, due to privacy concerns, we cannot simultaneously access the raw data residing on different clients. Therefore, distributed (Li et al. (014) or federated learning (McMahan et al. 2017) strategies have been proposed, where typically model parameters updated locally at each client with its own data and the parameter updates, such as gradients, transmitted out and communicate with other clients. During this process, it is usually assumed that cost, i.e., every client is willing to participate in the
the participation in the network comes collaboration. However, this is not always true in reality.
One example is the clinical research network (CRN) involving multiple hospitals (Fleurence et al.) 2014). Each hospital has its own patient population. The patient data are sensitive and cannot be shared with other hospitals. If we want to build a risk prediction model with the patient data within this network in a privacy-preservie be obtained through participating the CRN compared the one built from its own data collected from various clinical practice with big efforts. In this scenario, there has been a prior study showing that the model performance can decrease when collaborating with hospitals with very distinct patient populations due to negative transfer induced by sample distribution discrepancies (Wang et al. 2019 Pan & Yang 2009).
way, the expectation from each hospital is that a better model can
With these considerations, in this paper, we propose novel learning to collaborate framework. We allow the participating clients in a large collaborative network to form non-overlapping collaboration coalitions. Each coalition includes subset of clients such that the collaboration among them can benefit their respective model performance. We aim at identifying the collaboration coalitions that can lead to a collaboration equilibrium, i.e., there are no other coalition settings that any of the individual clients can benefit more (i.e., achieve better model performance).
To obtain the coalitions that can lead collaboration equilibrium, we propose Pareto optimization framework to identify the necessary collaborators for each client in the network to achieve its maximum utility. In particular, we optimize a local model associated with specific client the

---

Under review as a conference paper at ICLR 2022
(4) Benefit Grrpph
Finding coalitiinn
Re-build Benefit Graph
(d) Collabonation Equalibrium
Figure 1: (a) The benefit graph all clients; (b) Finding all stable coalitions and remove them; (c) reconstruct the benefit graph on the remaining clients; after Is removed, I re-identifies its necessary collaborators in { [ 14,11, [5, which is { as the added the red arrow from 1 to I in the figure; (d) iterate (b) and (c) until achieving collaboration equilibrium.
Pareto front of the learning objectives of all clients. Through the analysis of the geometric location of such an optimal model on the Pareto front, we can identify the necessary collaborators of each client. The relationships between each client and its necessary collaborators can be encoded in a benefit graph, in which each node denotes a client and the edge from I to I' represents I is one of the necessary collaborators for 1', as exemplified in Figure ] (a). Then we can derive the coalitions corresponding to the collaboration equilibrium through an iterative process introduced as follows. Specifically, we define a stable coalition as the minimum set such that its all involved clients can achieve its maximal utility. From the perspective of graph theory, these stable coalitions are actually the strongly connected components of the benefit graph. For example, C' = {I',12, ]a] in Figure (b) is stable coalition all clients can achieve their best performance by collaborating with the clients in C (compared with collaborating with other clients in the network). By removing the stable coalitions and re-building the benefit graph of the remaining client iteratively as shown in Figure [ (b) and (c), we can identify all coalitions as in Figure T (d) and prove that the obtained coalitions can lead to a collaboration equilibrium.
We empirically evaluate our method on synthetic data, UCI adult (Kohavi 1996). a classical FL benchmark data set CIFARIO (Krizhevsky al. 2009), and real-world electronic health record (EHR) data repository eICU (Pollard et al.) (0188), which includes patient EHR data in ICU from multiple hospitals. The results show our method significantly outperforms existing relevant methods. The experiments on eICU data demonstrate that our algorithm is able to derive a good collaboration strategy for the hospitals to collaborate.
2
RELATED WORK
2.1 FEDERATED LEARNING
Federated learning (FL) (MMMaha et al. 2017) refers to the paradigm of learning from fragmented data without sacrificing privacy. In typical FL. setting, global model is learned from the data residing in multiple distinct local clients. However, a single global model may lead to performance degradation certain clients due data heterogeneity. Personalized federated learning (PFL) (Kulka) mi et al. 2020), which aims at learning a customized model for each client in the federation, has been proposed to tackle this challenge. For example. [Zhang al. (2020) proposes
adjust the
weight of the objectives corresponding to all clients dynamically: Fallah et al. (2020) proposes meta-learning based method for achieving an effectively shared initialization of all local models followed by a fine-tuning procedure; (Shamsian et al. (202T) proposes to learn a central hypernetwork which can generate a set of customized models for each client. FL. assumes all clients are willing to participate in the collaboration and existing methods have not considered whether the collaboration can really benefit each client or not. Without benefit, a local client could be reluctant to participate in the collaboration, which is a realistic scenario we investigate in this paper. One specific FL setup that is relevant to our work is clustered federated learning (Sattler et al. 2020 Mansour et al.] 2020). which groups the clients with similar data distributions and trains a model for each client group. The scenario we are considering in this paper is to form collaboration coalitions based on the performance gain each client can get for its corresponding model, rather than sample distribution similarities.
2.2 MULTI-TASE LEARNING AND NEGATIVE TRANSFER
Multi-task learning (Caruana 1997) (MTL) aims at learning shared knowledge across multiple inter- related tasks for mutual benefits. Typical examples include hard model parameter sharing (Kokkinos) 2017), soft parameter sharing (Lu et al. 2017), and neural architecture search (NAS) for shared
2

---

Under review as a conference paper at ICLR 2022
model architecture (Real et al. 2019). However, sharing representations of model structures cannot guarantee model performance gain due to the existence of negative transfer, while we directly consider forming collaboration coalitions according to individual model performance benefits. In addition, MTL. usually assumes the data from all tasks are accessible, while our goal is to learn a personalized model for each client through collaborating with other clients without directly accessing their raw data. It is worth mentioning that there are also clustered MTL approaches (Standley et al. [020 Zamir al. 2018) which assume the models for the tasks within the same group are similar each other, while we want the clients within each coalition can benefit each other through collaboration when learning their respective models. Some works extend MTL multi- domain adaptation (Wen) et al. 2020; Duan et al., 2009) setting in which unlabeled data exist in some tasks. See detailed discussions in Appendix.
3
COLLABORATION LEARNING PROBLEM
We first introduce the necessary notations and definitions in Section 3.1 and then define the collabo- ration equilibrium we aim to achieve in Section 3.2
3.1 DEFINITIONS AND NOTATIONS
Suppose there are N clients I = [ in a collaborative network and each client is associated with a specific learning task T based on its own data D' the input space X and the output space Y' may or may not share across all N clients. Each client pursues collaboration with others to learn personalized model M by maximizing its utility (i.e., model performance) without sacrificing data privacy. There is no guarantee that one client can always benefit from the collaboration with others, and the client would be reluctant to participate in the collaboration if there is no benefit. In the following, we describe this through a concrete example.
i E (1.2..., N). where
No benefit, no collaboration. Suppose the local data [D'), i (1, .)} owned by different clients satisfy the following conditions: 1) all local data are from the same distribution D' ~ P; 2) D C D D3 ..... D. Since D contains more data than other clients, IN cannot benefit from collaboration with any other clients, so I will learn local model using its own data, Once IN refuses to collaboration, -N will also work on its own as JN can only improve its utility by collaborating with / N2 will learn individually out of the same concerns. Finally, there is no collaboration among any clients.
Due to the discrepancies of the sample distributions across different clients, the best local model for a specific client is very likely to come from collaborating with a subset of clients rather than all of them. Suppose U (I', C) denotes the model utility of client I' when collaborating with the clients in client set C. In the following, we define U Umzz( (T² C*) as the maximum model utility that can achieve when collaborating with different subsets of C.
Definition 1 (Maximum Achievable Utility (MAU)). This is the maximum model utility for specific client I' to collaborate with different subsets of client set C: Umow (1', C.) = maxcrec U (I', C").
From Definition] 1 MAU satisfies Umaz (I', C') S Umar (I', C) if C' is subset of C. Each client I' E I aims to identify its "optimal set" of collaborators from I to maximize its local utility, which is defined as follows.
Definition (Optimal Collaborator Set (OCS)), A client set CT'((1)) I an optimal collaborator set for 1s if and only if ofp (I') satisfies
AC II, U(T CTr 2(),C)(CCC) "U',CTT' (T') U(',C'
(1a)
VC & CCPt(T))
(Ib)
lap means that I can achieve its maximal utility when collaborating with (TC((T) and Eq. lb
means that all clients in CTrL (T') are necessary. In this way, the relationships between any client I' I and its optimal collaborator set (I') can be represented by a graph which is called the benefit graph (BG). Specifically, for given client set C c I, we use BG(C) to denote its corresponding BG. For the example in Figure I (a), an arrow from I to I' means 1 E C (I'), e.g., 11 1 means 1 E C.SL (13). For client set C. if every member achieve its maximum
3

---

Under review as a conference paper at ICLR 2022
model utility through the collaboration with other members within C' (without collaboration with other members outside C), then we call C' a coalition.
Forming coalitions for maximizing the local model utilities Sioure an example BG with clients. 1 can achieve its optimal model utility by collaborating with l². Similarly, I and 1 can achieve their optimal model utility through collaborating with I and 1s. In this case, C' { 1 ] denotes collab- oration coalition, and each client achieves its optimal utility by collaborating with other clients in C. If I is taken out from C, will leave C' as well because cannot gain any benefit through collaboration with others, and then 1 will leave for the same reason. With this ring structure of C, none of the clients in C' can achieve its best performance without collaborating with the clients in C.
Figure 2: Forming coalitions for maximizing the local utility
3.2 PROBLEM SETUP
As each client in I aims to maximize its local model utility by forming a collaboration coalition with others, all clients can form several non-overlapping collaboration coalitions. In order to derive those coalitions, we propose the concept of collaboration equilibrium (CE) as follows.
Suppose we have set of coalitions S =00, CI,...C'K } such that K O I and Oh n i for vk, * k2, then we say S reaches CE if it satisfies the following two axioms.
Axiom 1 (Inner Agreement). All collaboration coalitions satisfy inner agreement, i.e.
AC E S, VC CC, 31' E s.t., Umax (1', C*) < Umaa (1', C*)
(2)
From Axiom D inner agreement emphasizes that the clients of each coalition agree to form this coalition. gives the necessary condition for a collaboration coalition to be formed such that any of the subset C' & C can benefit from the collaboration with C',C'. Eq. 2 tells us that there always exists a client in C' that opposes leaving C' because its utility will go down if C" is split from C. In this way, inner agreement guarantees that all coalitions will not fall apart the clients involved will suffer. For example, S = {(72, 12, [4] { [1577% } in Figure 2 does not satisfy inner agreement, because the clients in the subset C' (I', 12, 13) achieves their optimal utility in C' and can leave C= 11, 13,
14) without any loss.
Axiom 2 (Outer Agreement). The collaboration strategy should satisfy outer agreement, iee.
VC' & S, 37 C', s.1. Umax (T' (T',C) Umaz (T (T,C) (T' CCES)
From Axiom outer agreement guarantees that there is other coalition C' which can benefit each client involved more than S achieves. Eq. tells us that if C" is a coalition not from S, there always exists client 1 and coalition in C E such that I can benefit more. The collaboration strategy S = { 12, 12, ,, {1}, in Figure 2 is CE in which the clients in {1², 13] and {TS, 16) achieve their optimal model utility. Though I does not achieve its maximum model utility in {r*), there is other coalitions which can attract I and 1 form new coalition with /4. Therefore, all clients have no better choice but agree upon this collaboration strategy.
Our goal is to obtain collaboration strategy to achieve CE which satisfies Axiom[]am and Axiom 2 so that all clients achieve their optimal model utilities in the collaboration coalition. For the nature of CE, we also share extended discussions in Appendix. In the next section, we introduce our algorithm in detail on 1) how to derive collaboration strategy that can achieve CE from the benefit graph and 2) how to construct the benefit graph.
COLLABORATION EQUILIBRIUM
In this section, we will introduce our framework on learning to collaborate. Firstly, we propose an iterative graph-theory-bant based method to achieve CE based given benefit graph.
4

---

Under review as a conference paper at ICLR 2022
4.1 ACHIEVING COLLABORATION EQUILIBRIUM GIVEN THE BENEFIT GRAPH
In theory, there are BN collaboration strategies for partitioning N clients into several coalitions, where By is the Bell number which denotes how many solutions for partitioning a set with N elements [Bell 1934). While exhaustive trying all partitions has exponential time complexity, in this section, we propose an iterative method for deriving a collaboration strategy that achieves CE with polynomial time complexity. Specifically, at each iteration, we search for stable coalition which is below, then we remove the clients in the stable coalition and re-build the benefit graph for the remaining clients. The iterations will continue until all clients are able to identify their own coalitions.
formally defined in Definition 3
Definition 3 (Stable Coalition). Given a client set I, a coalition C* is stable if it satisfies
1. Each client in C achieves its maximal model utility, i.e., 1) VI E EC*
U Umaz(1 (I', ,C)) = Umax (1', I)
(4)
2. Any sub coalition C' C C* cannot achieve the maximal utility for all clients in C², i.e.,
AC C aI E C², s.t., Umase (I', (2,CC C²) < Umar (o'aa(1",C)) C*).
(5)
From Definition] Eq. means that any client in a stable coalition cannot improve its model utility further. Eq. 5 states that this coalition is stable as any sub coalition C' can benefit from C*\C" Therefore any sub coalition has no motivation to leave C Eq.44) implies that stable coalition will not welcome any other clients to join as others will not benefit the clients in C' further. In Figure 2 {T,, (e} and {T", ] are the two stable coalitions. In order to identify the stable coalitions from the benefit graph, we first introduce the concept of strongly connected component in directed graph.
Definition 4 (Strongly Connected Component TTrjaan 1972)). A subgraph G' is strongly connected component of a given directed graph G if it satisfies: I) is strongly connected, which means that there is path in each direction between each pair of vertices in G'; 2) It is maximal, which means no additional vertices from G can be included in G' without breaking the property of being strongly connected.
Then we derive graph- method to obtain the collaboration coalitions that can achieve collabo- ration equilibrium by identifying all stable coalitions iteratively according to Theorem bellow. Theorem 1. (Proof in Appendix) Given a client set I and its (G( the stable coalitions are strongly connected components of (G(I).
With Theorem | need to identify all strongly connected components of BG((), which can be achieved using the Tarjan algorithm [Tarjan] 1972) with time complexity O(V + E). where V is the number of nodes and F is the number of edges. Then following Eq. we judge whether strongly connected component is a stable coalition by checking whether all clients have achieved their maximal model utility. A stable coalition C' has no interest to collaborate with other clients, so C will be removed and the remaining clients I' C' will continue to seek collaborations until all N clients find their coalitions. In this way, we can achieve a partitioning strategy, with the details shown in Algorithm 1 in the Appendix.
Theorem 2. (Proof in Appendix) The collaboration strategy obtained above achieves collaboration equilibrium.
The clients in all stable coalitions found in each iteration cannot improve their model utility further and will not collaborate with others because there are no additional benefits. Therefore, the collaboration strategy is approved by all clients. The iterative method achieves CE considering the BG varies in each iteration after removing the stable coalitions, which can be time-com meee-oonuiinggggg because we need to redefine BG in each iteration by re-learning optimal personalized model for each remaining client. Assumption 1. The benefit graph of a subset C (CG(C)) the subgraph of the BG
Assumption 1 claims that the benefit graph of the remaining clients I\C keeps unchanged when the subgraph BG(C*) is split from (T(.). It implies that for each pair of clients I and 13, whether J is one of the optimal collaborators for 1 will not be affected by other clients. In this case, we do not need bu-bdild the benefit graph and have the following corollary.
Corollary 1. (proof in Appendix) When Assumption I holds, the strongly connected components of (T( leads collaboration equilibrium.
5

---

Under review as a conference paper at ICLR 2022
4.2 DETERMINE THE BENEFIT GRAPH BY SPECIFIC PARETO OPTIMIZATION
The benefit graph of N clients consists of the clients and their corresponding OCS. However, each client has 2- collaborator sets and it's hard to determine which one the OCS. Exhaustive trying all sets to determine the OCS may be impractical, especially when there are many clients. To identify the OCS effectively and efficiently, we propose Specific Pareto Optimization (SPO) to alternately perform the following two steps: 1). learn Pareto model (defined below) given the weight of all clients d: 2). optimize the weight vector d to search for a best model M (T') by gradient descent.
Definition 5 (Pareto Solution and Pareto Front), We consider n objectives corresponding to n clients: : R" + i (1.2....,,1) Given a learned hypothesis h, suppose the loss vector I(h)= = =1,,1.....,!u represents the utility loss on clients with hypothesis h E H. we say h is Pureto Solution if there is no hypothesis h' that dominates h, often called Pureto optimality, i.e,
BN' E H. s.t. Vi: 1.4 (k') S 4(h) and 3j :1 (K)) (b))).
In a collaboration network with N clients {r' as each client has its own learning task which can be formulated as a specific objective, we use P((I',?,,... (PF) of the client set { formed by all Pareto hypothesis.
to represent the Pareto Front
Learning a best model and identify the OCS by SPO To search for an optimal model M
for I', we propose to firstly learn the empirical Pareto Front by a hypernetwork denoted as HN As each client owns its objective, given the weight of all clients (objectives), the learned PT by HN outputs a Pareto model M,
M (dddd,
(6)
where d d= [d' d d satisfying Ex d' - 1 and d' denotes the weight of the objective 4- specific Pareto model M, and all Pareto models M satisfy Pareto optimality
Each d corresponds that the losses on the training data of all clients cannot be further optimized.
Though the Pareto models maximize the utilization of the training data from all clients, they may not be the best models on the true (test) data distribution. For example, H (d2)) achieves a minimum loss on the training data of I shown in Figure 3 (b), but it is not the optimal model on the true data distribution of 2 shown in Figure (c). Therefore, we propose to search for a best Pareto model that achieves the best performance on the true (validation) data set of the target client I', i.e.
(7) where Per (d)) 12) denotes the performance of (d) on the validation data set of 75. We identify the OCS of I' based on the optimized weight of all clients d'. For example shown in Figure 3 c), the best model is hi for client I' and the corresponding optimized weight d' = dg =
M² = HNd)"), where d' = arg max Per ( I'), d
[0.7, 0.3, 0j. So the OCS of 7 consists of the clients with non-zero weights, which is (7) 12).
10
4
(a) ((1)))
(b) P((h,(a)
(c) performances true (testing) distribution
Figure 3: (a) the loss plane of P([1, 12, 4a)) learned from training data of [1',12,13; (b) the loss curve of (2)) learned from training data of {12, 12, 12] is embedded in the loss plane of 1(14,,2,,44) d1, d2, ., d1 are 4 vectors corresponding to 4 Pareto models in P( (2)): (3) the performances of the models h E P([h, 12)) on true (testing) distributions and hy (h3) achieves the optimal performance on client 7 (T2) corresponding to d3 (d2) in (b).
More information please refer Navon al. 2020

---

Under review as a conference paper at ICLR 2022
Proposition 1 (Pareto Front Embedding Property). (proof in Appendix) Suppose 1'* [1(h'') 11 C' and [], i E C are the loss vectors achieved by the PFs P(C") and P(C) where C' C C,
then
vh E P(C"), =h" E P(C), s.1, 4(h"") = =1")) VIEC".
(8)
From Proposition T] the loss vectors achieved by the PF of sub-coalition are embedded the loss vectors of the full coalition, such as the loss curve of P([ 12)) is in the loss plane of P([h, 12, 13)) shown in Figure (a) and (b).
Explanation of SPO from geometric point of view Intuitively, if the best model M (I) searched on the PF of all clients P(T) belongs to the PF of a sub coalition P(C) simultaneously, i.e.
M' E P(C) and M' E P(T).
then the clients [C are not necessary for obtaining (I')". However, exhaustively trying the PF of all sub-coalitions can have exponential time complexity. From Proposition I the PF of full coalition contains the PF of all sub-coalitions. Therefore, we propose SPO to search for a best model M (T') on the PF of full coalition I, and identify whether M ((') belongs to the PF of sub-coalition using the optimized weight vector d. For example, suppose there are three clients and the three corresponding objectives achieved by the PF are shown in Figure 3a) The model hi in Figure 3aa) a)
is on the PF P(141 12, 13 }). Since the corresponding weight d = [0.7, 0.3, OJ, from Figure 3 b). h also on the PF P(4 (2)), so 1 is not a necessary client and the OCS of I' is {4, 2 More discussion about optimality and implementation details are in Appendix.
5 EXPERIMENTS
To intuitively demonstrate the motivation of collaboration equilibrium and the effectiveness of SPO, we conduct experiments on synthetic data, real-world UCI dataset Adult (Kohavil 1996) and benchmark data set CIFAR10 (LeCun et al. 1998). Moreover, we verify the practicability of our framework on a real-world multiple hospitals collaboration network using the electronic health record (EHR) data set eICU (Pollard et al. 2018). As SPO aims to achieve an optimal model utility by optimizing the personalized model on the PF of all clients, we use SPO to denote the model utility achieved by SPO. According to the OCS determined by SPO we achieve a CE for clients and the model utility of each client in the CE can be different from the utility achieved by SPO. We use CE to denote the model utility achieved in the CE without causing further confusion. To verify the practicability of our framework, we also compare the time consumption and provide more experimental results in Appendix.
5.1 SYNTHETIC EXPERIMENTS
Synthetic data Suppose there are 6 clients in the collaboration network. The synthetic features owned by each client I' are generated by x ~ U[-1.0, 1.0]: the ground-truth weights u, = v v are samples as v ~ L/(000 1. 1.0). r, (Oaa, p²) where p² represents the client variance (if p² increases, the data distribution discrepancy among clients will increase). Labels of the clients are observed with i.idd noise ~ o²). To generate conflicting learning tasks assigned to different clients, we flip over the label of some clients: y = u,[xx + e, E 1,,1 and y = u.T x + e, E (3,4,5).
From Table I when there are fewer samples (n 2000) and less distribution discrepancy p 0.1 in the client set (7) / 12] or {T², _ (o) with similar label generation process, these clients collaborate with others to achieve a low MSE. In this case, the OCS of each client is the clients with similar learning tasks and we achieve CE as S = {(/")/- {ī as shown in the top of Figure 4 (a). With the increase of the number of samples and the distribution discrepancy, collaboration cannot benefit the clients and all clients will learn individually on their own data. Therefore, when n 20000 and p 1.0, the OCS of each client itself and the collaboration strategy S = ([1"). J. (I' }.., {
leads to a CE as shown in the bottom of Figure 4 (a).
UCI adult data adult contains more than 40000 adult records and the task is to predict whether an individual earns more than 50K/year given other features (e.g., age, gender, education, etc.). Following the setting in (Li et al,, Mohn et al.) (009)). we split the data set into two clients. One is PhD client (7") in which all individuals are PhDs and the other is non- non-PhD client (79). In this
7

---

Under review as a conference paper at ICLR 2022
experiment, we implement SPO on this data set and compare the performance with existing relevant methods AFL (Mohri et al. 2019) and q-FFL (Li et al. 2019
The two clients 1 and I' have different data distribution and non PhD client has more than 30000 samples while PhD client has about 500 samples. From Table 2 SPO achieves higher accuracy compared to baselines especially PhD clients (77.0). non-PhD client achieves optimal accuracy (83.5) by local training. Therefore, PhD client improves its performance by collaborating with non-PhD client while the performance of non-PhD client declines. The benefit graph is shown in the top of Figure 4 (b). The CE is non-collaboration as in the bottom of Figure 4 (b) and the model of both clients in the CE are trained individually.
5.2 BENCHMARK EXPERIMENTS
We compare our method with previous personalized federated learning (PFL) methods on CIFAR-
10 Krrizhvssky et al. 2009 Following the setting in (McMahan et al. 2016). we simulate non-i.i.d
environment by randomly assigning two classes to each client among ten total classes. Baselines
we evaluate are as follows: (1) Local training on each client; (2) FedAvg (McMahan et al. 20166);
(3) Per-FedAAg (Fallah et al. 2020), meta-learning based PFL. algorithm. (4) pFedMe (T Dinh
et al. 2020). a PFL. approach which adds a Moreau-enveloge
loss term; (5) LG-FedAvg (Liang et al.
2020 PFL method with local feature extractor and global output layers: (6) FedPer (Arivazhagan
et al. 2019), PFL approach that learns personal classifier on top of a shared feature extractor; (7)
PFedHN (Shamsian al. 202T), a PFL approach that generates models by training a hyper-network. In all experiments, our target network shares the same architecture as the baseline models. For each client, we split 87% of the training data for learning a Pareto Front by collaborating with the others
and the remaining 13% of the training data for optimizing the vector d to reach an optimal model as shown in Figure
(c). More implementation details are in Appendix.
Table reports the results of all methods. FedAve achieves a lower accuracy (51.4) compared to local training (86.46) which means that training a global model can hurt the performance of each client. Compared to other PFL methods in Table 3 SPO reaches optimal model on the PF of all objectives and achieves a higher accuracy (92.47). As the features learned from the images are transferable though there is label shift among all clients, the collaboration among all clients leads to a more efficient feature extractor for each client. Therefore, the benefit graph of this collaboration network is fully connected graph and the collaboration equilibrium is that all clients form full coalition for collaboration as shown in Figure (c). In this experiment, the accuracy model of each clients in CE equals to the accuracy achieved by SPO.
Table 1: Synthetic
Table 2: Adult
Table 3: CIFAR10
a 2000, 0.1
n. 20000, 1.D
Accursey
methods
accuracy
OCS
CR (MSF)
OCS
CF (MSF)
methods
Local
86.46 + 4.02
FedAve
51.42 a 2.41
r1,
0,2440.08
10-4+.0
AFL
$2.6
7..0
Per-HedAve
76.65 + 4.84
11
00
r. 1
0 0.2610.08
1e-42.0
FedPer
12
0.24400.44
Io-45.0
4.FFL.
12.4
74.4 9
pPedMe
$7.69
13
18
14
16
0.26400117
18
10-4.00
local
83.5
66.9 +: 1.0
L.GFedAve
89.11 2.66
gRedHN
50.83 +: 1,56
7
0,2610.09
Ie-4a.0
SPO
828
77.0
SPO (ours)
92.47 + 4,80
25
3
14
2
0.26410.03
10
16-42,0
CE (ouns)
$3.5
CF (ours)
92.47 x 4,80
(1) Hlneii Cingh
C2 Do collaburation
(1) hal osliburation
(a)
(b)
(c)
Figure 4: Collaboration equilibrium on synthetic data, Adult and CIFARIO.
5.3 HOSPITAL COLLABORATION
eICU (Pollard et al. 2018) is clinical data set collecting the patients about their admissions to ICUs with hospital information. Each instance is a specific ICU stay. We follow the data pre-processing
"hhe results of baselines are from Li al.
2019)
'The results of baselines from
Shamsian et al. 2021
8

---

and the model Under review as a conference paper at ICLR 2022
procedure in (Sheikhalishahi et al. 2019) and naturally treat different hospitals local clients. We conduct the task of predicting in in-hospital mortality which is defined as the patient's 's outcome at the hospital discharge. This is binary classification task, where each data sample spans l-hour window.
In this experiment, we select hospitals with more patient samples (about 1000) { {1'] }=== and
i==
hospitals with less patient samples { negative labels), For all methods, we use the ANN as the network structure as in (Sheikhalishahi et al. 2019).
(=5' Due to label imbalance (more than 90% samples have AUC to measure the utility for each client as in (Sheikhalishahi et al. 2019).
Table 4: eICU
AUC
methods
1
1²
[
/z
15
1
17
1
1
Local
66.89
85.03
61.83
68.83
82.31
59.65
67.78
40.00
61.90
70.00
FedAve
71.92
89.36
81.00
73.89
80.23
70.18
52.22
40.00
61.90
75,00
SPO (ours)
76.35
91.80
80.28
70.52
86.93
82.46
71.11
40.00
76.19
83.33
CE (ours)
77.93
87.28
70.47
70.64
83.48
64.92
68.89
45.00
61.90
70.00
The model AUC of each hospital is reported in Table Because of the lack of patient data for each hospital, Local achieves a relatively lower AUC compared to FedAve and SPO. While patient populations vary substantially from hospital to hospital, SPO learns a personalized model for each hospital and outperforms FedAve from Table
(a) benefit graph
(b) strongly connected components of (a)
(c) collahoration equi- librium
Figure 5: Collaboration Equilibrium of 10 real hospitals
Collaboration Equilibrium The benefit graph of all hospitals determined by SPO and its corre-
sponding strongly connected components are shown in Figure 5(a) and ((b) From Figure 5(a) 7
5
and 73 are the unique necessary collaborator for each other, C [1, is the first identified
stable coalition as shown Figure 5(b); 7 a tiny clinic that cannot contribute to any hospitals, no hospital is willing to collaborate with it and 1 learns local model with its own data by forming a simple coalition C² = {1 The benefit graph of the remaining clients are shown in Figure 5(b). On the one hand they cannot benefit 1 or 7 so they cannot form coalitions with them, the other hand they refuse contribute 1 without any charge. They choose form the coalition C 12, 14, 1s 1 1", [8} to maximize their AUC. Therefore, the CE in this hospital collaboration network is achieved by the collaboration strategy $ = {Ca, AUC of each client in the CE is in Table
C,,,,,C C3 ,C,,
Comparing Figure 5(b) and ((c) the strongly connected components of the benefit graph leads to CE. This empirically verifies that Assumption iis reasonable. Meanwhile, CE guarantees that every client in its coalition will not collaborate with harmful clients, so the client may achieve higher utility CE compared to collaborating with everyone such as the AUC of 7 in CE (77.93) is higher than in SPO (76.35).
CONCLUSION
In this paper, we propose learning to collaborate framework to achieve collaboration equilibrium such that any of the individual clients cannot improve their performance further. Comprehensive experiments on benchmark and real-world data sets demonstrated the validity of our proposed framework. In our study, some small clients could be isolated as they cannot benefit others. Our framework can quantify both the benefit and the contribution from each client in network. In practice, such information can be utilized to either provide incentives or to impose charges on each client, facilitate and enhance the foundation of the network coalition.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
We propose a novel collaboration framework for multiple clients, which is based the principle that each member in the coalition benefits others while aims to maximize its utility. We have read the codes of ethics and make sure this paper conforms to them. The procedures of data processing and experiments comply with requirements. Moreover, we also share our extended discussions about the applications and limitations of our method in Appendix.
REPRODUCIBILITY STATEMENT
Our all instructions and training details needed to reproduce the experimental results are in Appendix. The links of public data sets are also provided. We report the resources used in Appendix. The source code of our method will be made public when it is published. For all theoretical results, also give rigorous analysis, detailed proofs, and comprehensive discussions in Appendix.
REFERENCES
Manoj Ghuhan Arivazhagan, Vinay Aggarwal, Aaditya Kumar Singh, and Sunav Choudhary. Feder- ated learning with personalization layers. arXiv preprint 1rXiv:1912.00818, 2019.
Eric Temple Bell. Exponential polynomials. Annals of Mathematics, pp. 258-277, 1934.
Rich Caruana. Multitask learning. Machine learning, 28(1):41-75, 1997.
Koby Crammer, Michael Kearns, and Jennifer Wortman. Learning from multiple sources. Journal of Machine Learning Research, 9(8), 2008.
Lixin Duan, Ivor W Tsang, Dong Xu, and Tat-Seng Chua. Domain adaptation from multiple sources via auxiliary classifiers. Proceedings of the 26th Annual International Conference on Machine Learning, pp. 289-296, 2009.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta- learning approach. arXiv preprint arXiv:2002.07945 2020.
Rachael L Fleurence, Lesley H Curtis, Robert M Califf, Richard Platt, Joe V Selby, and Jeffrey S Brown. Launching pcomet, a national patient-centered clinical research network. Journal of the American Medical Informatics Association, 21(4):578-58) 2014.
Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Kdd, volume 96, pp. 202-207, 1996.
lasonas Kokkinos. Ubernet: Training universal convolutional neural network for low-, mid-, and high-level vision using diverse datasets and limited memory. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 1129-6138, 2017.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Viraj Kulkarni, Milind Kulkarni, and Aniruddha Pant. Survey of personalization techniques for federated learning. In 2020 Fourth World Conference on Smart Trends in Systems, Security and Sustainability (WorldS4), pp. 794-797, IEEE, 2020.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):228-23244 1998.
Mu Li, David G Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene Shekita, and Bor- Yor-Yinn Su. Scaling distributed machine learning with the parameter server. In 1thh USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), pp. 583-598, 2014.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. arXiv preprint arXiv: 10497, 2019.
10

---

Under review as a conference paper at ICLR 2022
Paul Pu Liang, Terrance Liu, Liu Ziyin, Nicholas B Allen, Randy P Auerbach, David Brent, Ruslan Salakhutdinov, and Loous--hhilipp Morency. Think locally, act globally: Federated learning with local and global representations. arXiv preprint arXiv:2001.01523, 2020.
Yongxi Lu, Abhishek Kumar, Shuangfei Zhai, Yu Cheng. Tara Javidi, and Rogerio Feris. Fully- adaptive feature sharing in multi-task networks with applications in person attribute classification. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 3334-3343, 2017.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation with multiple sources. In Proceedings of the st International Conference Neural Information Processing Systems, pp. 1041-1048, 2008.
Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications federated learning. arXiv preprint WxXiv2202./00619 2020.
Saeed Masoudnia and Reza Ebrahimpour. Mixture of experts: literature survey. Artificial Intelli- gence Review, 22(2)2275-2 2014.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: survey. Computers & Operations Research, pp. 105400, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. cummunication-efficeee learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282. PMLR, 2017.
H Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agūera y Arcas. Federated learning of deep networks using model averaging. arXiv preprint arXiv:1602.05622 2016.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Interna- fional Conference on Machine Learning, pp. 4615-4625, PMLR, 2019.
Aviv Navon, Aviv Shamsian, Gal Chechik, and Ethan Fetaya. Learning the pareto front with hypemetworks. arXiv preprint arXiv:2010.0410 2020.
Sinno Jialin Pan and Qiang Yang. A survey on transfer learning. IEEE Transactions on knowledge and data engineering, 22(10))1345-133 2009.
Tom J Pollard, Alistair EW Johnson, Jesse D Raffa, Leo A Celi, Roger G Mark, and Omar Badawi. The eicu collaborative research database, a freely available multi-center database for critical care research. Scientific data, 5(1):1-13, 2018.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V Le. Regularized evolution for image classifier architecture search. In Proceedings of the aaai conference on artificial intelligence, volume 33, pp. 4780-4789, 2019.
Felix Sattler, Klaus-Robert Müller, and Wojciech Samek. Clustered federated learning: Model- agnostic distributed multitask optimization under privacy constraints. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Aviv Shamsian, Aviv Navon, Ethan Fetaya, and Gal Chechik. Personalized federated learning using hypemetworks. arXiv preprint arXiv:2 2021.
Seyedmostafa Sheikhalishahi, Vevake Balaraman, and Venet Osmani. Benchmarking machine learning models eicu critical care dataset. arXiv preprint arXiv: 1eXivv991000096. 2019.
Trevor Standley, Amir Zamir, Dawn Chen, Leonidas Guibas, Jitendra Malik, and Silvio Savarese. Which tasks should be learned together in multi--askk learning? In International Conference on Machine Learning, pp. 9120-9132. PMLR, 2020.
Canh T Dinh, Nguyen Tran, and Tuan Dung Nguyen. Personalized federated learning with moreau envelopes. Advances in Neural Information Processing Systems, 33, 2020.
Robert Tarjan. Depth-fire first search and linear graph algorithms. SIAM journal on computing. 1(2): 146-160, 1972.
11

---

Under review as a conference paper at ICLR 2022
Zirui Wang, Zihang Dai, Barnabás Póczos, and Jaime Carbonell. Characterizing and avoiding negative transfer. Proceedings of the IEEE/CVP Conference on Computer Vision and Pattern Recognition, pp. 11293-11222 11302, 2019.
Junfeng Wen, Russell Greiner, and Dale Schuurmans. Domain aggregation networks for multi-source domain adaptation. In International Conference Machine Learning, pp. 10214-10224, PMLR, 2020.
Garrett Wilson and Diane J Cook. A survey of unsupervised deep domain adaptation. ACM Transactions on Intelligent Systems and Technology (TIST), 11(5):1-46, 2020.
Amir R Zamir, Alexander Sax, William Shen, Leonidas J Guibas, Jitendra Malik, and Silvio Savarese. Taskonomy: Disentangling task transfer learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3712-3722, 2018
Michael Zhang, Karan Sapra, Sanja Fidler, Serena Yeung, and Jose M Alvarez. Personalized federated learning with first order model optimization. arXiv preprint arXiv:2012.08865, 2020.
A PROOFS OF ALL THEORETICAL RESULTS
A.1 PROOF OF THROREM
To prove Theorem 1 first prove that the benefit graph of a stable coalition is strongly connected shown in Lemma
For a given client set I, the benefit graph of each stable coalition C is strongly connected, which means that there is path in each direction between each pair of vertices in (G((").
Lemma 1.
Proof. We will prove the Lemma by contradiction. Given stable coalition C suppose there exsits a pair of vertices 71, 12 E (G such that there is no path from 1 to 12, which is denoted Ap, s.t., IJ - T2 for expressive clearly. We split C into two sub-coalitions C' and C*) depending on whether the clients have paths to 12. The clients in C' have no path to 12, and the clients in C*N(C" have paths 12
VI E C² hp, s.t,, st., 122
(10)
vI E C" s.t. 1' + 12.
Obviously, C' and C² main text in the Definition of stable coalition, each client I' E C achieves its maximal utility by collaborating with others in C' which means that
empty because 1 C' and and 1 C.. From Eq. in the
YT' E C YP E CTP P E
(11)
From the Definition of Optimal Collaborator Set (OCS), each client I in the OCS of 1 has an edge from I to !2
VT (PpP*((1), Dp, s.t., 1 +
(12)
Therefore, because each client I E Copt is in C*NC', 12 can achieve its maximal utility in CC),C", Morever, we can prove that I' E Coppt (T2) achieves its maximal utiltiy in C*NC" because each client I E CCTPa(( (T2) and its corresponding OCS are in C*
AA' E (PP)((2), VT E C (T'), 3p, P + Pi
(13a)
VI E CTpl (12), 3p, s.t. I' + 12
(13b)
41 E CPpt((()) VP E (I'), 3p, 1 + 1$ 12
(13c)
12

---

Under review as a conference paper at ICLR 2022
From 13). the clients in the OCS of I' (I' (12) are in C* and I' can achieve its optimal utility. Based on the same analysis, for each client I' CM,C its OCS CT (4') is in Co C" because clients in (T'((r) have a path to I2. So we have the conclusion that all clients in COC achieves its optimal utility by collaborating with others in C*\ However, this contradicts
(6) in the main text in the Definition of stable coalition. Therefore, we prove that the benefit graph (C) of the stable coalition O is strongly connected in Lemma]
From Lemma] 1 the B is strongly connected, then we will prove that BG(C") is a strongly connected component of BG( by pointing out that BG(Cs) is maximal which means that no additional vertices from I can be included in BG(C*) without breaking the property of being strongly connected.
Proof. We will prove that BG(C*) is maximal by contradiction. Suppose there is another client 1o E TCC which can be added in (G(C*) without breaking the property of being strongly connected. Therefore, there exists I' C which has an edge from 1 to I'. This means that I is one of the necessary collaborators of I' (1 E CTT (I')) and 1 cannot achieve its optimal utility in C without collaborating with 7 However, this contradicts Eq.(5) in the main text in the Definition of stable coalition that all clients in C can achieve its optimal utility by collaborating with others in C Therefore, we prove that BG((") is strongly connected component as stated in Theorem |
A.2 PROOF OF THEOREM 2
Proof. 1. All coalitions S = {Ca, C',...,C*, satisfies Inner Agreement as in Axiom 1. As each coalition C" E S is a stable coalition, from (6) of the Definition of stable coalition, we have
YC E S, VC" CC 31 E C², s.l., Umav (I', C*) < Unar Umaax(1' C*).
(14)
Then 14 is the definition of Inner Agreement in (3) in the main text. Therefore, we prove that all collaboration coalitions in S satisfy inner agreement.
2. The collaboration strategy S satisties Outer Agreement as in Axiom 2.
We will prove it by contradiction. Suppose there exists new nonempty coalition C" {I F 1d) } & S which satisfies
YI' E C², Umax (LT,,C') > Um C" (I' E c e S).
(15)
Suppose that C*9 denotes the coalition in the first iteration. Then VI E C I' achieves its maximal utility in the client set and cannot increase its model utility further. So we have
YI E C², I Co.
(16)
The clients in the coalition C E S identified in the first iteration have no interest in collaborating with others and will be removed. Suppose C' denotes the coalition in the first iteration. VI' E C', F achieves its maximal utility in the client set CCC* and cannot increase its model utility further. So we have
VI E C², I' $ C.
(17)
Then C* will be removed and we have VA E C", 1 $ 12 Based on the same analysis, we finally have
E YC ES, 1 C
(18)
C' 0.
Therefore, we prove that there is no nonempty C' satisfying Eq. 15) and satisfies Outer Agreement.
13

---

Under review as a conference paper at ICLR 2022
A.3 PROOF OF COROLLARY
Firstly, we prove that all strongly connected components are disjoint as in Lemma 2
Lemma 2. Given a divected graph G and all its strongly connected components .C.... each pair of its strongly connected components C and C³ satisfies C* ni = 0.
Proof. We will prove it by contradiction. Suppose there exists pair of the strongly connected components which satisfies 1 E (C* (c) and C' = C² U For each pair of vertices I' P, we have
3p, l' + 1 - P. 3p, 1 + -
(19)
From C' is strongly connected which conflicts the definition of strongly connected compo- nents that each strongly connected component is maximal. Therefore, we prove that C* n' = 0. L
Theorem 2 states that the collaboration coalitions identified iteratively leads to a collaboration equilibrium. To prove the Corollary [ we will demostrate that the collaboration coalitions identified iteratively are all strongly connected components of BG(I) when Assumption holds.
Proof. Suppose the coalitions strategy S [ C )++ is determined iteratively and C is identified in the i-th iteration. From Theorem [ C one of the strongly connected components of (I). Cd is stable coalition which is one of the strongly connected componts of (G( When Assumption 1 holds, BG C() is the subgraph of BG(I) and any edge BG(I also the edge in (T and vice versa. Therefore, (G(C") is strongly connected in BG(T). Suppose CC is not a strongly connected component of BG( and there exists an additional client l
which can be added in C² without breaking the strongly connected property. From Lemma 2 l cannot be from another strongly connected component, so we have
F & CO.
(20)
I is from I UCC) and can be added into C without breaking the strongly connected property, it conflicts the definition that C' is strongly connected component of I C,C, So have
I & (ECCCCC))
(21)
there is additional I' which can be added in C without breaking the strongly connected property. So C is a strongly connected component of BG(T). For the same analysis, we can prove that VC S, Ci is strongly connected component of BG(T) when Assumption holds. Therefore, we prove that the strongly connected components of BG( (I) are the stable coalitions (C", C²,...C*k identified iteratively by Algorithm and these strongly connected components lead to a CE.
From Eq. 20 and Eq. 21).
A.4 PROOF OF PROPOSITION 1
Proof. For any hypothesis h E P(C"), h² satisfies
Bh' E H. s.t. Vi C¹ 14 (h') S 4(h²)) and 3j: b4:44:0 (h') < 44hh).
(22)
1) hf E P(C) which satisfies
#h' E H. s.t. C < 4hh) and : (h') < (h)).
(23)
then we let h² = AM* in Eq. so Eq.8 holds;
2) if hM & P(C), there exists h E P(C) which satisfies
14

---

Under review as a conference paper at ICLR 2022
Vi E & <4("") and Rj (k) <1,(1")
(24)
combining Eq. 22
we have
Vie C² 4 (k)) L(h")) and Ej e C\CC" :4 (k) 1((M²)
(25)
then we let h² h in Eq.
so Eq. holds.
B IMPLEMENTATION
In this section, we will introduce how to learn the Pareto Front of objectives corresponding to all clients. Then, will describe how determine the optimal collaborator set for each client.
B.I LEARNING PARETO FRONT
Multi-objective optimization (MOO) problems have set of optimal solutions, and these optimal solutions form the Pareto front, where each point on the front represents different trade-off among possibly conflicting objectives. We construct personalized model for each client which we call target network and it has the same architecture the baselines. To determine the parameters of the target network of each client, in our experiments, we learn the entire Pareto Front simultancously using hypernetwork which receives as input vector d and returns all parameters of the target network. The input vector is N-dimension bmd in which each entry corresponds to the client I and is sampled from the convex hull D,
N N, 2 O, and Σ d' 2d==1
d,
(26)
Specifically, we construct the hypernetwork following in the architecture introduced in (Navon et al. 2020). By a n-layer
3) MLP network with the activation function ReLU, inference the parameters of the target network. Then the obtained parameters will be assigned to the target network. We evaluate the performance of the parameters on the training set and the gradient information will be returned for updating the hypernetoork.
B.2 IDENTIPYING THE OPTIMAL COLLABORATOR SET
From the statement above, we train a hypernetwork HN for learning the whole Pareto front. HN bridges the mapping from the vector d to the corresponding model parameters of the target network. To obtain the optimal target network parameters that achieve the minimal value loss of the target objective on the validation set, we optimize the vector d by gradient descent. Specifically, given an initial direction do, we firstly obtain the parameters of the target network using the learned hypernetwork HNN (do). Like training the hypernetwork, the obtained parameters will be assigned to the target network. Then we evaluate the performance of the generated parameters on the validation set and compute the gradient of the input direction dp. Finally, the gradient information will be used for updating the vector iteratively until convergence.
d:+1 d, 71 Va.""
d:+1 +- Clip(da+1)
(27)
d <- Normalization((4..)
where 1 denotes the learning rate, Clip(d:41) means that we clip each values d' E d to satisfy co dgp < and Normalization(4,. is as follows,
15

---

Under review as a conference paper at ICLR 2022
d2+1 j= d
Vj (1
(28)
Finally, we reach the optimal direction d' and its corresponding Pareto model M (d")").
For each client, we determine the optimal collaborator set by the optimal direction d' and the loss value of all objectives 1 = [4 described Proposition [ an ideal direction d² is sparse vector in which indexes of non-zero values in d' are the necessary collaborators for the target client. In experiments, d' usually is not a sparse vector, but there are values in d' which are significantly small. Therefore, we set a threshold for d= determine which clients necessarylunnecessaayy
( (M*)). From the Pareto Front Embedded property
Algorithm 1: Achieving collaboration equilibrium
Input: N institutions I = 1 [ seeking collaborating with others Set original client set C'
Set collaboration strategy 5 4- 0;
while C * 0 do
forall client I' C do
Determine the OCS of I by SPO; end
Construct the benefit graph BG(C);
Search for all strongly connected components [C*,Ce, of BG(C) using Tarjan algorithm:
forall = 1, 3.... k do
if C stable coalition then
C Ci
$ Su
end
end end Output: collaboration strategy S
When Assumption holds, from Corollary proposed in the main text, the framework for obtaining a collaboration strategy that leads CE is simplified as in Algorithm
Algorithm 2: Achieving collaboration equilibrium under Assumption I
Input: N institutions I = [ Set original client set C' + I; Set collaboration strategy 5 < 0; forall client I' E C' do Determine the OCS of I by SPO;
j seeking collaborating with others
end
Construct the benefit graph BG(C);
Search for all strongly connected components S = {Ca, C2 C2,,..ckk) of BG(C) using Tarjan algorithm;
Output: collaboration strategy
C EXPERIMENTAL DETAILS
C.I SYNTHETIC DATA EXPERIMENTS
The synthetic data generation process is illustrated in the main text. In this experiment, we construct the hypernetwork using llaayer hidden MI.P for generating the target network parameters and the
16

---

Under review as a conference paper at ICLR 2022
target network is 1-layer MLP. The experiments have two settings, 1) 2000 training samples and = 0.1; 2) 20000 training samples and p == 1.0.
df, , d dd) varying in each iteration [d d' dd model for 1 When n 2000, p = 0.1 and the target client is 19, from Figure 6(()) {d d dd) decrease until reach the minimum and {a d ,,²} increase in each iteration. As p * 0, the data in (I2) and 1 does not satisfy i..d, so d slightly larger than and d² This means that the optimal personalized model of 1 is on PF(1", 1 12) and the OCS of 1 is {10 12). When n 20000, reach the minimum and d increases each iteration. This means that the optimal personalized model of 1 is on (F( and the OCS of 1 is {
We plot the vector
learn personalized
1.0 and the target client 1 from Figure ((b)))6(b))))))))))))) {d ,,,d,,e d, dd dd} decrease and
0.
0.7
0.5
0.4
0.4
0.3
02-
011
0
8
10
opach
opech
(a) n 2000, p
(b) n 20000, p 1.0
Figure 6: = [d d d2 d, d dd] varies in each iteration where d' corresponds to the client 7t.
After identifying all coalitions, all clients will re-learn personalized model by collaborating with other clients in its coalition.
C.2 UCI ADULT DATA EXPERIMENTS
UCI Adult is public dataset (Kohavi 1996 which is split training set and test set. We follow the dataset preprocessing procedure as in (Li et al. 2019 Mohri et al. 2019) and split the data into two clients PhD client and Non-PhD client. In this experiment, we construct the hypernetwork using 1-layer hidden MLP. The target network is a Logistic Regression model as in (Li et al. 2019 Mohri al. 2019). We split 83% training data for learning the PF and the remaining 17% training data for determining the optimal vector d. All hyperparameters are determined by the performance on the validation data set.
C.3 CIFARIO DATA EXPERIMENTS
CIFARIO is public dataset (LeCun et al. 1998) which contains 50000 images for training and 10000 images for testing. In our experiments, we following the setting in (McMahan et al.) 2016). We split the data into 10 clients and simulate non-i.i.d environment by randomly assigning to each client among ten total classes. The training data of each client will be divided into training (83%) and validation set( 17%). We construct the hypernetwork using 3-layer hidden MLP for generating the parameters of the target network and the target network is constructed following the work (Shamsian al.) 202T. J. All baselines share the same target network structure for each client. To determine the hyperparameters (c.g., learning rate), we evaluate the performance of different hyperparameter combinations on the validation set and choose the hyperparameter combination which achieves the optimal accuracy.
classes
C.4 EICU DATA EXPERIMENTS
eICU Data Asset eICU dataset (Pollard et al. 2018) is a dataset for which permission is required. We followed the procedure the website https::t.... : /uwcueucueeee erd. mit .du and got the approval
17

---

Under review as a conference paper at ICLR 2022
to the dataset. In this experiment, follow the data preprocessing as in (Sheikhalishahi et al. 2019) and select hospitals for collaboration as introduced in the main text. As all hospitals own relatively insufficient patient data samples (100 < 1300), dividing the data into training set and test set in different ways may lead to different CE. We construct the hypernetwork by a 1-layer MI.P for training the Pareto Front of all objectives. The target network is an ANN model following the work in ISheikhalishahi et al.) 2019).. We determine the hyperparameters by choosing the hyperparameter combination which achieves the optimal performance on the validation Full experiment results on eICU is in Table
Table 5: Full experimental results on eICU dataset.
AUC
methods
ave
1
/z
g
Local
66.44
66.89
85.03
61.83
68.83
82.31
$9.65
67.78
40.00
61.90
70.00
FedAvv
69.57
71.92
89.36
81.00
73.89
80.23
70.18
52.22
40.00
61.90
75,00
Per-FedAAv
68.82
68.72
89.82
71.19
72.70
74.96
68.42
46.67
45.00
85.71
65.00
FodPer
72.53
72.59
87.74
56.37
86.56
94.74
73.33
15.00
85.71
73.33
PFedMe
70.68
76.21
89.31
76.30
68.17
87.50
82.46
84.44
10.00
52.38
80.00
LG-FedAve
71.07
74.70
88,80
82.46
83.33
15.00
57.14
80.00
pFedHN
67.57
57.29
76.15
84.67
52.01
66.95
45.61
57.78
70.00
95,24
70.00
SPO (ours)
75.90
76.35
91.80
80.28
70.52
86.93
82,46
71.11
40.00
76.19
83.30
CE (ours)
70.05
87.28
70.64
83.48
61.90
70.00
C.5 TRAINING RESOURCES
We run our experiments on a local Linux server that has two physical CPU chips (Inter(R) Xeo CPU E5-2640 v4 @ 2.40GHz) and 32 logical kernels. We use Pytorch framework implement our model and train all models on GeForce RTX 2080 Ti GPUs.
D DETAILED DISCUSSIONS ABOUT MULTI-DOMAIN ADAPTATION
Multi-domain adaptation refers to the learning scenario that the target domains have no labeled data and researchers transfer the knowledge by aligning the feature spaces between the source domains and the target domains (Mansour et al. 2008 Crammer al. 2008), while the federated learning scenario in our work considers that all clients own labeled data and the feature spaces are shared. The differences between the methods in federated learning and multi-domain adaptation
follows:
1. the core goal of the methods in multi-domain adaptation is to align the feature spaces between the source domains and the target domains (Wilson Cook 2020), which may be redundant for the problem focus on because the feature space shared across all domains;
2. in the paradigm of federated learning/multi--n learning, the data of the target clients are labeled and it allows researchers to learn optimal model by supervised training while methods in multi-domain adaptation cannot;
3. federated learning requires that learning model across multi-client cannot have access to the raw data of the local clients, while methods in multi-domain adaptation can.
E EXTENDED DISCUSSIONS
E. COLLABORATIVE EQUILIBRIUM
The collaboration equilibrium collaborated network is affected by 1) the selected model structure; 2) the data distribution of the clients. For 1), different model structures utilize the data in different ways. For example, non-linear models can capture the non-linear mapping relations the data among different local clients while linear models cannot. For 2), the collaboration equilibrium is affected by the data distribution of the clients given the model structure. The data distribution of client determines whether it can benefit another when learning together and this was verified
18

---

Under review as a conference paper at ICLR 2022
by the experiments. From the experimental results shown in Table when the data distribution discrepancies increases from 0.1 to 1.0), I and I' could not benefit I anymore. Therefore, the collaboration equilibrium varies shown in Figure Ta).
E.2 OPTIMALITY
Identifying stable coalition to reach CE Our method guarantees the optimality of achieving a CE given a benefit graph. In particular, the stable coalitions (or collaboration equilibrium) are determined uniquely given the benefit graph of the client set. Based upon the constructed benefit graph, our approach guarantees the optimality of the obtained stable coalitions theoretically as the identified stable coalitions strictly satisfy the two conditions in Definition 3 as proved in Sec A.2 in Appendix. Moreover, we point out that the strongly connected components the benefit graph lead to CE under Assumption as proved in A.3;
Constructing benefit graph by SPO Given the client set and the model structure, the true optimal collaborator sets (OCS) of each client may be defined uniquely. However, the true OCS of each client is actually agnostic without any prior assumption and we have to train an optimal model for each subset and then determine the OCS by observing which model performs best. Due its exponential time complexity, we develop SPO to identify OCS by alternately optimizing the model and the collaborator set for each client. Roughly speaking, this procedure is similar to the Expectation- Maximization procedure performed in the mixture-of-expee of-experts (Masoudnia & Ebrahimpour 2014) approaches, in which the model for each expert and the ensemble weights for each sample are also learned alternately. We verify its effectiveness from the experimental results shown in Figure 4, SPO finds the true OCS on synthetic, adult and cifar10.
both synthetic and benchmark datasets. Specifically,
E.3 TIME COMPLEXITY
The analysis about the time complexity is as follows:
1. to find an OCS efficiently, we propose SPO to learn an optimal model by gradient descent and identify the OCS based upon the geometric location of the learned model on the Pareto Front according to Proposition 1, which avoids exhaustively trying;
2. to find the stable coalitions of a given client set, we propose to identify the OCS of all clients construct the benefit graph firstly. Then we propose graph-based method to recognize the stable coalitions which has O(V+E) time complexity as stated in Section 4.1;
3. to achieve a collaboration equilibrium, we propose to look for the stable coalitions and removes them iteratively. Combining (1) and (2), our method reach CE has polynomial time complexity.
The run time of SPO listed as in the following table. We also present the runtime of FedAve for comparison. As SPO learns the Pareto Front and optimizes the vector d to search for the OCS by gradient descent, there is no significant additional time cost compared to baselines.
Table 6: Running Time on Different Datasets
Dataset
FedAve
Ours
Adult
14 36s
14 min 14
CIFARIO 1 h4 min 52 m2n
4 h 4 min 40 s
eICU
21 min 30
26 min 6
E.4 APPLICATIONS
One cannot know which one should collaborate with unless it knows the result of the collaboration. This requires that all clients agree collaborate obtain the results of the collaboration, before finalizing the collaboration equilibrium. The premise of achieving the collaboration equilibrium is that all clients agree to collaborate first to construct the benefit graph. In practice, are inclined
19

---

Under review as a conference paper at ICLR 2022
to the view that this would be done by impartial and authoritative shird-party (e.g., the industry association) in the paradigm federated learning. The approved third-party firstly determines the benefit graphs by learning the optimal models from multiple clients without direct access to the data of the local clients. Then the approved third-party derives the collahoration equilibrium based upon the benefit graphs and publishes the collaboration strategies of all clients.
As our framework quantifies the benefit and the contribution of each client in a collaborative network, on the one hand, this promotes more equitable collaboration such as some big clients may no longer collaborate with small clients without any charge; on the other hand, it also leads to a more efficient collaboration as all clients will collaborate with the necessary collaborators rather than all participants.
E.5 LIMITATIONS AND FUTURE WORK
In this work, we study the collaborative learning problem and propose the core goal that collaboration strategy should lead to collaborative equilibrium (CE). In theory, it is combinatorial optimization problem with exponential complexity. There are plenty of works on addressing combinatorial optimization problems by reinforcement learning (Mazyavkina learning methods are mostly time-consuming and hard to obtain stable results. Though we propose an efficient allernat--ptimmizatin method for CE in polynomial complexity, the optimality of the OCS (or the benefit graph) is still an unsolved problem that will be explored in our future work.
al. 2021), though reinforcement
20


Reviews:
[{"review_id": "pj_nF08B1fY", "reviewer": "Reviewer_yALe", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main aspect of the proposed solution in the paper is the notion of maximum achievable utility (MAU) and optimal collaborator set (OCS) which each agent must derive.  These are well-studied principles in cooperative game theory and concepts like 'core' and 'stable coalition' are analogous to the definitions used in this work.  Similarly, the approach of using a 'benefit graph' to compute coalitions satisfying the proposed axioms also has an equivalent approaches.  See , for example, literature on \"stable group formation\" (Y. Bachrach, V. Syrgkanis, and M. Vojnovic, 2013; Arkin et. al., Geometric Stable Roommates, 2009; Aauman and Dreze, Cooperative games with coalition structures, 1974; Hart and Kurz, Stable Coalition Structures, 1982).\n\nFurther, the authors have not motivated clearly why this should be a learning problem and why it cannot be solved by using other techniques (example, in the literature mentioned above).  In its current form, I think the paper needs more work to distinguish itself from prior art and how it can use the federated learning framework to 'learn' the OCS instead of computing it directly.", "summary_of_the_paper": "The authors propose a model of collaboration to improve outcomes for any participating agent.   In their setting, the authors assume that every agent does not benefit from always collaborating with all other agents because of heterogeneity of the underlying data distributions.", "summary_of_the_review": "There is a lot of related work in the cooperative game theory and federated learning literature.  I think the authors need to do a much better comparison with the existing literature and propose why their work is different from it and carry out clear comparisons (in their experiments) to show the efficacy of their approach. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "n6HuoObCZnF", "reviewer": "Reviewer_Psa6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The authors consider an interesting problem as negative transfer is a real concern in federated learning and building a local model to avoid this phenomenon seems like a good direction.\n- I like the notion of collaboration equilibrium where a group of agents share their data only within clients in a given coaltion.\n\nWeaknesses:\n- My main concern about the proposed iterative algorithm is that it works only when assumption 1 holds and I believe this is not a realistic assumption in practice.\n- Although the definition is proposed for a general utility model, the authors assume a particular utility model in subsection 4.2. I have some concerns about this choice which I mention below.\n- I don't think the proposed definition properly captures the negative transfer phenomenon we observe in federated learning. For example, negative transfer also happens when a client shares too much data from another client as opposed to a small amount of data.\n- This paper talks about collaboration equilibrium but such notions of collaboration have been studied in cooperative game theory, probably in different context. I was surprised to see that the related work section doesn't have any mention of related work from game theory literature.\n\nQuestions for the authors:\n- Regarding the example shown in figure 1, it is not clear that you will always be able to find an initial coalition from the graph. It was later clear that under assumption 1, this problem boils down to finding a strongly connected component but this was not clear in the introduction.\nIn particular, I wonder how the iterative algorithm would start when assumption 1 fails.\n\n- Although the definition of optimal collaborator set is intuitive I am not sure how this captures the negative transfer phenomenon the authors talked about in the introduction. Negative transfer should imply that whenever I add a (harmful) client, the utility of the local model always drops. I don't think definition (1b) captures it exactly.\n\n- How realistic is assumption 1 in practice? I understand that this assumption simplifies the iterative algorithm as you don't have to recompute the benefit graph after eliminating each coalition. But if this assumption fails, recomputing the benefit graph shouldn't be computationally hard.\n\n- In section 4.2, I didn't understand the particular modeling assumptions about the clients' utility functions. In particular, it seems that the goal is to find a hypothesis that is at the pareto frontier. But why care about such a universal function if each agent wants to build their own local model? Additionally, how do the agents determine their weights?", "summary_of_the_paper": "This paper considers the problem of federated learning where different clients/entities share their datasets with other clients in order to obtain a model that performs best for the local loss functions. Standard federated learning setting usually share all datasets together to obtain a central model and might not be the best choice for each client separately. The authors propose a notion of collaboration equilibrium where each client shares data with a subset of all the available clients. In particular, a coalition of agents belong to a collaboration equilibrium if each agent gets maximum benefit by collaborating with all the agents in the subset, and the subset is maximal.\n\nIn order to obtain such a collaboration equilibrium the authors propose an iterative algorithm which under certain assumptions, is equivalent to finding strongly connected components in the graph. Finding the collaboration equilibrium requires identifying the benefit graph among the client. Under a very specific model of agents' utility functions, a pareto optimization based algorithm is proposed to find the graph. Finally, though experiments, the authors show that finding collaboration equilibrium does provide improvement compared to standard federated learning based methods.\n", "summary_of_the_review": "I thought the authors consider an interesting problem in this paper. Negative transfer in federated learning is a challenging problem and if you can avoid this issue by building a local model, that would be great! However, there seems to be several issues with the proposed definition. Moreover, the methods work under certain assumptions and I am not sure the assumptions are realistic.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NcLSxkX7iho", "reviewer": "Reviewer_Mxha", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the paper solves an interesting and important problem and that the model introduced is interesting and detailed. My main issue is that it does not appear that the introduced model captures the problem. Here are some points:\n\n1-The authors mention that privacy concerns are the main reason why a client would not share his data. But I don't see how the privacy cost is being modelled in the problem. For example, the number of individuals the client has to share his data with.\n\n2-Following point 1: I don't think the paper mentions this, but is it not possible for clients to share portions of their datasets instead, perhaps the portions that lead to positive transfer. This would further complicate things and also make it more meaningful to consider the amount of lost privacy. \n\n3-Similarly, the benefit graph does not include weights. But it seems plausible that a client would only benefit little from others datasets.\n\n4-Assumption 1: is there a motivation behind this assumption? do we expect real instances to satisfy it or it is only introduced to make the algorithm less time consuming? Also given the benefit graph can we verify that the assumption holds? \n\n5-Section 4.2 discusses how the benefit graph is obtained. It is not clear to me however, that the Pareto solution gives the actual benefit graph. I realize that the exhaustive search for the benefit graph would be infeasible. The issue is if this is an approximation of the benefit graph, then the error should be characterized and the algorithms and theorems in section 4.1 should be modified to reflect that they operate on a noisy estimate of the benefit graph. \n\n6-Unrelated to the model, but the number of clients in the experiments seems to be small (at most 9) even on the synthetic dataset. ", "summary_of_the_paper": "Given a network of clients each with his own private dataset, the locally learned model can be improved by obtaining data from other clients (assuming no domain mismatch). The paper models this problem by introducing the benefit graph which models how each client may benefit another. The concept of collaboration equilibrium is introduced and optimization algorithms to solve it are given. Some theoretical guarantees are shown along with experimental results.  ", "summary_of_the_review": "The introduced model does not seem to be complicated enough to capture the real details of the problem. Further, the algorithms and guarantees introduced do not seem to be rigorously justified. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "M3VhosW8iIM", "reviewer": "Reviewer_eyZ6", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n\nThe notion of collaboration equilibria appears natural, and the algorithm for computing such equilibria insightful.  Together with the SPO part, this provides a quite complete solution for personalized federated learning problems, and in particular, the equilibrium solutions take into consideration the incentives of self-interested agents, which is of potential practical importance.  The experiments appear to support the main claims of the paper.\n\n\n### Weaknesses\n\nSome parts of the overall approach lacks theoretical foundations (although they make sense).  The writing could be improved, e.g., by unifying terminologies and better connecting different parts of the paper.  Also, (this is not necessarily a weakness, but) I'm not familiar with the literature on federated learning, so I can't say much about the novelty of the method.\n\n\n### Detailed comments\n\nProblem setup, set of coalitions: since C^1, ... C^K partition I, isn't C^0 necessarily empty?\n\nAxioms 1 and 2: these are conceptually quite similar to the notion of the core in cooperative game theory.  The authors may want to discuss the relation between the two.\n\nTheorem 2: this claim is technically fine, but I think you still want to discuss why Algorithm 1 terminates, which isn't totally trivial (since very superficially it's possible that none of the components are stable so the algorithm gets stuck).  Indeed it does terminate, because after the SCC decomposition the new graph (over SCCs) is acyclic, which means it can be topologically ordered, and there exists a component which doesn't have incoming edges from other components.  That is a stable coalition that can be removed from C to make progress.\n\nDefinition 5: I'd say \"Pareto-efficient (or Pareto-optimal) solution\" instead of \"Pareto solution\"\n\nFootnote 1: \"(for) more information\"\n\n\"Learning a best model\" paragraph: what's a \"model\"?  What's a \"Pareto model\"?  From what I understand, a \"model\" is the same as a \"solution\" (which is a hypothesis), and a \"Pareto model\" is a solution or a hypothesis on the Pareto frontier.  Is that right?  In any case it would help to clarify these terms and unify them if they are in fact the same thing.", "summary_of_the_paper": "The paper considers the problem of agents sharing training data to improve the accuracy of the model obtained on their own population.  The high-level goal is to find \"stable\" collaboration patterns where no agents want to deviate (e.g., stop sharing or form their own groups of sharing).  The authors first consider an abstract formulation where each agent has a utility function over all sets of other agents to collaborate with.  Assuming that one can find the most beneficial set of collaborators for each agent, the authors present an efficient algorithm to divide agents into groups that form a stable collaboration pattern (aka a collaboration equilibrium).  Since the problem of finding this optimal set of collaborators for each agent is nontrivial in general, the authors come back to the setting of sharing training data, where they propose a theoretically principled approach to build the benefit graph (which encodes most beneficial collaborators) by optimizing on the Pareto frontier of hypotheses / models of accuracy of all agents.  The authors then evaluate their approach on synthetic and real data, and compare that against several benchmark methods for personalized federated learning.  Empirical results suggest that the collaboration equilibrium behaves roughly as one would expect.  Also, the model found by optimizing on the Pareto frontier appears to achieve remarkable performance, often comparable to or better than the best benchmark.  The accuracy at collaboration equilibria is somewhat worse, which is natural given that there might be a \"price of stability\".", "summary_of_the_review": "Overall I think this paper proposes a novel theoretically principled method for computing stable outcomes of data sharing or collaboration in general, which can also be applied to personalized federated learning.  Some of the theoretical results appear quite insightful.  The experiments are quite informative and support the main claims of the paper.  (Since I'm not familiar with the literature on federate learning, my evaluation regarding the novelty could be misled.)", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a model of agent collaboration to improve outcomes for any participating agent in a setting where every agent does not always benefit from collaborating with all other agents. The reviewers did find some of the theoretical results interesting, however, in its current (revised) form, they still argued during the discussion post-rebuttal that: (i) the game theoretic formulation of this problem is not entirely new and has been studied in various forms before and (ii) the particular application of the results to federated learning comes after making various (questionable) assumptions. I would encourage the authors to take into account (i-ii) for preparing a revised version of their paper and resubmit to another conference.
Decision: Reject