# Mitigating federated learning contribution allocation instability through
randomized aggregation.

Arno Geimer
University of Luxembourg
<EMAIL_ADDRESS>Beltran Fiz
University of Luxembourg
<EMAIL_ADDRESS>Radu State
University of Luxembourg
<EMAIL_ADDRESS>
###### Abstract

Federated learning (FL) is a novel collaborative machine learning framework
designed to preserve privacy while enabling the creation of robust models.
This paradigm addresses a growing need for data security by allowing multiple
participants to contribute to a model without exposing their individual
datasets. A pivotal issue within this framework, however, concerns the fair
and accurate attribution of contributions from various participants to the
creation of the joint global model. Incorrect contribution distribution can
erode trust among participants, result in inequitable compensation, and
ultimately diminish the willingness of parties to engage or actively
contribute to the federation. While several methods for remunerating
participants have been proposed, little attention was given to the analysis of
the stability of these methods when evaluating contributions, which is
critical to ensure the long-term viability and fairness of FL systems.
In this paper, we analyse this stability through the calculation of
contributions by gradient-based model reconstruction techniques with Shapley
values. Our investigation reveals that Shapley values fail to reflect baseline
contributions, especially when employing different aggregation techniques.
To address this issue, we extend on established aggregation techniques by
introducing FedRandom, which is designed to sample contributions in a more
equitable and distributed manner. We demonstrate that this approach not only
serves as a viable aggregation technique but also significantly improves the
accuracy of contribution assessment compared to traditional methods. Our
results suggest that FedRandom enhances the overall fairness and stability of
the federated learning system, making it a superior choice for federations
with limited number of participants.

##  1 Introduction

Federated Learning has gained a lot of traction in recent years as a prevalent
form of collaborative learning. It has seen adoption in a vast array of
domains, ranging from financial corporations and medical institutions to IoT
devices, with major industry players such as Google and Nvidia offering in-
house platforms and solutions.

In Federated Learning, a strategy defines the approach in which the central
server handles a federation. Since the inception of Federated Learning,
numerous strategies have been introduced to manage specific problems, among
which are poor performance on heterogeneous datasets, attacks by malicious
clients, and the convergence speed of the global model.

There are two primary categories of Federated Learning: cross-device and
cross-silo. In the cross-device approach, a large number of distributed
clients, usually with small volumes of data, collaborate to construct a robust
model. On the other hand, cross-silo involves a few participants with larger
amounts of data working together to create a model that incorporates the
specific knowledge of each entity. In an environment comprised of profit-
driven entities, correctly assessing contributions is of utmost importance, as
participants may invest money in infrastructure and compliance in hopes of
receiving their equitable part of the payout.

In the following sections, we delve into the analysis of a cross-silo FL
scenario and the stability of contribution evaluation. Specifically, this use
case portrays a federation whose clients may need an incentive to join and
stay in the federation (i.e. participants leave if they are not adequately
compensated).

By shedding light on the inherent instability of contribution evaluation
between some of the most popular strategies and how this can be mitigated, we
hope to provide a foundation for future aggregation strategies to self-
evaluate not only their performance under traditional metrics, but also the
contribution evaluation stability. In summary, we provide the following
contributions:

  1. 1.

Illustrate the inherent instability of contribution evaluation of popular
aggregation strategies, and how to mitigate it.

  2. 2.

Propose FedRandom, a contribution evaluation approach to reduce the
contribution disparity.

  3. 3.

Show that FedRandom allows for more stable calculation of contributions.

  4. 4.

Demonstrate that FedRandom significantly outperforms all other strategies in
approximating the baseline centralized data valuation approach.

The remainder of this paper is structured as follows: In section 2 we present
a summary of the current state of the art on contribution evaluation methods
in Federated Learning. Section 3 includes detailed explanations of the
aggregation strategies used in this paper and of Shapley values in Federated
Learning. In section 4.1, we detail the experimental setup. We present our
method, FedRandom, as well as an extensive analysis of its capabilities in
section 4. Finally, we discuss the implications of FedRandom and future work
in section 5.

##  2 Related Work

Several approaches have been devised for the evaluation of participants’
contribution during global model creation in Federated Learning. We give a
brief overview of the most common approaches, which can be based on either
numeric computations or self-disclosed information and estimations by the
central server.

#### Self-reported

The most direct approach seen in previous work is to have the participants
perform their own reporting, providing information regarding their local model
training process [20, 28] . The information provided may encompass aspects
such as the quality and quantity of data provided by the participant; costs
associated with data collection, processing and communication in the
federation. The aggregator then utilizes this data to assign contribution
ratings to the clients. A limitation of these approaches is that the
assumption of honesty and the ability of clients to evaluate their own
conditions.

#### Shapley values

Similarly to their usage in game theory to evaluate the contribution of
players to a common task, Shapley values are the most common approach to
numerically assess individual clients’ contribution to the shared model in FL.

Although it has been proposed to calculate Shapley values in FL by evaluating
the performance of fully-trained federated models [24], a more common approach
is to use gradient-based model reconstruction [22] or Monte Carlo methods
[25], which assess contributions at each federation round. This is of
particular interest in continuous learning tasks, where data and thus
contribution distributions might change. In these settings, payouts may occur
periodically instead of just once. To assess Shapley values, the evaluating
entity does need a validation dataset.

#### Influence

Another approach for quantifying the contribution of participants is through
the use of influence based methods. These apply a systematic method for
quantifying the impact of individual data points on the global model [10].
Influence can be computed by assessing the disparity in models when trained
with and without the specific data points. This approach was used in [18] to
provide incentives for clients to provide high-quality data during the
training process. Although the influence metric offers detailed insights, its
computation can be challenging due to the expensive nature of re-training
models, often exacerbated by the fact that access to the clients’ individual
data points might be limited due to privacy constraints.

#### Auctions

In diverse areas of Federated Learning, auctions serve as a fundamental
economic mechanism to allocate resources such as training data and
computational power, setting prices through bidding [23]. The primary
stakeholders involved are the bidders (model owners or FL service requesters),
sellers (data owners or clients), and auctioneers (intermediaries facilitating
the auction), aiming to optimise resource distribution and establish fair
pricing. While contribution estimation is an important aspect, other key
concepts in auction theory include valuation, utility, and social welfare,
with the ultimate goal being to enhance the efficiency and effectiveness of
resource allocation in FL environments. An example is [27], the multi-
dimensional procurement auction model FMore is proposed to incentivize clients
with more data quality in Mobile Edge Computing (MEC) to participate.

While the field of contribution estimation in Federated Learning is active, to
the best of our knowledge no previous work has focused on the evaluation of
the stability of these contribution estimations.

##  3 Methodology

###  3.1 Federated Learning

A basic Federated Learning architecture consists of a group of participants,
or clients, who each own a private local dataset $D_{k}$, along with a central
server or aggregator. After a model architecture and hyperparameters such as
aggregation strategy and local epoch numbers have been agreed upon, the
central server starts the federation by initializing and distributing the
global model. At the onset of each round, the aggregator selects a subset of
clients and transmits them the current global model. Each user trains a new
local model for $e$ local epochs on their respective data, and uploads their
model updates to the server. The server uses the agreed-upon aggregation
strategy to compute the new global model. This allows the collaborating
entities to gain a model incorporating knowledge of all clients which has been
shown to outperform locally trained models [14].

###  3.2 Aggregation strategies

In Federated Learning, different aggregation strategies may be employed based
on the specific circumstances and objectives of the participants. It is
important to note that all of the strategies used in this paper have been
widely adopted across their respective application domains. Assuming a
federation consisting of $K$ participants, each possessing $n_{k}$ of a total
of $n$ data points, we detail these strategies in the following section.

While our investigation includes aggregation strategies aimed at enhancing
defenses against model attacks, we do not include adversarial participants.
The performance metrics of the strategies, whether related to model accuracy
or defense against attacks, are not the primary focus of this paper. We
emphasize that each strategy achieves acceptable convergence (Figure 2),
justifying their inclusion in our experimental analysis.

  * •

FedAvg: Introduced in [14], FedAvg is the baseline Federated Learning
technique. As detailed in 3.1 and included in Algorithm 1, the server
initializes model weights and distributes them to the clients. These train the
model on their datasets for a predetermined number of epochs $e$ using
stochastic gradient descent, and updates are aggregated by the central server
using weighted averaging:

$w_{t+1}\leftarrow w_{t}-\Delta w\text{, with }\Delta
w=\sum_{k=1}^{K}{\frac{n_{k}}{n}w_{k}}$

The new global model $w_{t+1}$ is redistributed to the clients, iterating the
process until either global convergence is achieved or a predetermined number
of rounds has been reached.

FedAvg has the global objective function

$f(w)=\frac{1}{K}\sum_{k=1}^{K}{{F_{k}(w)}}.$

  * •

FedAvgM: Federated Averaging with Momentum [6] improves the poor performance
of FedAvg on heterogeneous data. It adds momentum when updating model weights:

$w_{t+1}\leftarrow w_{t}-v\text{, where }v=\beta v+\Delta w.$

  * •

FaultTolerantFedAvg: Fault-tolerant Federated Averaging is a unique
aggregation strategy designed to address potential client dropout scenarios. A
FedAvg-based aggregation method, it ensures successful functioning of the
federation in the event of client dropout. Under normal circumstances, without
dropouts, the strategy behaves as FedAvg.

  * •

FedAdagrad, FedAdam, FedYogi: The three optimization strategies, proposed in
[17], improve the convergence speed of the federation. With clients’ weight
updates considered a pseudo-gradient, the strategies use the Adagrad, Adam and
Yogi optimizers, respectively, instead of gradient descent. Model update
functions are detailed in the respective paper.

  * •

QFedAvg: Q-Fair Federated Learning aims to achieve a global model which
performs similarly on all individual datasets $D_{k}$. This is achieved by
weighing clients with worse performance higher in the objective function. The
parameter $q$ serves as a measure of equality, with $q=0$ resulting in FedAvg.

QFedAvg employs the objective function

$f_{q}(w)=\sum_{k=1}^{K}\frac{p_{k}}{q+1}F^{q+1}_{k}(w).$

The more complex model updates can be found in the respective paper.

  * •

FedMedian, FedTrimmedAvg: To reduce potentially adversarial updates, the
authors update the global model as the median and trimmed mean of client
updates, as opposed to a weighted average in FedAvg. In adversarial settings,
this guarantees substantial improvements over the baseline [26].

  * •

Krum: To counter against potential byzantine failures, [2] introduces the Krum
function based on barycentric aggregation. At each round, they calculate a
score for every client using the pairwise square distance to other close
updates. As effectively the most representative of all participants, the
update with the best score is selected as the new global model. Details are
established in [2].

###  3.3 Shapley values

In game theory, an n-person cooperative game is a game in which subsets of
players, called coalitions, can cooperate in order to obtain a utility $v$
[15], which they may distribute amongst themselves. To ascertain the exact
contribution of each player in the coalition to $v$, Shapley values [21] can
be used. Specifically, let $S$ be a coalition of players, then the
contribution $\phi$ of player $i\in S$ to $v$ can be determined as

$\phi_{i}(v)=\sum_{S\subseteq
N\setminus{i}}{\frac{|S|!(n-|S|-1)!}{n!}(v(S\cup{i})-v(S))}.$ (1)

Shapley values have a range of desirable properties:

  * •

If $v(S\cup i)=v(S)$, then $\phi_{i}(v)=0$.

  * •

If $v(S\cup i)=v(S\cup j)$, then $\phi_{i}(v)=\phi_{j}(v)$.

In fact, it has been shown in [8] that the Shapley value is the only
contribution measure satisfying these properties. These properties are
particularly important in a FL setting, where adversarial parties might try to
unfairly increase their perceived contribution by joining the federation as
multiple participants.

###  3.4 Shapley values in Federated Learning

In this paper, we will use the method proposed as One-Round Reconstruction in
[22] and as a special case in [25]: At each round, we reconstruct all sub-
models and evaluate all participants’ contribution to those sub-models. The
exact calculation, in a FedAvg-based scenario, is given in Algorithm 1.

In the following sections, we will call contribution of client $k$ the sum of
their Shapley values $\phi_{k}=\sum{k\leq K}{\phi_{k}^{t}}$, normalized with
respect to the vector of total contributions $\phi$. This allows us to
represent a participant’s total contribution on a percentage-scale as clients’
contributions sum up to 1. This allows for better comparisons between runs on
the same data split, as though numerical values of Shapley values may be
different, proportions stay comparable.

Algorithm 1 One-round reconstruction of Shapley values with FedAvg;
$\phi_{k}$, $n_{k}$ are the Shapley value resp. dataset size of client $k$.

1:server executes:

2:initialize $\omega_{0}$

3:$n=\sum_{k\leqslant K}{n_{k}}$

4:for each round $t=1,2,...$ do

5: for each client $k\leqslant n$ in parallel do $\omega_{t+1}^{k}$
$\leftarrow$ ClientUpdate($k$, $\omega_{t}$)

6: end for$\omega_{t+1}\leftarrow\sum_{k\leqslant
K}{\frac{n_{k}}{n}\omega_{t+1}^{k}}$

7: for each client $k\leqslant K$ do $\phi_{k}^{t}=\sum_{S\subseteq
K\setminus{k}}{\frac{|S|!(K-|S|-1)!}{K!}(f(\omega_{S\cup k})-f(\omega_{S}))}$

8: where $\omega_{S}=\sum_{i\in S}\frac{n_{i}}{n_{S}}\omega_{i}^{t}$

9: with $n_{S}=\sum_{i\in S}n_{i}$

10: end for

11:end for

12:for each client $k\leqslant K$ do $\phi_{k}=\sum_{t}{\phi_{k}^{t}}$

13:end for

##  4 Results

###  4.1 Experimental Setup

The experiments were developed using Pytorch [16] and Flower [1] as the
Federated Learning framework. They were trained on 50 nodes on the high-
performance computer (HpC) platform with 128 CPUs and an allocated 251 GB of
RAM per node.

####  4.1.1 Data heterogeneity

Data heterogeneity refers to the presence of varied and potentially non-iid
datasets across different participants in the federated learning environment.
It is important to consider the data heterogeneity of the participants in a
federated environment as it is a reflection of real-world scenarios and the
diverse conditions under which the federated model is expected to operate.

Similar to [12], we use Dirichlet sampling to split the dataset. Focusing on a
heterogeneous setting, we split the dataset in the following way: With a
Dirichlet-$\alpha$ of $50.0$, we determine the distribution of labels and of
total datapoints per client, and split the dataset accordingly. This gives us
highly heterogeneous datasets which vary by size as well as label
distribution. Since we simulate cross-silo settings, we set the number of
participants to the federation to 3.

####  4.1.2 Model and training pipeline

We are interested in image classification tasks in a cross-silo framework. As
we do not focus on the effect of the model on contribution differences, but
rather that of the optimization strategy, we study a simple convolutional
neural network on the CIFAR-10 image recognition task. The CNN consists of two
5x5 convolution layers, 2 dense layers with ReLu activation and 16x5x5x120 and
120x84 units respectively, and a dense layer with 84x10 units. Image
preprocessing, comprising random cropping, horizontal flipping and randomly
changing the brightness, contrast, saturation and hue, are part of the
training pipeline. While state-of-the-art models have reached up to 99%
accuracy on CIFAR-10 [4], our models’ performance is acceptable for our
requirements, as we are not interested in reaching optimal accuracy, but
rather study how different optimization strategies compare.

Including 10 different aggregation strategies, and due to the sampling process
involved in FedRandom as well as the use of a multitude of data splits, our
experiments cover more than 4000 different Federated Learning runs.

###  4.2 Aggregation strategy instability

Figure 1: Per-client percentage contribution variance between different
aggregation strategies.

Although global models based on different aggregation strategies may converge
to similar accuracies over time, there is no guarantee that between
federations, Shapley values share the same properties.

In Figure 1, we compare the difference in per-client contribution between
different strategies on the same task. We show that clients’ contribution may
differ between strategies, even though convergence may be similar. Although
FedYogi is a clear outsider in contribution evaluation, with up to $50\%$ per-
client difference, other strategies show disparities of over $10\%$ This may
lead to distrust and undermine the collaborative environment, leading to
defection of participants.

Robustness, fairness and generalization as parts of trustworthiness have
become an important aspect of Artificial Intelligence [11]. This is no
different in Federated Learning scenarios, where fairness of the global model
and trust between participants are crucial to the operation of the federation.
As we have shown that contributions might be highly different depending on
aggregation strategy, we argue that contribution evaluation in Federated
Learning is neither robust nor generalized, and, depending on the definition
of fairness, not fair. With high instability, as shown above, trust in the
contribution calculation and consequently in the federation should not be
expected. This may prove critical in environments where participants are
profit-driven participants, as it might lead to disagreements over
remuneration and non-participation as a result: A participant whose
contribution turns out to be less than expected may argue that the chosen
strategy disadvantages them. This hurts the overall federation, as the
particular participant might have possessed particularly valuable data which
the global model, and thus everybody involved, might profit off.

A solution could be to try out different strategies and use the means of
contribution values. However, as we have shown that contribution variance
between strategies is quite high, one would need a substantial amount of
different strategies to calculate a representative contribution value,
requiring the development and implementation of many different strategies.

###  4.3 FedRandom

We introduce FedRandom, a novel sampling technique that aims to address the
instability observed with individual aggregation strategies in contribution
calculation. FedRandom operates by randomly selecting at each round from a set
of established strategies. It then applies the chosen strategy for $E$ epochs,
and calculates contributions using federated Shapley Values (SV). A more
formal definition is shown in Algorithm 2. Computing several instances of
FedRandom allows us to use their mean contribution percentages as final
contributions. Our experiments and discussions address values
$E\in{1,3,5,10}$.

Algorithm 2 FedRandom with a set of strategies $S$,

1:server executes:

2:initialize $\omega_{0}$ (checkpoint)

3:$n=\sum_{k\leqslant K}{n_{k}}$

4:for each round $t=1,2,...$ do

5:sample a strategy $s_{t}\in S$ at random

6: for each client $k\leqslant K$ in parallel do

7: for epoch $\leq E$ do

8: $\omega_{t+1}^{k}$ $\leftarrow$ ClientUpdate($k$, $\omega_{t}$)

9: $\omega_{t+1}\leftarrow$
ServerUpdate($s_{t},(\omega_{t+1}^{1},...,\omega_{t+1}^{K}$)

10: end for

11: end for

12: Calculate Shapley values $\phi_{k}^{t}$

13:end for

14:for each client $k\leqslant K$ do $\phi_{k}=\sum_{t}{\phi_{k}^{t}}$

15:end for

By introducing randomness, FedRandom can mitigate biases associated with
individual strategies. Although the approach adds a layer of complexity in
managing the set of available strategies, it does not introduce additional
communication or computational overheads to the federation. We use FedAvg,
FedAvgM, FaultTolerantFedAvg, FedAdagrad, FedAdam and FedYogi as components in
FedRandom. We chose these strategies as they all use the same aggregation
technique, namely weighted averaging.

#### Performance

Figure 2: CIFAR-10 validation accuracy of all aggregation strategies, without
hyperparameter finetuning.
Top: In total - Bottom: The last 25 rounds

As shown in Figure 2, the performance of FedRandom lies between those of the
other aggregation strategies. This makes it a valid aggregation strategy,
although realistic usage is unreasonable since implementation is more complex
than an out-of-the-box strategy; and it does not inherit any of the properties
of its constituting strategies, such as Krum’s Byzantine resistance or
QFedAvg’s performance equality, and it does not achieve the performance of
methods employing advanced optimizers such as FedAdam and FedYogi.

###  4.4 Minimizing variance with FedRandom

We have run extensive experiments over multiple data splits to test how much
contribution values depend on the aggregation strategy. As discussed before, a
generalized and robust contribution evaluation is desirable, as opposed to the
instability observed in Section 4.2.

FedRandom enables us to efficiently sample large amounts of contribution
values, allowing the calculation of a statistically valid mean contribution.
Table 1 contains the average standard deviation $\sigma$ and the median
absolute deviation of (a) a sampling of the 10 strategies introduced in 3.2
over our experiments and (b) a FedRandom sampling on the same experiments. We
observe that FedRandom allows us to drastically decrease both measures.
Consequently, FedRandom sampling results in a more robust and stable
contribution allocation, leading to more confidence and trust in individual
contributions.

| $\sigma\times 10^{2}$ | $MAD\times 10^{2}$
---|---|---
Full strategies | 4.8 | 1.1
FedRandom-1 | 1.0 | 0.2
FedRandom-3 | 0.8 | 0.15
FedRandom-5 | 1.5 | 0.3
FedRandom-10 | 1.0 | 0.2

Table 1: Average standard deviation $\sigma$ and median absolute deviation
(MAD) of contributions, by sampling using the strategies introduced in 3.2 and
using FedRandom, lower is better.

###  4.5 Data Shapley

Federated Shapley values allow us to evaluate the contributions of different
participants to the shared model, but this evaluation does not necessarily
reflect the data valuation of participants. Using a central Shapley value, we
aim to establish a ground truth for the contributions of each participant. To
this end, we use the Data Shapley method introduced in [5], which allows us to
calculate the contributions of each participant’s own datasets to a central
model, which we will use as a baseline. Data Shapley has seen application in
federated learning [19, 9] as well as in other domains [13, 3]. The method has
been shown to outperform other methods in identifying data quality [5], and
has been tested extensively on several image classification tasks.

Data Shapley calculation is analogous to the Shapley value calculation in
equation 1, with $v$ the accuracy of a fully trained central model: For each
dataset $D_{k}$, we consider the sub-datasets stemming from all combinations
of client data, and evaluate the contribution of $D_{k}$ to a model trained on
the sub-datasets. In total, for a particular split, a Data Shapley calculation
necessitates $2^{K}$ full training runs. A cross-client environment, in which
the amount of participants is large, would necessitate Shapley approximation
methods.

Although we have shown in table 1 that sampling with FedRandom greatly
decreases variance when comparing different aggregation strategies, this does
not mean that FedRandom gives a realistic approximation of clients’
contributions.
However, by studying how different aggregation strategies compare to FedRandom
with Data Shapley as a baseline, we show that FedRandom outperforms all of the
chosen aggregation strategies. Indeed, Figure 3 showcases the distributions of
distances to Data Shapley, for individual strategies, as well as for different
instances of FedRandom. FedRandom samplings are significantly better at
approximating the Data Shapley baseline, especially for $E=3$. In addition,
they deviate less from Data Shapley, leading to higher confidence in result
accuracy. This is a strong argument for FedRandom, as it gives participants a
guarantee that they will be remunerated based on their data contribution, and
not on seemingly random factors when employing a single base strategy. To note
that, since FedRandom outperforms any individual strategy, it outperforms a
basic sampling using the mean contribution of multiple strategies as well.

Figure 3: Contribution $\mathcal{L}_{2}$-distance to Data Shapley, lower is
better. Medians are orange.

Table 2 goes into more detail about the difference to Data Shapley. We observe
that, the average square distance of FedRandom, especially FedRandom-3, is
considerably lower than that of basic aggregation strategies. Additionally,
the $\mathcal{L}_{\infty}$ distance metric shows that we decrease the average
maximal per-client difference to Data Shapley from more than $20\%$ in basic
strategies to only $5\%$ with FedRandom. This means that participants will, on
average, only lose or gain a maximum amount of $5\%$ of their Data Shapley
contribution.

This substantial improvement is a strong argument towards the adaptation of
FedRandom sampling when establishing a cross-silo federation. It helps
establish trust in the federation and helps eliminate any suspicion towards
received remuneration that clients may have.

Aggregation strategy |  | Mean $\mathcal{L}_{2}$ | Mean $\mathcal{L}_{\infty}$
---|---|---|---
FedAvg | ✓ | 0.148 | 0.232
FedAvgM | ✓ | 0.139 | 0.217
FaultTolerantFedAvg | ✓ | 0.14 | 0.219
FedAdagrad | ✓ | 0.258 | 0.409
FedAdam | ✓ | 0.267 | 0.419
FedYogi | ✓ | 0.252 | 0.396
QFedAvg | x | 0.139 | 0.218
FedMedian | x | 0.146 | 0.226
FedTrimmedAvg | x | 0.141 | 0.220
Krum | x | 0.273 | 0.435
FedRandom - 1 |  | 0.124 | 0.097
FedRandom - 3 |  | 0.064 | 0.050
FedRandom - 5 |  | 0.117 | 0.091
FedRandom - 10 |  | 0.126 | 0.098

Table 2: Aggregation strategies’ mean difference to Data Shapley, compared to
FedRandom sampling; lower is better. Strategies included in FedRandom are
marked with ✓.

##  5 Conclusions & Future Work

This work has brought to light a concern regarding the stability of popular
Federated Learning strategies when evaluating the contribution of
participants. Our findings underscore the potential challenges and risks
associated with deploying cross-silo federated learning platforms in
industrial settings, given the discrepancy of contribution amongst these
strategies. Future proposed FL strategies should take these findings into
account, conducting performative analysis on the accuracy of the strategies’
contributions compared to Data Shapley. If results are not satisfactory,
FedRandom can be proposed to circumvent the shortcomings of the strategy.

With FedRandom sampling, central servers can estimate contributions before
running a federation. Not only are these contribution values more stable than
when sampling different strategies, they are also closer to central Data
Shapley values than any single strategy we tested. In a deployed cross-silo
federation, this reduces friction between participants: As opposed to before,
when a specific aggregation strategy might have been more beneficial to a
client, they have already statistically relevantly sampled contribution
values. This leaves the option to choose the strategy which is most beneficial
to the federation as a whole, eliminating inter-client concurrence. Also, as
we have shown, participants get rewarded more fairly than with any single
aggregation strategy. Additionally, as FedRandom performs closely to other
strategies, using the best sample as an initial weight allows the federation
to perform better from the start. Assuming sampling is run in parallel,
training time stays the same, with only a minimal negative impact on optimal
performance during sampling.

FedRandom introduces additional computational effort to a federation. Being a
sampling technique, this effort scales linearly with the amount of generated
samples. However, more substantially, the computational effort scales
exponentially with the number of clients, rendering simulations in high-client
environments highly demanding. This problem is inherent to any numerical
contribution calculation using Shapley values, and does not stem from
FedRandom. Moreover, the implementation of FedRandom may prove more
complicated due to the major amount of aggregation strategies involved.

In future works, the effect of more aggregation strategies to FedRandom, as
well as the importance of the strategy types should be studied. An
implementation of faster Shapley computation methods such as FastShap [7]
would allow for more extensive experiments on bigger client sets.
Additionally, the possible benefits of randomly mixing strategies, as proposed
by FedRandom, should be explored in a more general context.

## References

  * Beutel et al. [2020] Daniel J Beutel, Taner Topal, Akhil Mathur, Xinchi Qiu, Javier Fernandez-Marques, Yan Gao, Lorenzo Sani, Hei Li Kwing, Titouan Parcollet, Pedro PB de Gusmão, and Nicholas D Lane.  Flower: A friendly federated learning research framework.  _arXiv preprint arXiv:2007.14390_ , 2020.
  * Blanchard et al. [2017] Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer.  Machine learning with adversaries: Byzantine tolerant gradient descent.  _Advances in neural information processing systems_ , 30, 2017.
  * Bommasani et al. [2021] Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altmadokcn, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, and Emma andockerd others Brunskill.  On the opportunities and risks of foundation models.  _arXiv preprint arXiv:2108.07258_ , 2021.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Ghorbani and Zou [2019] Amirata Ghorbani and James Zou.  Data shapley: Equitable valuation of data for machine learning.  In _International conference on machine learning_ , pages 2242–2251. PMLR, 2019.
  * Hsu et al. [2019] Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown.  Measuring the effects of non-identical data distribution for federated visual classification, 2019.
  * Jethani et al. [2022] Neil Jethani, Mukund Sudarshan, Ian Covert, Su-In Lee, and Rajesh Ranganath.  Fastshap: Real-time shapley value estimation, 2022.
  * Jia et al. [2019] Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas J Spanos.  Towards efficient data valuation based on the shapley value.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 1167–1176. PMLR, 2019.
  * Kaissis et al. [2020] Georgios A Kaissis, Marcus R Makowski, Daniel Rückert, and Rickmer F Braren.  Secure, privacy-preserving and federated machine learning in medical imaging.  _Nature Machine Intelligence_ , 2(6):305–311, 2020.
  * Koh and Liang [2017] Pang Wei Koh and Percy Liang.  Understanding black-box predictions via influence functions.  In _International conference on machine learning_ , pages 1885–1894. PMLR, 2017.
  * Li et al. [2022a] Bo Li, Peng Qi, Bo Liu, Shuai Di, Jingen Liu, Jiquan Pei, Jinfeng Yi, and Bowen Zhou.  Trustworthy ai: From principles to practices, 2022a.
  * Li et al. [2022b] Qinbin Li, Yiqun Diao, Quan Chen, and Bingsheng He.  Federated learning on non-iid data silos: An experimental study.  In _2022 IEEE 38th International Conference on Data Engineering (ICDE)_ , pages 965–978. IEEE, 2022b.
  * Liang et al. [2022] Weixin Liang, Girmaw Abebe Tadesse, Daniel Ho, L Fei-Fei, Matei Zaharia, Ce Zhang, and James Zou.  Advances, challenges and opportunities in creating data for trustworthy ai.  _Nature Machine Intelligence_ , 4(8):669–677, 2022.
  * McMahan et al. [2017] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data, 2017.
  * Parrachino et al. [2006] Irene Parrachino, Ariel Dinar, and Fioravante Patrone.  Cooperative game theory and its application to natural, environmental, and water resource issues: 3. application to water resources.  _Application to Water Resources (November 2006). World Bank Policy Research Working Paper_ , (4074), 2006.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems 32_ , pages 8024–8035. Curran Associates, Inc., 2019.
  * Reddi et al. [2021] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H. Brendan McMahan.  Adaptive federated optimization, 2021.
  * Richardson et al. [2019] Adam Richardson, Aris Filos-Ratsikas, and Boi Faltings.  Rewarding high-quality data via influence functions.  _arXiv preprint arXiv:1908.11598_ , 2019.
  * Rieke et al. [2020] Nicola Rieke, Jonny Hancox, Wenqi Li, Fausto Milletari, Holger R Roth, Shadi Albarqouni, Spyridon Bakas, Mathieu N Galtier, Bennett A Landman, Klaus Maier-Hein, et al.  The future of digital health with federated learning.  _NPJ digital medicine_ , 3(1):119, 2020.
  * Sarikaya and Ercetin [2019] Yunus Sarikaya and Ozgur Ercetin.  Motivating workers in federated learning: A stackelberg game perspective.  _IEEE Networking Letters_ , 2(1):23–27, 2019.
  * Shapley [1951] Lloyd S Shapley.  Notes on the n-person game—ii: The value of an n-person game.  1951\.
  * Song et al. [2019] Tianshu Song, Yongxin Tong, and Shuyue Wei.  Profit allocation for federated learning.  In _2019 IEEE International Conference on Big Data (Big Data)_ , pages 2577–2586. IEEE, 2019.
  * Tu et al. [2021] Xuezhen Tu, Kun Zhu, Nguyen Cong Luong, Dusit Niyato, Yang Zhang, and Juan Li.  Incentive mechanisms for federated learning: From economic and game theoretic perspective, 2021.
  * Wang et al. [2019] Guan Wang, Charlie Xiaoqian Dang, and Ziye Zhou.  Measure contribution of participants in federated learning.  In _2019 IEEE international conference on big data (Big Data)_ , pages 2597–2604. IEEE, 2019.
  * Wang et al. [2020] Tianhao Wang, Johannes Rausch, Ce Zhang, Ruoxi Jia, and Dawn Song.  A principled approach to data valuation for federated learning, 2020.
  * Yin et al. [2021] Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter Bartlett.  Byzantine-robust distributed learning: Towards optimal statistical rates, 2021.
  * Zeng et al. [2020] Rongfei Zeng, Shixun Zhang, Jiaqi Wang, and Xiaowen Chu.  Fmore: An incentive scheme of multi-dimensional auction for federated learning in mec.  In _2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS)_. IEEE, November 2020.  doi: 10.1109/icdcs47774.2020.00094.
  * Zhang et al. [2020] Jingfeng Zhang, Cheng Li, Antonio Robles-Kelly, and Mohan Kankanhalli.  Hierarchically fair federated learning.  _arXiv preprint arXiv:2004.10386_ , 2020.