BARA: Efficient Incentive Mechanism with Online Reward Budget Allocation in Cross-Silo Federated Learning

1 Introduction

Due to the rising concern on data privacy leakage in recent years, laws such as General Data Protection Regulation (GDPR) [Voigt and Von dem Bussche, 2017] have been made to regulate the collection and use of user data to protect data privacy. Federated learning (FL) [McMahan et al., 2016], as an emerging distributed machine learning paradigm, enables decentralized clients to collaboratively train a shared model without disclosing their private data. The workflow of FL mainly includes: 1) The parameter server (PS) distributes the latest global model to participating clients. 2) Each client updates the model with its local dataset and returns the updated model to the PS. 3) Model aggregation is performed on the PS to obtain a new global model for the next communication round. The above process is repeated until the maximum number of training rounds is reached. Due to its capability in preserving data privacy, the FL market is proliferating. According to [Newswire, 2022], the global FL market size is projected to increase from 127 million dollars in 2023 to 210 million dollars by 2028, at a compound annual growth rate of 10.6% during the forecast period.

∗An extended version of this paper (with the Appendix included) can be found in http://arxiv.org/abs/2305.05221.

†Corresponding author.

However, FL is unsealed without a mechanism to force clients to altruistically contribute their models, and thus an effective incentive mechanism motivating clients is very essential for the success of FL. It was reported in [Ng et al., 2021] that the final model accuracy of FL can be substantially improved by an incentive mechanism, which can inspire more high-quality clients to participate in FL. Reverse auction [Myerson, 1981] has been widely studied in the incentive mechanism design for FL. For example, Deng et al. [Deng et al., 2021] designed a quality-aware incentive mechanism based on reverse auction to encourage the participation of high-quality learning users. RRAFL [Zhang et al., 2021] is an incentive mechanism for FL based on reputation and reverse auction theory. A few works even attempted to design incentive mechanisms for FL enhanced by differential privacy. For example, FL-Market [Zheng et al., 2021] was proposed as a novel truthful auction mechanism enabling data owners to obtain rewards according to their privacy losses quantified by local differential privacy (LDP).

Yet, existing works focused on how to optimally allocate rewards between heterogeneous participating clients, ignoring the essential problem of how to allocate rewards between communication rounds. It usually consumes a large number of communication rounds to train advanced machine learning models. On the one hand, if excessive rewards are allocated per communication round, the reward budget will be used up instantly without fully utilizing clients' data for model training. On the other hand, if the amount of allocated rewards is insufficient to solicit high-quality clients, FL fails as well because of the low training efficiency per round.

How to optimally allocate the reward budget between communication rounds is extremely difficult because of the complicated relationship between the final model accuracy and reward budget allocation giving rise to the following three challenges. First, once we change the amount of reward budget per communication round, it yields two opposite influences. If we increase the amount of reward budget per communication round, it diminishes the total number of conducted rounds but increases the model utility improvement per communication round, and vice verse. Thereby, it becomes vague how the change of the reward budget allocation will eventually affect the change of final model utility. Second, the prediction is problem-related susceptible to random factors, which will be different when training different models using different datasets or hyperparameters (e.g., learning rate and batch size). Third, due to the constrained total reward budget, it is unaffordable to exhaustively make trials with different reward budget allocation strategies to search for the best one.

To address the reward budget allocation problem, we design a novel online reward budget allocation algorithm named BARA (Budget Allocation for Reverse Auction). Specifically, a Gaussian process (GP) model [Williams and Rasmussen, 2006] is established to analyze relationship between reward budget allocation and final model utility. Newton's polynomial interpolation is used to expand the training records for establishing the GP model based on historical information. Bayesian optimization is employed to dynamically search the reward budget allocation strategy that can maximize the predicted final model utility. Based on the above analysis, we design the BARA algorithm to determine reward budget allocation per round in an online fashion. It is worth noting that BARA is orthogonal to existing incentive mechanisms optimizing reward allocation between clients. Thus, it can be widely incorporated into existing incentive mechanisms to boost FL utility, which is exemplified by incorporating BARA into reverse auction-based incentive mechanisms in our work.

In summary, our main contributions are presented as follows:

• We establish a GP model to analyze the relation between reward budget allocation and model accuracy. Newton's polynomial interpolation is applied to enrich the training records for the GP model while the Bayesian optimization is employed to search the optimal reward budget allocation strategy.
• Based on our analysis, we propose an online reward budget allocation algorithm (BARA). To our best knowledge, we are the first to address the reward budget allocation across multiple communication rounds to incentivize FL clients.
• We conduct extensive experiments on four public datasets to evaluate our algorithm in comparison with other baselines. The results demonstrate the extraordinary performance and application value of BARA.

2 RelatedWork

In this section, we briefly discuss related works on incentive mechanism design for FL and Bayesian optimization.

2.1 Incentive Mechanisms in Federated Learning

Incentive mechanism design encouraging clients to contribute their resources for conducting FL has attracted intensive research in recent years. FAIR [Deng et al., 2021] was proposed as an incentive mechanism framework in which reverse auction was employed to incentivize clients by rewarding them based on their model quality and bids. Clients contributing non-ideal model updates will be filtered out before the model aggregation stage. Zeng et al. [Zeng et al., 2020] proposed an incentive mechanism with multi-dimensional procurement auction of winner clients. Theoretical results of this strategy was provided as well. RRAFL [Zhang et al., 2021] was designed by combining reputation and reverse auction theory together to reward participants in FL. A reputation calculation method was proposed to measure the clients' quality. Zhou et al. [Zhou et al., 2021] considered how to guarantee the completion of FL jobs with minimized social cost. They decomposed the problem into a series of winner determination problems, which were further solved by reverse auction.

It is a more challenging problem to incentivize clients in differentially private federated learning (DPFL) due to the disturbance of noises. FL-Market [Zheng et al., 2021] is a personalized LDP-based FL framework with auction to incentivize the trade of private models with less significant noises. It can meet diversified privacy preferences of different data owners before deciding how to allocate rewards. Liu et al. [Liu et al., 2021] introduced the cloud-edge architecture into FL incentive mechanism design to enhance privacy protection. Sun et al. [Sun et al., 2021] proposed a contractbased personalized privacy-preserving incentive mechanism for FL by customizing a client's reward as the compensation for privacy leakage cost.

Nevertheless, existing works failed to optimize the reward budget allocation across multiple communication rounds due to the difficulty to explicitly analyze the relationship between a reward budget allocation strategy and final model utility, and this problem will be initially investigated by our work.

2.2 Bayesian Optimization

Bayesian optimization based on Gaussian process (GP) is particularly effective in analyzing a complicated process susceptible to various random factors without the need to derive a closed-form solution. Based on kernel methods and GP models, significant contribution has been made in machine learning [Shahriari et al., 2015]. In [Williams and Rasmussen, 2006], smoothness assumptions of the objective function to be modelled are encoded through flexible kernels in a nonparametric fashion. Srinivas et al. [Srinivas et al., 2009] proposed GP-UCB, an intuitive upper-confidence based algorithm. Its cumulative regret in terms of maximal information gain was bounded, and a novel connection between GP optimization and experimental design was established. Bogunovic et al. [Bogunovic et al., 2016] considered a sequential Bayesian optimization problem with bandit feedback, which set the reward function to vary with time. GPUCB was extended to provide an explicit characterization of the trade-off between the time horizon and the rate at which the function varies.

Given the excellent performance of Bayesian optimization based on GP in modeling complicated processes influenced by multiple unknown random factors, our work is novel in applying this approach in FL incentive mechanism design.

3 Preliminaries

We investigate a generic FL system with a single parameter server (PS) owning the test dataset Dtest and N clients with local datasets {D1,D2, . . . ,DN}. FL training is completed by multiple communication rounds denoted by rounds {1, 2, . . . , t, . . . , T}. In communication round t, a typical FL system with a reverse auction-based incentive mechanism [Deng et al., 2021] works as follows:

• Step 1 (on clients): Client i reports its bid bt,i to the PS, representing the reward client i desires for participating in FL.
• Step 2 (on the PS): The PS measures the quality of each client (e.g., the size of local dataset) denoted by qt,i. Based on qt,i and bt,i, the PS selects nt (1 ≤ nt < N) as participating clients and rt,i represents the reward allocated to client i. Then, the PS sends out the latest global model ωt-1 to participating clients.
• Step 3 (on participating clients): Each participating client updates ωt-1 with its local dataset by using local update algorithm (e.g., the gradient descent algorithm [Ruder, 2016]). Then, model updates are returned to the PS.
• Step 4 (on the PS): The PS performs model aggregation based on returned model updates to obtain the global model ωt for the next communication round.

To effectively incentivize clients, reverse auction is widely adopted to determine the reward allocated between clients. More specifically, the PS ranks all clients in terms of the ratio of quality over bid, i.e., qt,i bt,i , in a descending order. Then, the PS can get a list of ranked clients with qt,1 bt,1 > qt,2 bt,2 > · · · > qt,N bt,N . Due to the limited total reward budget, the PS sets a reward budget limit Bt to reward participating clients in communication round t. Constrained by Bt, the PS selects top clients from the rank list until Bt is used up. Suppose top nt clients are selected, the reward for client i (1 ≤ i ≤ nt) is rt,i = bt,nt+1 qt,nt+1 qt,i. nt is determined by the constraint of Bt:

A straightforward strategy to determine Bt adopted by existing works is to set the target number of communication rounds Tmax. If the total reward budget is Btotal, the reward budget for each communication round is Bt = Btotal Tmax .

4 ProblemFormulation

In this work, we design a novel algorithm to adjust the number of participating clients based on the typical workflow of FL system with a reverse auction-based incentive mechanism in Section 3.

Let Btotal denote the total reward budget provided by the PS to recruit participating clients. Let at denote the model accuracy after communication round t and ∆at denote the incremental improvement of model accuracy, i.e., ∆at = at - at-1. n (1 ≤ n < N) is the number of participating clients. Our objective is to tune the number of recruited clients to adjust consumed reward budget per communication round so as to maximize the final model accuracy. If T communication rounds are conducted in total, our problem can be formulated as:

where a0 is the test accuracy of the initial global model ω0. However, it is a very challenging problem because: 1) ∆at is a function of n as a bigger n brings a larger ∆at. 2) Bt is a function of n since more participating clients consume more reward budget. 3) T is a function of n as well given a fixed Btotal. Thus, if these variables in P1 are expressed as functions of n, we can get:

With the knowledge of T(n), ∆at,n and Bt(n), we can solve P2. The term Bt(n) is determined by the reverse auction-based incentive mechanism once n is fixed. As discussed in Section 3, we can calculate the minimum reward budget Bt(n) consumed by selecting n clients to participate in FL in the t-th communication round as:

Based on Bt(n), T(n) can be computed correspondingly. Let xτ,n = 1 denote if there are n participating clients in communication round τ. T(n) can be estimated if n participating clients are selected in communication round t as:

where ¯Bt(n) = ∑tτ=1 xτ,nBt(n) ∑tτ=1 xτ,n is the average reward budget consumption per communication round estimated in round t. Unfortunately, there is no prior work that explicitly defines ∆at,n. Thus, the main challenge for solving at,n is how to accurately estimate ∆at,n.

5 Methodology

In this section, we propose an online reward budget allocation algorithm using Bayesian optimization to solve P2. We first utilize Newton's polynomial interpolation to synthesize training records based on historical records observing reward budget allocation and model accuracy improvement. Based on training records, a Gaussian process (GP) is established to model the relationship between final model accuracy and reward budget allocation strategies. Next, Bayesian optimization is employed to search for the optimal reward budget allocation strategy in an online fashion to maximize the final model accuracy.

5.1 Training Records Synthesis

How to exactly estimate ∆at,n (representing model accuracy improvement with n participating clients in the t-th communication round) is a challenging open problem. When training different models, we can get different ∆at,n. Until communication round t, we denote the number of participating clients in the τ-th communication round as nτ (1 ≤ τ ≤ t). However, we cannot compute ∆aτ,n prior to model training and it is also impossible to obtain ∆aτ,n if n ̸= nτ . Thereby, we approximate unknown training records during the model training process with historical records of ∆aτ,n. We can use a matrix Mt ∈ Rt×N-1 to denote ∆aτ,n until communication round t (i.e., Mt = [∆naτ,n] (1 ≤ τ ≤ t and 1 ≤ n < N). ∆aτ,n will be empty if n ̸= nτ . Each row represents a communication round and note that only a single element in each row is from FL training records since we can only select a single nτ for communication round τ.

However, to determine which n yields the highest final model accuracy, we need the knowledge of all elements in ∆a1,n, ∆a2,n, . . . , ∆aT (n),n. With all known elements in the n-th column of Mt, we employ the Newton's polynomial interpolation [Hildebrand, 1987] to approximate the values of those unknown elements.

Without loss of generality, we briefly explain how to apply the Newton's polynomial interpolation for a particular nth column. Let t1, t2, . . . , tJ denote indices of elements in the n-th column with known value from past training records. Then, we can define a number of divided differences as follows:

Here y[tj] = ∆atj,n for all 1 ≤ j ≤ J. We can easily compute y[t1, t2, · · · , tJ] with y[tj] and Eq. (8). Unknown values in Mt until t = T(n) can be estimated by:

for τ = 1, 2, . . . , t, . . . , T(n). Let T = max1≤n<N T(n) denote the maximum number of communication rounds we can conduct by selecting n clients per communication round. Based on interpolation results, we can create the estimation matrix ̂MT = [∆ˆat,n] (1 ≤ t ≤ T and 1 ≤ n < N).

Note that ∆ˆat,n is valid only if t ≤ T(n). Although ∆ˆa1,n, . . . ,∆ˆaT(n),n can be estimated through Eq. (9), the predicted model accuracy improvement is vulnerable to overfitting. In particular, in the first few communication rounds, the number of available historical records is insufficient for accurately finding the best n. Thus, we establish a learning process to dynamically predict the accuracy with different n before we can decide the optimal number of participating clients.

5.2 Searching for Optimal Reward Budget Allocation Strategy

It is known that the model accuracy performance is susceptible to various factors such as the data distribution among clients. It is difficult to accurately predict final model accuracy only based on the number of participating clients. In light of this complication, we use a Gaussian process (GP) to model the random evolution of final model accuracy when taking different reward budget allocation strategies.

As we collect more records of nt and ∆ˆat,nt along the training process, the matrix ̂Mt expands gradually and the predicted value of each unknown element will be updated according to Eq. (9). Note that our goal is to predict the final model accuracy when using different n. For convenience, we define ˆat(n) to represent the estimated final model accuracy predicted at communication round t. In other words, ˆat(n) = a0 + ∑T (n) t=1 ∆ˆat,n where ∆ˆat,n are elements in the n-th column of ̂MT .

Note that ˆat(n) is derived based on a few observations in matrix ̂MT . It only utilizes elements in the n-th column for prediction failing to fully utilize all observations to predict ˆat(n). To overcome this drawback, we model ˆat(n) with a GP to capture the relationship between ˆat(n) and ˆat′(n′ ) so that we can fully utilize all observations to more accurately predict ˆat(n).

To distinguish with final model accuracy obtained by interpolation via Eq. (9), we define zt(n) as the final model accuracy sampled from the GP model in the t-th communication round assuming that n clients are recruited to conduct FL in each communication round. Specifically, zt(nt) is modeled as a random variable sampling values from the distribution of GP(µ(nt), k(nt, nt)) where k(nt, nt) is the covariance (or kernel) function. The mean value of zt(nt) is denoted by µ(nt) = E[zt(nt)]. With multiple variables zt(nt), we needs to consider the covariance E[(zt(nt)-µ(nt))(zt(nt′ )- µ(nt′ ))] when modeling the relationship between two choices of nt and nt′ at two different communication rounds t and t′ , respectively.

According to [Srinivas et al., 2009], the squared exponential kernel function is widely adopted to model covariance for a GP. Note that the elements in ̂Mt (i.e., ∆ˆat,n) are approximated by Newton's polynomial interpolation. Therefore, the approximation gets better over time as we collect more observation records of ∆at,n, which means fresh observations are more valuable than stale ones. We construct the composite kernel to weigh stale and fresh observations differently based on Ornstein-Uhlenbeck temporal covariance function. Together with the squared exponential kernel function, the

Algorithm 1: The details of BARA algorithm

Input: clients' local datasets {Di=1}Ni ; initial global model parameters ω0 ; test dataset Dtest; GP prior (µ0, σ0, k); total reward budget Btotal Output: final global model parameters PS:

• 1: Test ω0 on Dtest to get a0
• 2: B ← 0
• 3: for t = 1 to Tmax do
• 4: Client i report bt,i to PS, i ≤ N
• 5: if t < T0 then
• 6: Randomly select nt from {1, 2, · · · ,N -1}
• 7: else
• 8: nt ← arg max1≤n<N µt-1(n) + √βtσt-1(n)
• 9: end if
• 10: Sort all clients in descending order of qt,i bt,i
• 11: Bt(nt) ← ∑nt i=1 bt,nt+1 qt,nt+1 qt,i
• 12: B ←B +Bt(nt)
• 13: if B > Btotal then
• 14: Return ωt-1
• 15: end if
• 16: for i = 1 to nt in parallel do
• 17: rt,i ← bt,nt+1 qt,nt+1 qt,i
• 18: Send global model parameters ωt-1 to client i
• 19: ∇l(ωt-1;Di) ←ClientUpdate(ωt-1,Di)
• 20: end for
• 21: Performmodel aggregation based on ∇l(ωt-1;Di) to obtain ωt and test it on Dtest to obtain at
• 22: UpdateMt, ̂Mt and performBayesian posterior update as in Eqs. (12) - (13) to obtain µt and σt
• 23: end for

ClientUpdate(ωt-1, Di):

• 1: Receive ωt-1 from the PS
• 2: Calculate ∇l(ωt-1; Di) based on ωt-1 and Di
• 3: Upload ∇l(ωt-1;Di) to the PS

covariance between zt(nt) and zt′ (nt′ ) is modeled by

where l > 0 is a length scale hyperparameter to determine howmuch the two points nt and nt′ influence each other. Intuitively, if nt is closer to nt′ , the value of k(nt, nt′ ) is bigger implying that zt(nt) and zt′(nt′) are more correlated. Thus, the information of zt(nt) is more useful for us to predict zt′(nt′). Moreover, stale observations should be weighted lighter and lighter over time. Here λ controls how fast the weights of stale observations decrease.

Until communication round t, we have made t different choices of nt. Thus, we can establish a GP with t variables to predict the distribution of zt+1(n). To simplify our presentation, let zt denote the vector of the first t choices of n, i.e., zt = {z1(n1), z2(n2), . . . , zt(nt)}. Let µ(nt) = {µ(n1), µ(n2), . . . , µ(nt)}. The deviation between the observed value and the real value can be gauged by a zeromean random noise ϵt ∼ N(0, σ2 ), which is independent with time. According to [Williams and Rasmussen, 2006], (zt, zt+1(nt+1)) is a sample drawn from the following distribution:

for 1 ≤ nt+1 < N. Note that nt+1 is the choice of round t + 1, which has not occurred yet. Here I is a t × t identity matrix. Kt is the positive definite kernel matrix [k(n, n′ )]∀n,n′∈nt and kt(nt+1) = [k(n1, nt+1), k(n2, nt+1), . . . , k(nt, nt+1)]⊤. It is easy to see that the joint distribution given in Eq. (11) describes the relationship between t+1 variables. It can be regarded as the prior knowledge of Bayesian optimization to learn the posterior knowledge. At the end of communication round t, we can update the posterior knowledge, i.e., estimated mean and variance for zt(n) when choosing different n, as follows:

for 1 ≤ n < N. Here, ˆat = {ˆa0(n), ˆa1(n), . . . , ˆat(n)}, which is computed based on the n-th column in matrix ̂MT . In Eq. (12), we jointly utilize the results of Newton's polynomial interpolation, i.e., ˆat, and GP which captures the correlation when choosing different n via the term k⊤t (n)[Kt +σ2 I]-1 to predict zt(n). In this approach, we can fully utilize all historical records to make prediction. In Eq. (13), the variance of zt(n) is updated accordingly to gauge the uncertainty of the estimation in Eq. (12).

Note that µt(n) represents the expected final model accuracy by choosing n clients per communication round predicted at communication round t. As t increases, we will collect more and more information to continuously improve our prediction. For the (t + 1)-th round, the decision aiming to maximize the final model accuracy should select the one that can maximize µt(n). However, considering the uncertainty of our prediction seized by σ2 t (n), it is better to add an exploration term based on σ2 t (n). Specifically, the decision of n for communication round t + 1 is:

where √βt+1 is a tuneable constant. √βt+1σt(n) is the exploration term, created based on previous empirical experience [Srinivas et al., 2009]. The convergence property of Eq. (14) been proved in [Bogunovic et al., 2016], which can guarantee that searched nt will gradually approach to the optimal n∗ . It will be further verified by our experiments in the next section.

It is worth mentioning that a random strategy to select n should be adopted at the early stage of FL training because observation records are insufficient to establish the GP for accurately learning posterior knowledge. Specifically, the online reward budget allocation algorithm has two stages: 1) a pure exploration stage and 2) an explorationexploitation stage. In Stage 1, the PS randomly selects nt from {1, 2, · · · ,N -1} in each communication round and observations will be recorded. In Stage 2, the Bayesian optimization is performed with enriched prior knowledge. The first pure exploration stage can be executed for a fixed T0 communication rounds. Then, it will proceed to the exploration-exploitation stage in the remaining communication rounds. Note that Stage 1 should not exhaust the reward budget such that Stage 2 can be conducted.

We describe the detailed procedure of BARA in Algorithm 1. For each communication round t < T0, the PS randomly selects nt from {1, 2, · · · ,N -1} in Stage 1 (line 6). After client selection and model update (lines 10-20), the PS updates the matrices Mt and ̂Mt, which employed to Bayesian posterior update to obtain µt and σt (line 22). In Stage 2, the PS balances exploration and exploitation based on the GP posterior (line 8). The time complexity of sorting all clients in descending order is O(N logN) (line 10). Here T = max1≤n<N T(n). The time complexity of updating Mt, ̂Mt and Bayesian posterior update (line 22) are both O(T 2 ). The overall time complexity of BARA is O(max {N logN, T 2}), which is lightweight in comparison with training advanced FL models.

6 Experiments

6.1 Experimental Setups

Datasets and Models

We use four public datasets for experiments: MNIST [LeCun et al., 1998], Fashion-MNIST (also abbreviated as FMNIST) [Xiao et al., 2017], CIFAR-10 and CIFAR-100 [Krizhevsky et al., 2009] datasets. Similar to [McMahan et al., 2016], we train a multilayer perceptron (MLP) model that consists of 2-hidden layers for classifying the MNIST dataset. A CNN (convolutional neural network) model that consists of two convolution layers (each followed by a max pooling layer and ReLU activation), then followed by a fully connected layer is trained for classifying the FMNIST dataset. For CIFAR-10 and CIFAR-100 datasets, we train the CNN model with the same structure as that in [Mills et al., 2021], which consists of two convolutional pooling layers, two batch normalization layers and two fully connected layers.

In real scenarios, the typical data distribution on FL suffers from statistical heterogeneity due to the fact that the training data owned by a particular client is usually related with userspecific features. Therefore, we allocate training datasets to clients in a non-IID manner. According to [Chen et al., 2022], for each dataset, we first sort samples by their labels and then split them into 2N shards equally. Each of N clients randomly selects 2 shards.

Parameter Settings

We set the total number of clients N as 20. Based on the empirical results in [Deng et al., 2021], we set the maximum number of communication rounds, i.e., Tmax, and the total reward budget of the PS, i.e., Btotal, as 200 and 1, 500, respectively. We implement a typical reverse auction-based incentive mechanism for FL: bid price first (i.e., all clients are of equal quality) [Deng et al., 2021]. Each client's bid for participating in each FL training round is independently sampled from a uniform distribution U(0.5, 1.5). Referring to [Bogunovic et al., 2016], we set hyperparameters in the GP as √βt = 0.8 log(0.4t), the length scale parameter l = 0.2 for squared exponential kernel and λ as 0.001. We set the noise variance σ2 to 0.01. The pure exploration stage runs for initial T0 = 40 communication rounds.

Compared Baselines

We compare BARA with the following reward budget allocation baseline methods:

• Even allocation (EA): The PS allocates the total reward budget Btotal evenly to each communication round (i.e., Bt = Btotal Tmax ), which is commonly adopted in existing works [Deng et al., 2021; Zhang et al., 2021; Zheng et al., 2021].
• Monotonically increasing allocation (MIA): The allocated reward budget Bt for round t is a monotonically increasing function with t (i.e., Bt = 2 Btotal T 2max t).
• Monotonically decreasing allocation (MDA): The allocated reward budget Bt of round t is a monotonically decreasing function with t (i.e., Bt = -2 Btotal T 2max t + 2 Btotal Tmax ).
• Random allocation (RA): In each communication round, the PS randomly selects the number of participating clients from {1, 2, · · · ,N - 1}. The FL training process halts once the total reward budget is used up.

Evaluation Metrics

We adopt two metrics, test accuracy and regret, to evaluate our algorithm. Test accuracy evaluates the accuracy of ωt on Dtest in each communication round t. By comparing test accuracy, we can evaluate how much performance gain can be achieved by optimizing the reward budget allocation in FL. Regret evaluates the gap between the solution of our algorithm and the theoretically optimal solution. To obtain the theoretically optimal solution, we enumerate n in FL to find which n∗ can achieve the highest final model accuracy on the test set. Due to the limited reward budget in practice, it is impossible to enumerate all possible n. Thus, the constraint of the reward budget is not considered for searching n∗ . Once n∗ is determined, we define the regret at round t as Regt = ∑tτ=1 (aT(n∗ )(n∗ ) - ˆaτ(nτ)) where ˆaτ(nτ) is the estimation of model accuracy predicted by our model. Intuitively, if Regt approaches 0 with t, i.e., lim t→∞ Regt/t = 0, it implies that BARA can approximately find the optimal solution after a certain number of rounds.

6.2 Experimental Results

We first conduct experiments to compare BARA with other reward budget allocation methods. The experimental results are plotted in Figure 1 with the x-axis representing different reward budget allocation methods and the y-axis representing the final model accuracy on Dtest. The results in Figure 1 manifest that BARA can significantly outperform other baselines in term of final model accuracy. The analysis of experimental results are presented in Appendix A.

Next, we investigate the learning process of BARA for searching the optimal number of participating clients. Based on experimental results in Figure 1, we plot the number of participating clients selected by BARA for each dataset in Figure 2. Here, the x-axis represents the communication round and the y-axis represents the number of participating clients per communication round. From Figure 2, we can observe that 1) In the initial T0 = 40 communication rounds, the number of participating clients fluctuate over time as the PS randomly selects n for participating in FL. 2) The number of participating clients quickly converges to a stable value beyond the critical point T0 = 40 indicating that BARA can efficiently explore n∗ with sufficient historical records.

To further verify the effectiveness of BARA, we evaluate the regret of BARA for each dataset. In each communication round, we plot Regt/t in Figure 3 with the x-axis representing the communication round and y-axis representing Regt/t. From Figure 3, we can observe the fast convergence of the regret curve when t > T0. As the regret approaches to 0, it implies that BARA finds n∗ for determining the number of participating clients.

BARA is applicable for various different incentive mechanisms. To demonestrate this generic value of BARA, we implement two more typical reverse auction-based incentive mechanisms for FL. Their performance can be further enhanced by incorporating BARA into their mechanisms. The detailed experimental results are presented at Appendix B.

7 Conclusion

To our best knowledge, our work is the first one to investigate the reward budget allocation problem between training rounds in federated learning given a limited total budget. Due to the complicated relationship between reward budget allocation and final model utility, we established a Gaussian process (GP) model to predict model utility with respect to reward budget allocation. To expand the historical knowledge for building the GP model, Newton's polynomial interpolation was applied to generate artificial records. We further employed the Bayesian optimization to determine the reward budget allocation to maximize the predicted final model utility. Based on our analysis, an online reward budget allocation algorithm called BARA was proposed, which is lightweight for implementation. Finally, extensive experiments were conducted to demonstrate the effectiveness of BARA by extensively improving model accuracy compared with baselines.

Acknowledgements

This work was supported by the National Natural Science Foundation of China under Grants U1911201, U2001209, 62072486, and the Natural Science Foundation of Guangdong Province under Grant 2021A1515011369.