GTG-Shapley: Efficient and Accurate Participant Contribution Evaluation in Federated Learning

Under this category of approaches, FL participants’ contributions are measured by their self-reported information regarding their sensitive local data (e.g., data quantity, quality, committed computational and communication resources).

In (Yu et al., 2020), the authors proposed an incentive mechanism to sustain FL long-term operation which compensates participants for their contributions and cost for join in the federation. The contributions are measured based on self-reported data quantity and quality. In (Zeng et al., 2020), the proposed incentive scheme utilizes self-reported local data size and the bandwidth between the participants and the federation for calculating utility with Cobb-Douglas function. In (Zhang et al., 2020), authors use publicly verifiable factors about the participants (e.g., data quality, data volume, cost of data collection) to assign types to them and then, determine their contribution levels. In (Ding et al., 2020), the authors proposed a contract-based FL incentive system in which FL participants can determine their contribution types based on own data usage cost and communication time. In (Feng et al., 2019), self-reported training data sizes are treated as the contribution values under the assumption that more training data will lead to better FL model performance. In (Tang and Wong, 2021), the authors proposed an FL incentive schemes that allows the participants to self-report the resources they are willing to commit to the FL task and the expected reward through negotiation. In (Kang et al., 2019), the proposed approach also requires participant to self-report local information, however, this is used for user selection instead of quantifying contributions.

The advantage of self-reporting is that it makes contribution evaluation straight-forward. However there is a strong assumption that the self-reported information is truthful.

The general idea of individual performance-based FL contribution evaluation is that a participant shall be assigned a contribution value for his performance on specific tasks. This category of contribution evaluation approaches focus on individual performance instead of the overall performance of the FL model.

In (Zhao et al., 2021), the authors measure individual contribution based on similarity between local model updates and the aggregated FL model. The assumption is that local models similar to the FL model are more valuable. In (Pandey et al., 2020), the contribution is evaluated through local relative accuracy levels for individual participants. Individual evaluation can also be performed by each participant. Participants exchange necessary information between each other for rating other participants with locally owned data. In (Lyu et al., 2020b), the proposed approach performs pairwise similarity comparison to allow participants to perform mutual evaluation on each others’ generated samples. The approach in (Chen et al., 2020) measures individual contributions by calculating the mutual cross-entropy loss between each local model with the aggregated FL model. There are also techniques leveraging on reputation systems (Yu et al., 2010, 2013). In (Lyu et al., 2020a), the approach utilizes reputation to evaluate FL participant contribution. A participant’s stand alone model accuracy is used to update his reputation.

These approaches generally assume that participants with local models similar to the aggregated model (or with the local models of other participants) are more valuable to the federation (or the other participants concerned). However, this assumption might not always stand, especially in FL settings. As non-i.i.d scenarios are common in FL (Tan et al., 2021), for individual participant holds partial knowledge of the learning task, others possessing complementary knowledge tend to be more valuable than those possessing similar knowledge.

Utility game-based FL participant contribution evaluation focuses on the changes in the coalition utility when a data owner joins. In a utility game (Gollapudi et al., 2017), a set of players join teams to produce social utility, and receive individual utility in the form of payments in return.

There are three profit-sharing principles: 1) egalitarian, 2) marginal gain-based, and 3) marginal loss-based. The most common profit-sharing schemes are fair value game, labor union and Shapley Value-based game (Augustine et al., 2015). Fair value treats a player’s utility as the marginal loss in the overall utility when a player leaves a coalition. Labor union treats a player’s utility as the marginal gain in the overall utility when a player joins a coalition. The order of joining a coalition affects the individual utility values in the labor union scheme. Shapley Value utilize the marginal loss to calculate individual utility free of the order of joining the coalition.

There are FL participant contribution evaluation approaches based on utility games. In (Wang et al., 2019), the authors proposed a data influence approximation method for horizontal FL using the marginal loss value. In (Ghorbani and Zou, 2019), the authors proposed gradient Shapley to estimate data values. Gradient Shapley uses the marginal loss of every data point to approximate the Shapley value of the dataset. The outcome is still affected by the order of each data point in each permutation of evaluation order. In (Richardson et al., 2019), the authors proposed influence-based FL contribution evaluation. The marginal loss related to the loss function is used as the utility. The purpose of such a design is to incentivize high quality data owners to join FL as early as possible. In (Nishio et al., 2020), FL contribution is evaluated by gradient-based fair value scheme. However, for utility game-based approaches, participants’ contributions are affected by the order in which they join in the federation. Therefore, SV-based approaches have been proposed to achieve fairer FL participant contribution evaluation.

SV-based FL participant contribution evaluation has been the main focus of recent research. Introduced in 1953 as a solution concept in cooperative game theory, SV can fairly calculate a player’s contribution in a coalition (Shapley, 1953).

The original SV calculation incurs exponential computational costs. There have been techniques for improving SV calculation efficiency. In (Castro et al., 2009), random sampling Monte-Carlo (MC) estimation method is proposed to approximate SV with fewer utility evaluations. In (van Campen et al., 2018), the authors proposed a structured random sampling MC estimation method to approximate SV efficiently. Since the utility values of different coalitions vary without a clear pattern, the proposed method swaps players to different positions in the coalition ordering. Similar approaches have been developed to improve SV estimation efficiency in FL data valuation, which can be applied in FL participant contribution evaluation. In (Jia et al., 2019), the authors proposed to use group testing to accelerate SV estimation. In (Ghorbani and Zou, 2019), the authors leveraged SV to quantify the contribution of individual data points to a learning task. Furthermore, they proposed an efficient approach, TMC-Shapley, to estimate SV by using random sampling Monte-Carlo to estimate and truncate unnecessary utility evaluations in each permutation sampling round.

These methods focus on reducing the number of permutations sampled to calculate SVs. However, under each FL participant permutation, the corresponding FL model needs to be trained from scratch. This requires FL participants to incur significant computation and communication overhead, making such approaches not suitable for practical applications.

Gradient-based Shapley is proposed to avoid redundant retraining of FL models when evaluating SVs. Instead of training from scratch, the FL sub-models corresponding to different participant permutations are approximated by gradient updates from the participants. Participants’ gradient update in each round are stored in the FL server and used to reconstruct the corresponding FL sub-model when necessary. This approximation technique has been adopted by state-of-the-art SV-based FL participant contribution evaluation approaches.

In (Song et al., 2019), the authors proposed two gradient-based SV schemes: 1) one-round (OR) evaluation and 2) multi-round (MR) evaluation. Both schemes use gradient updates to reconstruct sub-models to replace the actual FL model training process. The difference is that MR calculates SVs during every round of FL model training, while OR calculates SV only once after all the training rounds are complete. In (Wei et al., 2020), the authors proposed the Truncated MR (TMR) approach, which extends MR by eliminating the entire rounds with decay factor $\lambda$ values lower than a pre-defined threshold. These three schemes significantly improves the efficiency of estimating SVs. However, they still require evaluating every possible FL sub-model as in the original SV setting. In (Wang et al., 2020), the authors proposed the Federated SV approach with two acceleration techniques for within-round SV estimation: 1) random permutation sampling and 2) group testing. However, the number of random sampling is fixed and not tailored to each permutation. This can result in under-sampling or over-sampling, missing important FL participant permutations and causing inaccurate estimation of SVs.

To improve SV estimation accuracy and reduce computational cost, the SV approximation methods should consider: 1) accelerating utility evaluation, 2) the importance of different FL training rounds and their effects on the SVs, and 3) reducing unnecessary evaluations. None of the existing approaches cover all three aspects. In this paper, the proposed GTG-Shapley approach bridges this gap and simultaneously enhances efficiency and accuracy.

GTG-Shapley utilizes the gradient updates, $(\Delta)$, as surrogates for datasets to evaluate FL participants’ contributions. Thus, Eq. (5) is re-expressed as:

In this way, when the calculation of SV requires the evaluation of the utility of $S$, the process of retraining a sub-model $M_{S}$ is replaced by the process of sub-model reconstruction which is based on previous gradient updates and the current FL model. Hence, the main bottleneck of applying SV in FL is resolved, and SV calculation can be performed entirely on the FL server, thereby incurring no additional computational cost for the participants.

With the efficiency of sub-model retraining improved, the majority of the time required to estimate SV is consumed by the model reconstruction and performance evaluation steps (as shown in Figure 2(a)). For models with a large number of parameters and federations with large test datasets, model evaluation severely slows down SV estimation. Thus, it would be beneficial to eliminate unnecessary model reconstruction and evaluation when estimating SVs following Eq. (4).

A participant’s Shapley value is estimated based on its marginal gain in different participant permutations, and the FL server performs SV utility evaluation. Based on the insight of utility distribution between different rounds (Figure 2(b)), the rounds of SV calculation with low marginal utility gain can be discarded, according to Eq. (4), without significantly affecting SV estimation. Moreover, based on the insight of marginal utility gain contributed by participants in different positions in a permutation (Figure 3), those in later positions contribute little marginal utility gain. Therefore, they can be omitted without significantly affecting SV estimation. In addition, this insight also shows that the marginal utility gains concentrate at the front positions in a permutation. Thus, it is important to ensure that participants have fair opportunities to occupy different positions across multiple permutations.

To leverage on these insights, we propose a between-round truncation policy in GTG-Shapley to opportunistically drop entire rounds of SV calculation when the remaining marginal utility gain is small. In addition, a within-round truncation policy is proposed for opportunistically terminating the ongoing sub-model evaluation in permutations when the remaining marginal gain is small. We also propose a guided sampling policy to fairly distribute FL participants in different positions across multiple permutations.

The pseudo code of the proposed GTG-Shapley approach is shown in Algorithm 1. The initial FL model $M^{(t)}$ is an empty set ($S=\{\}$) for the $t$-th round of SV calculation. The final model $M^{(t+1)}$ is the FL model learnt during the $t$-th round of gradient updating, which is the full set of coalition ($S=\{1,...,n\}$). Lines 1-2 show parameter initialization and the performance evaluation of two input models. GTG-Shapley performs Monte-Carlo truncation at two levels. It performs between-round truncation first. If the marginal gain of the $t$-th round $|v_{N}-v_{0}|$ is not larger than a pre-defined threshold $\epsilon_{b}$, entire round $t$ is ignored, and GTG-Shapley returns 0 for every participant. Otherwise, GTG-Shapley estimates the $t$-th round’s SVs. Line 7 is an essential part of GTG-Shapley. The partial permutation is the proposed guided sampling policy with the following rule. The first $m$ ($m<<n$) bits in the sequence are circulated in a fixed order $P(n,m)$ by $n$ participants, and the last $n-m$ bits are randomly sampled permutations of the rest. By doing so, there are two benefits: 1) it avoids unsatisfactory SVs estimations, and 2) it improves convergence rate. Lines 11-17 show the within-round truncation operation at the sequence level. The idea is that successive sub-model evaluations in a sequence can be dismissed when the remaining marginal gain is smaller than a pre-defined truncation threshold $\epsilon_{i}$. Otherwise, the sub-model consisting of updates from $C$ participants is assembled and evaluated as shown in Lines 12-14. Then, participants’ SVs is updated by their marginal gain in $\pi^{k}$.

The pseudo code for FL participant contribution evaluation using GTG-Shapley is shown in Algorithm 2. Line 2 shows that the FL training process lasts $T$ rounds. In each round $t$, participants download the global FL model $M^{(t)}$ to the client side. Line 5 indicates that participant $i$ trains the local model $M^{(t)}$ with its local datasets, and sends the gradient updates $\Delta^{(t+1)}_{i}$ to the FL server. Then, participants wait for the next round FL training. For FL server side (Line 8), the FL server collects the uploaded gradient updates $\{\Delta^{(t+1)}_{i}\}$ and executes FedAvg (McMahan et al., 2017) to update the FL model $M^{(t+1)}$. In Line 9, the FL server executes GTG-Shapley to compute the contributions by each participant in this round of training. For the $t$-th round, GTG-Shapley uses the previous FL model $M^{(t)}$, the updated FL model $M^{(t+1)}$, the evaluation function $V$ and the gradient updates from participants $\{\Delta^{(t+1)}_{i}\},\forall i\in\{1,\dots,n\}$ to estimate the latest SVs $\{\phi^{(t+1)}_{i}\},\forall i\in\{1,\dots,n\}$.

The complexity of stand-alone Monte-Carlo approximation of Shapley Value has been studied in (Maleki et al., 2013). For each round of Shapley value computation, the Hoeffding’s bound gives the minimal number of permutations needed for Monte-Carlo sampling to achieve an $(\epsilon,\delta)$-approximation, which is $K=(2r^{2}N/\epsilon^{2})\log(2N/\delta)$, where $r$ is the range of marginal contributions. Therefore, the number of evaluations required over $T$ rounds of SV computation is expressed as $K_{total}=TK=\mathcal{O}(TN\log N)$.

GTG-Shapley performs within-round and between round truncation to accelerate SV computation. Similar as traditional machine learning, HFL also shows patterns of diminishing returns both on the marginal gain of within-round participant evaluation order in a sampled permutation (Figure 3), and the marginal gain values across different rounds (Figure 2(b)). A participant can be categorized as ‘valuable’ or ‘not valuable’ based on its marginal gain. GTG-Shapley only needs to evaluate those ‘valuable’ participants in a sampled permutation. For simplicity, we use bounded $Patero(\alpha_{i},1,N)$ to model the probability of participants to be ‘valuable’ at each position in a given sequence. The mean of the Patero distribution, $\overline{L_{i}}$, is the average length of participant combinations with valuable positions which GTG-Shapley needs to evaluate:

By the same logic, the probability of the marginal gain of a given round categorized as ‘valuable’ in all $T$ position can also be modeled as another bounded $Patero(\alpha_{b},1,T)$. The average length $\overline{L_{b}}$ of ‘valuable’ rounds in all $T$ rounds is:

The number of evaluations required for GTG-Shapley to achieve an $(\epsilon,\delta)$-approximation is:

where $\epsilon^{\prime}=\max\{\epsilon_{i},\epsilon_{b}\}$.

Depending on the data distribution, the complexity of GTG-Shapley is between $\mathcal{O}(T\log N)$ to $\mathcal{O}(TN\log N)$. For HFL involving i.i.d. datasets with an easy learning task, it is possible that the truncation point is right after the first position in a sequence, meaning that the ones after the first participant can hardly improve the FL model, and truncating them has little impact on Shapley value approximation. In such cases, $\overline{L_{i}}\approx 1$, meaning that the complexity of GTG-Shapley is $\mathcal{O}(T\log N)$.

In this section, we first introduce the experiment settings and baselines. Then, we compare GTG-Shapley with the state of the art baselines under various FL settings involving both i.i.d. and non-i.i.d data silos.¹¹1Link to dataset and code is available in https://github.com/liuzelei13/GTG-Shapley.

In this section, we analyze the experimental results under the five aforementioned settings. The original Shapley Values for the five settings are shown in Figure 5. In each case ,there are 10 points representing participants’ contributions. In the following subsection, both the x-axis and the y-axis for each figure are presented in $\log$ scale.

In this section, we analyze experimentally the effect of the main components of GTG-Shapley. The experimental settings are the same as in the previous experimental evaluation section.