Incentivized Federated Learning and Unlearning

Federated learning is a promising distributed machine learning paradigm, in which multiple users collaborate to train a shared model under the coordination of a central server [1]. This approach allows users to keep their local data on their own devices and only share the intermediate model parameters, which helps protect their raw data. However, despite these measures, it may not provide sufficient privacy guarantees [2, 3].

For privacy reasons, one desirable property of a federated learning platform is the users’ “right to be forgotten” (RTBF), which has been explicitly stated in the European Union General Data Protection Regulation (GDPR) [4] and the California Consumer Privacy Act (CCPA) [5]. That is, a user has the right to request deletion of his private data and its impact on the trained model, if he no longer desires to participate in the platform. Users may seek to leave a platform for a variety of reasons. For example, they may feel that the benefits from the platform are not sufficient to compensate for their potential privacy leakage from participation. Furthermore, until they participate in the platform, they may not have full knowledge of these benefits and costs due to incomplete information about other users’ data. For instance, users’ privacy costs in federated learning depend on how unique their data is [6], which they can infer from their training loss after training [7].

To remove data from a trained federated learning model, the concept of federated unlearning has recently been proposed [8]. In this concept, after some users request to revoke their data, staying users will perform additional training or calculations to eliminate the impact of leaving users’ data and obtain an unlearned model. A simple yet costly approach is to retrain the model from scratch with the requested data being removed from the training dataset [9]. To be more efficient and effective, existing literature (e.g., [10, 7, 11]) focused on alternative federated unlearning methods that obtain a model similar (in some distance metrics) to a retrained model with lower computational costs. However, these studies usually assumed that users are willing to participate in federated learning and unlearning. This assumption may not be realistic without proper incentives since users incur various costs during the training process (e.g., time, energy, and privacy costs). Our goal in this paper is to develop incentive mechanisms to help retain valuable leaving users and create a sustainable learning platform for both the users and the server.

To design the incentive mechanism for federated learning and unlearning, there are several challenges to tackle. First, different leaving users will lead to different unlearned model performances and unlearning costs, the relationship among which is still an open problem yet essential for designing incentives. Second, it is difficult for the server to design incentives for a large number of heterogeneous users, when users have multi-dimensional private information (e.g., training costs and privacy costs) and unknown information (e.g., users’ training losses before federated learning). Third, unlearning incentives for retaining valuable leaving users require careful design. High incentives may encourage strategic users to intentionally request revocation to obtain retention rewards, while low incentives may fail to retain valuable users. It is also crucial for the server to distinguish between high-quality leaving users (e.g., with rare and valuable data) and low-quality ones (e.g., with erroneous data), both of which can lead to high training losses. Fourth, both learning and unlearning incentives affect the server’s and users’ payoffs but are determined in different stages - before or after federated learning. Meanwhile, there are different information asymmetry levels in each stage, as the federated learning process can reveal some information such as users’ training losses and contributions. Thus, the mutual influence of the incentives and dynamic information asymmetry further complicate the incentive mechanism design.

The above discussion motivates us to answer the following interesting question:

Furthermore, although federated unlearning is important for protecting users’ right to be forgotten and data privacy, no work has studied whether allowing federated unlearning is economically beneficial to the server or users by comparing the following two scenarios:

• •

  Unlearning-Allowed Scenario. The federated learning server allows users to revoke data and will perform federated unlearning;

• •

  Unlearning-Forbidden Scenario. The federated learning server does not allow users to revoke data after they decide to participate in the federated training.

Different unlearning scenarios will lead to different optimal incentive mechanisms, as well as the server’s and users’ payoffs. When unlearning is optional, studying the superiority of each scenario will facilitate the server’s and users’ selection. The performance comparison also provides insights into the policy design of a market regulator. This motivates the second key question of this paper:

We summarize our key contributions below.

• •

  Incentive mechanism design for federated learning and unlearning. We propose a four-stage Stackelberg game to analyze the optimal incentives of the server and the optimal strategies of users within this game. To the best of our knowledge, this is the first analytical study of incentive mechanisms for federated learning and unlearning.

• •

  Theoretical characterization of global model accuracy and unlearning communication rounds. We theoretically derive bounds on the global model optimality gap given non-IID data for federated learning algorithms (Scaffold [12] and FedAvg [1]) and the number of global communication rounds required for a federated unlearning method.

• •

  Optimal incentives and revocation decisions under multi-dimensional incomplete information. Due to the complex interaction, users’ multi-dimensional private information, and dynamically updated knowledge, the server’s optimization problem in Stage I of the four-stage game is highly complex. We summarize users’ multi-dimensional heterogeneity into several one-dimensional metrics and develop an efficient algorithm with linear complexity, to handle the exponentially large number of possible cases involved in optimal mechanism design. We also identify and analyze a supermodular game among the users to obtain their optimal data revocation decisions.

• •

  Comparison of unlearning-allowed and unlearning-forbidden scenarios. We show that (i) when users’ unlearning costs in the unlearning-allowed scenario are large, the server needs to compensate them with large incentives and thus prefers the unlearning-forbidden scenario. Surprisingly, users prefer the unlearning-allowed scenario where they have large costs, due to the excess rewards they obtain under information asymmetry. (ii) When users’ perceived privacy costs in the unlearning-forbidden scenario are large, the server prefers the unlearning-allowed scenario while users prefer the unlearning-forbidden scenario for similar reasons as in (i).

• •

  Insights and Performance Evaluation. We show that high costs and training losses motivate users to leave, while the server will retain the leaving users who make significant contributions to model accuracy but not necessarily low training losses, as small losses of retained users will reduce privacy costs yet increase unlearning costs. We numerically show that compared with state-of-the-art benchmarks, our proposed incentive mechanism decreases the server’s cost by up to 53.91%. Moreover, the results demonstrate that it is beneficial for the server to retain valuable leaving users and jointly optimize the federated learning and unlearning incentive mechanisms.

The concept of machine unlearning, which refers to the process of removing the impact of a data sample from a trained model, was first introduced by Cao et al. in 2015 [13]. Most related literature was about centralized machine unlearning (e.g., [9, 14]), in which the unlearned model (not retrained from scratch) was trained on summarized (e.g., aggregates of summations) or partitioned subsets rather than individual training samples. As a result, the model only needed to be updated on the subset(s) of data that are associated with the requested samples.

Centralized unlearning methods are not suited to federated learning, due to (i) lack of direct data access, (ii) the fact that the global model is updated based on the aggregated rather than the raw gradients, and (iii) the possibility that different users may have similar training samples [7]. This motivated the emergence of federated unlearning, which focuses on deleting the impact of revoked data in federated learning.

Only a few studies proposed federated unlearning mechanisms using methods such as gradient subtraction (e.g., [10, 8]), gradient scaling (e.g., [7]), or knowledge distillation (e.g., [11]). Albeit with good numerical performance, there is no theoretical guarantee of these proposed federated unlearning methods. To fill this gap, we propose theoretical bounds on the model optimality gap and communication rounds for one approach to federated unlearning in this paper.

Furthermore, there is a wide spectrum of literature on incentive mechanisms for various systems, including crowdsensing (e.g., [15]), wireless networks (e.g., [16]), data trading (e.g., [17]), and energy sharing (e.g., [18]). Some important work studied incentive mechanism design for federated learning to discourage valuable clients from leaving (e.g., [19, 20, 21, 22]). However, very few of them considered users’ multi-dimensional private information (e.g., [20]), and none of them incorporated the unique aspects of federated unlearning (e.g., unlearning costs) or the dynamics of users’ payoffs (e.g., pre-/post-training and before/after some users leave). This paper is the first to focus on incentive mechanism design for both federated learning and unlearning.

The rest of the paper is organized as follows. In Section 2, we characterize the models of federated learning and unlearning. The system model is described in Section 3. We give the optimal incentive mechanisms in the unlearning-allowed and unlearning-forbidden scenarios in Sections 4 and 5, respectively. We provide simulation results in Section 6 and conclude in Section 7.

Consider an example of data $(x_{a},y_{a})$, where $x_{a}$ is the input (e.g., an image) and $y_{a}$ is the label (e.g., the object in the image). The objective of learning is to find the proper model parameter $w$ that can predict the label $y_{a}$ based on the input $x_{a}$. Let us denote the prediction value as $\tilde{y}(x_{a};w)$. The gap between the prediction $\tilde{y}(x_{a};w)$ and the ground truth label $y_{a}$ is characterized by the prediction loss function $f_{a}(w)$. If user $i$ selects a set of local data with data size $d_{i}$ to train the model, the loss function of user $i\in\mathcal{I}$ is the average prediction loss on all his training data:

The purpose of federated learning is to compute the model parameter $w$ by using all users’ local data. The optimal model parameter $w^{*}$ minimizes the global loss function, which is an average of all users’ loss functions [12, 23]:¹¹1This model treats each user equally. Some papers (e.g., [1]) adopted another objective, a weighted sum of all users’ losses, where the weights (i.e. $d_{i}/\sum_{i=1}^{I}d_{i}$) reflect the differences in data size. The two objectives are equivalent when users’ data sizes are the same. Our results can be easily extended to the weighted case.

A federated learning process maps users’ data into a model space, while a federated unlearning process maps a learned model, users’ data set, and the data set that is required to be forgotten into an unlearned model space. The goal of federated unlearning is to make the unlearned model have the same distribution as the retrained model (i.e., retrained from scratch using the remaining data).²²2The distribution is due to the randomness in the training process (e.g. randomly sampled data and random ordering of batches).

A natural method for federated unlearning is to let the remaining users (excluding leaving users) continue training from the learned model $w^{*}$, until it converges to a new optimal model parameter $\tilde{w}^{*}$ that minimizes the global loss function of remaining users:

where $\mathcal{I}_{leave}$ is the set of users who leave the system through federated unlearning. This method is typically more efficient than training from scratch, as the minimum point may not change much after some users leave.

Given the objectives of federated learning and unlearning, we analyze the model accuracy gap and unlearning time in the following.

We use two widely adopted algorithms, Scaffold[12] and FedAvg [1], as the federated learning algorithms when deriving the optimality gap of the global model. In each local iteration of the algorithm, every user computes a mini-batch gradient with batch size $s_{i}$. A batch or minibatch refers to equally sized subsets of the training dataset over which the gradient is calculated. In this paper, we consider the widely adopted setting that users’ batch sizes $\{s_{i}\}_{i\in\mathcal{I}}$ are in the same proportion to their data sizes $\{d_{i}\}_{i\in\mathcal{I}}$ (i.e., $s_{i}=\iota d_{i},\forall i\in\mathcal{I},\iota\in(0,1)$) [9, 24, 20].

The following proposition presents bounds on the optimality gap for the global models trained with Scaffold or FedAvg:

The proof of Proposition 1 is given in Appendix A in the technical report [25]. As a large optimality gap $\|w_{t}-w^{*}\|^{2}$ means a high accuracy loss of the global model, Proposition 1 presents a relationship between the expected global model accuracy loss and the users’ data sizes. As shown in (6) and (7), the expected accuracy loss of the global model decreases in the users’ training batch sizes $\{s_{i}\}_{i\in\mathcal{I}}$ (and thus data sizes $\{d_{i}\}_{i\in\mathcal{I}}$). Moreover, we explain two asymptotic cases of (6) and (7) for better understanding. When the initial point is optimal (i.e., $w_{0}=w^{*}$), the bound does not go to zero due to sample randomness. When batch size $s_{i}$ is large enough, the randomness is then highly reduced and the bound is controlled by the initialization of the algorithm, i.e., the farther the initial point $w_{0}$ is from the optimal solution $w^{*}$, the more iterations are needed.

Then, after applying the result in Proposition 1 to the natural unlearning model introduced in Section 2.2, we have the following proposition about federated unlearning rounds:

The proof of Proposition 2 is given in Appendix B in the technical report [25]. Each user’s gradient $\|\nabla F_{i}(w^{*})\|$ can represent his training loss (denoted as $\ell_{i}$) because the calculated gradient increases in the loss. Hence, Proposition 2 reveals the relationship between the number of communication rounds required for federated unlearning and the training losses of leaving users. As indicated in (8), a larger total training loss of the leaving users $\sum_{i\in\mathcal{I}_{leave}}\ell_{i}^{2}$ (i.e., a larger $\sum_{i\in\mathcal{I}_{leave}}\|\nabla F_{i}(w^{*})\|^{2}$) requires more communication rounds $T_{unlearn}$ to achieve unlearning.

We will apply the derived results about model accuracy loss and unlearning rounds in building the system model in the next section.

We consider a set $\mathcal{I}\triangleq\{1,2,...,I\}$ of users in the system with two-dimensional private information: marginal cost for training effort $\theta$ and marginal perceived privacy cost $\xi$. We refer to a user with $(\theta_{j},\xi_{j})$ as a type $j$ user. We further assume that the $I$ users belong to a set $\mathcal{J}\triangleq\{1,2,...,J\}$ of $J$ types. Each type $j$ has $I_{j}$ users, with $\sum_{j\in\mathcal{J}}I_{j}=I$. The total number of users $I$ and the number of each type $I_{j}$ are public information, but each user’s specific type is private information.⁴⁴4The server can have knowledge about statistics of type information through market research and past experiences, but it is hard for it to know each user’s private type.

Under private information, it is difficult for the server to predict users’ strategies. To this end, we propose to design a contract mechanism for the server to elicit information.

We use a multi-stage Stackelberg game to model the interaction between the server and users in each of the two scenarios.

At each stage, every user or the server seeks to maximize his expected payoff (or minimize his expected cost) based on his current knowledge. As knowledge updates occur between stages, the payoffs of the users or the server (maximization or minimization objectives respectively) take different forms in each stage.

Similar to Stages I and II in the unlearning-allowed scenario, we now specify the users and the server’s payoffs in the unlearning-forbidden scenario. The difference here is that there are no unlearning considerations (e.g., data revocation or retention incentives). We will use the superscript ^′ for the unlearning-forbidden scenario to differentiate the notations in the two scenarios.

Given the server’s contract $\bm{\phi}$ in Stage I, the users’ contract item choices in Stage II, and the users’ revocation decisions $\mathcal{I}_{u}$ in Stage III, the server needs to determine which users to retain $\mathcal{I}_{r}$ and the corresponding retention incentives $\{r^{U}_{i}\}_{i\in\mathcal{I}_{r}}$ in Stage IV.

As we discussed in Section 3.3.4, the server seeks to minimize the cost in (17) in Stage IV, which can be formulated as follows:

The constraint (20b) is to ensure that the retention incentives are enough to make the target users stay in the system. The left-hand side of the constraint is a user $i$’s payoff after accepting the retention incentive (including unlearning reward, learning reward, learning cost, privacy cost, and unlearning cost), and the right-hand side is his payoff of not accepting (i.e., he has to return the learning reward to the server and only has sunk learning cost).

The following proposition presents the solution to Problem 1.

The proof of Proposition 3 is given in Appendix C in the technical report [25]. Proposition 3 highlights a trade-off regarding the retention of users and their training losses. Users who have larger training losses incur higher privacy costs and thus require higher incentives to retain (indicated by $\gamma\xi_{i}\ell_{i}d_{i}$ in (21)). However, retaining such users also helps reduce the unlearning costs since the objective in (21) increases with the aggregated loss of the leaving users. Furthermore, the server has the incentive to retain users who contribute more to the model accuracy, which corresponds to smaller values of $v_{i}$. Additionally, users with smaller marginal costs $\theta_{i}$ and $\xi_{i}$ are also desirable to reduce unlearning incentives.¹²¹²12Note that in (21), the server may not only include users with a negative value in the brackets, as retaining some users with positive values may reduce the server’s objective through the aggregated losses. This is an integer programming problem with complexity $\mathcal{O}(2^{I_{u}})$. When the number of leaving users $I_{u}$ is large, the server can reduce the complexity by classifying the leaving users into several categories to retain, each category with similar contributions and costs.

Considering the server’s optimal retention strategies in Stage IV, each user $i$ decides whether to revoke his data in Stage III given the information announced in Stages I and II.

Based on the server’s optimal retention incentives (22) and the user’s payoffs in Stage III (i.e., the updated (13) and (14) with realized losses), a user $i$’s payoff after revoking data is $-\theta_{i}d_{i}T$, regardless of whether the user is retained by the server or not. Thus, user $i$’s expected payoff in Stage III can be rewritten as

where $x_{-i}=\{x_{k}\}_{k\in\mathcal{I}\backslash\{i\}}$ is the revocation decisions of all users except user $i$ and $q=\mathbb{E}[q_{j}]$ is the expected retention rate of all users, as users do not know each other’s type.¹³¹³13Here we use the historical retention rate $q$ to calculate the expected payoffs instead of the retention rate obtained in Stage IV (i.e., ${|\mathcal{I}_{r}^{*}|}/{|\mathcal{I}_{u}|}$). This is because users do not know their federated Shapley values and cannot calculate $\mathcal{I}_{r}^{*}$. If they calculate the expectation $\mathbb{E}[\mathcal{I}_{r}^{*}]$ based on type statistics, according to (21), the result will be user type retention instead of user retention (e.g., retain all type-i users and not retain all type-$j$ users regardless of different data distributions and losses of the same type of users), which is not true. Conversely, historical rates ranging between $[0,1]$ allow for more realistic partial retention of same-type users. Therefore, we assume that the users have a belief at this stage in the retention rate which is the same as the historical rate. In the following analysis in Stages I and II, we will also use the historical rates for calculating the expected cost/payoffs for similar reasons. As shown in (23), each user’s payoff depends on the other users’ revocation decisions, so users engage in a non-cooperative game in Stage III.

We formally define users’ non-cooperative sub-game as follows.

The following proposition characterizes the Nash equilibrium (NE) of Sub-Game 1:

The proof of Proposition 4 is given in Appendix D in the technical report [25]. Based on Algorithm 1, we can find the set of users who revoke data in one NE, i.e., $\mathcal{I}_{u}^{*}=\{i:x_{i}^{*}=1,i\in\mathcal{I}\}$. Basically, Algorithm 1 corresponds to doing best response updates of the users starting from all users choosing not to revoke (i.e., 0). It is well known that for supermodular games, these updates will converge monotonically to a NE. Algorithm 1 will terminate within $I$ iterations.¹⁴¹⁴14We can also initialize all the users’ decisions as 1 and check whether there exists a user who wants to change his action from 1 to 0 for payoff improvement. If the equilibrium is the same as that found by Algorithm 1, it is the unique NE, as Game 1 is a supermodular game. The resulting equilibrium strategies and insights will be illustrated through simulation in Section 6.2.2.

Based on the analysis in Stages III and IV, a type-$j$ user’s expected payoff in Stage II (15) can be rewritten as:

where

and $D(\ell_{m})$ is the variance of type-$m$ users’ training losses.

Each type-$j$ user in Stage II will choose a contract item that gives him a maximum non-negative expected payoff, leading to the constraints that the server needs to consider in Stage I.

In Stage I, the server designs a contract to minimize its expected cost, considering the results in Stages II-IV.

When designing the contract, the server needs to ensure that each user achieves a non-negative payoff, so that the user will accept the corresponding contract item. Moreover, since the server does not know each user’s type in Stage I, the server also needs to make a user choose the contract item intended for him (i.e., the user does not misreport his type).¹⁵¹⁵15Revelation principle demonstrates that if a social choice function can be implemented by an arbitrary mechanism, then the same function can be implemented by an incentive-compatible-direct-mechanism (i.e. in which users truthfully report types) with the same equilibrium outcome. Thus, requiring IC will simplify the mechanism design without affecting optimality. In other words, a contract is feasible if and only if it satisfies Individual Rationality (IR) and Incentive Compatibility (IC) constraints:

Considering the constraints in Definitions 1 and 2, the server in Stage I seeks to design the contract $\bm{\phi}=\{(d_{j},r^{L}_{j})\}_{j\in\mathcal{J}}$ to minimize its expected cost in (11), which is rewritten as follows after combining the results in Stages II-IV:

Solving Problem 2 involves two challenges. First, users’ multi-dimensional heterogeneity leads to a challenging multi-dimensional contract design for the server. We will simplify the analysis by summarizing users’ multi-dimensional heterogeneity into several one-dimensional metrics, to guide the server’s design of the optimal rewards and data sizes in the contract. Second, as the total number of IR and IC constraints is large (i.e., $J^{2}$), it is challenging to obtain the optimal contract directly. To overcome such a complexity issue, we will first transform the constraints into a smaller number of equivalent ones (Lemma 1). Then, for any given data size $\bm{d}=\{d_{j}\}_{j\in\mathcal{J}}$, we derive the server’s optimal reward $\{r^{L*}_{j}(\bm{d})\}_{j\in\mathcal{J}}$ (Lemma 2) in Section 4.4.1. Finally, we derive the optimal data size $\bm{d}^{*}$ (Proposition 5 and Theorem 1) in Section 4.4.2.