Price of Stability in Quality-Aware Federated Learning

We consider $N$ clients, denoted by $\mathcal{N}=\{1,2,\ldots,N\}$. Each client $n\in\mathcal{N}$ has a local dataset $\mathcal{D}_{n}$ with $d_{n}$ data samples. We focus on supervised learning tasks in FL, where each data sample consists of a set of features and a label. These clients cooperate in training a global model that maps from feature to label with their local datasets. We consider a scenario where the utility of each client relies on the accuracy of the global model, e.g., network operators can use the global model for product improvement to earn revenues.

There may exist label noise/errors in clients’ datasets, i.e., the labels of some data samples may be incorrect. Let $\epsilon_{n}$ denote the noise rate of client $n$’s dataset, i.e., the fraction of client $n$’s data samples that have incorrect labels. Suppose clients are able to rectify incorrect labels with some costs [5]. Let decision variable $x_{n}\in[0,\epsilon_{n}]$ denote the noise rate of client $n$’s dataset after label correction, and $\bm{x}\triangleq\left(x_{n},n\in\mathcal{N}\right)$. Then, the average noise rate after correction among all clients is given by

After the FL process, the global model has an accuracy of

where $g(\cdot)$ is a concave and decreasing function. Such assumptions on $g(\cdot)$ are supported by the experimental results under random flipping and instance-dependent noise in Section V. Intuitively, the average noise rate (rather than the noise rate of any arbitrary client) affects the accuracy of the global model. When the average noise rate is higher, the accuracy is lower. Meanwhile, the marginal decrease of the accuracy is increasing in the average noise rate.

From a social perspective, correcting labels can improve the global model accuracy. From a client’s perspective, it incurs additional costs. Thus, the clients’ individual interests may conflict with the goal of social welfare maximization.

Given decision variable $\bm{x}$ and accuracy $A\left(\bm{x}\right)$, the utility of client $n\in\mathcal{N}$ is given by

where $w_{n}>0$ is the unit revenue of client $n$. For example, when clients are network operators, $w_{n}$ is the revenue that the operator can earn per accuracy improvement [7, 10].

Given decision $x_{n}$, client $n$ has a cost for label correction:

We assume that $f(\cdot)$ is a strictly convex and decreasing function. Intuitively, the label correction cost is proportional to the size of the dataset $d_{n}$. Meanwhile, as the noise rate of the dataset decreases, the cost of reducing the same noise rate of the dataset increases. If the dataset has not been corrected (i.e., $x_{n}=\epsilon_{n}$), the cost is zero. We show a specific formulation of $f(\cdot)$ with practical insights in Section V.

The payoff function of a client $n\in\mathcal{N}$ is defined as the difference between its utility and cost:

From a social perspective, clients should optimize the average noise rate after correction to maximize the social welfare. The socially optimal solution $\bm{x}^{\textsc{swm}}$ is given by

However, clients are usually self-interested. The interaction among clients is modeled as a non-cooperative game.

The stable state of the quality-aware FL system with self-interested clients corresponds to the situation under Nash equilibrium (NE) $\bm{x}^{\textsc{ne}}$ of Game 1, i.e., the strategy profile such that no client has the incentive to deviate from. Let $\bm{x}_{-n}\triangleq(x_{i},i\in\mathcal{N}\setminus\{n\})$ denote the decisions of all clients except client $n\in\mathcal{N}$. For presentation simplicity, we use notations $P_{n}(\bm{x})$ and $P_{n}(x_{n},\bm{x}_{-n})$ interchangeably.

We aim to analyze the label denoising strategies of clients and determine the PoS of quality-aware FL systems.

Since problem (6) is a convex programming problem, we determine its optimal solution by checking the KKT conditions. Specifically, let $h^{\textsc{swm}}_{n}(x_{n})\triangleq{\partial(\sum_{i\in\mathcal{N}}P_{i}\left(\bm{x}\right))}/{\partial x_{n}}$ denote the partial derivative of the social welfare with respect to $x_{n}$. Let $\bar{w}\triangleq\sum_{i\in\mathcal{N}}w_{i}/N$ and $\bar{d}\triangleq\sum_{i\in\mathcal{N}}d_{i}/N$. Thus,

which is strictly decreasing in $x_{n}$ due to the strict convexity of $f(\cdot)$ and the concavity of $g(\cdot)$. We use $x^{\circ\textsc{swm}}_{n}$ to denote the unique zero point of $h^{\textsc{swm}}_{n}(x_{n})$. The optimal solution to problem (6) is given as follows.

Lemma 1 can be proven by analyzing the impact of system parameters $\bar{w}$, $\bar{d}$, and $d_{n}$ on the zero point of $h^{\textsc{swm}}_{n}(x_{n})$ in (8). The detailed proof is given in [11].

Lemma 1 shows that if the average unit revenue of the clients (i.e., $\bar{w}$) is larger, then each client $n$ should choose a smaller noise rate $x_{n}$ (i.e., a higher data quality) to maximize the social welfare. Moreover, if the average number of data samples is smaller, then a smaller noise rate $x_{n}$ should be chosen by the clients in order to maintain sufficient data samples with correct labels. However, given a fixed average number of data samples, the increase in the number of data samples of a client does not affect the optimal solution.

According to Lemma 1, we further derive the necessary condition for the optimal solution $\bm{x}^{\textsc{swm}}$. The condition can provide additional insights and will be used for the algorithm design in Section IV-A. We first present a lemma to support our analysis, with the proof given in [11].

Now, we can derive the necessary condition for $\bm{x}^{\textsc{swm}}$.

Based on Proposition 1, to maximize social welfare, clients need to give priority to reducing the noise rate of those clients’ datasets with the highest noise rate. Meanwhile, Proposition 1 inspires the efficient algorithm design for deriving the optimal solution in Section IV-A.

We derive the NE of Game 1 based on the best response of each client $n\in\mathcal{N}$. Specifically, let $h^{\textsc{ne}}_{n}(x_{n})\triangleq{\partial P_{n}(\bm{x})}/{\partial x_{n}}$ denote the partial derivative of the payoff function of client $n$ with respect to $x_{n}$. Thus,

which is strictly decreasing in $x_{n}$ due to the strict convexity of $f(\cdot)$ and the concavity of $g(\cdot)$. Let $x^{\circ\textsc{ne}}_{n}$ denote the zero point of $h^{\textsc{ne}}_{n}\left(x_{n}\right)$. The NE is determined as follows.

Proposition 2 is proven based on the best response of the clients and the impact of system parameters on the zero point of $h^{\textsc{ne}}_{n}\left(x_{n}\right)$. The proof of uniqueness is given in an online technical report [11]. In contrast with the optimal solution in Lemma 1, client $n$ cares about its own unit revenue, i.e., it reduces its noise rate under a larger $w_{n}$. In addition, similar to the optimal solution, if the average number of data samples decreases, client $n$ has the incentive to reduce its noise rate to improve the accuracy of the global model.

We characterize the PoS¹¹1We use the term “PoS” to refer to the performance reduction due to the self-interested clients. In Section V, we will follow the conventional mathematical definition of PoS and define it as the ratio of the maximum social welfare to the social welfare under the unique NE in our work. by showing that when compared wtih the optimal solution to problem (6), the NE of Game 1 leads to a higher average noise rate and hence a lower global model accuracy. Note that determining such an analytical result is not straightforward, because the socially optimal solution is not the solution that maximizes the model accuracy due to the fact that higher accuracy is at the expense of higher correction costs for the clients. Specifically,

Based on Lemma 3, we derive the main result on accuracy.

Theorem 1 implies that, when compared with maximizing the social welfare, clients always obtain a global model with lower accuracy by considering their own interests at NE.

Moreover, we present the PoS in social welfare for motivating our experiments in Section V. This result is obtained based on the definition of social welfare maximization.

Based on Lemma 1, we can determine the optimal solution to problem (6) by finding the threshold $\theta$. Let $x_{n}(\theta)\triangleq\min\left(\theta,\epsilon_{n}\right)$, and $\bm{x}(\theta)\triangleq(x_{n}(\theta),n\in\mathcal{N})$. Define a function $H\left(\theta\right)\triangleq\text{SW}\left(\bm{x}(\theta)\right)$. Then, we formulate a problem with respect to $\theta$ as follows:

Given the optimal solution $\theta^{\textsc{swm}}$ to problem (14), we can obtain the optimal solution to problem (6) based on (11).

To solve problem (14), we derive the property of $H\left(\theta\right)$.

The proof is given in the online technical report [11]. Based on Lemma 5, since $H(\theta)$ is a unimodal function with respect to a single-dimensional variable $\theta$, we can find its maximum point by ternary search, based on which we can determine the optimal solution to problem (6) using Proposition 1. We present the algorithm in Algorithm 1. The time complexity for obtaining optimal $\theta$ is $\mathcal{O}(N\log({1}/{\mu}))$, where $\mu$ denotes a pre-defined threshold that bounds the gap between algorithm output and ground truth values of $\theta$.

According to (12), we propose a best response algorithm in Algorithm 2 to find the NE of Game 1. Sepcifically, given the decisions of other clients, each client alternatively updates its noise rate to maximize its payoff. The algorithm terminates until convergence, i.e., the decision update gap of every client is smaller than a predefined Convg_Thresh.

We first study how label noise affects FL in terms of convergence and generalization. Fig. 1 plots how the test accuracy of the global model changes with the training rounds (i.e., convergence). We observe that for both random flipping and instance-dependent noises, the existence of label noise slows FL convergence. Moreover, under random flipping, a large noise rate (e.g., $0.2$) causes overfitting. However, overfitting is not obvious under instance-dependent.

Fig. 2 plots how the test accuracy changes with the noise rate at round $50$ (i.e., generalization). We observe that the global model performance decreases in the error rate. Interestingly, we observe that instance-dependent noise is less harmful to the model accuracy. Furthermore, we use curve fitting to simulate the impact of noise rate on global model accuracy and obtain the results below:

• •

  Random flipping: The accuracy degradation across noise rate $\epsilon$ fits a linear function. In addition, Table I shows that given the same average noise rate, the heterogeneous noise rates of the clients do not have a significant impact on the accuracy. Based on the above observation, we adopt a linear formulation of $g(\bar{x}(\bm{x}))$ with respect to $\bar{x}(\bm{x})$ for random flipping:

  $$g\left(\bar{x}(\bm{x})\right)=\kappa\bar{x}(\bm{x})+g_{0},$$

  (15)

  where $\kappa<0$ and $g_{0}\in(0,1]$ correspond to the accuracy decreasing per unit of noise rate and the model accuracy under no label error, respectively.

• •

  Instance dependent: The accuracy degradation across noise rate $\epsilon$ approximately fits a quadratic function:

  $$g\left(\bar{x}(\bm{x})\right)=g_{2}\left(\bar{x}(\bm{x})\right)^{2}+g_{1}\bar{x}(\bm{x})+g_{0},$$

  (16)

  where $g_{2}<0$, $g_{1}<0$ and $g_{0}\in(0,1]$.

Note that the two fitted functions validate our assumption on $g(\cdot)$, which is a concave and decreasing function. In what follows, we will use the fitted functions to evaluate the PoS.

To study the PoS, we use the following function to help model the denoising cost (see (4)):

where $c<0$. Formulation (17) is determined based on an error correction method called FedCorr [5].²²2In each round of training, each client rectifies the data samples with incorrect labels using the recent training models. Assuming that with the model obtained in each training round, a fixed fraction of noisy data samples can be found, then the correction cost is given by (17). Let $\phi(\mu,\sigma,a,b)$ denote a truncated normal distribution with mean $\mu$, variance $\sigma$, and truncated range $[a,b]$. We consider $c=-1$,³³3Note that the relative values of $c$ and $w_{n}$ (rather than their absolute values) affect simulation results. We choose a unit cost for simplicity. $w_{n}\sim\phi(10^{6},10^{4},5\times 10^{5},1.5\times 10^{6})$, $\epsilon_{n}\in\{0,0.02,\cdots,0.2\}$ for $n\in\mathcal{N}$. Each experiment is repeated for 100 runs, and we show the averaged results. Algorithms 1 and 2 are used to compute the socially optimal solution and NE, respectively.

In Fig. 3, we compare the socially optimal solution (denoted by “SWM”) and NE in terms of model accuracy and the PoS in social welfare (i.e., the social welfare under SWM divided by that under NE). We observe that for both random flipping and instance-dependent noises, the model accuracy and social welfare under “SWM” are higher than that under NE.⁴⁴4In Figs. 3(c) and 3(d), a PoS that is larger than one implies a higher social welfare under SWM than that under NE. This observation is consistent with Theorem 1 and Lemma 4. Importantly, in Fig. 3(b), the PoS in social welfare is generally larger under higher noise rate. That is, the non-cooperative behavior of clients imposes a higher efficiency loss when they have noiser data. This calls for an effective incentive mechanism to reduce the gap between socially optimal solutions and the equilibrium outcomes. Perhaps counter-intuitively, in Fig. 3(d), the impact of unit revenue $w$ on the PoS relies on label noise. Under instance dependent, a larger unit revenue leads to a higher necessity for motivating cooperative behaviors among clients.