Gradient-Driven Rewards to Guarantee Fairness in Collaborative Machine Learning
Year: 2022

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.

heading: 1 Introduction
text: In collaborative machine learning (CML), multiple agents (e.g., researchers, organizations, companies) pool their resources (e.g., data) together for a common learning task. It spans a wide variety of real-world applications such as digital healthcare [49], clinical trial research [13, 23], wake word detection for smart voice assistants [27], and next word prediction on mobile devices [15].
Federated learning (FL) provides a natural paradigm of CML [18, 29, 41, 43, 57, 62]. In FL, the agents perform local model training (e.g., using stochastic gradient descent) and share their resulting model parameter updates/gradients via a trusted server [40, 56, 59]. An important distinction of our work here from the standard FL literature is that the agents are self-interested and hence not necessarily cooperative like the worker nodes in distributed learning. The implication is that to achieve competitive predictive performance for the learning task, it is imperative to incentivize/reward the agents for contributing/sharing high-quality information in the form of model parameter updates/gradients [47, 48, 52].
∗Equal contribution.
35th Conference on Neural Information Processing Systems (NeurIPS 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 a suitable notion of fairness? The Shapley value (SV) [50] from cooperative game theory is an appealing choice and has been used in ML [14] and FL [54, 56]. However, existing SV-based works [19, 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 uploaded/contributed model parameter update/gradient vector (or that aggregated over some agents) to that aggregated over all agents (hence measuring its quality/value and circumventing the need for a validation dataset [12, 52]) 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 preallocated budget [65, 66] or the total revenue generated from the collaboration through FL [9, 10] have been proposed. 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. Instead, we propose to 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 update/gradient downloaded from the server as reward to each agent at training time (rather than post hoc [48, 52, 65]) such that its quality is commensurate to that of the agent’s uploaded/contributed parameter update/gradient [2, 7]. 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) [52].
In summary, the contributions of our work here to 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 of CGSV with a bounded error (Sec. 3.3). • Based on the approximate CGSV, we design a novel training-time gradient reward mechanism (Sec. 3.4) with a fairness guarantee (Sec. 3.5) 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 is 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).

heading: 2 Related Work
text: Reward design and choice in CML. In related topics such as FL [30, 36, 38, 47, 59, 63, 66], Bayesian CML [52], collaborative generative modeling [55], and data sharing [13, 23, 48], designing appropriate rewards to encourage collaboration (e.g., sharing real or synthetic data, gradients, or other information) is a non-trivial problem. A useful solution concept should provide a formal notion of fairness, a suitable form/denomination of reward, and a principled way to guarantee fairness via a carefully designed reward mechanism. Previous works have considered monetary rewards from a pre-allocated budget [65, 66] or the total revenue generated from the collaboration [9, 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 a reverse auction to guarantee truthfulness in its mechanism instead of fairness.
Fairness notions. The Shapley value (SV) [50] from cooperative game theory is widely regarded as a principled notion of fairness [4, 11, 42] due to its several desirable properties such as symmetry and null player. Existing SV-based 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 [37, 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 fairness definition in [31], we adopt a fairness notion formalized by SV [14, 19, 52, 54, 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. 3.2) to fairly evaluate the expected marginal contribution of each agent’s uploaded model parameter update/gradient. Based on the CGSV, we design a novel training-time gradient reward mechanism (Sec. 3.4) with a fairness 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).

heading: 3 Fair Gradient Reward Mechanism

heading: 3.1 Vanilla Federated Learning (FL) Problem Setting and Notations
text: The vanilla FL problem [56, 59] involves a set N := {i}i=1,...,N of N honest agents learning a D-dimensional vector w ∈ RD of model parameters to minimize a loss function F(w) that can be additively decomposed into N local differentiable loss functions Fi(w) defined using the local dataset Di of agent i ∈ N and weighted by its importance pi ≥ 0 (e.g., proportional to |Di|). That is, F(w) := ∑ i∈N pi Fi(w) where ∑ i∈N pi = 1. We call N the grand coalition; a coalition S ⊆ N is then a subset of the grand coalition N of N agents. In iteration t = 0, every agent i ∈ N starts with the same initialized parameter vector wi,0 := w0 as the server. In iteration t > 0, every agent i ∈ N calculates a parameter update ∆wi,t := −ηt∇Fi(wi,t−1) with step size ηt and gradient ∇Fi(wi,t−1) w.r.t. parameter vector wi,t−1 and uploads it to a trusted server who normalizes and aggregates all agents’ parameter updates as follows:
ui,t := Γ ∆wi,t/‖∆wi,t‖ , uN ,t := ∑ i∈N ri,t−1 ui,t (1)
where Γ is a normalization coefficient used to prevent gradient explosion [33, 45] and the importance coefficient ri,t−1 will be described later in Sec 3.4. So, we call (1) the gradient aggregation step. The gradient download step then follows where every agent i ∈ N downloads the aggregated parameter update/gradient uN ,t (1) from the server (as reward) for updating its model parameters wi,t := wi,t−1 + uN ,t to the same wt := wt−1 + uN ,t as the server. That is, wi,t = wt for all i ∈ N and t ∈ Z+ ∪ {0}. We define uS,t for any coalition S ⊆ N in a similar way as uN ,t (1). For brevity, we omit t from our notations in Secs. 3.2 and 3.3 since we only refer to iteration t.

heading: 3.2 Cosine Gradient Shapley Value (CGSV) for Fairness
text: In the gradient aggregation step (1), the quality/value of coalition S’s (normalized) aggregated parameter update/gradient uS can be measured by its cosine similarity cos(uS ,uN ) := 〈uS ,uN 〉/(‖uS‖‖uN ‖) to the grand coalition N ’s aggregated parameter update/gradient uN [12, 28, 35]. We use this cosine similarity measure as our gradient valuation function ν(S) := cos(uS ,uN ). Intuitively, if the direction of uS aligns more closely with that of uN , then its quality/value ν(S) is higher. Using ν, the contribution φi of agent i ∈ N is defined based on the notion of Shapley value (SV) [50] which measures its expected marginal contribution when joining the other agents preceding it in any permutation and satisfies certain desirable fairness properties [5], such as null player (i.e., an agent with no marginal contribution has zero SV), symmetry (i.e., agents with identical marginal contributions have equal SVs), among others, as formally discussed in Appendix A.1:
Definition 1 (Cosine gradient Shapley value (CGSV)). Let ΠN be a set of all possible permutations of N and Sπ,i be the coalition of agents preceding agent i in permutation π ∈ ΠN . The CGSV of agent i ∈ N is defined as
φi := (1/N !) ∑ π∈ΠN [ ν(Sπ,i ∪ {i})− ν(Sπ,i) ] . (2)
If φi is negative, then it follows from the weighted sum of parameter updates/gradients in (1) that ui points in an opposite direction to some other parameter updates/gradients 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 a 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].

heading: 3.3 Efficient Approximation of CGSV
text: Since evaluating agent i’s CGSV φi (2) exactly incurs O(2ND) time and is thus costly, we propose an efficient approximation by directly measuring the cosine similarity of its (normalized) parameter update/gradient ui to the grand coalition N ’s aggregated parameter update/gradient uN , which reduces the incurred time by a factor of 2N and has a bounded error from φi (Theorem 1): φi ≈ ψi := cos(ui,uN ) . (3) Theorem 1 (Approximation Error). Let I ∈ R+. Suppose that ‖ui‖ = Γ and |〈ui,uN 〉| ≥ 1/I for all i ∈ N . Then, φi − Liψi ≤ IΓ2 where the multiplicative factor Li can be normalized away.
Its proof is in Appendix A.2. From Theorem 1, the approximation error is bounded and decreases quadratically with normalization coefficient Γ. However, Γ cannot be reduced to be arbitrarily small, which may cause |〈ui,uN 〉| ≥ 1/I not to hold. It also does not hold when ui is orthogonal to uN or is close to the zero vector, hence implying the quality of that agent i’s parameter update/gradient is not high enough. So, every agent is encouraged to contribute a parameter update/gradient of sufficiently high quality in order to ensure the quality of the approximation ψi (Theorem 1).
We have performed a simple experiment to compare the quality of our approximation ψi with that of a sampling-based ( , δ)-approximation φ̄i [39], the latter of which is widely used by existing works in data valuation and CML/FL [14, 19, 52, 56, 60]. In this experiment, we have drawn N random D-dimensional vectors from a standard multivariate normal distribution to simulate u1, . . . ,uN and calculated the resulting exact CGSVs φ := (φi)i=1,...,N , our approximation ψ := (ψi)i=1,...,N , and the sampling-based (0.1, 0.1)-approximation φ̄ := (φ̄i)i=1,...,N . Fig. 1 shows the results for `1 error, `2 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 an increasing number N of agents (left figure).

heading: 3.4 Server-Side Training-Time Gradient Reward Mechanism
text: We will now describe the exact details of the gradient aggregation and download steps performed by the server to implement our proposed fair gradient reward mechanism:
Gradient Aggregation Step. With a specified normalization coefficient Γ and an initialized coefficient ri,0, the server performs normalization and aggregation of all agents’ parameter updates into uN ,t using (1), as previously discussed in the FL problem setting (Sec. 3.1). Then, the server computes our approximation ψi,t (3) of the CGSV φi,t (2) and updates (and normalizes) the importance coefficient ri,t in iteration t via a moving average of ψi,t given the relative weight α on ri,t−1 from previous iteration t− 1:
ri,t := α ri,t−1 + (1− α) ψi,t , ri,t ← ri,t/ ∑ i′∈N ri′,t (4)
where ri,0 := 0. Note that ri,t (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 ,t+1 (1) in iteration t+ 1. The use of a moving average of ψi,t 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 [31, 56]. It also allows a flexible weighting over the iterations of the entire training process: In particular, setting α < 1 can effectively mitigate the noise from random initialization of model parametersw0 because the weight on ψi,t′ in earlier iteration t′ < t decays exponentially with t [54].
Gradient Download Step. Recall from the vanilla FL problem setting (Sec. 3.1) that in each iteration t, this step involves all agents downloading an identical aggregated parameter update/gradientuN ,t (1) from the server (as reward) for updating their model parameters to the samewt (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/contributing a parameter update/gradient of higher quality [37, 63] when it can afford to. To ensure fairness, each agent should download some form of aggregated parameter update/gradient as reward that is commensurate to the quality/value of its uploaded/contributed 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 sparsifying2 the aggregated parameter update/gradient uN ,t downloaded from the server as reward to agent i in each iteration t. Specifically, we zero out fewer of its smallest components (hence higher-quality gradient reward) when the importance coefficient ri,t (4) (i.e., moving average of the approximate CGSV ψi,t) is larger: vi,t := mask(uN ,t, qi,t) , qi,t := bD tanh(β ri,t)/maxi′∈N tanh(β ri′,t)c (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, 61], and β ≥ 1 specifies the degree of altruism: Greater altruism β gives any agent with a smaller ri,t a larger improvement in the quality of its gradient reward, i.e., a larger reduction in the sparsity of its downloaded vi,t as reward. In the extreme case of β = ∞, we recover the vanilla FL problem setting (Sec. 3.1) where all agents are rewarded equally with uN ,t (i.e., best-quality gradient reward vi,t = uN ,t for all i ∈ N with no sparsification), albeit with importance coefficients ri,t possibly differing across agents i ∈ N and dynamically updated over iteration t ∈ Z+. Hence, increasing β from 1 to∞ trades off fairness for equality in gradient rewards by being more altruistic to any agent with a smaller ri,t; we empirically show the effect of varying β on training loss in Fig. 7 of Sec. 4.2. Note the agent i∗ := argmaxi′∈N tanh(β ri′,t) with the largest possible ri∗,t does not benefit from such altruism since it already downloads the best-quality gradient reward (i.e., uN ,t) according to (5).
Suppose that there exists a known threshold r > 0 s.t. ri,t ≥ r for all i ∈ N and t ∈ Z+ and we want to limit the sparsity of any downloaded vi,t or, equivalently, ensure the minimum quality of any gradient reward: Specifically, given a predefined threshold c ∈ (0, 1], we want to guarantee qi,t ≥ bD × cc holds for all i ∈ N and t ∈ Z+. By setting β s.t. tanh(β r) ≥ c, it follows from (5) and maxi′∈N tanh(β ri′,t) ≤ 1 that tanh(β ri,t)/maxi′∈N tanh(β ri′,t) ≥ tanh(β ri,t) ≥ tanh(β r) ≥ c and hence qi,t ≥ bD × cc ensues. By using the property that tanh(β r) = (exp(2β r) − 1)/(exp(2β r) + 1), β ≥ ln((1 + c)/(1 − c))/(2r) can be derived and used for setting β. It further informs us that reducing the sparsity of any downloaded vi,t or, equivalently, improving the minimum quality of any gradient reward (i.e., by increasing c) requires greater altruism β to be introduced, while improving the minimum quality of uploaded/contributed parameter updates/gradients by any agent over the entire training process (hence larger r) eases the need of introducing greater altruism β.
2Sparsifying a parameter update/gradient vector means zeroing out some of its components and leaving the others unchanged [7, 33].
To see why the sparsifying gradient trick (5) can ensure fairness, we illustrate its effect in an FL problem with N = 5 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 3 have 20%, 40%, and 60% randomly corrupted labels, respectively. The uploaded/contributed parameter updates/gradients thus decrease in quality from agents 1 to 3 (i.e., ψ1,t = 0.194, ψ2,t = 0.088, and ψ3,t = 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., ψ4,t = 0.331 and ψ5,t = 0.342 on average) due to uncorrupted labels in their datasets. Consequently, agents 1 to 3 have increasing sparsity (resp., 34.9%, 67.6%, and 83.0% on average) while agents 4 and 5 have little/no sparsity (resp., 3.5% and 1.1% on average) in their downloaded vi,t as rewards (β = 1). Fig. 2 shows that the converged model parameters of agents 1 to 3 grow in `2 distance from that of the server (hence increasing training loss) while agents 4 and 5 have the closest converged model parameters (hence lowest training loss).
We provide the pseudocodes performed by the server and agent i ∈ N in each iteration t below. We will discuss in Sec 4.2 how the hyperparameters Γ in (1), α in (4), and β in (5) are set in our experiments.
Server (t) 1: for all i ∈ N do 2: Download ∆wi,t from agent i 3: . Gradient Aggregation Step 4: Compute ui,t and uN ,t (1) 5: for all i ∈ N do 6: Compute ψi,t (3) and ri,t (4) 7: . Gradient Download Step 8: for all i ∈ N do 9: Compute vi,t (5) for download by agent i
Agent (i, t)
1: Upload ∆wi,t = −ηt∇Fi(wi,t−1) to server 2: Download vi,t from server 3: Update wi,t = wi,t−1 + vi,t

heading: 3.5 Fairness Guarantee
text: We have previously discussed the intuition underlying our notion of fairness in Sec. 3.4 that 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. Note that the importance coefficient ri,t (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 a notion of fairness that under some conditions on loss function F and the server’s model parameters wt, if an agent i has a larger importance coefficient ri,t and model parameters wi,t−1 closer to that of the server (i.e., wt−1) than another agent by at least 2‖vi,t‖ in previous iteration t− 1, then it is rewarded with model parameters wi,t incurring smaller training loss F(wi,t) in iteration t: Theorem 2 (Fairness in Training Loss). Let δi,t := ‖wt − wi,t‖. Suppose that wt is near to a stationary point of F for t ≥ t∗ ∈ Z+ and some regularity conditions on F hold. For all i, i′ ∈ N and t ≥ t∗, if ri,t ≥ ri′,t and δi′,t−1 − δi,t−1 ≥ 2‖vi,t‖, then F(wi,t) ≤ F(wi′,t).
Its proof is in Appendix A.3. Our experiments in Appendix B.3 will empirically verify the fairness guarantee in Theorem 2 (and fairness in test accuracy) without needing to impose its conditions.

heading: 4 Experiments and Discussion

heading: 4.1 Experimental Settings
text: 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 [25], a 3-layer CNN for CIFAR-10 [22], and a text embedding CNN for MR and SST [20].
Baselines. We consider several existing FL baselines such as FedAvg [40], q-FFL[31], CFFL [37], and an extended contribution index (ECI) method from [54] utilizing validation accuracy-based SV
and setting qi,t for i ∈ 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, we implement simple FL baselines based on round robin (RR), dataset weighted download (DW), and Euclidean distance (EU). RR is commonly adopted in mechanism design to ensure fairness [6, 34] and also used in FL to schedule gradient downloads [51, 67]. For DW (EU), qi,t for i ∈ N in (5) are set to be proportional to the agents’ local dataset sizes (negative Euclidean distance of their 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.
Performance Metrics. To measure fairness, we consider the scaled Pearson correlation coefficient3 ρ := 100×pearsonr(ϕ, ξ) ∈ [−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 = T . The corresponding experimental results will be reported in Sec. 4.2. To empirically verify the fairness guarantee in Theorem 2, we have also reported in Appendix B.3 results on the fairness metric ρ between the importance coefficients ϕ := (ri,T )i=1,...,N (4) (i.e., measuring overall qualities of the parameter updates/gradients uploaded/contributed 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 distinct 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 1, 3, 5, 7, 10 classes, respectively; so, agent 1 (5) has a local dataset with 1 (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/homogeneous data partition (UNI) where the agents are expected to achieve comparable predictive performance.
Additional details of the experimental settings are described in Appendix B.1.

heading: 4.2 Experimental Results
text: Predictive Performance. Table 1 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
3The Pearson correlation coefficient has been applied to a similar use case in [19].
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 β = 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 β = 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 (1) via ri,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 β = 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, q-FFL aims to equalize the local training losses w.r.t. the agent’s local datasets, which may be suboptimal for heterogeneous data partitions like POW and CLA. We provide further results in Appendix B.5 empirically 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 ρ achieved by our fair gradient reward mechanism vs. tested baselines on all datasets. From Table 2, 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 −45.6. 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 as it adopts the leave-one-out approach which seems less accurate than SV in valuing the contributions of the agents [19]. Both q-FFL and RR promote egalitarian fairness 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 heterogeneous data partitions among the agents on MNIST and CIFAR-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 3 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,t for agent i = 1, 3 varies over iterations t: Interestingly, for the CLA data partition, though agent 3 (brown solid line) is initially mistaken to
provide a low contribution, the dynamic update of r3,t (4) allows its true contribution to be recognized quickly. Fig. 5 (Fig. 6) shows how the `2 distance between the downloaded sparsified gradient vi,t (5) of agent i = 1, 3 and aggregated parameter update/gradient uN ,t (1) (last layer’s model parameters of agent i = 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 updates/gradients of lowest (highest) quality over the entire training process downloads vi,t as reward that is further from (closer to) uN ,t, hence training last layer’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 β leads to all agents downloading higher-quality gradient rewards vi,t (5) and thus incurring smaller training loss. In particular, agent 1 (abbreviated to A1 and represented by a blue solid line) who uploads/contributes parameter updates/gradients of lowest quality over the entire training process benefits most as β increases, as explained previously in Sec. 3.4. Additional results w.r.t. test loss are reported in Appendix B.4.
Time Overhead. Table 3 compares the time overhead (seconds) of our fair gradient reward mechanism 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.4× of the training time, while ECI incurs a significant time overhead of up to 140× of the training time due to the calculation of the CI incurring O(2N ) time, even with the permutation sampling-based approximation [39, 56] for 10/20 agents. CFFL incurs at most 2× of the training time (i.e., 5-6 times longer than ours) from the additional validation in each iteration.
Hyperparameters. We find that α ∈ [0.8, 1)(i.e., relative weight on ri,t−1 in (4)), β ∈ [1, 2] (i.e., degree of altruism in (5)) and Γ ∈ [0.1, 1] (i.e., normalization coefficient in (1)) are effective in achieving competitive predictive performance and fairness. In our experiments, we set α = 0.95, β = [1, 1.2, 1.5, 2], and Γ = 0.5 for MNIST, Γ = 0.15 for CIFAR-10, and Γ = 1 for SST and MR.

heading: 5 Conclusion and Future Work
text: 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/gradient in FL without needing an auxiliary validation dataset and present an efficient approximation of CGSV with a bounded error (Sec. 3.3). Based on the approximate CGSV, we have designed a novel trainingtime fair gradient reward mechanism (Sec. 3.4) 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 is commensurate to that of the agent’s uploaded/contributed 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, as demonstrated in our fairness guarantee (Sec. 3.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. 4). 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.
Our proposed fair gradient reward mechanism also provides practitioners the flexibility to trade off between fairness and equality in gradient rewards via a hyperparameter β controlling the degree of altruism (Sec. 3.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-018). Any opinions, findings and conclusions or recommendations 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).

Review summaries:
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. 

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.

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.