Gradient Driven Rewards to Guarantee Fairness in Collaborative Machine Learning
Authors: Xinyi Xu
Lingjuan Lyu
Xingjun Ma
Chenglin Miao
Chuan-Sheng Foo
Bryan Kian Hsiang Low
Venue: NeurIPS 2021 Poster (2021)
Keywords: Federated learning
Shapley value
Fairness
Incentives

Abstract: In collaborative machine learning(CML), multiple agents pool their resources(e.g., data) together for a common learning task. In realistic CML settings where the agents are self-interested and not altruistic, they may be unwilling to share data or model information without adequate rewards. Furthermore, as the data/model information shared by the agents may differ in quality, designing rewards which are fair to them is important so that they would not feel exploited nor discouraged from sharing. In this paper, we adopt federated learning as the CML paradigm, propose a novel cosine gradient Shapley value(CGSV) to fairly evaluate the expected marginal contribution of each agent’s uploaded model parameter update/gradient without needing an auxiliary validation dataset, and based on the CGSV, design a novel training-time gradient reward mechanism with a fairness guarantee by sparsifying the aggregated parameter update/gradient downloaded from the server as reward to each agent such that its resulting quality is commensurate to that of the agent’s uploaded parameter update/gradient. We empirically demonstrate the effectiveness of our fair gradient reward mechanism on multiple benchmark datasets in terms of fairness, predictive performance, and time overhead.

Gradient-Driven Rewards to Guarantee Fairness in Collaborative Machine Learning
Xinyi Xu Lingjuan Lyu²r Xingjun Ma², Chenglin Miao", Chuan Sheng Food, and Bryan Kian Hsiang Low
Department of Computer Science, National University of Singapore, Republic of Singapore' Sony AI2, School of Computer Science, Fudan University, People's Republic of China Department of Computer Science, University of Georgia, USA*
Institute for Infocomm Research, A STARR, Republic of Singapore (xuxinyi, 1owkh) nus edu. sg' lingjuan. lv@sony. com?
danxjma@gmail.commmm com", cmiaoouge edu foo chuan seeaaainsseeeei a-star edu.sg sg"
Abstract
collaborative machine learning (CML), multiple agents pool their resources (e.g., data) together for common learning task. In realistic CML settings where the agents are self self-interested and not altruistic, they may be unwilling to share data model information without adequate rewards. Furthermore, the data/model information shared by the agents may differ in quality, designing rewards which are fair them important that they would not feel exploited nor discouraged from sharing. In this paper, we adopt.fderre federated learning as the CML paradigm, propose novel cosine gradient Shapley value (CGSV) fairly evaluate the expected marginal contribution of each agent's 's uploaded model parameter update/gradient without needing an auxiliary validation dataset, and based on the CGSV, design a novel training-timg time gradient reward mechanism with fairness guarantee by sparsifying the aggregated parameter update/gradient downloaded from the server as reward to each agent such that its resulting quality is commensurate to that of the agent's uploaded parameter update/gradient. We empirically demonstrate the effectiveness of our fair gradient reward mechanism on multiple benchmark datasets in terms of fairness, predictive performance, and time overhead.
Introduction
In collaborative machine learning (CML), multiple agents (e.g., researchers, organizations, compa- nies) pool their resources (e.g., data) together for common learning task. It spans wide variety
of real-world applications such as digital healthcare [49], clinical trial research [3] 23), wake word
detection for smart voice assistants [27], and next word prediction mobile devices [15]
Federated learning (FL) provides a natural paradigm of CML 18
FL, the agents perform local model training (e.g., using stochastic gradient descent) and share their resulting model parameter updates/gradients via trusted server [40] 56 59). An important distinction of self-interested and hence not
57
work here from the standard FL literature is that the agents necessarily cooperative like the worker nodes in distributed learning. The implication that to achieve competitive predictive performance for the learning task, it is imperative to incentivize/reward the agents for contributing/sharing high-quality information the form of model parameter up- dates/gradients
47 48
'Equal contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Our work here adopts FL as the CML paradigm for designing a fair reward mechanism such that the (self-interested) agents who contribute more would not feel exploited but be rewarded commensurately. This is often regarded as fairness in cooperative game theory [42], mechanism design 4. and computational social choice 11. To design such a fair reward mechanism, we need to address three main questions:
Firstly, what is suitable notion fairnss? The Shapley value (SV)
150 S4
from cooperative game
theory is an appealing choice and has been used in ML [4] and FL
56
However, existing
SV-based works [9 37 54 56] typically require the availability of (and all agents to agree on) an auxiliary validation dataset and significant time overhead from evaluating the agents' contributions in the form of SVs and the resulting model training. To overcome these difficulties, we propose to instead exploit the alignment (specifically, cosine similarity) of an agent's 's uploaded/conrribtte model parameter apdatte/rrdient vector (or that aggregated over some agents) to that aggregated over all agents (hence measuring its quality/value and circumventing the need for validation dataset [12 [2 for devising our proposed cosine gradient Shapley value (CGSV) (Sec. 3.2) which can be efficiently approximated with a bounded error (Sec. 3.3
Secondly, what is the choice of reward? Various choices such as monetary rewards from a pre- allocated budget [63] (66] or the total revenue generated from the collaboration through FL [ [0] have been proposed. Though may seem natural to consider monetary rewards, it is not obvious how a common denomination between money and data/gradients [1 [6]] can be readily established, which
makes it challenging apply these works in practice. Instead, we propose consider the aggregated parameter updates/gradients downloaded from the server as rewards to the agents.
Finally, how can the gradient reward mechanism ensure fairness? Our proposed mechanism exploits a sparsifying gradient trick (Sec. 3.4) for controlling the quality of the aggregated parameter up- date/grad Sate/gradient downloaded from the server as reward to each agent at training time (rather than post hoc [48] 52 (51) such that its quality is commensurate to that of the agent's uploaded/coontributed
parameter update/gradient 2 77. Consequently, an agent who uploads/contributes higher-quality parameter updates/gradients over the entire training process should eventually be rewarded with converged model parameters whose resulting training loss (and hence predictive performance) is closer to that of the server, as demonstrated in our fairness guarantee (Sec. 3.5 152.
In summary, the contributions of our work here CML. and FL. include the following:
We propose a novel cosine gradient Shapley value (CGSV) (Sec. 3.2) to fairly evaluate the expected marginal contribution of each agent's uploaded model parameter update/gradient without needing an auxiliary validation dataset and present an efficient approximation CGSV with a bounded error (Sec. 3.3).
Based on the approximate CGSV, we design a novel sruiningttime gradient reward mechanism (Sec. 3.4) with a fairness guarantee (Sec. (355 by exploiting the trick of sparsifying the aggregated parameter update/gradient downloaded from the server as reward to each agent such that its resulting quality commensurate to that of the agent's uploaded/contributed parameter update/gradient We empirically demonstrate the effectiveness of our fair gradient reward mechanism on multiple benchmark datasets in terms of fairness, predictive performance, and time overhead (Sec. 4
2
Related Work
Reward design and choice in CML. In related topics such FL 33 36
38
47
59
63
66
48 designing appropriate rewards encourage collaboration (c.g., sharing real or synthetic data, gradients, or other information) is non-trivial problem. A useful solution concept should provide formal notion of fairness, a suitable form/denomination of reward, and a principled way guarantee fairness via carefully designed reward mechanism. Previous works have considered monetary rewards from a pre-at allocated budget [65] 66) or the total revenue generated from the collaboration ( 10], or simply an abstract yet quantifiable form of reward 47 48 Though it may seem natural to consider monetary rewards, it is not obvious how a common denomination between money and data/gradients [1 46) can be readily established, which makes it challenging to apply these works in practice. The work of [66] has explored a different avenue of using reverse auction to guarantee truthfulness in its mechanism instead of fairness.
Bayesian CML. [52], collaborative generative modeling [55), and data sharing [13
23

---

Fairness notions. The Shapley value (SV) 50 from cooperative game theory is widely regarded as a principled notion of fairness [
42 due to its several desirable properties such as symmetry
and null player. Existing SV-hased works have considered fairness in the sense of rewarding agents
according to their contributions [19 54 56 However, they typically require the availability of (and
all agents to agree on) an auxiliary validation dataset [77 52] and significant time overhead from
evaluating the agents' contributions in the form of SVs and the resulting model training [14] 19 56].
In contrast, the work of [31] has adopted an egalitarian notion of fairness by aiming to equalize the final individual performance among agents, which is fundamentally different from SV.
Different from the fairesss definition in B1,, we adopt fairesss notion formalized by SV [14 19 52
56) Our proposed work is novel in the application of SV: While previous works use the validation accuracy [14 19 54 [56], we exploit the cosine similarity between model parameter updates/gradient
vectors 12 for devising our proposed cosine gradient Shapley value (CGSV) (Sec. (32) to fairly
evaluate the expected marginal contribution of each agent's uploaded model parameter uppate/gradient Based on the CGSV, we design a novel training-time gradient reward mechanism (Sec. (34) with a
fairesss guarantee (Sec. 3.5) and empirically show that it outperforms several existing FL baselines in terms of predictive performance, fairness, and time overhead (Sec. 4.2).
3 Fair Gradient Reward Mechanism
3.1 Vanilla Federated Learning (FL) Problem Setting and Notations
The vanilla FL problem (56
59 involves set N (i),.,,... of N honest agents learning D-dimensional vector w R.. of model parameters to minimize loss function F(w) that can be additively decomposed into N local differentiable loss functions (((w)) defined using the local dataset D. of agent i N and weighted by its importance p; 2 0 (e.g. proportional to [D; ). That is, F(w) = EiEN P; (wr) where DiENP: Pi: = 1. We call A the grand coalition; a coalition S S W then a subset of the grand coalition N of N agents. In iteration t = O, every agent i N starts with the same initialized parameter vector w;,0 = wo as the server. In iteration t >> 0, every agent i E A calculates parameter update Aw,, = - 1/ VF, (w.,.-1) with step size 1/2 and gradient VF, ( w.r.t. parameter vector , and uploads it to a trusted server who normalizes and aggregates all agents' parameter updates as follows:
U := Aw,,e Aw,,,l
uN = EiEN ri,--1 Uiet
(I)
where I is a normalization coefficient used to prevent gradient explosion 33 45 and the importance coefficient ri,--1 will be described later in Sec Sec So, call (1) the gradient aggregation step. The gradient download step then follows where every agent E N downloads the aggregated parameter update/gradient uN ① from the server (as reward) for updating its model parameters Wi,t = t-,t- + UN, to the same w; == Wt-1 + UNN', as the server. That is, Wi, = w. for all i N and E g U (0). We define us, for any coalition S C W in similar way as uvv ( For brevity, we omit t from our notations in Secs. 3.2 and 3.3 since we only refer to iteration t.
3.2 Cosine Gradient Shapley Value (CGSV) for Fairness
In the gradient aggregation step [ the quality/value of coalition S's (normalized) aggre- gated parameter update/gradient us be measured by its cosine similarity cos(us, uy)
(us. an)/(1 us [[) to the grand coalition ' aggregated parameter update/gradient uw [2
28 35) We use this cosine similarity measure cos( u.s un)) Intuitively, if the direction of u. aligns more closely with that of uy, then its quality/value v(8) is higher. Using v, the contribution Φi of agent E A is defined based on the notion of Shapley value (SV) (50) which measures its expected marginal contribution when joining the other agents preceding such as null player (i.c.. an agent with no marginal contribution has zero SV), symmetry (i.c., agents with identical marginal contributions have equal SVs), among others, as formally discussed in Appendix A.
gradient valuation function v(S)
any permutation and satisfies certain desirable fairness properties (5).
Definition 1 (Cosine gradient Shapley value (CGSV)). Let Ilw be set of all possible permutations of ' and S be the coalition of agents preceding agent i in permutation क E 11y. The CGSV of agent i E N is defined as
&i (LIN!)E=en
[M(S,, v(S..))
(2)
3

---

If @; is negative, then it follows from the weighted sum of parameter updates/gradient in that points an opposite direction some other parameter updates//radients and hence has negative cosine similarities to them. In practice, due to the noisy training arising from the use of stochastic gradient descent (SGD) and/or highly non-convex loss function, Φi may at times be negative even for an honest agent i. When the number of such cases is limited, training via SGD can still converge to yield a competitive predictive performance, as empirically validated in [12].
3.3 Efficient Approximation of CGSV
Since evaluating agent i's CGSV Φ; exactly incurs O(2 D) time and thus costly, we propose an efficient approximation by directly measuring the cosine similarity of its (normalized) parameter update/gradient u, the grand coalition ' aggregated parameter update/gradient u.v which reduces the incurred time by factor of 2 and has a bounded error from o; (Theorem
cos(u,, uN))
(3)
Theorem (Approximation Error), Let I E Rt. Suppose that ||u,|| I' and (uu, uN) 2 1/1 for all i E N. Then, o, Lidh S IT where the multiplicative factor L; can be normalized awwy..
Its proof in Appendix A.2 From Theorem [ the approximation error is bounded and decreases quadratically with normalization coefficient 1". However, I' cannot be reduced to be arbitrarily small, which may cause (u,, ux)) 2 1/7 not hold. It also does not hold when u, is orthogonal to uv or is close to the zero vector, hence implying the quality of that agent i's parameter update/ is not high enough. So, every agent is encouraged contribute a parameter update/gradient of sufficiently high quality in order to ensure the quality of the approximation ab; (Theorem
We have performed simple experiment compare the quality of approximation ti; with that of a sampling-based (e, -)approoxnnttion d; [39], the latter of which is widely used by existing works in data valuation and CML/FL [4
19 52 56 60]. In this experiment, we have drawn N random D-dimensional vectors from a standard multivariate normal distribution to simulate Uj...., uN and calculated the resulting exact CGSVs &f (o+))=1,....N) our approximation &b (v4) Φ == (o.)i=1....., .N. Fig. shows the results for & error, & error, and the incurred time averaged over 10 runs: Our approximation & performs better in all three metrics with varying D (right figure) and the performance gap widens with increasing number N of agents (left figure).
and the sampling-bai
(0.1, 0.1)
I Distancee
AI
A2
Training Loos
0.06
11 Mil
0.04
Time (scronis))
1.0
0.04
0.02
110- M0la
0.5
A5
0.02
18--80 901
2 0.02
0.00
100
100
0.00
Iteaatios
Iterations
6
8
10
20000
agentts
Figure 2: (Left) l2 distance between model pa- rameters of agent 1, ....... 5 (abbreviated to Ad) vs. that of the server, and (right) correspond- ing training loss for FL problem with N agents using local MNIST datasets of 600 im- ages each to collaboratively learn 2-layer CNN parameters where the datasets of A1 (blue), A2 (orange), and A3 (green) have 20%. 40%. and 60% randomly corrupted labels, respectively. The brown line denotes Eg distance between wo (initialization) vs. server's model parameters.
Figure 1: Comparison of & error (blue), & er- ror (orange), and incurred time (green) (i.e., av- eraged over 10 runs) between our approximation ab (solid lines) vs. a sampling-basee -based approxima- tion & (dashed lines) [39 of the exact CGSVs & with (left) varying number N of agents and D 1024, and (right) varying vector dimension D and = 10. For all metrics, lower better.
3.4 Server-Side Training- Training-Time Time Gradient Reward Mechanism
We will now describe the exact details the gradient aggregation and download steps performed by the server to implement our proposed fair gradient reward mechanism:

---

Gradient Aggregation Step. With specified normalization coefficient I' and an initialized coeffi- cient Ts.0. the server performs normalization and aggregation of all agents' parameter updates into uN.. using ( as previously discussed in the FI. problem setting (Sec. [.Tp. Then, the server com- putes our approximation t)t, (3) of the CGSV di,t (2) and updates (and normalizes) the importance coefficient ri, in iteration i via a moving average of V/. given the relative weight a on fi,-- from previous iteration - 1:
The == a 1i + (1 a)) tist Vi.e -i. vi,e/ EVEN
(4)
where Ti.o == O. Note that ri,e 4 is used for deriving the sparsified gradient (5) in the gradient
download step as well as the aggregation of all agents' parameter updates into uN ① in iteration
++ The use of a moving average of the, to compute ri,t 4 provides a smoothed estimate without abrupt fluctuations and reduces the effect of noisy training due to the use of SGD in practice 56).
It also allows a flexible weighting over the iterations of the entire training process: In particular, setting a < 1 can effectively mitigate the noise from random initialization of model parameters wo because the weight on V/,,"' in earlier iteration 1' < l decays exponentially with 55
Gradient Download Step. Recall from the vanilla FL problem setting (Sec. 3.1 that each iteration f, this step involves all agents downloading an identical aggregated parameter update/gradient u.y. ( from the server (as reward) for updating their model parameters to the same w. (as the server), which is expected to converge to yield a competitive predictive performance 8 32 However, such equal rewards to all agents is unfair and will discourage any agent from uploading/contribuing a parameter apdate/gradien of higher quality [7 63 when it can afford to. To ensure faireess, each agent should download some form of aggregated parameter update/gradient as reward that is commensurate to the quality/value of its uploaded/contributer parameter update/gradient. Consequently, an agent who uploads/contributes higher-quality parameter updates/gradients over the entire training process should eventually be rewarded with converged model parameters whose resulting training loss (and hence predictive performance) is closer to that of the server (Theorem 2
To achieve this, we adopt the trick of sparsifying 2 the aggregated parameter update/gradient uw,r downloaded from the server as reward to agent in each iteration Specifically, we zero out fewer of its smallest components (hence higher-quality gradient reward) when the importance coefficient Ts. (i.e., moving average of the approximate CGSV v)..)) is larger:
(5) where mask(u, q) retains the largest max (0, q) components (in magnitude) of u and zeros out all of its other components 2 [1) and 3 > specifies the degree of altruism: Greater altruism gives any agent with a smaller Te,t a larger improvement in the quality of its gradient reward, i.e., a larger reduction in the sparsity of its downloaded v as reward. In the extreme case of B oc, we recover the vanilla FL problem setting (Sec. (Sec.B.1) where all agents are rewarded equally with uN (i.e., best-quality gradient reward v,,, = uv. for all E NN with no sparsification), albeit with importance coefficients ri, possibly differing across agents i E W and dynamically updated over ac trades off fairness for equality in gradient rewards
Vie == mask mask(u,,, qi.:), att- == [D tanh(B r2,e)/ //axxme tanh(3 ry.:)]
iteration E Z+. Hence, increasing /3 from by being more altruistic to any agent with a smaller ri.e: we empirically show the effect of varying B on training loss in Fig. of Sec. 4.2 Note the agent 1* == argmax, tanh(3 rv..) with the largest possible . .t does not benefit from such altruism since it already downloads the best-quality gradient reward (i.e., u.).) according to (5)
Suppose that there exists known threshold r > 0 s.t. Tue 2 for all i E N and t E Z+ and we want to limit the sparsity of any downloaded v,, or, equivalently, ensure the minimum quality of any gradient reward: Specifically, given a predefined threshold c E (0, 1]. we want to guarantee qt.t 2 D cl holds for all i E N and E Z+. By setting 3 s.t. tanh(8 r) 2 C, it follows from 5) and max tanh(3 r..)) < 1 that tanh(8 rs.1)/ (.a)/maxPEN' tanh(3 rT..) 2
tanh(8 rr.)) 2 tanh(3 r) 2 c and hence qu 2 [ x cl ensues. By using the property that (3 r) = (exp(2,3 r) 1)x(exp((2 r) + 1), 3 > In((1 + c) (2)/ can be derived and used for setting B. It further informs us that reducing the sparsity of any downloaded u., or, equivalently, improving the minimum quality of any gradient reward (i.e., by increasing c) requires greater altruism 3 to be introduced, while improving the minimum quality of uploaded/contributed parameter updates/gradient by any agent over the entire training process (hence larger r) eases the need of introducing greater altruism B.
'Sparsifying parameter update/gradient vector means zeroing out some of its components and leaving the others unchanged (33.
5

---

To see why the sparsifying gradient trick (5) can ensure fairness, we illustrate its effect in an FL problem with N agents using local MNIST datasets of 600 images each to collaboratively learn the parameters of a 2-layer convolutional neural network (CNN) where the datasets of agents 1, 2. and have 20%, 40%, and 60% randomly corrupted labels, respectively. The uploadeddcconrributed parameter updates//radients thus decrease in quality from agents 1 to 3 (i.e., 11,e 0.194, 2/2,; = 0.088, and v = 0.043 on average) due to increasingly noisy labels in their datasets, while agents 4 and 5 upload/contribute parameter updates/gradients of high quality (i.e., 14,t = 0.331 and P/.. = 0.342 on average) due to uncorrupted labels their datasets. Consequently, agents to have increasing sparsity (resp.. 34.9%, 67.6%, and 83.0% average) while agents 4 and 5 have little/no sparsity (resp.. 3.5% and 1.1% on average) in their downloaded vi as rewards (3 = 1). Fig. 2 shows that the converged model parameters of agents 1 to grow in &g distance from that of the server (hence increasing training loss) while agents and 5 have the closest converged model parameters (hence lowest training loss).
We provide the pseudocodes performed by the server and agent N in each iteration below. We will discuss in Sec 4.2 how the hyperparameters I' in in (4) and B in (5) are set in our experiments.
Server (f)
I: for all i do
2: Download Awi, from agent
Agent (i,
3: > Gradient Aggregation Step
4: Compute u44 and M4,.. ①I
1: Upload Aws, 1j: VF; (wi..::)1) to server
5: for all i N do
2: Download vs,, from server
Compute Wae (3) and rrA 7: > Gradient Download Step
3: Update wts = WV,,t + V/.t
8: for all i E N do
9: Compute ua, 5 for download by agent
3.5 Fairness Guarantee
We have previously discussed the intuition underlying our notion of fairness in Sec. 3.4 that an agent who uploads/contrrbutes higher-qualiy parameter updates/gradients over the entire training process should eventually rewarded with converged model parameters whose resulting training loss (and hence predictive performance) is closer to that of the server. Note that the importance coefficient rs. 4 measures the overall quality of the parameter updates/gradients uploaded/contributed by agent i over the entire training process till iteration t. Our main result below guarantees notion of fairness that under some conditions on loss function and the server's model parameters w;, if an agent i has larger importance coefficient ri, and model parameters W,,r- closer to that of the server (i.e., w than another agent by at least 2/[2%;..] || in previous iteration t - 1, then it is rewarded with model parameters wic incurring smaller training loss F(w.,)) in iteration t:
Theorem 2 (Fairness in Training Loss). Let dz, == ||w, - wi,ell- Suppose that we is near to stationary point of F for i 1" Z and some regularity conditions on F hold. For all i, il N and L 2 t", if ri.t 2 Tyr, and 0,,,--1 8i,1-1 2 21| |, then F(ws,.) S F(wa.).
Its proof is in Appendix A.3 Our experiments in Appendix B.3 will empirically verify the faireess guarantee in Theorem (and fairness in test accuracy) without needing to impose its conditions.
Experiments and Discussion
4.1 Experimental Settings
Datasets. We perform extensive experiments on image classification datasets like MNIST (26 and CIFAR-10 [21] and text classification datasets like movie review (MR) [44] and Stanford sentiment
treebank (SST) (20]. We use a 2-layer convolutional neural network (CNN) for MNIST (3), a
3-layer CNN for CIFAR-10 [2],, and a text embedding CNN for MR and SST 20
Baselines. We consider several existing FL baselines such as FedAvg 40 q- FFFF CFFL 37
and extended contribution index (ECI) method from [54] utilizing validation accuracy-based SV

---

Table Average test accuracy (%) achieved by the agents collaborating via our fair gradient reward mechanism with varying degrees of altruism 3 vs. tested baselines on all datasets. Each value in brackets denotes the highest test accuracy achieved by any agent.
MNIST
CIFAR-10
MR
SST
No. Agents
10
20
T0
Data Partition
UNI
POW
CLA
UNI
POW
CLA
UNI
POW
CLA
POW
POW
Standalone
(11)
(92)
53 (92)
(91)
89 (92)
48 (90)
(47)
(49)
(44)
47(56)
3T(34)
FodAvg
93 (94)
92. (94)
53 (93)
93 (93)
92 (94)
49 (92)
48 (48)
47 (50)
32 (47)
51(63)
33(35)
4.FFL.
(91)
(45)
(64)
88 (91)
40
(46)
(36)
(28)
12(18)
23(25)
CFFL
(92)
85 (90)
34 (44)
91 (93)
88 (91)
39 (46)
39 (41)
35 (45)
22 (40)
44(53)
31(32)
ECI
(94)
92 (94)
53 (94)
94 (94)
92 (94)
(92)
(49)
(51)
(46)
56(61)
33(34)
DW
93 (94)
92 (94)
53 (93)
(93)
(94)
(92)
48 (48)
47 (50)
32 (47)
ST(622
33(35)
RR
94 (95)
95 (95)
64 (72)
94 (95)
94 (95)
50 (56)
47 (59)
49 (51)
26 (29)
63(65)
36(36)
Our (EU)
94 (94)
94 (94)
54 (94)
(94)
94 (94)
49 (92)
49 (49)
(51)
(46)
54(59)
34(36)
Ours (8 1)
96 (97)
94 (95)
74 (95)
95 (96)
96 (97)
65 (93)
61 (62)
(62)
(54)
62(76)
35(36)
Ours 18 1.2)
(95)
95 (95)
75 (95)
96 (96)
96 (97)
65 (93)
61 (62)
(62)22
(54)
62(75)
34(37)
Ours (8 1.5)
(97)
95 (95)
75 (95)
96 (97)
94 (95)
65 (93)
61 (62)
59 (62)
(54)
62(74)
35(37)
Ours (8
(96)
95 (96)
73 (94)
97 (97)
95 (96)
66 (95)
62 (62)
61 (62)
(54)
62(75)
35(37)
and setting 9t,r for i E N in (5) to be proportional to the agents' CIs. CFFL also utilizes the validation accuracy but is more efficient by using a leave-one-out approach instead of SV, while q-FFL aims at achieving egalitarian fairness by equalizing the local training losses of the agents. Furthermore, implement simple FL. baselines based on round robin (RR), dataset weighted download (DW), and Euclidean distance (EU). RR is commonly adopted in mechanism design ensure faimess 6 34 and also used in FL to schedule gradient downloads [51] 67). For DW (EU). qi. for E N in (5) are set be proportional unnormalized parameter updates from that of the server). We also include standalone agents as a baseline, i.e., each agent trains its CNN using only its local dataset without involving FL..
the agents' local dataset sizes (negative Euclidean distance of their
Performance Metrics. To measure fairness, we consider the scaled Pearson correlatton coefficien p 100 x pearsonr(4p <) [-100, 100] between the test accuracies & achieved by the agents when standalone 37] vs. that & achieved by them when collaborating via a gradient reward mechanism in FL after the entire training process has ended at iteration = T. The corresponding experimental results will be reported in Sec. [.2] To empirically verify the fairness guarantee in Theorem 2 we have also reported in Appendix results
the faimess metric p between the importance coeffi- cients 9 == (ri.r))ml...... I...... (4) (i.e., measuring overall qualities of the parameter updates/gradien uploaded/contrrbbuted by the agents) vs. test accuracies (or negative training losses) & achieved by them. We consider other performance metrics like predictive performance (i.e., average and highest test accuracies achieved by the agents) and time overhead of the tested gradient reward mechanisms.
Data Partitions among Agents. We carefully construct two heterogeneous data partitions by varying the agents' local dataset sizes and corresponding numbers of distinct classes. For imbalanced dataset sizes (POW), we follow a power law to partition the entire dataset among the agents. For MNIST, we partition the entire dataset of size (3000, 6000, 12000), respectively, among {5, 10, 20) agents s.t. each agent has a randomly sampled local dataset of size 600 on average [40]. The size of the local dataset increases from the first to the last agent. Since the local dataset sizes vary significantly (i.e., superlinearly) among the agents, the agents with larger local datasets are expected to achieve better predictive performance. For imbalanced class numbers (CLA), we vary the number of distinet classes in the local datasets of the agents, while keeping their sizes fixed at 600. For this setting, we only consider MNIST and CIFAR-10 datasets and partition classes in a "linspace" manner as both contain 10 classes. To illustrate, for MNIST with 5 agents, agents 1, 2, 3, 4, 5 own local datasets with 3, 5, 7, 10 classes, respectively; so, agent (5) has local dataset with (10) class(es). Similarly, the agents with local datasets containing more classes are expected to achieve better predictive performance. We also include the simplest setting of the uniform/homogeneouss data partition (UNI) where the agents are expected to achieve comparable predictive performance.
Additional details of the experimental settings described in Appendix B.
4.2 Experimental Results
Predictive Performance. Table I shows results of the average and highest test accuracies achieved by the agents collaborating via our fair gradient reward mechanism vs. tested baselines on all
'The Pearson correlation coefficient has been applied to similar case in 19
7

---

Table 2: Faimess metric P E 1-000, 100] achieved by our fair gradient reward mechanism with varying degrees of altruism 3 vs. tested baselines on all datasets. Higher value means greater fairness.
MNIST
CIFAR 10
MR
SST
No. Agents
10
20
10
5
Data Partition
UNI
POW
CLA
UNI
POW
CLA
UNI
POW
CLA
FOW
POW
FodAvg
-45.00
55.24
24.12
0.85
-32.58
40.83
18.47
97.48
98.75
48.08
57.50
g-FFL
-44.73
39.00
22.38
-22.01
38.71
48.07
-17.64
51.33
94,06
56.43
-75.92
CIFLL
83.57
91.80
81.24
82.52
94.70
72.55
81.31
93.34
FCT
85.26
99.83
99.98
80.95
99.41
95.21
75.85
79.50
99.55
97.69
95.00
DW
89.15
98.93
65.34
86,94
99.63
35.21
-23.14
91.97
45.45
99.20
97.12
RR
83.77
71.17
-26.75
-18.64
25:47
95.86
0.70
90.67
44.16
-25.11
Ours (EC)
84.25
98.25
99.82
80,55
97.77
99.97
78.25
94.24
94,95
97.58
93.21
Ours 1)
94.03
95.74
94.54
84,47
96.39
97.23
98.80
98.78
99.89
96.01
98.
Ours (8 1.2)
94.75
97.28
96.23
90.52
97.72
95.21
91.07
91.59
99.82
96.
98.47
Ours [8 1.5))
96.34
86.99
95.37
82.68
90.94
98.75
93.55
93.78
95.89
95,32
97.88
Ours 2)
94.66
91.20
95.38
96,90
91.33
94.32
89.80
88.78
93.39
92.22
95.74
datasets. Our fair gradient reward mechanism generally outperforms the tested baselines on both metrics, especially for heterogeneous data partitions and on the MR dataset. On MNIST, for the CLA data partition among 10 agents, our fair gradient reward mechanism achieves average (highest) test accuracy of 75% (95%) at B 1.5, while the best-performing ECI baseline achieves only that of 53% (94%). On CIFAR-10, for the CLA data partition among 10 agents, our fair gradient reward mechanism achieves average (highest) test accuracy of 36% (54%) at B 2. while the best-performing DW baseline achieves only that of 32% (47%). On the MR dataset, our fair gradient reward mechanism achieves average (highest) test accuracy of 62% (76%) at / 1, while the best-performing RR baseline achieves that of 63% (65%). Its better performance may be attributed to the adaptive re-weighting in the gradient aggregation step ① via Ti.t, which can dynamically account for the heterogeneity in the agents' local datasets [32]. While EU performs comparably to both FedAvg and ECI (i.e., difference in average test accuracies between EU vs. FedAvg/ECI is less than 3%), it does not perform better than our fair gradient reward mechanism (e.g., on MNIST, for the CLA data partition among 10 agents, the difference in average test accuracies between EU vs. our fair gradient reward mechanism at 3 = 1.5 is more than 20%) because unlike cosine similarity, Euclidean distance fails to capture the directional difference between gradients, which is important since the negative gradients are pointing in the direction of lower loss. Importantly, g-FFL aims to equalize the local training losses w.r.t. the agent's 's local datasets, which may suboptimal for heterogeneous data partitions like POW and CLA. We provide further results in Appendix B.5 emppiriclly comparing the predictive performances of our fair gradient reward mechanism vs. q- FFL.
Fairness. To empirically verify the fairness guarantee in Theorem 2 Table 2 shows results on the fairness metric p achieved by our fair gradient reward mechanism vs. tested baselines all datasets. From Table our fair gradient reward mechanism achieves a high degree of fairness of above 80, while the commonly used FedAvg performs suboptimally s.t. it produces the lowest degree of fairness of -4.66 On MNIST, for the POW data partition among 10/20 agents and the CLA data partition among 10 agents. ECI outperforms our fair gradient reward mechanism, albeit at a much higher time overhead of over 100 times and with additional information from an auxiliary dataset. CFFL underperforms our fair gradient reward mechanism and ECI it adopts the leave-one-ous approach which seems less accurate than SV in valuing the contributions of the agents [19]. Both g-FFL and RR promote egalitarian fairnsss instead of our notion of fairness via SV and hence do not perform optimally. DW achieves high degrees of fairness only for the POW data partition because it uses the agents' local dataset sizes to determine their gradient rewards. Fig. 3 illustrates an intuitive trend of the predictive performances achieved by 10 agents collaborating via our fair gradient reward mechanism for homogeneous and heterogencous data partitions among the agents on MNIST and CIFAR-10: 10: For the UNI data partition, all agents achieve comparable predictive performance. Their predictive performances vary more (most) for the POW (CLA) data partition, hence demonstrating that our fair gradient reward mechanism can distinguish the contributions of the agents and reward them with sparsified gradients fairly.
We have performed an additional experiment to understand our fair gradient reward mechanism for homogeneous and heterogeneous data partitions among agents on MNIST and CIFAR-10 where for POW and CLA, agent 1 (3) uploads/contributes parameter updates/gradients of lowest (highest) quality over the entire training process. Fig. 4 shows how ri, for agent 1,3 varies over iterations t: Interestingly, for the CLA data partition, though agent (brown solid line) is initially mistaken to
8

---

MNIST
That Aocuricy
1.00
MNIST (UND 2
Tbat Accuracy
1,00
MNIST (POW) 2
Tbal Accuracy
1.0
MNIST (CIA) B-2
0.75
Intermediato
0.95
0.90
0.8
M
AB
0.90
AS
A10
0.90
0.6
0.25
GAT
0.05
20
40
63
0.85
20
40
60
0.4
20
43
60
0.00
0
UN8
20
40
(terations
Iterations
Iterations
Iterations
CIFAR-10 8=
CIFAR-10 (POW) 2
CIFAR-10 (CLA)
0.6
CIHAR-10
Thst Arcuraty
0.6
Test Accuraty
0.6
Teat Accuracy
0.6
Intermediate fct
A3
A8
0.4
0.4
A6
A0
A5
A1U
0.2
0.2
008
Iterations
180
200
Iberations
100
200
0.0
0
Iterations
100
200
0.0
Iterations
50
100
Figure 3: Test accuracy achieved by agent I,..., 10 (abbreviated to Figure 4: Graphs of Ai) collaborating via our fair gradient reward mechanism at /3 = 2 for ri. ④ for agent i = 1.3 the UNI (left), POW (middle), and CLA (right) data partitions among vs. iteration / for UNI, the 10 agents on MNIST (top) and CIFAR-10 (bottom). Their predictive POW, and CLA data par- performances vary least, more, and most for the respective UNI, POW, and CLA data partitions.
titions among 3 agents on MNIST and CIFAR-10.
MNIST
CIFAR-10
CIFAR-10
0.2
12A1
0.2
2013
0.3
Norm
Vorm
Norm
0.2
1x Norr
0.1
0.1
92
0.1
0.0
0.0
UN13
DOW
CLAS
0.0
034
KOW
0
40
100
50
Dlraatioss
Deerations
lteaaions
Iterations
Figure 5: Graphs of &g distance between down- Figure 6: Graphs of & distance between last loaded Va (5) of agent i = 1.3 and aggregated layer's model parameters of agent i 1. uN.t ① iteration t for UNI, POW, and CLA and that of the server vs. iteration t for UNI. data partitions among 3 agents on MNIST (left) POW, and CLA data partitions among 3 agents on MNIST (left) and CIFAR-10 (right).
and CI (right).
provide low contribution, the dynamic update of ra.t (4) allows its true contribution to be recognized quickly. Fig. (Fig. shows how the l2 distance between the downloaded sparsified gradient vi, (5) of agent: i T, and aggregated parameter update/gradient uN,. (T) (last layer's model parameters of agent 1, 3 and that of the server) varies over iterations t: In particular, for the CLA data partition, agent i = 1 (i = 3) who uploads/contributes parameter apdates/gradients of lowest (highest) quality over the entire training process downloads Va,; as reward that is further from (closer to) uy, a, hence training last layer's 's model parameters to be further from (closer to) that of the server. Such results further validate that in Fig. 2 previously.
Lastly, Fig. 7 confirms that for the CLA data partition among 10 agents on MNIST, increasing the degree of altruism 33 leads to all agents downloading higher-quality gradient rewards va, ( and thus incurring smaller training loss. particular, agent (abbreviated to A and represented by a blue solid line) who uploads/contributes parameter updates/gradients of lowest quality over the entire training process benefits most as 3 increases, as explained previously in Sec. 3.4 Additional results w.r.t. test loss reported in Appendix B.4
Time Overhead. Table 3 compares the time overhead (seconds) of our fair gradient reward mecha- nism vs. tested baselines on all datasets; the ratio between the time overhead vs. training time is given in brackets. Our fair gradient reward mechanism is much more efficient than ECI and CFFL which also consistently achieve fairness. In particular, our fair gradient reward mechanism incurs a small time overhead of at most 0.4x of the training time, while ECI incurs a significant time overhead of up to 140x of the training time due to the calculation of the CI incurring O(2N) time, even with the permutation sampling-bur
approximation [39 566 for 10/20 agents. CFFL incurs most 2x of the
training time (i.e., 5-6 times longer than ours) from the additional validation in each iteration.

---

MNIST (C-A))8-1 8-1
MNIST (CLA) 8.1.
MNIST 8-1.
MNIST (CLA)
Train Loss
15
Train Loss
15.
Train Loss
Train Loss. To
10:
10
To
AU A3C
20
40
60
20
40
60
20
40
60
20
40
60
Iterations
Deeaations
Iterations
tterations
Figure 7: Training losses incurred by agent i i= =, ...... 10 (abbreviated to Ai) collaborating via our fair gradient reward mechanism with varying degrees of altruism 3 = 1.0, 1.2, 1.5, 2 for the CLA data partition on MNIST.
Table Time overhead (seconds) of our fair gradient reward mechanism tested baselines on all datasets. Each value in brackets denotes the ratio between the time overhead vs. training time.
MNIST
CIFAR-10
MR 5
SST
No. Agents
5
10
20
5
FodAvg
1.17 (7--3)
1,05 (le-2)
4.29 (1o-2)
(76-))
(o-22
1.3 (lc(4)-)
1.31 (6o-4)
4-FFL
6,14 (4e-2)
4.97 (5c-2)
91.20 (0.3)
97.28 (0:4)
58.94 (7c-2)
90.01 (8c-3)
82.85 (4o-2)
CFFL
32.15 (0.2)
21.79 (0.3)
500.03 (1.6)
570.12 (2.0)
302.44 (0:4)
479. 12 (0.2)
487.71 (2e-1)
ECI
2377.33
11937,80 (141)
23749:06
3571.75
58835.83 (84)
422.85 (4e 2)
801.20
DW
0.89 (6e-3)
0.79 (9e-3)
1.60 (Se-3)
(5e-3)
5.29 (7e-3)
0.99 (1e-5)
0.98 (5c-4)
RR
0.89 (6e-3)
(9e
1.60 (5e-3)
3.31 (1e:2)
(7e-3)
1.01 (5e
0.99 (5e-4)
Ours: (FL))
0.89 (6e-3)
0.81 (9e-3)
1.61 (5e.3)
1,22 (Se-3)
5.33 (7e-3)
1.01 (5c-4)
0.99 (5e-4)
Ours (Cosinc)
6.34 (4o-2)
4.94 (5o-2)
94.30 (0.3)
98.39 (0.4)
54.94 (7o-2)
89.81 (8o-3)
82.87 (4o-2)
Hyperparameters. We find that a E [0.8, 1),i.., relative weight ri in B [1,2] (i.e., degree of altruism in (5) and r E [0.1, (i.e., normalization coefficient in ① are effective in achieving competitive predictive performance and fairness. In our experiments, we set = 0.95, 3 = 1.2, 1.5, 2], and I = 0.5 for MNIST, I = 0.15 for CIFAR-10, and I' = 1 for SST and MR.
5
Conclusion and Future Work
In this paper, we have described a novel cosine gradient Shapley value (CGSV) (Sec. 3.2) to fairly evaluate the expected marginal contribution of each agent's uploaded model parameter update/gradien in FL without needing an auxiliary validation dataset and present an efficient approximation of CGSV with bounded error (Sec. 3.3). Based on the approximate CGSV, we have designed a novel training- time fair gradient reward mechanism (Sec. 3.4) by exploiting the trick of sparsifying the aggregated parameter ppdate/gradien downloaded from the server as reward to each agent such that its resulting quality is commensurate to that of the agent's uploaded/contributee parameter update/gradient. Conse- quently, an agent who uploads/contributes higher-quality parameter updates/gradient training process should eventually be rewarded with converged model parameters whose resulting training loss (and hence predictive performance) closer to that of the server, as demonstrated in our fairness guarantee (Sec. (.5). We have empirically demonstrated the effectiveness of our fair gradient reward mechanism on multiple benchmark datasets in terms of fairness, predictive performance, and time overhead (Sec. In particular, our fair gradient reward mechanism is much more efficient than several existing FL baselines since it requires only slight calculations by the server.
over the entire
Our proposed fair gradient reward mechanism also provides practitioners the flexibility to trade off between fairness and equality in gradient rewards via a hyperparameter 3 controlling the degree of altruism (Sec. (.4). For future work, it would be interesting to consider the notion of fairness when there are some adversaries. We would also consider generalizing our work and fairness guarantee to
other types of CML (e.g., model fusion [16] 17 24 and collaborative Bayesian optimization [53].
Acknowledgments and Disclosure of Funding
This research is supported by the National Research Foundation, Singapore under its AI Singapore Programme (Award No: AISG2-RP-2020-01
Any opinions, findings and conclusions or recom- mendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore. Xinyi Xu is supported by the Institute for Infocomm Research of Agency for Science, Technology and Research (A *STAR).
10

---

References
[1] A. Agarwal, M. Dahleh, and T. Sarkar. A marketplace for data: An algorithmic solution. In Proc. EC, 2019.
[2] D. Alistarh, T. Hoefter, M. Johansson, S. Khirirat, N. Konstantinov, and C. Renggli. The convergence of sparsified gradient methods. In Proc. NeurlPS, 2018.
[3] M. Bahir, M. And, B. Peleg, M. Maschler, and B. Peleg. A characterization, existence proof and dimension bounds for the kernel of game. Pacific Journal of Mathematics, 18(2), 1966.
[4] E. Balkanski and Singer. Mechanisms for fair attribution. In Proc. EC, 2015.
[5] G. Chalkiadakis. Elkind, and M. Wooldridge. Computational aspects of cooperative game theory. In R. J. Brachman, W. W. Cohen, and T. G. Dietterich, editors. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2011.
[6] C. Chen, W. Wang, and Li. Round-robin synchronization: Mitigating communication bottlenecks in parameter servers. In Proc. IEEE INFOCOM, 2019.
[7] C. Y. Chen, J. Choi, D. Brand, A. Agrawal, W. Zhang, and K. Gopalakrishnan. ADaComP: Adaptive residual gradient compression for data-parallel distributed training. In Proc. AAAI, 2018.
[8] M. Chen, B. Mao, and T. Ma. Fedsa: A staleness-aware asynchronous federated learning algorithm with non-iid data. Future Generation Computer Systems, 120:1-12, 2021.
[9] Z. Chen, Z. Liu, K. L. Ng. H. Yu, Y. Liu, and Q Yang. gamified research tool for incentive mechanism design in federated learning. In Q. Yang, L. Fan, and H. Yu, editors, Federated Learning, volume 12500 of Lecture Notes in Computer Science, pages 165-175. Springer, Cham, 2020.
[10] M. Cong, H. Yu, X. Weng, and S. Yiu. A game-theoretic framework for incentive mechanism design in federated learning. In Q. Yang, L. Fan, and H. Yu, editors, Federated Learning, volume 12500 of Lecture Notes in Computer Science, pages 205-222 Springer, Cham, 2020.
[11] V. Conitzer and T. Sandholm. Computing shapley values, manipulating value division schemes, and checking core membership in multi-issue domains. In Proc. AAAI, 2004.
[12] W. Dai, Y. Zhou, N. Dong, H. Zhang, and Eric P. Xing. Toward understanding the impact of staleness in distributed machine learning. In Proc. ICLR, 2019.
[13] J. M. Drazen, S. Morrissey, D. Malina, M. B. Hamel, and E. W. Campion. The importance and the complexities - of data sharing. New England Journal of Medicine, 375 182111))1112-1833, 2016.
[14] A. Ghorbani and Y. Zou. Data Shapley: Equitable valuation of data for machine learning. In Proc. ICML, 2019.
[15] A. Hard, K. Rao, R. Mathews, F. Beaufays, S. Augenstein, H. Eichner, C. Kiddon, and D. Ram- age. Federated learning for mobile keyboard prediction. arXiv: 1811111110000 1,03604, 2018.
[16] Q M. Hoang, T. N. Hoang, B. K. H. Low, and C. Kingsford. Collective model fusion for multiple black-box experts. In Proc. ICML, pages 2742-2750, 2019.
[17] T. N. Hoang, C. T. Lam, B. K. H. Low, and P. Jaillet. Learning task-agnostic embedding of multiple black-box experts for multi-task model fusion. In Proc. ICML, pages 4282-4292, 2020.
[18) Y. Hu, D. NIu, J. Yang, and S. Zhou. Fdml: collaborative machine learning framework for distributed features. In Proc. SIGKDD, page
2019.
[19] R. Jia, D. Dao, B. Wang, F. A. Hubis, N. Hynes, N. M. Gürel, B. Li, C. Zhang, D. Song, and C. J. Spanos. Towards efficient data valuation based on the Shapley value. In Proc. AISTATS, 2019.
11

---

[20] Y. Kim. Convolutional neural networks for sentence classification. In Proc. EMNLP, 2014.
[21] A. Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, Depart- ment of Computer Science, University of Toronto, 2009.
[22] A. Krizhevsky, I. Sutskever, and G. E. Hinton. ImageNet classification with deep convolutional neural networks. In Proc. NeurIPS, 2012.
[23] H. M. Krumholz and Waldstreicher. Toward faimess in data sharing. New England Journal of Medicine, 375(5):405-400 2016.
[24] C. T. Lam, T. N. Hoang. B. K. H. Low, and Jaillet. Model fusion for personalized learning. In Proc. ICML, pages 5948-5958, 2021.
[25] Y. LeCun, B. Boser, Denker, D. Henderson, Howard, W. Hubbard, and Jackel. Hand- written digit recognition with fack-propagation network. In Proc. NeurlPS, 1990.
[26] Y. Lecun, L.. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 1998.
[27] D. Leroy, A. Coucke, T. Lavril, T. Gisselbrecht, and J. Dureau. Federated learning for keyword spotting. In Proc. ICASSP, 2019.
[28] H. Li, Z. Xu, G. Taylor, C. Studer, and T. Goldstein. Visualizing the loss landscape of neural nets. In Proc. NeurlPS, 2018.
[29] Q. Li, Z. Wen, Z. Wu, S. Hu, N. Wang, Y. Li, X. Liu, and B. He. A survey on federated learning systems: Vision, hype and reality for data privacy and protection. IEEE Transactions on Knowledge and Data Engineering, 2021.
[30] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-66 2020.
[31] Li, M. Sanjabi, A. Beirami, and V. Smith, Fair resource allocation in federated learning. In Proc. ICLR, 2020.
[32] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang. On the convergence of FedAvg non-iid data. In Proc. ICLR, 2020.
[33] Y. Lin, Wang. S. Han, W. Dally, and H. Mao. Deep gradient compression: Reducing the communication bandwidth for distributed training. In Proc. ICLR, 2018.
[34] R. Lipton, E. Markakis, Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In Proc. EC, 2004.
[35] E. Lorch. Visualizing Deep Network Training Trajectories with PCA. In Proc. ICMI., 2016.
[36] L. Lyu, Y. Li, K. Nandakumar, J. Yu, and X. Ma. How to democratise and protect Al: Fair and differentially private decentralised deep learning. IEEE Transactions on Dependable and Secure Computing, 2020.
[37] L. Lyu, X. Xu, Q. Wang, and H. Yu. Collaborative faimess in federated learning. In Q. Yang, L. Fan, and H. Yu, editors, Federated Learning, volume 12500 of Lecture Notes in Computer Science, pages 189-204. Springer, Cham, 2020.
[38] L. Lyu, J. Yu, K. Nandakumar, Y. Li, X. Ma, J. Jin, H. Yu, and K. S. Ng. Towards fair and privacy-preserving federated deep models. IEEE Transactions on Parallel and Distributed Systems, 31(11):2524-2541 2020.
[39] Maleki, L. Tran-Thanh, G. Hines, T. Rahwan, and A. Rogers. Bounding the estimation error of sampling-based Shapley value approximation with/without stratifying. arXiv:1306.44 2013.
[40] B. McMahan, F. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication--fficieen learning of deep networks from decentralized data. In Proc. A/STATS, 2017.
12

---

[41] B. McMahan and D. Ramage. Federated learning: Collaborative machine learn-
ing without centralized training data. federated Leatee---eaninngollbabbeoaa
https: h/taaaigggggbbl/ 1ooggleeloo..cm/2217/00000 Accessed: 2021-10-08.
html
[42] T. P. Michalak, P. L. Szezepański, T. Rahwan, A. Chrobak, S. Brânzei, M. Wooldridge, and N. R. Jennings. Implementation and computation of value for generalized characteristic function games. ACM Transactions on Economics and Compulation, 2(4), 2014.
[43] D. Ng. X. Lan, M. M.-S. Yao, W. P. Chan, and M. Feng. Federated learning: a collaborative effort to achieve better medical imaging models for individual sites that have small labelled datasets. Quantitative Imaging in Medicine and Surgery, 11(2), 2020.
[44] B. Pang and I.. Lee. Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales. In Proc. ACL., 2005.
[45] R. Pascanu, T. Mikolov, and Y. Bengio. On the difficulty of training recurrent neural networks. In Proc. ICML., 2013.
[46] R. Raskar, P. Vepakomma, T. Swedish, and A. Sharan. Data markets to support Al for all: Pricing, valuation and governance.
2019.
[47] A. Richardson, A. Filos-Rassikar and B. Faltings. Budget-boundee incentives for federated learning. In Q. Yang, L. Fan, and H. Yu, editors, Federated Learning, volume 12500 of Lecture Notes in Computer Science, pages 176-188, Springer, Cham, 2020.
[48] A. Richardson, A. Ailos-Rassikas, and B. Faltings. Incentivizing and rewarding high-quality data via influence functions. In Proc. ICMI. Workshop on Incentives in Machine Learning, 2020.
[49] N. Rieke, J. Hancox, W. Li, F. Milletari, H. R. Roth, S. Albarqouni, S. Bakas, M. N. Galtier, B. A. Landman, K. Maier-Hein, S. Ourselin, M. Sheller, R. M. Summers, A. Trask, D. Xu, M. Baust, and M. J. Cardoso. The future of digital health with federated learning. npj Digital Medicine, 3(119), 2020.
[50] L. S. Shapley, A value for n-person games. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games, volume 2, pages 307-317, Princeton Univ. Press, 1953.
[51] R. Shokri and V. Shmatikov. Privacy-preserving deep learning. In Proc. ACM SIGSAC, 2015.
[52] R. H. I. Sim, Y. Zhang, M. C. Chan, and B. K. H. Low. Collaborative machine learning with incentive-aware model rewards. In Proc. ICMI., 2020.
[53] R. H. L. Sim, Y. Zhang, B. K. H. Low, and P. Jaillet. Collaborative Bayesian optimization with fair regret. In Proc. ICML, pages 9691-9701, 2021.
[54] Song, Y. Tong, and S. Wei. Profit allocation for federated learning. In Proc. IEEE International Conference on Big Data, 2019.
[55] S. Tay, X. Xu, C. S. Foo, and B. K. H. Low. Incentivizing collaboration in machine learning via synthetic data rewards. Proc. AAAI, 2022.
[56] Wang, Rausch, C. Zhang, R. Jia, and D. Song. principled approach to data valuation for federated learning. In Q. Yang, L. Fan, and H. Yu, editors, Federated Learning, volume 12500 of Lecture Notes in Computer Science, pages 153-167. Springer, Cham, 2020.
[57] K. Wei, J. Li, C. Ma, M. Ding, and H. V. Poor. Differentially private federated learning: Algorithm, analysis and optimization. In Federated Learning Systems: Towards Gexe-Geneo AI, pages 51-78. Springer International Publishing, Cham, 2021.
[58] E. Winter. The Shapley value. In R. Aumann and S. Hart, editors, Handbook of Game Theory with Economic Applications, volume 3, chapter 53, pages 2025-2054. Elsevier B.V., 2002.
[59] X. Xu and L. Lyu. A reputation mechanism is all you need: Collaborative fairness and adversarial robustness in federated learning. In Proc. ICMI. Workshop on Federated Learning for User Privacy and Data Confidentiality, 2021.
13

---

[60] X. Xu, Z. Wu, C. Foo, and B. K. H. Low. Validation free and replication robust volume-based data valuation. In Proc. NeurIPS, 2021.
[61] Z. Yan, D. Xiao, M. Chen, J. Zhou, and W. Wu, Dual-way gradient sparsification for asyn- chronous distributed deep learning. In Proc. ICPP, 2020.
[62] Q. Yang, Y. Liu, T. Chen, and Y. Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology, 10(2), 2019.
[63] Q- Yang, Y. Liu, Y. Cheng, Y. Kang, T. Chen, and H. Yu. Federated Learning. Morgan & Claypool Publishers, 2019.
[64] H. P. Young. Monotonic solutions of cooperative games. International Journal of Game Theory, 14(2):65-72, 1985.
[65] H. Yu, Z. Liu, Y. Liu, T. Chen, M. Cong, X. Weng, D. Niyato, and Q. Yang. A fairness-aware incentive scheme for federated learning. Proc. AIES, 2020.
[66] J. Zhang, Wu, and R. Pan. Incentive mechanism for horizontal federated learning based on reputation and reverse auction. In Proc. WheWebConf, page 947-956, 2021.
[67] S. Zhang, A. Choromanska, and Y. LeCun. Deep learning with elastic averaging SGD, In Proc. NeurIPS, 2015.
14


Reviews:
[{"review_id": "qxvK2WO8A6", "reviewer": "Reviewer_P3C7", "summary": "This paper proposed an interesting algorithm that aims for collaborative fairness using gradient information (cosine gradient shapley). Overall the paper is well-written and well-motivated. My main concerns are two folded: (1) The current empirical setting is not clear; (2) the fundamental motivation and the potential application of this proposed method is not clear to me. I, therefore, hope authors can elaborate more along those lines.", "questions": "", "limitations": "", "rating": 6, "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": "Pros:\n\n(1) This paper is well-written and well-organized. \n\n(2) The empirical section considers an adequate amount of datasets. In the fairness result, it is interesting to see the proposed algorithm can correct misidentified agent (who was originally mistaken to have low contribution).\n\n(3) The technique/theoretical results are correct to me.\n\nCons:\n\n(1) The authors define the reward as the quality of the downloaded gradient. Specifically, a local device with a high contribution should be given a gradient that is close to the true averaged gradient while devices with lower contributions should be given sparsified gradients. This strategy intuitively makes sense to me. However, after thinking about it in-depth, I am worried about the convergence behavior. Specifically, since the local gradients are sparsified (contaminated), the trained local model will also be contaminated. Therefore, at the aggregation stage, the aggregated gradient/parameter is problematic. Will this strategy still make the optimizer converges to a stationary point? If not, the authors should clearly discuss this limitation. If yes, what is the intuition behind this? Is there any theoretical justification?\n\nFurthermore, since the aggregated gradient is, in fact, contaminated, it is also unfair to the high-contributed devices: for instance, why should they get this contaminated aggregated gradient/parameter? Under some extreme conditions, why not training solely on their local data/model instead of collaborating with others?\n\n(2) It is not clear to me how to reasonably sparsify the gradient. Suppose all local devices are honest and willing to train a global model. However, some devices have very little data or low-quality data, which they cannot control by themselves. In this case, the proposed algorithm will discriminate against those minorities and assign them low-quality gradient/parameter. This vicious cycle will continue and situations will become worse and worse. Is this still fair?\n\n(3) The experimental setup for results in Table 1 is not clear. Specifically, how many local devices provide low-quality models? If so, what is the reason? Is it because they are unwilling to share gradients, providing fake gradients, or they have low-quality datasets? \n\n(4) Authors mentioned that \"we expect the agents with more classes to receive better models\". This is fundamentally an unfair argument for fairness, even though the goal is collaborative fairness. Also, this statement clearly assumes all agents are honest or almost honest and classifies agents based on their provided gradients. Under this scenario, what if a local device with a large amount of high-quality data is unwilling to collaborate with others and providing a fake gradient? Will this local device significantly affect other devices and the overall performance?\n\nOverall, if I understand correctly, the proposed model is in fact ranking local devices by the quality of their data/model. This is unfair to honest users with low-quality or small amounts of data. Given this argument, I am unsure why the proposed fairness definition is meaningful. I, therefore, hope the authors can clearly define the real-world justification (not application) scenario of the proposed algorithm. Here kindly note that I am not asking for additional experiments. Instead, I want to see under what scenario will this model be useful and proposed fairness definition is justifiable. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The defined collaborative fairness somehow conflicts with traditional fairness. I understand that the fundamental goal is different but this proposed algorithm is unfair to minority groups. I, therefore, want to see how to make the proposed algorithm balance between collaborative fairness and traditional fairness (e.g., q-FFL).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "qrDOMGZKQxC", "reviewer": "Reviewer_Frjv", "summary": "The paper studies a collaborative setting where platform aims to facilitate self-interested agents pooling their resources towards a common learning task. Each agent calculates the gradient on their local objective that is based on their local dataset, and the common goal is to optimize a weighted sum of these objectives. The author propose that agents be given sparse approximations of the average gradient, where the approximation quality matches the ranked order given by the Shapley value, where the value of a subset is the angle between the average gradient reported by agents on that subset and the average gradient across all agents. They prove that agents who upload better agents have better predictive performance guarantees and evaluate their approach on several datasets. ", "questions": "", "limitations": "", "rating": 6, "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": "While collaborative learning is becoming more mainstream in applications, there has been limited attention in the academic literature on how to best facilitate the pooling of resources by self-interested agents. The idea of using the Shapley value (which is standard in cooperative game theory) to determine rewards in the context of collaborative learning is very natural and interesting. The approach of giving agents information whose “quality” is based on the Shapley value, rather than simply using the Shapley value to determine monetary transfers, is very interesting.  The paper is generally well-written.\n\nOne weakness is with the definition of Cosine Gradient Shapley Value. It is not clear that taking the inner product with the average gradient reported by all agents is always meaningful. Even if the agents start at the same point at initialization, their trajectories might diverge significantly since they are given different gradients, and so the geometric proximity to the average gradient may not be an appropriate measure of quality. \n\nAnother weakness is that the authors do not provide theoretical insights into how the predictive performance for each agent changes with beta (the “altruism degree”) or how the rate of convergence changes with beta. \n\nLastly, regarding the estimator of Cosine Gradient Shapley Value in (3), this estimator does not seem to be unbiased, and the resulting bound in Theorem 1 requires an assumption on the inner products.  The empirical comparison against typical sampling-based approaches is fairly limited, and it would be helpful to discuss the advantages and disadvantages of the proposed estimator.\n\nIt would also be helpful to discuss motivating applications where agents give gradients at each step, rather than directly sharing their data or their learned model with the platform.\n\n----------\nUpdate: Thanks to the authors for their detailed responses! I appreciate the authors' additional justifications of Cosine similarity (e.g. in relation to the cited work below and also in Appendix A.1), and have raised my score. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately discuss the societal impact within the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "PKeZLuFCLY7", "reviewer": "Reviewer_ztAX", "summary": "A gradient-based solution to the fair reward allocation problem in gradient-based collaborative ML/FL with theoretical guarantees on fairness. The authors proposed a Cosine Gradient Shapley to formalize the fairness.\n", "questions": "", "limitations": "", "rating": 7, "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:\n1. An efficient approximation to the Cosine Gradient Shapley to address the computational issue of the Shapley value. \n2. No validation dataset is required to evaluate participant's contribution.\n3. Extensive experiments to demonstrate the effectiveness of the proposed solution in achieving fairness.\n\nWeakness:\n1. The high-level explanation on how fairness is achieved using sparsification of gradients can be clearer.\n2. More comparison with existing methods such q-FFL should be added.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "0tFgbUGV6o2", "reviewer": "Reviewer_USs6", "summary": "This paper explores the problem of unequal contribution in a gradient-based collaborative learning. The authors propose Cosine Gradient Shapley (CGS) measure together with gradient compatibility function to evaluate shared gradient qualities to assign a fair reward to contributing agents. Extensive set of experiments were conducted to support the proposed ideas and show effectiveness of the approach.", "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": "This work builds upon existing solutions by improving the reward allocation function through a CGS. One of the main advantages of the work is that authors provide an approximation of CGS, since an original measure is computationally expensive. This submission is technically sound and properly supports claims by theoretical analysis.\n\nWhile most of the paper is clear, I would recommend making a number of corrections. First, “Fairness” is a separate direction of research in ML. It is clear in what context authors are using term “fairness”, I would still recommend changing it and use something like “fair distribution”, i.e. clarify context of fairness.\n\nPlease clarify the following question: since it was not clear to me after reading the paper. For those agents, who fail contributing good gradient since the start of the training, is there a chance for them to recover? Or they end up crossing the point of no return? The second question is: what would be edge cases in your solution? And how to properly address them? For example, imagine the situation that in the beginning of the training all returned gradients are pointing into different directions equally distant from each other. What to do? And is this situation possible? Or what if we have agents, which dominate the training and getting most of rewards, are we missing valuable gradient corrections from other agents in this case? Can we check it somehow?\n\nSome comments about proofreading and typos, e.g. line 81 “ the following the optimization” and line 179 “leads to to …”\n\nThe information on experiments and hyperparameters is enough to reproduce the results. Here are some suggestions on the Experiment section: Pictures are extremely small. While I can zoom in on them on my PC, it is impossible to read them on a printed version. How are hyperparameters picked? e.g. degree of altruism, what works for which tasks.\n\nRelated Work section needs to be improved. Please elaborate more on the existing reward designs and combine section “Reward designs in CML” and “Reward selection” and provide more discussion on advantages and disadvantages of existing works, e.g. in abstract authors mention a necessity of using a validation dataset.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors noted potential limitations in their work in section 4.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper develops an interesting measure for user contribution in collaborative machine learning and an associated compensation mechanism. In general, the reviewers are positive about this paper.  The discussion has resolved several issues raised by the reviewers. Please update the paper to clarify the issues in the next revision. 
Decision: Accept (Poster)