Incentive-Aware Federated Learning with Training-Time Model Rewards
Authors: Zhaoxuan Wu
Mohammad Mohammadi Amiri
Ramesh Raskar
Bryan Kian Hsiang Low
Venue: ICLR 2024 poster (2024)
Keywords: Collaborative learning
Incentives
Global-to-local design
Primary area: societal considerations including fairness, safety, privacy
TL;DR: A novel algorithm that distributes training-time model rewards to incentivize client contributions for federated learning.

Abstract: In federated learning (FL), incentivizing contributions of training resources (e.g., data, compute) from potentially competitive clients is crucial. Existing incentive mechanisms often distribute post-training monetary rewards, which suffer from practical challenges of timeliness and feasibility of the rewards. Rewarding the clients after the completion of training may incentivize them to abort the collaboration, and monetizing the contribution is challenging in practice. To address these problems, we propose an incentive-aware algorithm that offers differentiated training-time model rewards for each client at each FL iteration. We theoretically prove that such a $\textit{local}$ design ensures the $\textit{global}$ objective of client incentivization. Through theoretical analyses, we further identify the issue of error propagation in model rewards and thus propose a stochastic reference-model recovery strategy to ensure theoretically that all the clients eventually obtain the optimal model in the limit. We perform extensive experiments to demonstrate the superior incentivizing performance of our method compared to existing baselines.

Published as a conference paper at ICLR 2024
INCENTIVE-AWARE FEDERATED LEARNING WITH TRAINING-TIME MODEL REWARDS
Zhaoxuan Wu', Mohammad Mohammadi Amiri', Ramesh Raskar & Bryan Kian Hsiang Low Institute of Data Science, National University of Singapore, Republic of Singapore Department Computer Science, Rensselaer Polytechnic Institute, USA $ Media Lab, Massachusetts Institute of Technology. USA
i -Department of Computer Science, National University of Singapore, Republic of Singapore (wu. zhacxuan, lowkh) comp. nus edu, st mamiri@rp edu teskar@mitt.duu
ABSTRACT
In federated learning (FL), incentivizing contributions of training resources (e.g.. data, compute) from potentially competitive clients is crucial. Existing incentive mechanisms often distribute post-training monetary rewards, which suffer from practical challenges of timeliness and feasibility of the rewards. Rewarding the clients after the completion of training may incentivize them to abort the collab- oration, and monetizing the contribution is challenging these problems, we propose an incentive-aware algorithm that offers differentiated training-ting model rewards for each client at each FL. iteration. We theoretically prove that such a local design ensures the global objective of client incentivization. Through theoretical analyses, we further identify the issue of error propagation model rewards and thus propose stochastic reference- model recovery strategy ensure theoretically that all the clients eventually obtain the optimal model in the limit. We perform extensive experiments to demonstrate the superior incentivizing performance of our method compared to existing baselines.
practice. To address
INTRODUCTION
Federated learning (FL) a popular framework that fosters collaboration among distributed clients while keeping the raw data on their local devices (McMahan et al., 2017). The clients perform local optimization on local data, while the server performs centralized parameter updates by aggregating these local model updates (Li et al., 2020a). It is essential to motivate potentially competing clients to contribute their training resources since they incur nontrivial costs for data collection (Sim et al. 2020), local computation (Sarikaya & Ercetin 2020). and federated communication (Lim et al. 2020). Moreover, self-interested clients may refrain from contributing to the best of their abilities or drop out of the FL due to insufficient rewards (Zhan et al. 2022). which can delay model training and worsen model performance (Tu et al.
2022). To address these issues, a number of incentive mechanisms
have been proposed (Tu et al.
2022 Khan et al. 2020 Zhang et al., 2021 Liu et al. 2023).
Most existing incentive mechanisms distribute external resources (e.g., money) post-training ZZan al. 20222 Tu al., 2022). which poses practical challenges regarding the timeliness and feasibility of the incentives. Firstly, rewarding clients only after the completion of the FL process can discourage their participation as they usually anticipate timely rewards due the continuous contribution of costly resources throughout the process (LMAA 2019). It is also impractical to withhold compensation for clients until the end of the FL process as they have the freedom to exit the collaboration in the middle of the process. Secondly, monetary incentives are often infeasible in situations where the source of revenue unclear, the budget is limited (Sim et al. 2020), and the contribution-to-de value denomination is difficult to determine (Xu et al.) 2021 To tackle these challenges, it is vital to design training-timi ttim model rewards at each iteration of the FL process to achieve the overall incentivization goal. However, few work have explored this direction (Xu et al. 2021 Kong et al.) 2022), and their heuristic methods overlook the important theoretical implications of local design choices the performance of rewarded models and thus client incentivization.
A central issue is the global-to- tollocal design: How should each client be rewarded locally in each FL iteration, given the global incentivization objective? Inspired by the game-theoretic insights,

---

Published as a conference paper at ICLR 2024
propose that the proportion of local model updates, which client can aggregate as local reward, should be commensurate with his contribution in each FL iteration. Therefore, clients receive different models (each aggregated using a specific proportion of local model updates) such that highhe-contributing clients receive models aggregated from a larger proportion of local model updates. We prove this local reward scheme ensures that higher-contributing client gets final model with better performance guarantee. However, we observe an undesirable phenomenon of error propagation from the performance bound: Low-contributing clients can worsen every client model as aggregating low-quality model updates can adversely influence the high-quality models (Deng et al. 2022).
This phenomenon implies that achieving the incentivization goal prevents the client models from reaching optimality. Ideally, our algorithm should allow clients to eventually get the globally optimal model. How to adjust our local reward scheme if we want every client to obtain the best model the limit yet without hurting their incentives? To address this challenge, we propose a reference-mode! recovery strategy that stochastically provides every client with the same reference model at each FL iteration. This approach mitigates the enror propagation, and we further prove that all the client models asymptotically converge to the global optimum as long as their contributions do not diminish "too quickly" with the FL iterations. Consequently, every client is better off and is expected to eventually receive the best model while still being incentivized to contribute in finite FL iterations.
In summary, we propose an incentive-awan federated learning (IAFL) algorithm with training- tramning-time model rewards commensurate with client contributions, while being agnostic to any contribution measures (Section 4 Then, we theoretically justify our design choices through convergence anal- yses (Section 5). Finally, we demonstrate through extensive experiments that our method enjoys superior incentivizing performance compared to other baselines (Section
2 RELATED WORKS
Mechanism design for FL incentives. Popular tools to model the behaviors of the server and clients
include Stackelberg games (Khan et al., 2020 Zhan al. 2020), auctions (Zhang et al.) [022] Cong
iet al. 2020) and contract theory (Liu et al. 2023 Kang et al. 2011)). which all utilize post-training
monetary incentive schemes to motivate client contributions (Zhan al., 2022 Tu et al., 2022).
Karimireddy et al. (2022) suggested post-training model rewards of various utilities achieved through noisy model perturbation. However, this method may not be effective in FL since clients have already obtained the best global model during the model broadcasting of the FL process. Our paper instead directly integrates the incentive mechanism into the FL algorithm using training-time model rewards.
Heterogeneity and personalized FL. Data heterogeneity among distributed clients is common challenge in FL (Wang et al. 2020aa Chen et al. 2022). Methods like FedProx (Li et al., 2020b) and FedNova (Wang et al., 2020a) train single shared model that aligns clients' potentially mismatched
objectives caused by heterogeneous local data distributions. Personalization in FL yields a personal- ized model for each client and focuses on improving performances on local test sets (Tan et al. 2022).
Personalized models are achieved by personalizing layers or structures of the shared model (Liang et al. 2020 Collins et al. 2021 Li al. 2021 Pillutla et al.) 2022). In contrast, we focus on tailored client model rewards trained by optimizing a shared global objective with data heterogeneity (e.g.. a client with only MNIST digits from class 0-2 still interested in model that classifies all digits).
Training- training-time model incentives for FL. CGSV (Xu et al. 202I) and Rank (Kong et al., 2022) have explored training-time model incentives during FL. However, their heuristic approaches lack theoretical convergence analyses. Additionally, Rank impractically assumes access to a validation set to rank local model performances for aggregation. CGSV presents a contrasting perspective to ours: CGSV zeroes out partial model update parameter values for all clients, while our IAFL effectively zeroes out partial client model updates for all parameter values. Our aggregation approach is more aligned with the partial client participation setting in FL. (L.i et al., (220dd). CGSV's local performance guarantee cannot be generalized to the global incentivization objective for the entire FL training.
3 NOTATIONS AND BACKGROUNDS
We consider N federated clients collaboratively learning predictive model 0 E Rd. Client i has a lo- cal dataset DD of size B, such that the grand dataset D -,, Dr has size B == Di= B, The global
N
2

---

Published as a conference paper at ICLR 2024
B, EdED, f( d) loss F(0) = - (,Fi(0) is weighted sum of local loss functions F. 1
where -+( is empirical loss function. Let 0, denote the global model FL. iteration t. FL. conducts two steps for T iterations: (1) Clients download the global model 0 6, where 0%, denotes the model at client i before the j-th step of the local update; (2) Clients perform steps of ( (.,,) where T/ is the learning rate and E, is the local batch randomly chosen for the stochastic gradient descent step. Then, each client i uploads 1,t7 (,,)) to the server.
local updates according to 0/ 0-, 7i P. 1,2:
the model update gt,- = 0,, 0 = 7) Σラ=1 VF,
Game-theoretic formulation for incentivization. Instead of assuming benevolent clients as in the standard FL, we consider more practical setting where client i has the freedom to strategically decide his resource contribution Pi E IRz-- Let p-; [p) ,P,,,,,... Pi pi..........00 PP]] E RR5-1 we define P-4 E R20 as the aggregate contribution of clients other than i. We define rewarding function v(p,, P-+) that continuous, non-decreasing and concave on both arguments, reflecting the diminishing marginal return of contribution. It is usually observed in machine learning that the marginal increase in model accuracy diminishes with the increase in training dataset size (Wang et al.) 2021 & Chakrabarti] 2022). Furthermore, client incurs a non-trivial constant cost C; > 0 for offering some marginal contribution (Sim al. (2000) and the cost is essential for the clients to decide an optimal amount of contribution that yields the highest utility (i.e., benefit minus cost). Practically, e, could account for the cost associated with collecting an additional data sample, computing the gradients for larger dataset, or increasing the rate of partial federated participation.
INCENTIVE- FEDERATED LEARNING
Standard FL focuses training globally shared model and neglects the incentives for clients join the FL procedure. We rethink the server-centric objective of FL and aim to develop a client-centric procedure to incentivize participation. The main idea is to offer training-tine time model rewards that commensurate with client contributions through our proposed mechanism implementation.
4.1 INCENTIVE MECHANISM
When multiple clients are free to decide their contributions, clients' behaviors depend on the rewarding strategy formalized as a mechanism My 1R% - [0, 11a The rewarding mechanism M, = P(p,.P-)) maps the contribution vector p to the corresponding reward values using the rewarding function v. In standard FL, the global model is synced with all the clients at cach FL iteration. Clients lose their incentives to increase p; since they receive the best aggregate model regardless of contributions. Therefore, we have P-; h(p->) where the aggregate function h only depends p-g. Our idea is make P_, dependent on P; by defining a new aggregate function h(p; P-.).
Proposition 1. h satisfies dh(p:.p-.) > 0 and h(p....)...-..). > 0, then a mechanism [M, = Dh(p.p-1)
dp,
v(p., h(p., p-))) incentivizes a client to contribute more than that the standard FL mechanism.
The proof is in Appendix B.1 Specifically,
0 implies that client should benefit more from other clients if his contribution pt is larger, and @v(p,,
p-.) > indicates the feasibility of improving the reward from increasing the aggregate contribution of other clients. Proposition D
reveals possible better designs of the mechanism that incentivize clients to contribute more resources. This result aligns with Karimireddy et al. (2022). which showed that the standard FL mechanism leads to catastrophic free-riding where only the lowest cost client contributes.
Mechanism design. Following Proposition we propose to design a function h and a mechanism to reward clients based on contributions. Intuitively, we allow clients with higher contribution p; to be rewarded based on a larger proportion of the aggregate contribution other clients h h(p=:). We first propose (p)):
y (pi, (p:/ w//max, Pj h/)((( (p..))) However, this mechanism with relative rewarding strategy may result in an undesirable equilibrium. It is possible that clients converge to an equilibrium where all clients give similar but little contributions. Such equilibria are undesirable as little contribution may translate to a bad model. The proof for the existence of undesirable equilibria is provided in Proposition 3 in Appendix B.2 To circumvent this problem, propose to replace
3

---

Published as a conference paper at ICLR 2024
max; Py with pre-defined contribution ceiling Peet and tunable sharing coefficient [0, 1],
Mu(p)]: = y (pi, (min (pi/Peeit 13) - hpp.:))
Here, Poeil can be viewed as a hypothetical upper limit for a client's contribution imposed by the mechanism. For example, Poeil = implies full client participation in all FL iterations if p; measures the rate of client participation. As for the sharing coefficient, K determines the extent of sharing enforced by the server. A larger x makes the rewards more equitable across clients. One limitation of this design is that the clients lose incentive for p; > Peeil- The server can mitigate this by setting high Poeit upper limit (to keep incentivizing high contributors) while setting a larger k. (to even out the fractions (ps/Pcea)) towards 1 to motivate low contributors).
To interpret, :)) can be seen as local model updates from other clients (i.e., other than client i) in FL and a client with higher contribution p; is rewarded a model trained with a broader range of local model updates. If an averaging aggregation strategy is adopted, the model of a higher-contributing is updated using an aggregated average from larger proportion of local model updates.
Definition 1 (Individual Rationality (IR) in FL). A mechanism (p(p) satisfies individual rationality if [M. 2 u(p., h())) for any i and p. That is, any client will receive a reward at least as good as what they can achieve on their own.
Remark 1. Our mechanism 7 satisfies IR (Definition [.. an established concept for player incen- rivization now adapted FL. In our FL process, client i always utilizes the resource ps that he contributes. This essential property of our mechanism ensures the participation of all rational agents.
4.2 IMPLEMENTATION OF THE MECHANISM IN FL
We present an implementation of mechanism I in the FL algorithm. We extend the setting in Sec- tion 4.1 to allow client i to vary its contribution Pi, across iterations t (instead of a fixed p,). Aligning with the conditions in Proposition [ we propose the idea that, instead of sharing the global model in each iteration, the server shares updates of varying qualities with the clients. Accordingly. a client with higher contribution receives a higher quality model. This can be achieved by first computing a client reward rate "/, = (min (mi.tpp.e//r (ps.t/eenii Peeit 1))=- min (Pt,((/////// -==, 1 and then using it to vary the proportion of local model updates { N
i- that a client can average from in iteration f. To ensure convergence to the global optimum, we additionally introduce a stochastic recovery (with probability q) of client models using a flexible user-defined reference model Over, trained with custom induced reward rates Yfo,t- z- We defer the justification and details of the stochastic recovery technique to Section 5.1 The details of the incentive-awan federated learning (IAFL)
algorithm are in Algorithm where [N] == (1.,...., N} and [-] denotes the ceiling.
Algorithm Incentive- Federated Learning
Procedure 2: ServerAgg(t)
Initialize 0.00 Oret.o Oo and 9:.0 O;
foreach client do Compute
2 for t to T do
3 Perform Procedure 2 such that { Oref,t-1 = ServerAgg(t- - -1); foreach client i do with probability do Server shares 0.ef,e-1 with client 02,- = 0zef,c-1:
78, min (ps.e/Pcal) "
Sample S S ( Kújje Ni. #
randomly s.t.
|5,,1 = [ - 1)]:
Include client i's update
St, = (1) U.
else
A0,, |sr.el Eyes,, 95.1i
Server shares A with client é;
0.1 0, A0
Sample Spef, S [N] randomly such that |Stetal = 1o
0_1 O.. T/t Σj= VF, C.
1,13
0 = 0 + [uur.al Ejes.r. Iisi
Upload the local update gi.t 0
12
return [A0,,)N Oret.
An intuition for the connection between the mechanism in and the IAFL algorithm is provided in Appendix|C Overall, clients keep different versions of the model and update their respective models using the partially averaged model updates rewarded to them over the FL iterations. The models have varying qualities as the updates rewarded to the clients are crafted to match their contributions. This approach incentivizes clients increase their contributions to the learning process.
4

---

Published as a conference paper at ICLR 2024
Contribution measurement. Our IAFL is agnostic to contribution measures and distributes training- time model rewards that are commensurate with client contribution Pt, This is beneficial because clients have the option define custom contribution measure collaboratively. Besides the con- ventional measures depending on dataset size or participation rate, it is possible to utilize external knowledge to value contributions. For example, meta attributes such the timeliness of the data, reliability of the client network and closeness of clients' relationships are all possible considerations of the contribution measure. Importantly, our method also gives the flexibility to vary p; with FL itera- tion t through Pi,e- Our IAFL is also plug-and-pla with existing FL contribution evaluation methods capturing the quality of local model updates, such as FedSV (Wang et al. 2020b), ComFedSV (Fan)
et al. 2022). CGSV (Xu et al. 2021 FedFAIM (Shi et al. 2022) R-RCCE (Zhao et al.
2021
etc.
5
THEORETICAL ANALYSIS
This section provides theoretical justification for IAFL via convergence analysis. Our training-time local reward scheme ensures that a higher-contributing client receives a final model with a better performance guarantee. We further propose stochastic reference- the theoretically observed error propagation problem and ensure the asymptotic convergence of client models to the global optimum as T + oc. For ease of analysis, we consider full client participation, where the results can be extended to partial client participation following Li et al. (2020d). We define an induced reward rate Y. "/, (7.. - 1)/N, which represents the fraction of the local model updates used by client at FL iteration t.
recovery strategy to mitigate
5.1 PERFORMANCE GUARANTEE
Formalized in Assumptions (Appendix D we assume that the loss functions F.(-) are L-smooth and j--ttroggyy convex. The average expected variance of stochastic gradients is Στ, and the squared 12-norm of stochastic gradients is bounded by G. We let each client have the equal weight w; = 1/N in the global objective F and further use r = F - Σ i=1 w.F, to denote the extent of data heterogeneity where F and Fç are the optimum values of F and F,, respectively.
Theorem 1 (Performance bound). With full clients participation and a decreasing learning rate 2LT(2T + 3)I + 2T -252² (a pr (2 > then the performance of the client model
Me अनें where a AL(7+1) define
1)p² 1 0-]]3] and HTT O.r trained over T FL iterations using IAFL is bounded by
L C+ 16 [[F(O,T)]-F F 21272 a+T
HT ΣΣ
T
T T+a [+a) i+a
1 7m.e
where Cr
T1.t
The proof is given in Appendix D.I Here, B is constant W.r.t and the client contributions only affect Th and thus Cy. To interpret, our IAFL ensures that a nigher-contributing client (i.e., larger )(.)) receives a model with better performance guarantee measured in terms of the expected performance gap to the global optimum. This aligns with our goal of rewarding nigher-contributing clients more and hence incentivizing client participation and contributions. However, we observe that Cr grows with FL iterations T and causes non-convergence of client model 0gr-- This undesirable behavior is caused by the lack of model synchronization and we next propose a remedy to the problem.
Error propagation and non-convergence. The non-convergence is seen in Theorem a T oo. Asymptotically, we require Cr/T - for the algorithm to converge to F*. Since we already have (IIT/T) ΣT= /22 O(T), we need 1/ = o(1/T") for the convergence to hold, where the big-O and small-o notations are defined in Definition D.I and Definition D.2 However, this cannot be achieved as Yh, < 1, Vt. Consequently, we instead require that Y = I for all i E [N], E [T], which corresponds the situation where all the clients contribute at their maximum capacity.
Corollary 1. When all the clients contribute their maximum capacity, i.e., Pi.1 Peeit for all [N], t E [T], we have Cr = 0 and achieve asymptotic convergence limy-+0e E [F(O..)) - 0.
Corollary D states a very strong assumption that recovers the FedAvg algorithm: Even when only one client fails to contribute at the maximum, all client models cannot be guaranteed converge the
5

---

Published as a conference paper at ICLR 2024
optimum, including for the highest-contributing client. We call this phenomenon ervor propagation because low-quality model updates from lowtcontributing clients deteriorate the high-quality models.
Stochastic recovery strategy. To ensure convergence to the global optimum. propose stochastic recovery strategy, which shares the current reference model with a client at probability q. The reference model is allowed to have custom induced reference reward rate Veef.e- Specifically, the reference model is trained by aggregating local model updates (gi,))ess,c. where Stof, is randomly sampled from [M] such that |S
: N. Therefore, every participating client at each FL iteration has an equal chance q of receiving the current reference model. With probability - the client still receives from the server an update that is aggregated with the corresponding proportion of local model updates. Algorithm| outlines the implementations. As we present in the following theorem, this method prevents persistent error propagation and enables the convergence of the model.
Theorem 2 (Improved bound). Let T = Tta and B, Hr be defined in Theorem I
With a stochastic recovery rate of q. the performance of client model Oir trained over T FL iterations bounded by
_
T (1
T
T
[[ - F*
II
110| - 1- +
Σ
+ D2 + E.)
II 1=++1
(1 - 2pmnT
2
HT
N
T
2
1
1
-2/
2 2) (1 99) T-+11
where
DT
N
t+a a
Veof.
Er= = HT
T
T T+a) a
2
(11
(
1
-
(1 (1-9)T-(+1.
t+a
Ti,t
Weet
Proposition 2 (Asymptotic convergence). If T.. = (
12
for all i E [N] and 1
12
logt
Ye Togg
lim E [F(00.T)] - F 0.
T-+00
The proofs are in Appendix [D3 and Appendix D.4 Asymptotically, all clients are expected to achieve the optimal model regardless of their contributions. To interpret the conditions for convergence, the contributions of all clients i E [N] and the induced reference reward rate do not decrease too quickly over time. The first condition satisfied as 1/76, S N by definition whereas the second is user- defined. While offering the same model in the limit may seem to work against client incentives at first glance, clients who exit the collaboration early will not obtain the global optimal model. Theorem 2 shows that the impact of contribution Y., is reflected on Er, where Ey decreases with 74,- Therefore, a client that contributes more receives a better model with smaller performance gap to the global optimum. This improvement is more highlighted for limited FI. iterations T (see Section 6.2
6 EXPERIMENTS
In this section, we show the effectiveness of IAFL and the impacts of its hyperparameters. We also show that IAFL is suited for custom contribution measure definitions and partial client participation.
Datasets & partition strategies. We use the datasets and heterogeneous data partition pipelines in the non-IlI FL Benchmark (Li et al. 2022). We simulate 50 clients for all experiments. We perform extensive experiments on various vision datasets like MNIST (LeCun et al. 1989), FMNIST (Xiao) al. 2017). SVHN (Netzer al. 2011), CIFAR-10/100 (Krizhevsky 2009), Tmmg-lm (Deng et al. 2009) and language datasets Stanford Sentiment Treebank (SST) T) (Socher et al.) 2013). Senti-
ment140 (Go al. (209). The datasets are partitioned among the clients following five partitioning strategies: (I) Distribution-
label distribution skew simulates label imbalance by sampling
proportions Te from a Dirichlet distribution Dir(B) where 33 is the concentration parameter. For each label class k we sample n and allocate Tk of label-k samples to client i; (2) Quantity-based label distribution skew, denoted by #C = k. creates another type of label imbalance by sampling label classes for each client and then randomly and equally distributing samples from class k among eligible clients; (3) Noise-based Seatuur feature distribution skew only applies to vision datasets and adds noises with distribution No i/N) the data of client i; (4) Quantity skew allocates n. proportion of total data randomly to client from a Dirichlet sample π ~ Dir(B): (5) Homogeneous partition, denoted by IID, partitions the samples from each class randomly and equally among the clients.

---

Published as a conference paper at ICLR 2024
Table 1: Comparison of aaeu among IAFL and baselines using different dataset partitions. Each value reports the mean and the standard error of 10 independent evaluations and partition seedings.
Category
Dutaset
Partitioning
FedAvg Finelune
LG-FedAvg
CGSV
Rank
IAFL
MNIST
(.r(
0.85+0.01
0.96==0.1
0.95=0.01
0.79=0.08
1.00::0.00
#C 3
0,73++0,06
1.00-0.00
1.00-0.00
0.84+0.02
1.00-0.000
FMNIST
(055
0.65100.33
0.89.10.01
0,95100.11
0.8010.02
0.9910.01
#C' =3
0.4120.04
0.99:0.01
0.9920001
0.7120002
1.00:0.000
Distribution
Label
SVHN
(ar(0.5)
#C*
0,9910.00
0.35
0.97
1.00
0.561:0.09
0.90
0.92.0..22
0.46::0.02
0.82.10.02
1.0010.00
Skew
CIFAR-10
(ar(0.5)
#0
0.26:20.09
0.00+00000
0.45=00.09
0.01=0.01
0.12=00.06
0.01=0000
0.33=00.10 10
0.02=00001
0.67:=0.05
0.46::0.03
CIFAR-100
(8r(0.5)
0.37++0.05
0.96-00.22
0.00-00.00
0.83::0.02
1.00: 0.00
#C
0.02110.01
0.14.10.3
0.001:0:00
0.4010.055
0.64
SST
(1.5
0.47=20.04
0.65=0.02
0.47=00.33
0.75=00.03
0.79::0.03
0.96:t0.01
0.58=0002
0.51=0005
0.85=0.01
0.89:00011
MNIST
0.19:00.3
0. 0.70=0.044
0.98=00.01
0.21=00044
0.71=00.09
Feature
FMNIST
0.66++0.03
0.16--0.05
0.02+0.01
0.68+00.3
1.00--0.00
Distribution
SVIN
N((0.1)
1.00100000
1.00.0.00
1.00
0.97.10.01
1.00
Skew
CIFAR-10
1.00:0.00
1.00=0.00
0.16:00.07
1.00=00000
1.00:0.00
CIFAR-100
1.00=0.00
1.00=0.00
0.46=0.10
0.98=0.01
1.00:00000
MNIST
0,7510.02
0.8910.01
0.95100011
0.97.10.01
0.9910.01
FMNIST
0.88++0.02
0.80--0.3
0.52+00.2
0.90+00.22
1.00
Skew
Quantity
CI
SVIIN
(..(
0.912:001
10.00
0.96:20.01
1.00
0.65=0.02
0.9910001
0.63.10.06
0.5420.04
0.96:10.00
1.00.0.00
CIFAR-100
0.98=#0.01
0.99=0000
0.68=00011
0.68=00044
0.98=
SST
1.00+00.00
0.57=0005
1.00-0.00
0.94+0001
1.00--0.00
MNIST
0.23+20.02
0.58:20.04
0.99
0.25=20.06
0.71=00007
EMNIST
0.60+00.05
0.37=00.3
0.01=0.01
0.68=0004
1.00:0.00
Homogeneous Partition
SVHN
1,00::0000
1.00:00000
1,00
1.00=0.00
1.00:00000
CIFAR-10
H1
1.00::0.00
1.00=0.00
0,26=00099
0.99=0000
1.00::0.00
CIFAR-100 100 SST
1.00++0.00
1.00=0.00
0.64++0.08
1.00=00.00
1.00::0.00
1,00 1.00:
0.51
0.00
0.96.10.01
1.00:00.00
Number times that performs the best
10
11
7
3
24
Baselines. We compare to a FedAvg (McMahan et al. 2017) baseline with local finetuning, a personalization method G-FeeAAg (Liang et al.) 2020) and two FL training-tine model incentives methods, CGSV (Xu et (201]) and Rank (Kong et al. (022). In particular, CGSV has demonstrated empirical superionity over other popular techniques such as q-FFL (Li et al., 2020c), CFFL (Lyu et al., 2020) and ECI (Song et al. 2019). We refer to Appendix F. for the implementation details.
6.1 INCENTIVIZATION PERFORMANCE
Incentivized participation rate (IPR). Cho et al. (2022) proposed using IPR to measure the incentivization performance of an FL algorithm. We let IPR be the percentage of clients receiving a model not worse than his standalone model in terms of the test loss. Likewise, We define IP but in terms of the test accuracy. Here, a standalone model refers to the model trained only with the client's local dataset. IPR therefore indicates IR (Definition) TT. Table subbarrism the IPR for different methods. datasets and partitions. Notably, our IAFL achieves the highest IPR 24 times out of the 29 experimental settings, out of which 17 of them have a 100% IPR Although FedAvg Finetune and L-F-FeAAy achieve comparable performance as IAFL., they are significantly worse than IAFL under the heterogeneous learning setting with label distribution skew, which may be the most challenging regime and the regime of interest for FL. Therefore, we have demonstrated IAFL's ability to facilitate effective collaboration to achieve better learning performance for federated clients. Additionally, we attribute the imperfect IR (Remark concave assumptions for the rewarding function in practice, which is defined as the test accuracy in this experiment. Alternatively choosing v as the test loss, IAFL achieves perfect IR for almost all settings. We show the results for IPR in Table of Appendix E.2 Additional results on complex large-scale datasets, ImageNn and Sent140, are in Appendix
the violation of non-decreasing and
Correlation to contribution. Another way to quantify the incentivization performance is by mea- suring the Pearson correlation coefficient p between the client model accuracies achieved by the algorithm after 7' FL iterations and their standalone accuracies (Xu et al. 2021). We use standalone accuracies as surrogate for the client contributions in FL,, hence a good incentivizing method should produce client models with accuracies highly correlated to the respective client contributions. Table 2 presents the effectiveness of various methods under different types of heterogeneity. Most methods, including LG-FedAvg. CGSV and Rank, could only perform well when the quality of client datasets
7

---

Published as a conference paper at ICLR 2024
Table 2: The incentivization performance under different dataset partitions, measured using the Pearson correlation coefficient p between the final client model accuracies and standalone accuracies. Each value reports the mean and the standard error over 10 independent evaluations.
Category
Dataset
Partitioning
FedAvg Finetune
LG-FedAAg
CGSV
Runk
IAFL
MNIST
#C
0.27-40.66
0.74+0.05
0.66+0.066
0.12-40.33
-0
-0800+0.02
0,56++0.03
0,71+00.08
0.59:0002
0.81--0.02
(.5
0.85=#0001
0.82=0.02
0.23=
0.92:0.01
0.84+00.02
FMNIST
#C
-0.05+0.099
0.35+0.05
0.28+00.4
0.65+0.01
0.86+-0.02
Label
SVHN
(05(
0.87.10.01
0.75.10.01
0.57.10.33
0.85110.01
0.811
Distribution
#C =3
100010.00
0.0120.02
0.49=0005
0.7910.02
0.8410.01
(5x(0.5)
0.76.10.04
0.79
0.79
CIFAR-10
#C' =1
0.83:10.01
0.88
0.31
0.56:10.06
0.63:10.02
CIFAR-100
#C = (15
0.58:10.4
0.43:0.04
0.20=0007
0.6020.05
0.89:00001
0.70=#0.02
0.55
0.01=0007
0.53+00.03
0.87
(15
0.83=1001
0
0.73=0004
0.89:0.02
0.7240.02
SST
#C=
0.86+
0.93=:0.01
0.53=00.09
0.84+0.01
0.66+0.02
MNIST
0.01 10.03
0.09110.04
0.0210.04
0.03:10.04
0.391.0.09
Feature
FMNIST
0.015
0.03++0.04
0.39
Distribution
SVIIN
((01.))
0.00.10.05
0.14
0.01
0.13:10.05
0.41.10.07
Skew
CLFAR-10
0.08
0.0220.04
0.2011004
0.57:10.03
CIFAR-100
0.12:#0.04
0.16=#0.04
0.0050005
0,20+0.03
0.72:+0.02
MNIST
4..56+0.03
0.82+0.04
0.37=0.16
0.88
0.77++0.03
FMNIST
-0.3++0.03
0.90++.01
0.86+0.04
0.94+0.01
0,78++0.02
Quantity
SVIN
(ir(0.3)
0,20010.03
0.83
0.75
0.9410.01
0.77
Skew
CI
0.25++006
0.73-00.4
0.95++0.01
0,80+-0011
CIFAR-100
00,241.0.04
0.80
0.66
0.931
0,83-10.01
SST
0.2011.006
0.49:0005
0.7010.02
0,47:10.5
MNIST
-0.03+00.05
0.02++0.05
0.08+00.4
0,01
0.39++0.12
FMNIST
0.04=0005
+..06:0.05
0.01=0.03
0.12:0.04
0.39::0.05
Homogeneous Partition
SVHN
0.04+#0.03
0.20+0007
-0.04+0.044
0.11+00.08
0.40::0.06
IID
CIFAR-10
0.00::0.05
0.08
-0.03-10.05
0.09::0.03
0.59:
CIFAR-100
0.002=0.033
0.08++0.00 04
0.05=00.07
0.18+0004
0.71::0.02
SST
0.27++0.04
0.69 00002
0.22-00.44
0.56++0.02
0.44
Number times that performs the best
15
exhibits distinct differences under severe lahel and quantity skew. They cannot handle the more chal- lenging scenarios under feature skew or homogeneous partition, where client data only present minor differences in standalone accuracies. In partieular, Rank further assumes access a good global validation set to rank local models during training, which could be infeasible in practice. FedAvg Finetune fails the quantity skew data partition, showing even negative correlations. In contrast, IAFL shows superior incentivization performance across extensive settings. It can achieve relatively high p for all settings and perform the best for 16 out of 29 experimental settings. Therefore, IAFL has demonstrated its ability to distribute model rewards that are commensurate with client contributions.
Predictive performance. We compare the average and highest client model test accuracies achieved by IAFL and the baseline methods. Presented in Table 5 of Appendix E.3 and Table T0 of Ap- pendix E.9 our IAFL outperforms other baselines in nearly all the settings. The high average client model performance illustrates the effectiveness of collaboration following IAFL. Additionally, IAFL able to maintain the model performance of high-contributing clients by updating their local models using data from larger proportion of clients, which is important in collaborative training setting. Additional results showing the average increase in test accuracies are in Table of Appendix E.4
6.2 EFFECT OF HYPERPARAMETER ON EMPIRICAL CONVERGENCE
Sharing coefficient K. As introduced in (I, [0, 1] determines the extent of sharing in IAFL and reflects an essential practical trade-off between model performance and client incentivization (more in Appendix E.7). larger K results in more equitable and better client models, but this can hurt the incentives of high-contributing clients as they receive models similar to those received by low-contributing clients. This is reflected Figure where we plot the model performance of clients with different X (see Section 5) A larger better utilizes local model updates and achieves higher accuracies. However, it results in models with more similar model performance and thus worse client incentivization measured by p. For convergence, Figure confirms the results in Theorem that less contributing clients converge to worse models, further away from the global optimum.
Stochastic recovery rate q. Stochastic recovery is introduced in IAFL to ensure asymptotic conver- gence to the global optimum for all client models. In a stochastic manner, each client has an equal probability g be recovered with reference model in each FL iteration. In practice, we recommend
8

---

Published as a conference paper at ICLR 2024
Table 3: Performance compari- son to baselines when ps corre- sponds to the participation rate.
p- 0
0.38
0.54
0.0
500
0.0
1000
0.0
253
500
Method
IPRaa
Acc. (highest)
iterationa
Earaabons
(tem
FedAvg
15
K11000
Y, 0.52
Ys 0.60
0.24
16 10.000
Finetune
0.06
0.28
(..1..0.16)
LG-FedlAg
-0.25
0.60
(0,15)
Figure 1: Effects of sharing coefficient x with a fixed stochastic
CGSV
Ronk
0.74
0.90
0.94
0.00
0.24 (0.31)
(0.07)
recovery rate. We use CIFAR-100 with quantity skew and N = 50.
IAPL
0.94
1.00
0.44 (0.53)
0.5
p 0.94
1.0
0.6
6.63
0.6
accursy
0.4
0.8
0.3
0.4 2.400
0.6 06
0.2
0.2
0.1
0.2
1000
500 Iterations
0.0
0.0
Iterations
herations
10
20
30
40
50
Client Index
55
-1.00
-00002
-4-
0.50
2.44
02-4
16 10.000
Figure 3: Visualization of corre-
Figure 2: Effects of stochastic recovery rate q with a fixed sharing coefficient. We use 110AR-100 with quantity skew and N = 50. the participation rate.
lation P when ps corresponds to
the reference model be updated with the best reward (largest X,)) ) in each FL iteration, whereas another choice of the "median" reference model is discussed in Appendix H..5 As shown in Figure 2 stochastic recovery presents a trade-off between incentivization performance measured by p and the test accuracies of client models. A small is sufficient q 0.01 results in higher test accuracies while maintaining a relatively high incentivization performance of p = 0.61 in finite FL iterations. The empirical convergence observed in Figure corroborates the theoretical guarantee in Theorem 2
Free riders behavior. With differentiated training time model rewards, IAFL can offer worsened or delayed rewards to free riders. In Figures | and 2 we identify client 6 with Xg- 0.09 as the free rider as it contributes very little compared to other clients. With q = O, the free rider only achieves 4.6% accuracy when 0 and 19.2% accuracy when the к 0.8. After the stochastic recovery is incorporated, we observe the free rider receives a good recovered reward at a delayed time stochastically and continues to worsen due the poor model updates received in each FL iteration.
6.3 ALTERNATIVE CONTRIBUTION MEASURES
IAFL is flexible to alug-and-play with various contribution evaluation techniques out of the box (i.e., no modification is needed). To demonstrate the effectiveness with partial client participation, we let the client participation rate be the measure. Specifically, in Figure 3 There is a high correlation of 0.94 between the test accuracies of client models and client contributions measured by the participation rate pj. In Table 3 IAFL also achieves the best average (highest) client model accuracy of 44% (53%) and IPR across all methods. In Appendix [.. we further show IAFL's superior effectiveness when using the established CGSV contribution measure.
define p: 0.5 x (1 (1+i/N) as illustrated
CONCLUSION & DISCUSSION
In this paper, we have introduced the IAFL, a novel algorithm that distributes training-time model rewards to incentive client contributions for FL. In particular, we propose a proportional aggregation scheme for local training-time rewards that achieves the global incentivization objective. By analyzing the theoretical guarantees of the method, we observe the eтror propagation phenomenon that creates tension between client incentives and achieving optimality on client models. We then mitigate the problem with a stochastic reference-mode recovery strategy, which enables us to distribute globally optimal models in the limit while preserving client incentives. Our method highly versatile and can be applied to wider range of domains (c.g., financial, biomedical, etc.) as it allows novel definitions of the contribution measure according to the specific resources that are valuable in the domain.
Our work also opens up several directions for future investigation. It is important to study the roles of the server and clients in determining the contribution measure and rewarding strategy. Additionally, there can be tensions and mismatches between the contribution measure and the model rewards because clients can continuously contribute, while model performance cannot grow infinitely and suffers from diminishing returns. We further elaborate on the broader societal impacts in Appendix

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
We have carefully discussed all the assumptions for the theoretical results and included the complete proofs for all theorems, lemmas and propositions in Appendix B To further improve the repro- ducibility of our work, we elaborate in Appendix [E.1 the details for dataset preprocessing, models architectures, hyperparameters for training using IAFL as well as training using all the baseline methods that we compare to. The code has been submitted as supplementary material.
ACKNOWLEDGEMENT
This research/project is supported by the National Research Foundation Singapore and DSO National Laboratories under the AI Singapore Programme (AISG Award No: AISG2-RP-2020-018)) The authors thank Fusheng Liu for many interesting discussions.
REFERENCES
Daoyuan Chen, Dawei Gao, Weirui Kuang, Yaliang Li, and Bolin Ding. pFL-bbenh: A comprehensive benchmark for personalized federated learning. In Proc. NeurIPS (Datasets and Benchmarks Truck), pp. 9344-9360, 2022.
Yae Jee Cho, Divyansh Jhunjhunwala, Tian Li, Virginia Smith, and Gauri Joshi. To federate not to federate: Incentivizing client participation in federated learning. In Proc. NeurlPS Workshop on Federated Learning: Recent Advances and New Challenges, 2022.
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared represen- tations for personalized federated learning. In Proc. ICML, pp. 2089-2099, 2021.
Mingshu Cong, Han Yu, Xi Weng, and Siu Ming Yiu. A game-theoretic framework for incentive mechanism design in federated learning. In Federated Learning: Privacy and Incentive, pp. 205-222. Springer International Publishing, 2020.
Abir De and Soumen Chakrabarti. Neural estimation of submodular functions with applications differentiable subset selection. In Proc. NewrlPS, pp. 19537-19552, 2022.
Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A large-scale hierarchical image database. In Proc. CVPR, pp. 248-255, 2009.
Yongheng Deng, Feng Lyu, Ju Ren, Huaqing Wu, Yuezhi Zhou, Yaoxue Zhang, and Xuemin Shen. Auction: Automated and quality-awaar client selection framework for efficient federated learning. IEEE Transactions Parallel and Distributed Systems, 336)):19962009,, 2022.
Zhenan Fan, Huang Fang, Zirui Zhou, Jian Pei, Michael P Friedlander, Changxin Liu, and Yong Zhang. Improving fairness for data valuation in federated learning. In Proc. ICDE, pp. 2440-2453, 2022.
Alec Go., Richa Bhayani, and Lei Huang. Twitter sentiment classification using distant supervision. CS224N project report, Stanford, 1(12):2009, 2009.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proc. CVPR, pp. 770-778, 2016.
Kevin Hsich, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The non-iid data quagmire of decentralized machine learning. In Proc. ICML, pp. 4387-4398, 2020.
IMDA. Guide to data valuation for data sharing. Technical report, The Infocomm Media Development Authority (IMDA) Singapore, 2019.
Jiawen Kang, Zehui Xiong, Dusit Niyato, Shengli Xie, and Junshan Zhang. Incentive mechanism for reliable federated learning: A joint optimization approach to combining reputation and contract theory. IEEE Internet of Things Journal, 17700-1177 2019.
10

---

Published as a conference paper at ICLR 2024
Sai Praneeth Karimireddy, Wenshuo Guo, and Michael Jordan. Mechanisms that incentivize data sharing in federated learning. In Proc. NeurIPS Workshop on Federated Learning: Recent Advances and New Challenges, 2022.
Latif U. Khan, Shashi Raj Pandey, Nguyen H. Tran, Walid Saad, Zhu Han, Minh N. H. Nguyen, and Choong Seon Hong. Federated learning for edge networks: Resource optimization and incentive mechanism. IEEE Communications Magazine, 58(10):88 93, 2020.
Shuyu Kong, You Li, and Hai Zhou. Incentivizing federated learning. arXiv:2205. 10951, 2022.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Department of Computer Science, University of Toronto, 2009.
Yann LeCun, Bernhard Boser, John Denker, Donnie Henderson, R. Howard, Wayne Hubbard, and Lawrence Jackel. Handwritten digit recognition with a tack-propagation network. In Proc. NeurIPS, 1989.
Qinbin Li, Yiqun Diao, Quan Chen, and Bingsheng He. Federated learning on non-iid data silos: An experimental study. In Proc. ICDE, pp. 965-999599 965-978, 2022.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-66 60, 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks, In Proc. MLSys, pp. 429-450, 2020b.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. Proc. ICLR, 2020c.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In Proc. ICML, pp. 6357-6368, 2021.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of FedAvg on non-IID data. Proc. ICLR, 2020d.
Paul Pu Liang Terrance Liu, Liu Ziyin, Nicholas B. Allen, Randy Auerbach, David Brent, Ruslan Salakbutdinov, and Louis-Philipee Morency. Think locally, act globally: Federated learning with local and global representations. arXiv:2001.01523, 2020.
Wei Yang Bryan Lim, Nguyen Cong Luong, Dinh Thai Hoang, Yutao Jiao, Ying-Chang Liang, Qiang Yang, Dusit Niyato, and Chunyan Miao. Federated learning in mobile edge networks: A comprehensive survey. IEEE Communications Surveys Tutorials, 22(3):001-2263 2020.
Yuan Liu, Mengmeng Tian, Yuxin Chen, Zehui Xiong, Cyril Leung, and Chunyan Miao. A contract theory based incentive mechanism for federated learning. In Federated and Transfer Learning, pp.
117-137. Springer International Publishing, 2023.
Lingjuan Lyu, Xinyi Xu, Qian Wang, and Han Yu. Collaborative faireess in federated learning. In Federated Learning: Privacy and Incentive, pp. 189-204. Springer International Publishing, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication--fficee learning of deep networks from decentralized data. In Proc. AISTATS, pp. 1273-1282. 2017.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In Proc. NewrIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Quoe Phong Nguyen, Bryan Kian Hsiang Low, and Patrick Jaillet. Trade-off between payoff and model rewards in shapley-fair collaborative machine learning, In Proc. NeurlPS, pp. 30542-30552 2022.
Krishna Pillutla, Kshitiz Malik,
Mohamed, Mike Rabbat, Maziar Sanjabi, and Lin Xiao. Federated learning with partial model personalization. Proc. ICML, pp. 17716-17758, 2022.
11

---

Published as a conference paper at ICLR 2024
Yunus Sarikaya and Ozgur Ercetin. Motivating workers in federated learning: A stackelberg game perspective. IEEE Networking Letters, 2(1):23 20223-77,20 2020.
Zhuan Shi, Lan Zhang, Zhenyu Yao, Lingjuan Lyu, Cen Chen, Li Wang, Junhao Wang, and Xiang- Yang Li. Fedfaim: A model performance-based fair incentive mechanism for federated learning. IEEE Transactions on Big Data, pp. 1-13, 2022.
Rachael Hwee Ling Sim, Yehong Zhang, Mun Choon Chan, and Bryan Kian Hsiang Low. Collab- orative machine learning with incentive-aware model rewards. Proc. ICML, pp. 8927-8936, 2020.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng. and Christophe Potts. Recursive deep models for semantic compositionality over sentiment treebank. In Proc. EMNLP, pp. 1631-1642, 2013.
Tianshu Song, Yongxin Tong, and Shuyue Wei. Profit allocation for federated learning. In IEEE International Conference on Big Data (Big Data), pp. 2577-2586, 2019.
Alysa Ziying Tan, Han Yu, Lizhen Cui, and Qiang Yang. Towards personalized federated learning. IEEE Transactions Neural Networks and Learning Systems, pp. 1-17, 2022.
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. IEEE Transactions on Cognitive Communications and Networking, 83)):156--159,, 2022.
Hui-Po Wang, Sebastian Stich, Yang He, and Mario Fritz. Progfed: effective, communication, and computation efficient federated learning by progressive training. In Proc. ICML, pp. 23034-23054, 2022.
Janyy Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. In Proc. NeurlPS, pp. 7611-7623, 2020a.
Tianhao Wang, Johannes Rausch, Ce Zhang, Ruoxi Jia, and Dawn Song. A principled approach to data valuation for federated learning. Federated Learning, pp. 153-167. Springer International Publishing, 2020b.
Tianhao Wang, Si Chen, and Ruoxi Jia. One-round active learning. arXiv:2104. 2021.
Yuxin Wu and Kaiming He. Group normalization. In Proc. ECCV, pp. 3-19, 2018.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. 1xXiv:100..077 2017.
Xinyi Xu and Lingjuan Lyu. A reputation mechanism is all you need: Collaborative fairness and adversarial robustness in federated learning. Proc. ICML Workshop on Federated Learning for User Privacy and Data Confidentiality, 2021.
Xinyi Xu, Lingjuan Lyu, Xingjun Ma, Chenglin Miao, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Gradient driven rewards guarantee fairness in collaborative machine learning. In Proc. NeurlPS, pp. 16104-16117, 2021.
Yufeng Zhan, Peng Li, Zhihao Qu, Deze Zeng, and Song Guo. A learning-based incentive mechanism for federated learning. IEFE Internei of Things Journal, 7(7):6300-636) 2020.
Yufeng Zhan, Jie Zhang, Zicong Hong, Leijie Wu, Peng Li, and Song Guo. survey of incentive mechanism design for federated learning. IEEE Transactions Emerging Topics in Computing, (M2)::035-1044, 2022.
Jingwen Zhang, Yuezhou Wu, and Rong Pan. Incentive mechanism for horizontal federated learning based on reputation and reverse auction. In Proc. WWW, pp. 947-956, 2021.
Jie Zhao, Xinghua Zhu, Jianzong Wang, and Jing Xiao. Efficient client contribution evaluation for horizontal federated learning. In Proc. ICASSP, pp. 3060-3064, 2021.
Xingyu Zhou On the Fenchel duality between strong convexity and Lipschitz continuous gradient. arXiv: 803.06573, 2018
12

---

Published as a conference paper at ICLR 2024
A BROADER IMPACTS AND ETHICS
Designed to promote client contribution among potentially competitive clients in Fl., our incentive- aware federated learning algorithm with training-time model reward offers versatile applications in various fields such finance, healthcare, the Internet of things, etc. While our proposed method is capable of shaping the pipeline of collaboration between the server and clients in distributed learning, also see potential societal impacts associated with the development of such incentive methods.
Firstly, the use of highly customizable contribution measures presents both advantages and challenges. While it is technically feasible employ any contribution measure, ethical considerations arise when certain choices of the contribution measure do not align well with the training-tima model reward. For instance, the rewards based on model performance (e.g., using the performance as utility measure), cannot infinitely improve and should exhibit diminishing returns with respect to the contribution of learning resources. This raises questions about the ethical implications of incentivizing client contributions in these later stages of model training, especially when the marginal utility is minimal. Is it ethical continue incentivizing client contributions later FL iterations (e.g., near convergence). knowing that the marginal utility of contribution is small? Is it reasonable to reward a client less at later FL. iteration, even though the client contributes more in this FL iteration as compared to some earlier iterations? These concerns need to be addressed with specific application scenarios, taking into account the characteristics of the server and clients. In order to mitigate these ethical concerns, it may be necessary enforce regulations the protocol to ensure the adoption of an accumulative contribution measure.
Secondly, the ethical considerations regarding the distribution of rewards require closer examination. In this paper, we adopt the perspective of collaborative fairness (Xu & Lyu [202]). where our incentive-awart algorithm encourages client contributions by providing rewards commensurate with their level of contribution. However, some may argue that this approach violates equitable fairness (Li et al.,,, (020c) among clients. Interestingly, our stochastic reference-mode recovery with tunable probability q ensures equitable fairness in the long run (i.c., as the number of FL iterations approaches infinity). By adjusting the value of q, balance can be struck between collaborative fairness and equitable fairness. Smaller q values prioritize collaborative fairness, while larger values emphasize equitable fairness. Therefore, guidelines should be established to assist the server and clients in collaboratively determining the algorithm's 's hyperparameters, thereby minimizing potential ethical concerns.
Thirdly, reward distribution within the broader spectrum of collaborative learning may require careful ethical considerations. In this paper, we give out training-time model rewards due to the difficulties of timeliness and feasibility (discussed in Section associated with post-training monetary rewards. We believe future investigations could potentially open up new opportunities if we can incorporate both monetary and non-monetary (e.g., model) rewards when considering client incentives in FL training. However, the challenge lies in determining the denomination between monetary incentives and model incentives both technically and ethically. Nguyenn et (022) offer some insights on dealing with the following scenario: How can one rectify a situation where a client's 's contribution does not correspond good model reward, but the client desires to obtain better model by offering additional monetary payments? Addressing these interesting questions could bring us more holistic view of incentivization and collaboration in learning. At the same time, apart from the technical perspective, more in in-depth ethical studies may be necessary to regulate such denominations between monetary and non-monetary rewards for client incentivization in practice.
B PROOFS
B. PROOF OF PROPOSITION 1
Proposition 1. h satisfies dh(p:.P.)) > 0 and Mpp.p-pppp--l))) > 0, then a mechanism [M,(p)] dp. Ohlp. :)
h(p, p-:)) incentivizes client contribute more than that in the standard FL mechanism.
13

---

Published as a conference paper at ICLR 2024
Proof. The utility of client with p. contribution can be written
24 [Mr(p)]; c.p
v(ps, hipp. P-i)) caPi
Thus, taking the derivative with respect to Pt. we have
dv dp:
dv ah(p,. p-t)
dh(pi, -i
u =
0p, dp:
dpi
(2)
dv +
dv
dh(p,, p-i) Ci
0p. Oh(p,
dpi
In the standard FL mechanism, have h(p,, p-i) h(p-i) where h(p-;) is independent of pi.
This implies di(p..--.) O. The derivative of the utility is
dpc
(FL) Ov Op:
G.
If the following conditions satified: ! we will have u³ u4 To maximize the utility, rational client will contribute pf such that u/ 0. Since u, is in general
Ov ph(p..p-.)
0 and 2
dhip:.p-. dp,
0, according to 2
((FL) for any p:-
concave function and u/ > u, (FL) for any p. with !
ah(pv.p-i) and 2
8y
dh(p..p-s). 0, we have dp.
p Pi (FL) That is, the mechanism with such a h incentivizes client to contribute more than that in the standard FL mechanism.
B.2 PROOF OF PROPOSITION 3
Proposition 3. There exists an undesirable equilibrium the relative reward mechanism (M)(p)] = (pr max, hppp))). Specifically, the equilibrium elicits contributions from all client that sums to what single client would contribute without the federation.
Proof. This is a constructive proof for existence.
We consider N identical clients each with common cost C; c, Vi (I,..,,, Let the rewarding function v be a composition function such that v(p,, P-,) = gff(p,, P-i)) where is continuous non-decreasing concave function and fp, P-:) = p: P-,. Furthermore, we define the aggregate function as h (ppp... p = jjse(N Pj-
= g'("') This Define optimal contribution p" for individual client, such that v'pp", P-s) = because P-, = h(p_,) when there is only an individual client.
Now, if every client contributes p" /N (i.c., p (p" Ip'/N, /N..... ..... .." /ND. have max; Pj
1 for all i
and thus
[Mc(P)]; v(p" /N, h(pp' /N, .......p///TT NN))
N-1
=(ff(""/ /N,
Σ pJ))
p² N + (N 1)
=((p))
In this case, clients reach a bad Nash equilibrium as the total contribution from all the federated clients is the same single client's contribution in the non-federated environment. Here, in the
14

---

Published as a conference paper at ICLR 2024
Nash equilibrium, each client is assumed to know the equilibrium strategies of the other participating clients, and no client can increase one's 's own utility by deviating to other strategies. other words, the mechanism does not incentivize clients contribute more.
C CONNECTION BETWEEN THE MECHANISM AND THE IAFL ALGORITHM
We draw the connections between the IAFL algorithm in Algorithm I and the mechanism in through a simplifying scenario. Consider N homogeneous clients producing updates {g., J that follow population with the same mean μ.. The update A0;; follows the sampling distribution of the mean with Var(A0,,) = / /|al where o; is the population variance. Note that step 4 of Procedure 2 aggregates the contribution of client i, A0r,, with the sampled contributions of other clients. Taking the reciprocal of the variance as the quality of the training- taining-time time model update reward, then
1
1
Pi. Poeil
11)
N
+
min
Var( (ar()),.))
oi
o
which matches the mechanism in T
D PROOF OF THE CONVERGENCE
Th.t: Vi. Recall that the j-th step of F(0)). = where 0 is the optimal solution of F; (0). We define the data bias as r A F E F We set the learning rate for client at FL iteration to common rate
Denote the optimal solution of ((0) by 0" such that F*
Similarly, we denote F Fi (0
stochastic gradient decent at client is 0 0², ne (. (0 El,,) where E/ is the local batch randomly chosen for the SGD step. Note that 0,, Oz, is the model at client i the beginning of FL iteration 1. At the end of each FL iteration, client updates its model to
0 0,, 1t S
ΣΣ
V (
m.rs Sm.t)
I=.
where S i defined in Algorithm the of indices that client can aggregate from in a given FL iteration f. Without loss of generality. we assume that V4 V is an integer. In practice, the ceilling N7 can be used. Note that [S.,l = N.
For simplicity, we denote the update for client in iteration
R4, T1t SS,.e
Σ
Σ
V Fm m, (,,)
MES,,
Since Ris essentially computes the i.i.d. sample mean from the population { m. e N= for each FL iteration we have R[R,,] R, for all i,j
J.V.
{-r Fm (0) NN.
For the analysis in this section, we make the following assumptions on the functions Fi,..., Fx: Assumption (L-smoothness). The loss function F,, is L-smooth, then for all u, Rd 2(F F..(w) S 2(u - v, F (v)) + L ||u -012 Vm E [N]. Assumption 2 (uussroon convexity). The loss functions F1...., convex, then for all u. Rd
......,Fyy FN for all N clients are p-strongly
(u) (u)) > 2(u - v, (u)( + / p - w112 2 Vm E [N]. Assumption (Expected stochastic gradient variance). The variance of stochastic gradients client is bounded,
Fm (0' m sm,)) - V F' (on.))
2m Vm E Vj
We further define $2 = & NN o2 as the average expected stochastic gradient variance among clients.
15

---

Published as a conference paper at ICLR 2024
Assumption 4 (Expected squared norm), The expected squared no-mr the the stochastic gradients uniformly bounded,
E V (0,, sm.t)
) SC', Vm [M], [
D.1 PROOF OF THEOREM
Theorem 1 (Performance bound). With full clients participation and a decreasing learning rate pr(t+a) where a 2 1L(7+1) define B = 22r + 3)Г + 3r + T (a 1) 0-] and Hr = (2 ) then the performance of the client model OrT trained over FL iterations using IAFL is bounded by
Me
B + CT
E [[ - F² S
2/
a ++
T
H N
T+a
where
CT
+ -2
t+a
m,
7e.t
t=1
Proof. Define a decreasing learning rate 1aa for some 3 >
I and a 2 41((+1)
2μ0
From Lemma
D.I
we have the following for any client i after we train for T FL iterations,
E |10 0-1
$ (1 2
E
|10,T-
13
+ 22T + 3)
(3)
N
+ (2 2
1
Σ
||o5 m 01T 1 + n
m=1j=1
From Lemma
D.2,
we have the following for any pair of clients w and v after we train for T FL
iterations.
|2]
T
-2) - 1
E
0 W.T
S
Σ
m
+
(4)
To
1=1
Then.
E - 1
< (1 2 E
- -10
+ 22T + I + -22
(2 2
1
G2
"
1
1
- 2
1
1)10-11002
Vm,t
12.t
j=1
= (1 2 }E
||0AT - 0-]
+ 1/
2LT + 3)T + (2 - 2 G 2
> (j
+
2
N
T
+ (2 - 2
G2
Σ
1
12
1
N
Ym,t
T/,t
m=1
j=1
(=1
< (1 2
||0.T
0<]]]]
+ +
(2LT(2T + 3]] 2 2 72522)
N
T
(1) Ymm,t
T T+a*
+ 12 - (nurr) 33 6²
+ -
N
t
%/.t
m=1 t=1
-1 (1-2TTTTEEE 1100:-000 (1-2w77)1(1000--0
+ ( + Cr)
16

---

Published as a conference paper at ICLR 2024
where for simplicity define shorthands Q
2LT(2T + +)r 2T + + Hr (2
) ? and Cr = Hr Em=1 Σ
T+e Ita
2). Note that Q is constant T,
7
whereas CT is dependent T.
Let A E
0 1-]
We now aim to prove A
ct by induction where
(Q++)))
23pr-1 (a 1)A1}.
When t 1, we have A
a+I by definition. Now assume
A S
Pt for some 1, then from a+!
we have
(Q++))))
A A++ 1
t a
t a
(t+
Ut
28pT -1
(t+ a)² Us
t+a a
t
V
Ut
1
(1+
a)2
(6)
Ut
1
t
(t+
Up
t+a+l
Ut+1
where (a) follows from C. S C1+1 and H, S H1+1.
From the L-smoothness of F.
E [ F* Ar a+T
Specifically, we let B = and train for / = T iterations, then
(8(Q +
Cr) Cr)
UT max
(aa 1)41
23μTT -
8²QQ CT) +
(8)
28μT -1
Q+C
1272 + +
Finally, substituting X
into get
(Q+ 1272
[[F(OLT) S 2( TT)
+ (a (a+1)))))
(9)
Define B = = (a + 1 |10 - 1T] we simplify the inequality to
[[F(O,)) Fa <
(Q+Cr+ (a (at))+22))
2 (a + T)
(10)
L
B B+Cr
21²72
7T
17

---

Published as a conference paper at ICLR 2024
D.2 DEFERRED PROOFS OF LEMMAS
Lemma D.I. Given т S TI[++1] and Assumptions
|10 - 0-1
- (1 T |10 0-13] -011
+ 22T + +3)n
(11)
N
m,t 01,1 9//1"²
+ (2 2pmTe)
E
+ =
N
m==
1=1
Proof. In this proof, define
Σ R1, 11 7/,, mES,,;
Σ
V Fm (0
(12)
To simplify the notation in this proof, we use 0₂, interchangeably with 0! denote the model of client i at FL iteration t without performing any local updates.
We write
0 1¹1
110,, + Ri, - -0- 0-- -Re, + Rs,ell
(13)
||0,. 0" + Re,el² + || R +2 0" Ra,,, Ra, R(g)
Step 1: Bounding the second and third term in
113
Bound the second term in 13 in expectation with respect to En,t and Si.t
Es.E
Rii
Rig
N
R.s.
Σ
V Fm (0) mo Sto,t) V Fm (0) m))))
mES., j=l
N
< 17 TEs
1
Ee
V F' ( (O', Smmee - V (0
(14)
N
mES, j=1
N
< 2_ 2Es
2
N
N
mES,
(b 252
1/2
where (a) and (b) both follow from Assumption
3
The expectation of the third term in 13 is zero. That is.
E 1
0" Rict Ri, Ri,,)] 0
(15)
because [R R.t..
Step 2: Bounding the first term in (13)
We write
0 0¹ + RR,ell ||0,,c 0-112 || 2(0,, 0", R,,)
(16)
We will next bound
|Ra. and 2(0 0r, Rai)) respectively.
18

---

Published as a conference paper at ICLR 2024
Step 2.1: Bounding
|Rae|
From the Assumption|
Tf L-smoothness for Fm. due to Lemma 4 of (Zhou 2018), we have
v FF (Om.))
|| s 2L( (6 - Fmm
(17)
Bounding the second term in the RHS of T6.. we have
R
n
Σ
V Fm (mmm.)
mES,, j=1
S 116 N mES,,
Σ
V O mm)e)
j=1
(18)
S n T ,,,~ mES,, j=l
Σ
V (0 m,n
s 2
Σ
(m (0 (0mm.) FTh)) -
Yi N
m j=1
Step 2.2: Bounding 2(0,, 0- R2,i)
Bounding the last term in the RHS of (16), we rewrite
2(0,,- 0", .R,,)) =
2(0,, =
0", -1 N mES,,
Σ
m (0
2m N
Σ
Σ
0 0r,.. V V (0 (Bm,))
mES;, 1=1
(19)
2n N
0 1mmt Or,0, V ( (mn)))
mES,, j=1
+ 2m R
Σ
Σ
0 0 m.t. V (0 m.t. (0m.)))
N
MES,, f=1
Consider the first term in
19
21
Σ
0 m, O2,, V..... (oh,))
m
1 Ø m.t
Vm (0 ( [']
< 1pp K
+ m7
(20)
N
mES, j=1
Σ
0 m,t
O2.1
12
+ 11
Σ
V Fm (0 (m,)) 1
Ti N
mESL, j=1
Consider the second term in (9).
21 M
Σ
10 G V E (Ohm))
N
m mES, j=1
(21)
2n
Σ
F (m)) - Fm (m
0-110)
2 m.t
MES.A
19

---

Published as a conference paper at ICLR 2024
where (a) follows from Assumption 2
Step 3: Putting the results together
In the previous step, we want to bound (6).. Applying (8
20 and 21
we have
00,, 0¹ + Ri,ell |
110 0 12 Ri..11 2(fr, 0-, Ra,t)
1 Σ
|10. 1²1 + 2111 27
Σ (Fm(Omm.) m,,)) - Pmm)
J
V Fm @ ( }
0 m.
03.1
+ m
N
M N
mES,, j=1
mES j=1
+ 2m (t)
(0() - F' (0 m,
11
0
0- 0-11"
2
m,
m j=l
@
10
0"
peltl
0
0011
0 m,t 04.1/
N mES,.e
mES
2T + 1)mk
Σ
Fm (m (O
FMh
2m
Fma(0*) - Fm (0 ()))))
K
N
mES,, j=1
mES, j=1
Ac
S |10 - 1-1 2 - 2pm 7,, N
0 - -0112
mES.,t j=1
(1 2pmme) 1
0 0m,t
05.1 1|2 + Ae
N.N mES.
O O1. 2 A.
(1 1-22m)TT 01, 1²1 + (1 2pmTIe) N
Σ
(22)
mES, j=1
where (a) follows from L-smoothness in 17) and rearranging and (b) follows from l 0-1|2 5
2 o 0.. + +2 1
We next bound A, in expectation. Define W, = 21,(1 - 2L(T + 1)m).. Note that we define n such that 17 I - Hence, W, 0.
20

---

Published as a conference paper at ICLR 2024
From the definition of A above, we have
A 2T(T + 1)ni V,,N-
1
E
Σ
(0 F
meS,, j=l
+ 27 N4,N
Σ
F'm
Fmm + Pm
F'm (m((m.)))
meS, j=1
=-2nc(1 - 2T(r + 1)m)
Σ Σ mES.,
(mm() Fm))
(23)
+ 24h N N
(mm(0)) Fm)
mESt,1 j=1
= - K Σ
Fm (6 m.)) - FF) WeT
(F
VeN mESL.
mESL.J==
+ 2117 N mESi.
(Fn F
Therefore,
[AJ = E
W; V,,N
Σ
{(Fm -F+) +
mESI, j=l
WiT N
E
Σ MES..
(F* - Fmn)
+ 211T 11,1 N
Σ mES,,
(Fm - FFi)
(24)
W V
(m - FF)) + ALT(T + 11),TT
mES,,1 j=1
where (a) follows from EE
V.,N Emes,, (F' =
1 N
>ma=n (F+ F = T
Note that in the equation above, we have
1
Σ
(F F²)
N
N
mES,,1
1=1
Σ
(Fm. m,,) - Fm (OLL)) +
Σ
Fm (O..)) F*)
N
N
mES., J=1
mES.. j=l
Σ
V (O..). o - +
1
Σ
Σ
(O..) F*)
n N
NN
mES j=l
mES,,
Σ
The V (0,0))
@i m.a Oz,1
27
N
7/
MES,, f=1
Σ
(0..) - F*)
mES,
W8
Σ
(LL(Fm(O..))) -F +
0 0 -
0,,
27
2m
mES, 1=1
Σ Σ (O,,) - -F*)
(25)
f=1
21

---

Published as a conference paper at ICLR 2024
where (a) follows from Assumption 2 and (b) follows from 17 Therefore,
Wi N
Σ
Fm (0mm,)) -
m j=1
S Wt N
Σ
(0..)) - -Fm) +
1
@ m.t 02,1
2
2ne
J=
We -W
Σ
(0.,e) -F
meS,, j=1
(26)
Wi(n 1) M mES, j=1
(0tt
-WoLL
E V meS,,1
(F'
Fm) +
Wt
E
0 m,t 64,1
2T V,,N.
mESt,
S WilL
F Fm
Σ
m. 0i,1
N
m j=1
mES,, j=1
where (a) follows from n S 0 and N,N Emes.. Ej=( (Fm((..)))) - -F*) 2 0. and also from
the fact that 7, S W < 2//² given that 7)2 S TL[T+I)
Then, substituting
26 into 24
E [A. S WT
Σ mES,
(F* F
V
12
+ E
0 m. Oit
+ 4T + 1)
(27)
Ni.N mES., J=1
(
@ 0mnt 04.1 ?
2L 33] +E
K mES.. j=1
where (a) again follows from N..N Emes,,
(F* - P%t = Em (F+
Fr r.
Finally, taking expectation of 22 and then substituting
27 have
E 01, 0' + +R..el?)
(1 - BB |10,.- 1100,,--111 0-113]
+ (1 2pm E
0 0:,1
No mES,, j=l
/ 0n.1 |
+ 22T + 3)m21 EE
(28)
K.NN
mESi, 1=1
= (1- - 1B
[100,.
+ (2T +37221
1
N
0 - 02.1 1']
+ (2 2pm N
E
j=1
Step 4: Concluding the proof
22

---

Published as a conference paper at ICLR 2024
Lastly, take expectation of 13 and substitute
28
14 13
0 10,1+ ---1- 011
||0.,t 0² Rs..el IF
Ru, Ri,e
x (1 T) |10 - -0113]
+ 22T + +3)n,
(29)
(2 2pmm)
Σ M @
B
0..ll²
+ +
Note that we have two sources of uncertainties above. They are 1) the random selection of updates from S in Ri and 2) the stochastic gradients c/ Sm... We have taken expectation with respect to both of them above.
Lemma D.2. Given Assumption 4
E
o 0b.113
S ST
G
2
1
+
2
+
1
(30)
Tw
Yo,e
Proof. Using the Cauchy-Schwee inequality, we first bound
E
0 ]1]
E
Ruw,
)
E
Rie,=
R
==1
1
E
1/2
VF (0) m, 2m,))
Fm O
m. ed S
Suu,
|Su
mES j=l
mES..e 1=1
1 Yo,
Σ
Σ
VF
(0 5m,25 et.
No,
2=1
mES j=1 E...
Σ
Σ
F (0
el 2
Σ
Σ
Fm el
Fm m, Smn,z)
Yw
N
No
mES... 1=1
mES.. j=1
AmgS...
AmpSw..
1/
N
+ Y/m. (1 %
Nu
Vo
N
1=1
+76. (1
E
V Fm (0 m. (/
Vo
N
1
+
-
Σ
E
V
Fm 0
m, sm,2)
N
m=1
23

---

Published as a conference paper at ICLR 2024
I T G2
Σ
1/
(31)
Tw,z
Ye
where (a) follows from the independent nature of R at different 2, Vi and E. Rur, R
(b) follows from the algorithm such that |S = 7t. (N- - +1+ +1 = _ for all E [M, (c) follows
from expected number of party indices in Sw,es w. S and (d) follows from Assumption Note that here we assume 7 N is a positive integer w.l.o.g.
Then, bound the model that has performed j local gradient steps.
E
0
02.0
(32)
10,
j
27
E
01
V Fi
( w Su,,
0:
(33)
w.t
b=1
1-1
=
E
[10] u.t
+
V
( w.t: Swi,)
(34)
b=1
+
E
2(01 10,t
0%
V Fi (0 wi Swote)
(35)
@
E
0
+E
F ( m Swnt))
(36)
6ml
j-1
E
0
nī 1) Σ 00,r1""]
E [VFF
(37)
b=1
(h)
E
10 10,
0u.l1"]
1 1)
(38)
(0)
G2
1
1
v G2 To.z
1-2
(39)
ww
where (a) follows from E
11, = E.-1
Rww, Rw,z = O, (b) follows from Assump-
tion (c) follows from mit
D.3 PROOF OF THEOREM 2
Theorem 2 (Improved bound). Let = Eta and B, Hr be defined in Theorem I With a stochastic
8
recovery rate of g, the performance of client model 0gT trained over T FL iterations is bounded by
T
T
T
E (((.))))) - <
II
110: - 10 +
(Q + D + E.)
II 1=++
(1 - 2
2
HT
N
T
)
2
1
1 1-2) (1 T-+1
where
DT
N
t+a
Fmm
Voot.
T
T+a) 2
(1 (
- 11t122) (1 10-22111))) TT-9)
1
Er = HT
tta
Thet,
Proof. Let S q < be the probability of stochastic recovery. During stochastic recovery, client recovers reference model. We denote Oref as the reference model parameter and Rief, as the reward for the reference model at iteration i, which determined by the induced reference reward rate T Let h be the number of iterations the client has not synchronized for.
24

---

Published as a conference paper at ICLR 2024
With the introduction of the reference model, the difference ||0m, -s.ell between two models at an iteration & can be broken down into 10mm reff lI2 and |0ref,t 0 11 which can be better bounded using the stochastic recovery rate 0 S -
We now derive new bound for the expected difference between a client model w,r and the reference model TT at iteration T,
E
0 W.T
T
Σ
(11
Σ
Ru,,= Reof.z)
h=1
1=T+1- h
T
T
9)ah
E [| [R., 111
h=1
L
T
(1
9)*h
[Ru R1d +...+
Σ
(1 4)th E |l - Reor,
-=T
T
Σ
[1 4)
E'
[llRw,T+1-1
-1e1--+1-1112]
97 02
2
1/+---1
((1-9) - 9)th
Net.r+1-1
1
118
2
2 1- ((1 - 44)² - (1 -11-9)741
No,T+111
Noo.T++111
+
1
2
the ((1 -2) ()-'t - (1 - 4)
Ywrt
Vrot.
1=1
$ G²
2 n² -T
(40)
Tee
where (a) follows from the independent nature of Ra, 's at different t. Vi and E [R - R =
(b) follows from 31p. (c) follows from the closed form of the summation D1 9)
(1-w)² -1--0)))) T+ and (d) follows from replacing with t such that t T + +1-1. I.
9
From Lemma
D.I
we have
E
10 1-1
< (1 - 1-2UATTT
-110,T-0-1' 0-
+ +2LT(2r + + +
N
1
|z M.T -0,I 27
+ (2 2pm)
E
N
m=1
1=1
(1 2E
|10
1²
+ +22 + 33 + 7
(41)
N
(2 2pmr)
1
|100 1000 0/.1121 1パ 1)962)
N
m=
2 (1 2 E
|| - 0" 1-] + 2LT + 3) + 2 G22 + 2552
N
ohrr- 0 olor,z [1]] (2 - 24177 TE -
+ (2 2 T
E
m=1
where (a) follows from (38) and (b) follows from [0 E [o:5
25

---

Published as a conference paper at ICLR 2024
Then, substitute (40).
-0"133]
$ (1 - 2/
|10.T - 00 (2T + 7
G² + T
+ 12 -4mm)) G²
1
T+
(Nintt
-2 2 -2 (1 (1-9)
N
t+a
Veet
(42)
m=1 t=
+ 12 2TTMT)) G2
T +
1 +
1
-2 (1 (T-)
t t+a a
Ti
Ted,t
|1 - 0-] + + + DT +T)).
(1 -1-221 2
Note that in the above, we have defined Q = 22r - 2-25, HT = (2- 2
Theorem I and we further define
HT N
T a
DT
+
2 (1 9) (1- T-1-1
t+a
7/me
Trottt
m=1
t=1
(43)
2/1
ET HT
T+
1
+
-2 2) (1 (1-9)
tta
Tie
Vrotee
From the L-smoothness F,
E [F(O,)))] - F
$ B |10,0- 1-12]
(44)
L
L
$
II (1 - 110: - 0-112++ 1101-0012+ 1=1
Σ
(Q + D1 Fa) II (1 2(mET)
2 t=1
1=t+1
D.4 PROOF OF PROPOSITION 2
Definition D.1. We write
f(x) o(g())
as x
for all positive real number M, there exist real number zu such that
[f(z)) < Mg(x)
Vx 2
Or equivalently,
lim f(x)
0.
g(x)
Definition D.2. We write
fxx) = Og(())
as -
if there exists positive real numbers M and such that for all defined with 0 < fx al < 6,
[f(x) < Mg(x)
Vx 2 3p
Or equivalently,
lim [f(z))
<0.
x0000 g(z)
Proposition 2 (Asymptotic convergence). If Th.s
=o ( c2
for all i [N] and o
logt
logg))
we achieve
lim E (((0,))) F 0. 7-000
26

---

Published as a conference paper at ICLR 2024
Proof. Firstly, we define new functions (t(t) - for all i [N] such that t Z Define %,
non-decreasing function ā:(() such that @;(() 2 a:(t) for all specifically,
a (t) = max a, (z) ze[t]
(45)
Note that (t) 0 6² and (t)r(t)
1² logt
still hold.
logt
Consider the term Ef in (42)
T T+a
2
E7 = Hr E
2 (1-9)2-143
+
1+a
T1.t
Tret,t
T "T+a'
2
S G²
(a:(1) + drrt(())
(1 (1-1)
1+ a
T-1
( T+a
x 2 G²
Σ
(a+(T - 1) + arof -1))
(T-++a (1-
(46)
(0) G2
T-1
T T- ) (1-
T T+a
Σ
(T) + aref (T))
1=0
T-1
< 22²' and
Σ
11+1+0))80 -//
ST
where (a) follows from t= T - (b) follows from the definition of (t) and the non-decreasing nature of it.
Notice in (46). Sr is non-decreasing in T, we can then use the limit of Sr to bound it. The limit has a closed form,
(g a)(- 20g + + 9-2) 2)
lim Sr T4000
(47)
d²
Therefore, bound the term Ey,
Er S M (T)
(48)
where M is a constant
M 27 (g ( 1)(-229²
22q + q 2)
(49)
q3
and
A (T) o,(T) + azot
(50)
Similarly, we bound the term Dr in 42
N
1
Dr M
(am (T') + āret (T))
N
m=1
(51)
M
A Am.ro (T).
N
Notice that we have (T) =
2 log T
for all i E [N].
27

---

Published as a conference paper at ICLR 2024
Now, we define A, = E |0.,. 0-1]] Yi 1=:1= + rer + M NNNNN Em= Amrre(()) and let
From 42
we can write
2pm
A+41 S (1- (1-2umeE)A) A + (Q + D. + B,)
1
Y;
A+t1 $
1 +
D +
(a + t)²
(52)
Y2
(a+t)Aut S (a 1)4
+
a a+t
Let Ô, (a + 1)4, where A ad1, we have
Y
Å S A
(53)
a+t
Therefore,
T-1
ÅT S adi + Yr
(54)
1=1 a+l
due to the non-decreasing nature of (t) with t. Now,
Å
lim AT = lim T-x
T
T + a -
a + (Q + M rre
+ Em=1 Am (T))
IT-1
lim T-000
N
at!
T
(55)
Aireet (T) + Em=
Amrre(
21= a+tl
lim
lim
T-000
T
T-000
T
Aireet (T) + Em Am.ref(T
Et=1 atl
lim
lim
T-x0
72
T-000
log T
log T
Note that (T) o 1
Vi [N]. hence by definition
log
A (T) + 1/ Σmm ro 0.
lim T-000
(56)
log T
Also, since ΣT a-1
O(log T),
ΣT ati Z
lim
(57)
T-000
log T
where Z is a constant.
Therefore, substituting that AT 2 O,
56) and
57
into
55
to obtain limm- AT 5 0, and further considering
lim T-
AT = 0.
(58)
From the L-smoothness of F, we conclude that
lim E [[((0.))] - F* < lim Ar = 0. T4000
(59)
7 2
28

---

Published as a conference paper at ICLR 2024
E ADDITIONAL EXPERIMENTS
E DATASETS AND IMPLEMENTATION DETAILS
We provide a comprehensive comparison between our method and the existing baselines using widely-used benchmark datasets, following heterogeneous data partitioning benchmark (Li et al. 2022). All experiments were carried out on server with Intel(R) Keon(R)@2.70GHH) processors and 1.5TB RAM. We utilized one Tesla V100 GPU for the experiments.
Dataset preprocessing, For all vision datasets, we standardized the pixel values of the images. We additionally applied data augmentation techniques of random cropping and random horizontal flipping to the CIFAR-10 and CIFAR- 100 datasets. For natural language datasets, we performed standard tokenization and vocabulary building. We simulated the federated environment with 50 clients for all experiments. We employed five different heterogeneous partitioning strategies, namely; 1) Distribution- label distribution skew, 2) quantity- label distribution skew, 3) noise-based feature distribution skew, 4) quantity skew and 5) homogeneous partition. More detailed information on the implementation of these partitioning strategies can be found in Section 6
FL models. To ensure the reproducibility of the experiments carried out in this paper, used common and well-established model architectures. Specifically, we utilized the following model architectures:
1. Convolutional neural networks (CNN) following that of (Li et al. 2022 The CNN consists of convolutional layers followed by 3 fully connected layers.
2. R (He et al. 2016). We replaced the batch normalization layers in ResNet18 with group normalization ensure stable training with highly heterogeneous clients (Wu & He
2018 Hsieh et al. 2020; Wang et al., 2022). The number of groups used for the four layers of ResNet18 were 4, 16 and 32, respectively.
3. Long short-term memory networks (LSTM). The network comprises an embedding layer of a dimension 300, an LSTM layer and 3 fully connected layers.
In Section 6.1
Appendix E.3 and Appendix E.4 we conducted fair evaluations using architectures and In Section 6.2 we utilized the more complex architecture 2 to demonstrate the ability of IAFL to achieve high accuracies on the challenging CIFAR-100 dataset. Architecture 2 was also employed in experiments conducted in Section 6.3 and Appendix E.5
Appendix E.2
Hyperparameters and options for training. We used default initial learning rate of nju 0.001, unless otherwise specified. We used an exponential learning rate decay with a rate of 0.977, causing the learning rate decrease by 10 folds in 100 iterations. For MNIST, we used 17o- 0.01. For CIFAR-100 with ResNet18, we used 7/u = 0.005 with a decay rate of 0.988. The total number of FL training iterations used was 50 for MNIST, FMNIST, SVHN and 100 for CIFAR-IO, CIFAR-IO0 and SST. Each FL iteration involved a client training for local epoch. For all classification tasks, we employed the cross-entropy loss.
FedAvg finetune. Standard FedAvg returns the same model to all clients in each FL iteration. In this case, the correlation metric p in Section undefined and uncomputable. To address this and create a personalized model for each client, we consider a simple modification that allows clients to train for an additional epoch at the end of the FL algorithm. Therefore, this variation, named FedAvg finetune, serves as straightforward FL personalization baseline.
LG-FedAvg (Liang et al., 2020). Local global federated averaging (LG-FedAvg) achieves personal- ized models by personalizing the layers or structures of the shared model, Specifically, each client learns a personalized local feature extractor and the local representations of client data are federated to train shared global layers. To achieve this, the model updates averaged by the server are exclusively used to update the shared global layers. In our experiments, we specify the last fully connected layers of the model architecture the shared global layers.
CGSV (u et al. 2021). Cosine gradient Shapley value (CGSV) evaluates client contributions based on the cosine similarity between client's gradients and the average of all clients' gradients. During the rewarding phase (i.e., when the server sends respective updates), CGSV masks out (i.e., zeroes out) portions of the gradient update aggregate according the client contributions. This masking is
29

---

Published as a conference paper at ICLR 2024
Table Comparison of Isss among IAFL and baselines using differents datasets and partitions.
Each value reports the mean and standard error of 10 independent evaluations and partition seedings.
Calegory
Dataset
Partitioning
FedAvg Finetune
LG-FedAvg
CGSV
Rank
IAFL
(ir(U.5)
0.97+0.01
0.93+00.22
1.00+-0.00
0.80+0.02
1.00--0,00
MNIST
#C =3
0.89=0.01
0,90:10.02
1.00::0.00
0.68:-0.02
1.00:10.00
Dir(0.5)
1.00=0.00
0,98:+0.01
1.00::0.00
0.85+0001
1.00=0..00
FMNIST
#C
0.92++0.01
0,95+00.01
1.00+-0.00
0.81+0002
1.00+00.00
Dir(0.5)
1.00:0.00
1.00=0.000
1.00::0.00
0.95=00011
1.00=0.000
Distribution
Label
SVHN
=C
1.00=0.00
1.00+-0.00
1.00+00.00
0.94+0.01
1.00=0..00
Skew
CIFAR-10
Dir(0.5)
0.99=0.01
1.001:0.00
1.00::0.00
0.92:10.01
1.00=0.00
#C=3
0.91=00011
L00::0000
1000::0.00
0.85=0.02
1.00=00.00
Dir(0.5)
1,00
100010.000
1.00:10.00
0.00
1.00
CIFAR-100
#C =0=00 30
1.00=0.00
1000:0.000
1.00:0.000
0.92=00.01
1.00
(ir(0.5) #C-=3
0.00:0.00
0,00:10.00
0.99
0.741:0.01
1.00
SST
1.0000,00
0.00110.00
1.0010.000
0.78+0.02
1.00:0.00
MNIST
0.66::002
0.24:10.01
100:10.00
0.76:10.04
1.00:0.000
Feature
FMNIST
1,00=0.00
0.92-10.02
1.00::0.00
0.96:00.01
1.00:0.00
Distribution
SVHN
N(01.)
1.00
1.00::0.00
1.00:10.00
0.97
1.00:0.000
Skew
CIFAR-10
1.00:0.00
1.001:0.00
1.00:0.000
1.00
1.00::0000
CIFAR-10 100
1.00 0,00
1. 0.00
1.00
1.00 0.00
1.00++0.00
MNIST
0.96::0:1
0.56.10.02
1.001:0.00
0.92110.2
1.00:00.00
FMNIST
1.00 1.00=0.00
0.74++0.02
1.00++0.00
0.99
1.00 1.00+0.00
Quantity
SVHN
Dir(0.5)
1.00:
10001:0.00
1.00::0.00
0.00
1.00:0.000
Skew
CIFAR-10
0.96
0.98:-0.00
0.85++0.01
0.90+0.02
0.98=00.01
CIFAR-100
1.00:00.00
1.00:-0.00
0,99:+0.00
0.99
1.00
SST
1.00=0.00
0,00=10.00
1.00::0.00
0.77=00.22
1.00::0.00
MNIST
0.81
0,41++0.03
1.00++0.00
0.76+00.04
1.00++0.00
FMNIST
1.00=0.00
0,98:10.01
1.00::0.00
1.00:0.000
1.00=:0.00
Homogeneous
SVHN
1.00 0.00
1.00=10.000
1.00++0.00
1.00
1.00=+0.00
IID
Partition
CIFAR-10 10
1.00=0,00
1.00::0.00
1.00::0.00
1.00=0.000
1.00:0.000
CIFAR-100
1.00=0.00
1.00=:0.00
1.00::0.00
1.00=0.00
1.00
SST
1.00:0.00
0,00:10.00
1.00:10.00
0.67=00.2
1.00
performed layer- where the contribution determines the proportion of parameter values being masked out in each model layer's 's gradient updates. For our experiments, utilized the original implementation of Xu et al. (202T).
Rank (Kong et al. 2022). Rank rewards clients in each iteration based the accuracy of their respective models on a validation dataset. The method ranks the clients by their validation accuracies before rewarding them. Client
aggregate model updates from other clients that have lower validation accuracy than that of client i. Since no code has been released for this work, we followed the original paper for our own implementation.
IAFL. The implementation follows that of Algorithm 1 For baseline comparisons in Section we set the sharing parameter ξ and stochastic recovery probability q 0. Subsequently, we investigated the effects of these hyperparameters in Section 6.2 In all experiments except Section 6.3 we used the standalone accuracies of clients as their contributions Pi,t, which remain fixed across iterations. In Section 6.3 we instead used the participation rates of clients as the contribution measure.
E.2 INCENTIVIZED PARTICIPATION RATE USING TEST LOSS
We expect IAFL to satisfy individual rationality (IR) if the mechanism strictly follows (M,(
(P:. (min (Pi/Peen: 1}}² h(p-.) and the rewarding function v(p,, P-;) is continuous, non- decreasing, concave and exchangeable with respect to both arguments. However, the assumptions on are often violated, as shown by the results of Table iin Section 6. Here we show that using the test loss as the rewarding function v better fulfills the assumptions needed for v. The comparison of |Pss (i.e.. using the test loss) among IAFL and baselines is shown in Table 4 Our IAFL has excellent incentivization performance as it achieves the highest |ps in all settings and perfect IR in all but one setting.
30

---

Published as a conference paper at ICLR 2024
Table The average (highest) accuracies achieved by the client models. The values show the top-1 test accuracy measured in percentage (i.e., %). Each value reports the mean of 10 independent
evaluations and partition seedings.
FedAvg
Category
Dataset
Partitioning
Finetume
LG-FedAvg
CGSV
Rank
IAFL
(ir(0.3)
79 (95)
86 (94)
89 (93)
71 (94)
90 (96)
MNIST
#C
32 (46)
47 (63)
(42)
(66)
(96)
FMNIST
Dir(0.5)
60 (77)
64 (75)
71 (73)
62 (80)
74(83)
#C=3
30 (46)
35 (46)
47 (54)
32 (47)
(78)
Dir(0.5)
57
(77)
59 (68)
56 (75)
(79)
Distribution
Label
SVHN
#C==3
26 (41)
35 (52)
(04)
25 (41)
38 (69)
CIFAR-10
Dir(0.5)
28 (39)
30 (39)
(30)
(40)
(45)
#C =3
21 (24)
22 (26)
16
22 (25)
(36)
CIFAR-100
(0,)
8(11)
11313)
6(6)
(0
(17)
#C =0
(
(
(
(9)
913)
(1r(0.5)
23 (33)
23 (30)
23 (29)
24 (31)
26 (34)
SST
#C=
29
25 (30)
24
(37)
MNIST
92 (96)
95 (97)
96 (96)
91 (96)
95 (96)
Feature
FMNIST
79 (82)
(69)
(75)
79 (83)
84 (84)
Distribution
SVHN
N)(0.))
83 (85)
79 (81)
83 (83)
#2 (85)
(86)
CIFAR-10
52 (54)
49 (51)
42 (42)
51 (54)
(56)
CIFAR-100
17 (18)
16
(
(18)
(20)
MNIST
95 (98)
93 (97)
96 (96)
97 (97)
FMNIST
82 (85)
76 (83)
75 (76)
75 (83)
85 (86)
Quantity
SVHN
(ir(0.3)
84
77
79 (84)
(86)
Skew
CIFAR-10
53 (55)
46 (57)
41 (44)
37 (50)
52 (56)
CIFAR-100
18 (20)
15 (20)
(9)
(15)
15 (20)
SST
(38)
25 (29)
33 (35)
29 (35)
37 (38)
MNIST
93 (96)
94 (96)
96 (96)
91 (96)
95 (96)
FMNIST
79 (82)
78 (80)
75 (75)
(83)
(84)
Homogeneous
SVHN
HID
84 (85)
(83)
(83)
83 (85)
86 (86)
Partition
CIFAR-10
53 (55)
$1 (53)
(43)
52 (54)
(56)
CIFAR 1O0
17 (18)
(18)
(
(68)
(20)
SST
36 (38)
25 (28)
35 (36)
30 (35)
37 (38)
E.3 AVERAGE AND HIGHEST TEST ACCURACY
is important to achieve high overall performance for client models as obtaining good models serves strong motivation for clients to actively participate in the federated learning process. To assess the effectiveness of IAFL and baseline methods in this regard, we compare the average and highest client model test accuracies. As presented in Table our IAFL consistently outperforms the other baselines in almost all settings. These results indicate that IAFL successfully incentivizes clients to actively contribute and enables them benefit from the collaborative process. The higher highest accuracies achieved by IAFL further demonstrated its ability to effectively leverage the decentralized data of clients to achieve superior predictive performance. We further note that the low accuracies obtained for CIFAR-100 can be attributed to the CNN model architecture used in this experiment. Further results in Section 6.2 show that IAFL achieves competitive accuracies on CIFAR-106 using a more complex ResNet18 88 model.
E.4 AVERAGE INCREASE IN ACCURACIES
Following (Pillutla et al. 2022). we compare the average increase in client model performance measured by test accuracy. Table 6 demonstrates that IAFL generally yields the most significant improvements in test accuracies across all clients. Intuitively speaking, such significant increases in test accuracies before and after the adoption of federated collaboration via IAFL serve as strong incentives for clients to actively participate and use the IAFL algorithm. These findings further complement the earlier experiments on IPR and IPR which only provided a percentage for binary outcomes (i.e., whether client model improved after collaboration not). Through this additional experiment, we have clearly shown the extent of client model improvements on the individual standalone models that IAFL brings.
31

---

Published as a conference paper at ICLR 2024
Table 6: Average accuracy increase clients. The unit for this table is %6 and report the mean of 10 independent evaluations.
FedAvg Finetune
Category
Dataset
Partitioning
I.-FeedAvg
CGSV
Rank
IAFI.
Dir(0.5)
8.6=0.55
15.020.7
18.240.6
0.944.5
19.1=0.77
#C =
2.7.0..5
17.210.9
34.01124
84:0.33
63.2:0.4
FMNIST
Dir(0.5)
3.0=0.5
7.240.3
14.240.5
5.5=0.4
17,5=0.4
19=0.3
6.8+0.4
18.3+15
35-004
42.7=1.1
Dir(0.5)
9.2++0.5
2..5+-0.6
10.3+0.77
7.8+0.6
18.6+00.5
Label
Distribution
SVHN
#C
7,9+0.5
3,0428
-12-00
11.1-0.9
Skew
CIFAR-10
Dir(0.5)
-1.7+0.9
0,140.9
5.7+0099
-1.0+100
2.5+0.9
2.010.1
Dir(b.5)
40220011
2,8:033
2.660011
10010.1
0.5:002
CIFAR-100
#C
Dir(0.5)
-0.0:0.3
0.340.0
00020033
111:0.1
0.3
SST
4.6=0.2
0,240.0
-1.020.4
2.0=0.2
5.1=0.3
MNIST
-1.900.5
1.0+0.5
2.2+0.4
-3.3+0.6
1.400.4
Feature
FMNIST
2.640.4
Distribution
SVIN
N(O..)
10.810.3
6.8.1.44
10.7.10,5
9.1.0.5
13.1
Skew
CIAAR 100
8.6.0.22
7.310..2
0.1.10.2
6.1.0.1
10.2.0.2
10.1=088
7,740.5
1084+0.6
633-04
11,3-066
FMNIST
10.6+0.6
5.240.4
4.1+0.66
3.740.4
13.5
Quantity
Dir(0.5)
26.9-1.0
19.34088
21.6+099
29-1.0
27.1=0.9
Skew
CIFAR 10
15.8 0.3
8.740.3
4.1+0.33
-.0000.4
15.6+003
CIFAR-100
SST
10.7+00.1
0,24-.2
8.6-0.22
4.2+0.2
11.8
MNIST
-122004
0.5+0.4
2.3+0.4
-2.900.5
1,=04
FMNIST
0.3+0.22
-0.7+0.1
-3.6+0.2
0.9+0.2
5.2-0.2
Homogencous
SVHN
10.9=0.5
9.240.5
10.2:0.4
10.2+0.5
13.3=0.3
Partition
CIFAR-10
9.1=-033
7.4+0.4
-13300
7,8-0.5
11.400.4
7.240.2
SST
10.3:002
-01110.2
9.6.10.3
4.410.2
11.6:02
E.5 CHANGING THE REFERENCE MODEL
IAFL is flexible with the reference model definition, long the reference model at the server is also updated using portion of the client model updates in each FL iteration, similar to any other federated client. The reference model, of course, does not contribute any learning resources (e.g.. data). The proportion of client model updates used by the reference model is determined by the user-defined custom induced reference reward rate Yee,e-
the induced reference reward rate %ee [axie[[] V In other words, the induced reference reward rate is equal to the highest induced reward rate among all clients in given iteration In this section, explore the possibility of changing the reference model to a median reward, i.c. Koef, = mediangeeN)? Intuitively, the clients are now stochastically recovered with "roughly median" model among all clients in any given iteration. The results are shown in Figure and should be viewed in comparison to Figure where the highest induced reference reward rates are used update the reference models. Overall, the incentivization performances are comparable under the two reference model definitions. We observe that lower
In the experiments of Section 6.2
0=0.5, q=0
k=0.5, q=0.005
k=0.5, q=0.01
0.6
0.6
0.6
Test accuracy
p 0.88
0.59
0.57
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
250
500
750
1000
500
750
1000
250
500
750
1000
FL iterations
FL iterations
FL iterations
V, 1.00 V/2
0.82 V/3
0.60
0.44
0.24
0.09
Figure 4: Effects of the stochastic recovery rate q with a fixed sharing coefficient and reference model trained with median induced reward rates. The dataset is CIFAR- 100 with quantity skew and 50 clients. The figures should be viewed in comparison to Figure
32

---

Published as a conference paper at ICLR 2024
CIFAR-16n, Quaniiy Skew. ResNei18, 0.
CIFAR-100 Duartity Skew, ResNet1B, 6- 0.5, 0.01
CIFRR-1.. Quantity Skew. CNN. K- D. Q=0
OFAR-10, Label Distribution Skew.
CNN. -
Valication accurwey
0.6
0.5
0.4
0.4-
0.2
0.2
90
6-6.11
0.0
Foides
0.0
Fadlen
Poaden
0.1
250
500
750
1000
0
250
500
750
1000
25
50 FL. iterations
100
0
23
50
75
100
FL.
ilittaations
iterations
iterations
Figure 5: Comparing IAFL. and FedAvg for the speed of convergence. Generally, clients with different levels of contribution induce different reward rates y and result in different speeds for convergence. Notably, the stochastic reference model recovery is vital to the convergence to the global optimum.
induced reference reward rates Vret. may hinder convergence to the global optimum and affect the overall average accuracy. However, lower Yrgf. values have the advantage of better incentivizing iop-contributors because it becomes more diffieult for the lower-contributing clients to obtain the geghest-performing models within a limited number of iterations. Therefore, the choice of the reference model definition becomes an important hyperparameter of IAFL, as it determines the extent of sharing and collaboration among clients. In practical settings where clients are more altruistic in their contributions (e.g., collaboration among non-profit organizations or government agencies), having a high Ver, value is recommended.
E.6 EMPIRICAL CONVERGENCE
In this section, we investigate the effect of IAFL on the empirical convergence speed of different clients contributing different levels. Figure 3 illustrates the empirical convergence curves of selected representative clients. Based on Figure a), when q = 0 (i.c., the stochastic reference model recovery deactivated), even the client with the highest induced reward rate 7 experiences slowed convergence, eventually to a suboptimal model. Therefore, the proposed stochastic reference model recovery strategy is essential to the convergence to the global optimum. Upon the activation of the stochastic recovery at 0.01, as shown in Figure b).), we observe that the convergence rates of client models trained using IAFL are comparable to FedAvg. In Figure (5c) and (d), observe similar behavior to that in Figure 5|a) using different datasets and data partitions: The empirical convergence is slower than FedAvg as expected when stochastic recovery is deactivated.
E.7 PRACTICAL TRADE-OFF BETWEEN PERFORMANCE AND INCENTIVIZATION
discuss the controllable hyperparameters of the IAFL algorithm and their effects on the practical trade-off between model performance and our goal of client incentivization. Generally, larger values of rs, q and setting Y closer max;e[N] 7h, favor overall client model performances (at the same time promoting equality among clients) while trading-off client incentivization (i.e., compromising collaborative fairness and distributing less distinctive client models). In this paper, we have presented recommended values for casy usage that strike good balance between these goals. The following set of values
In Section 6.2.
0.5
q 0..1
Nee. maX 7h,
generally worked well in our experiments. Consequently, we recommend using them as the default configuration.
If practitioners wish to achieve a different degree of trade-off with our IAFL framework, they could calibrate these hyperparameters to favor either client incentivization model performance, from different perspectives depending on the hyperparameter. Our proposed IAFL algorithm provides a high degree of flexibility for the server and clients (c.g., users, practitioners) to adjust the hyperpa- rameters such that they align with users' perceptions and preferences. However, we highlight that this flexibility is not without constraint: must trade off between fairness and equality, implying that there
33

---

Published as a conference paper at ICLR 2024
certain scenarios infeasible for accommodation. For example, the "winner takes all' perspective falls outside the spectrum of our trade-off as it violates both fairesss and equality. Similarly, is also unrealistic to expect to achieve both faimess and equality together in the IAFL's training- -imm model rewards distributed to the clients.
E.8 ALTERNATIVE CHOICES OF THE CONTRIBUTION MEASURE
As discussed in Section IAFL as an incentive mechanism can be applied vast range of contribution measures. In this section, we adopt the cosine gradient Shapley value (CGSV) discussed in Section 2 as the contribution measure to determine Рı, and conduct IAFL training. We denote this specific method as CGSV-IAFL and compare it with the original CGSV implementation with gradient masking (Xu et al. 202T). Table shows the superior incentivization performance of CGSV-IAFL. across various data partitioning strategies CIFAR-10. 10. Therefore, IAFL works with alternative choices of contribution measures. Additionally, we demonstrate through this experiment that our rewarding scheme detailed in Procedure 2 is more effective than the gradient masking technique of the original CGSV.
Table Comparison of the incentivization performance between CGSV and IAFL after adopting a common contribution measure defined by CGSV. The incentivization performance is measured using the Pearson correlation coefficient p between the final client model accuracies and standalone accuracies. Each value reports the mean and the standard error over 10 independent evaluations.
Category
Partitioning
CGSV
CGSV-IAFL
Label Distribution Skew
Dir(0.5) #C' 3
0.46:10.04
0.69=10.33
0.31
0.62:10,03
Feature Distribution Skew
((0.1)
-0.02++0.04
0.06
Quantity Skew
Dir(0.5)
0.73:10.04
0.81
Homogencous Partition
IID
-0.03:10.05
-0.03:10.04
E.9 EXPERIMENTS ON COMPLEX BARGE-SCALE DATASETS
We additionally conduct experiments on complex large-scale datasets: Tiny-ImageNet for vision tasks and 140 for language tasks. The results are shown in Table
Table 8: The incentivization performance under different dataset partitions, measured using the Pearson correlation coefficient/ p between the final client model accuracies and standalone accuracies. Each value reports the mean and the standard error over 3 independent evaluations.
Category
Dataset
Partitioning
FedArg Finetune
LG-FedAvg
CGSV
Rank
IAFL
Distribation
Tiny-ImageNet
#C 60
Dir(0.5)
0.27=0.06
0.38-+0.06
0.10=0.07
0.37-0.11
-0.02=0.00
0.10++0.8
0.34+0.11
0.22-40.10
0.82+0.01
0.81=0.07
Skew
Scnt140
Dir(0.5)
0.93=0.01
0.99=0.00
0.23+0.32
0.98+00.0
0.84+0.03
#C
1.00::0.00
1.00=0.00
1.00:0.00
1.00:10.00
0.07:0.07
Feature Distribution Skew
Tmageem
((0.1)
undefined
-0.04+0.07
-0.04+0.10
0.04440.10
0.77+40.0
Quantity
Tiny-ImageNee
Dir(0.5)
undefined
0.95-0.00
0.38+0.11
0.8540.022
0.83+0.02
Skew
4cnt140
-0.74+0.04
1.00=0.00
0,80=0.02
0.99+00.00
0.90=0.01
Homogeneous
Tiny-ImageNet Sent140
undefined
-0.02++0.66
0.07+0.1 10
0.02440.01
0.78=10.08
Partition
IID
0.08+0003
0.27-0.00
0.20++0.08
0.06-+0.04
-0.06++0.11
Number of times that performs the best
5
For the complex -may-Im dataset, IAFL achieves the best incentivization performance in the majority of the data partition settings. The correlations p between the final client model accuracies and standalone accuracies are generally above 0.75. Note that finetuning the network trained by FedAvg with the local client dataset for small number of epochs may not affect the performance of the networks. Therefore, in some cases, the final models received by the clients have the same accuracy (as the global FedAvg model) and thus the correlation p is undefined.
For the S4n dataset, we notice that other methods such as FedAvg Finetune and LG-FedAvg outperform IAFL in terms of incentivization performance measured by the correlation p in many
34

---

Published as a conference paper at ICLR 2024
cases. Further investigation reveals that using p alone to assess the effectiveness of collaborative learning is insufficient. Comparing the IPR in Table 9 the high p of baselines on Sent #C= corresponds to 0% client incentivization measured by IPR This is because collaboration through baseline methods does not result in any improvement of the client's model. We further provide the results of the average (and highest) accuracies achieved by clients on Sent140 in Table [T] The results illustrate that IAFL rewards better models to clients as compared to other baselines. Overall, IAFL achieves the best incentivization performance considering both metries p and IPRisss while outputting client models with the highest model accuracies.
Table 9: Comparison of gos among IAFL. and baselines on 140 Each value reports the mean and standard error of 3 independent evaluations and partition seedings.
Category
Partitioning
FedAvg Finetune
I.G-FedAvg
CGSV
Rank
IAFL.
Label
(ir(0.5)
0.84++0.02
0.01-0.01
0.93-00077
0.62+0.00
0.87:+0.22
Distribution Skew
#C =
0.00+00000
0.00=0.00
0.00=00.00
0.00=00.00
0.83
Quantity Skew
(o.(0.3)
1.00+0.00
0.00=0000
1.00:0.00
0.91
1.00
Homogeneous Partition
IDD
1.00=00.00
0.00=0.00
1.00=0.00
0.71#00011
1.00=00.0
Table 10: The average (highest) accuracies achieved by the client models on Sent140. The values show the top-1 test accuracy measured in percentage (i.e., %).. Each value reports the mean of independent evaluations and partition seedings.
Category
Partitioning
FedAvg Finetune
LG-FedAvg
CGSY
Rank
IAFL
Label
Dir(0.5)
68 (83)
61 (77)
61 (72)
66 (83)
71 (84)
Distribution Skew
#C =
50 (50)
(50)
50 (50)
50 (50)
56 (70)
Quantity Skew
Dir(0.5)
(85)
(80)
79 (81)
(85)
85 (85)
Homogeneous Partition
IID
84 (85)
(76)
81 (81)
81 (83)
85 (85)
F FREQUENTLY ASKED QUESTIONS AND DISCUSSIONS
Question 1: Is it more natural to incentivize the clients contribute using their full capacity?
Answer:
While having clients contribute to their full capacities for the best learning outcome is the ideal scenario, this goal is unrealistic because every client incurs non-trivial costs to contribute. Importantly, the actual contribution of clients depends on the interplay between rewards and costs for different contribution levels.
In our work, we propose the next achievable alternative: To incorporate the goal of "incentivizing clients to contribute as much as possible" on top of satisfying individual rationality. To this end, we designed IAFL such that Theorem [ and [2 are fulfilled. These theorems suggest that clients will be rewarded with better models if they contribute more. This will incentivize clients further contribute to their full capacity for improved model performance received, of course, subject to their marginal utility increment in the presence of cost c,. Clients will contribute up till the marginal increment in reward still surpasses the associated cost.
Question 2: What if client does not faithfully compute and upload the full local model updates?
Answer: Our framework does not place any assumption on what kind of local model updates are computed and uploaded by a client. Instead, the client can freely decide whether he or she wants to make "full" or "Zero" contribution. The contribution measures (in Section 4.2) capture the quality of the local model updates as contributions, e.g., FedSV (Wang et al.) 2020b), ComFedSV (Fan al. 2022). CGSV (Xu et al.) 2021), FedFAIM (Shi et al. 2022 are examples of such contribution measures. We summarisc the whole process here: The client's 's behavior model decides the quality of the local model updates being computed (e.g., using different portions of its local data). Then, the quality of the local model updates affects the client contribution level (as assessed by the contribution evaluation measures mentioned above), which in turn affects the reward rate in IAFL. Subsequently, the reward rates of clients affect their model convergence.
Question 3: Does convergence speed become faster the number of agents N grows?
35

---

Published as a conference paper at ICLR 2024
Answer:
The simple answer is, adding clients that "help than hurt" is going to improve the conver- gence speed.
To elaborate, the effecc depends on the contribution levels of the clients. We can look at the term
C Cr= Hr Em_ E
(+ (+a
2
Tm. + 1--11-1- -2). when N increases, the denominator becomes 76.1
bigger but the same time there additional terms in the summation.
We can consider a case where we increase N = to N = n + 1. Abstracting away the constants
Hr. T and a for simplicity, we can make a comparison for CT Em=1 7 7i 2 when
+ Note that 7 can also be treated constant here. Informally speaking, observe that when N increases, the term CT generally decreases in its scale if the added client has contribution 7 at least the Em Ym, Therefore, the decrease in CT tightens the performance bound in Theorem and makes the convergence faster.
N ni against the case for CT =+1 Em=1
-+++- when
"average contribution" of the existing clients 4
An exception that we can derive from the above is that when the added clients contribute badly with a very low Tn it could slow down the convergence despite the increase in N. In practice, this implies that the model update provided by the added client is bad, harmful, or even adversarial, and is detected by the contribution evaluation measure. Theoretically, the convergence adversely affected if we add "harmful" clients. However, we could easily implement client selection methods based on this insight on contribution evaluation to filter such clients during the training process to ensure faster convergence when N grows.
Question 4: Is it fair that for small clients, even if they contribute to their best, they still cannot receive high-quality model? Yet the large clients only need to contribute above some threshold to receive the best model?
Answer: There are two prevalent concepts of fairness in literature: (a) collaborative fairness (Lyu et al. 2020) (i.e., contribute more get back more), and (b) equality (Li et al. 2020c). To be fair, people from one of the camps will not view the other as fair.
In our paper, we have demonstrated results for the collaborative fairness view. Specifically, the contributions of clients are fairly evaluated by contribution evaluation measure, e.g., CGSV (Xu 2021). and then used to fairly reward the clients with model that has performance commensurate with their contributions.
If the designer of the FL process views fairness more towards equality such that "if everyone puts in their best efforts, they should be treated equally", it is possible use "individual efforts percentage" (e.g., how many percentages client contributes to his/her best effort) as contribution evaluation measure (assuming that individual efforts of clients can be measured). This measure can be seamlessly combined with the IAFL framework, too. However, would like to clarify that "individual efforts percentage" is not commonly used as a contribution measure in literature.
36


Reviews:
[{"review_id": "wXZcV47Y45", "reviewer": "Reviewer_LXR6", "summary": "This paper studies incentive mechanism for federated learning. Existing works in this direction typically incentive clients via post-training monetary rewards. The authors argue that, clients may anticipate timely rewards during FL process, and may decide to quit when not being properly incentivized. Moreover, monetary rewards may be infeasible in some situations, e.g., when revenue is unclear or budget is limited. Therefore, the authors propose a new formulation, where the clients are reward during the FL process in the form of global model updates of varying quality, depending on the contribution of each client. The authors derive a convergence guarantee of the proposed method, where the convergence rate of each client depends on its reward rate $\\gamma_{i,t}$.", "questions": "Can the authors elaborate on, in Theorem 1, why $o(1/\\gamma_{i,T}^{\\prime})$ suffices to make the convergence hold? Where did the $(T+\\alpha)^{2}$ in the numerator go?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The idea of providing incentives during the FL process instead of postponing to the end of FL is novel and well-motivated.", "weaknesses": "1. What it means for a client to be incentivized is not well-defined in this paper.\n\nFrom Proposition 1, it seems as long as the gradient of client $i$'s utility w.r.t. its contribution $p_{i}$ is higher than that under standard FL mechanism, we say the client $i$ is incentivized. It is not clear why we, as the designer of the mechanism, cares about whether the gradient of utility for each client is higher than what the client gets under a standard FL mechanism. Instead, a more natural goal is to incentivize the clients to contribute to FL using their full capacity in order to get the best learning outcome. \n\nIn this regard, the intrinsic cost $c_{i}$ of each client also plays an important role, i.e., it is possible that the cost value is high, such that we end up with a negative gradient of the utility (contributing more leads to even lower utility). Therefore, a rational client will decide to contribute $p=0$ in this case, which affects the convergence of the FL process.\n\n2. Current convergence analysis over-simplifies the effect of contribution level on local gradients\n\nDue to the simplification of the \"contribution measurement\" mentioned in Section 4.2, the current convergence result given in Theorem 2 is independent from client's behavior model. Currently, the only place that contribution level of a client plays a role in the convergence result, is the reward rate $\\gamma_{i,t}$ (the quality of the global model that the server decides to give to this client). However, the contribution level should also affect the quality of the local gradient that client provides to the server, e.g., lower contribution means computing the local gradient using smaller portion of its local data (Other than simply saying the client will always faithfully compute the full local gradient w.r.t. the given global model). \n\nIn the extreme case mentioned in my first comment, where the client decides to make zero contribution, then the server will not get the local gradient from this client. However, in the current analysis, the authors assume that the server can always get the local gradients of all the clients no matter what, which does not seem to be reasonable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8XBnpo1O4s", "reviewer": "Reviewer_dsGp", "summary": "The paper proposes an incentive-aware federated learning algorithm that encourages client contribution by training-time rewards. Concretely, the authors propose a local reward scheme to ensure that a higher-contributing client receives a better final model.", "questions": "The problem this paper studies is interesting. However, it could be that I'm missing something, in Theorem 1 and Theorem 2, does convergence speed become faster as the number of agents $N$ grows? It would be helpful to simplify the bound and make the dependence on $N$ explicit. Does adding more clients lead to a faster convergence rate? I would happily increase my score if the question is addressed.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The scope of the experiment is extensive. The authors experiment with different data partition methods, different metrics for measuring incentives, and benchmark against various baselines.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ofVi4ET1qO", "reviewer": "Reviewer_xzxw", "summary": "In federated learning, each client contributes the gradient updates computed with its own local data and then shared with the center. The center aggregates the updates from clients to update the model, and then share the model to the clients to start the next round. In this process, selfish clients may get the most up-to-date model by free-riding, and hence hurt the overall performance of the system. Prior work proposes to incentivize the clients with monetary transfers, while this work focuses on designing an incentive mechanism to share the model in a way such that the more a client contributes, the better model it will receive.\n\nThe proposed mechanism includes two key features to incentive each client to contribute more:\n* Sharing the model updates from a subset of the other clients, the size of the subset is proportional to this client’s contribution;\n* With some probability, give the client the most up-to-date model to prevent the client’s local model being too off.\n\nTheoretical results:\n* All clients have strictly positive incentive to contribute more\n* Each client is better off to participate in the federated learning (individually rational)\n* The bound on the performance loss of the client models (against the optimal benchmark not suffering from any free-ride challenge), which converges to zero with additional assumptions.\n\nExperiments:\n* Partition training data to simulate the distributed data in the federated learning setting\n* Evaluate the percentage of clients where the IR condition is respected\n* Evaluate how the hyperparameters influence the performance of client models at different contribution levels.", "questions": "* What is the tradeoff between the strength of incentive and the loss of (center) model accuracy?\n* Is there a fairness concern that for small clients, even if they contribute to their best, they still cannot receive a high quality model? Yet the large clients only need to contribute above some threshold to receive the best model?\n* It seems to me that the small clients may have incentive to cooperate to pretend as one big client to receive a better model without a significant cost overhead? Will this lead to exchange platforms where one can first send their gradient updates to the platform, then the platform aggregates the gradient updates from many small clients together, and finally pretend as one big client to cheat in the proposed incentive mechanism? (maybe good to call out the limitation of incentive mechanisms without monetary transfers)", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Very interesting idea to an important problem\n* Solid results", "weaknesses": "* The incentive guarantee is weak in the sense that only a positive incentive is guaranteed, which might not be enough when the clients do suffer certain costs to contribute more to the center. When the cost is higher than the incentive, one may still not contribute 100% effort in the federated learning.\n* The tradeoff between the strength of incentive and the loss of (center) model accuracy is not established, which might be more important in practice. In particular, if I understand correctly, this work assumes all clients contribute 100% of its effort given the constructed incentives. Hence the performance loss of the center model is considered as zero and not measured. However, I can see at least two reasons for the clients to not contribute at its full capacity:\n  * Contribution already exceeds the threshold parameter $p_\\mathsf{ceil}$\n  * When maintaining a certain level of incentive is necessary, one may have to limit the sharing of the gradients, i.e., sufficiently low $\\kappa$ and $q$. In this case, the performance loss of the center model should emerge as the client model might be quite off from the center model and lead to low quality of the gradient updates from local models.\n* I would suggest the authors to at least discuss the above limitations", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K8b2W34Uje", "reviewer": "Reviewer_EksS", "summary": "The paper proposes Incentive-Aware Federated Learning (IAFL), an FL algorithm which is generally applicable to varying measures of client contribution such as participation rate or local update steps. To incentive client contribution, IAFL takes a personalized FL approach where the server shares higher-quality model updates with clients with higher contribution. Additionally, the paper ensures that all clients, despite limited contribution, are able to reach the optimal model by stochastically synchronizing client models with a common reference model. The paper shows that IAFL outperforms various FL baselines in terms of IPR in several heterogeneous settings.", "questions": "Reading through this paper, I assumed that client contribution is not being adjusted in response to the rewards. Please clarify if this is inaccurate.\n\nAssuming contribution is participation rate, wouldn't there already be a disadvantage to partial participation if the server broadcasts an update (rather than the updated model) to the participating clients, as the local model could become desynchronized? Or does the paper assume the server is sending an updated model?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This work appears novel in the sense that it personalizes the outcome of each round to individual clients, whereas earlier approaches attempt to produce a single global model that is compatible with multiple clients' incentives.\n\nAs mentioned in the paper, it is applicable to settings where earlier incentive-aware FL works are not, such as partial participation and lack of server-side data.", "weaknesses": "The behavior of IAFL is not clearly explained in the experiments. \n- What is client contribution here? Is it number of local updates? How is this set / varied across clients / time?\n- How is incentivization determined? Do you compare a locally trained model to the (fully trained) server model?\n\n6.1: \" We measure the performance of a model using the test loss and the test accuracy, denoting them as IPR_loss and IPR_accu, respectively.\" This doesn't make sense to me. Doesn't IPR_accu (Table 1) refer to the fraction of clients who are \"incentived\" to participate, and not an accuracy metric?\n\nBased on the results in Table 3 it is surprising to see that IAFL achieves much better accuracy than non-IR methods. However, shouldn't the other methods have an advantage when comparing raw accuracy, as they distribute a high-quality model to all clients without considering incentives? What exactly does this accuracy metric refer to?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)