Incentivizing Data Collection from Heterogeneous Clients in Federated Learning

We want to thank the reviewer for their positive feedback and comments. We will address individual comments below.

Response to W1: Please see our responses to ``Question 1-4, 7, 8, 18”.

Response to W2: Please see our responses to ``Question 5, 11, 14”.

Response to W3: We would like to clarify that we are not proposing a looser upper bound. Compared to Example 1's upper bound of the divergence term ( $4\eta_t^2(E-1)^2G^2$), our bound shown in Lemma 4.2 ($64 \delta_k^2 (1+2\eta_t)^{2(E-1)} \eta_t^2 (E-1) G^2$) aligns consistently. We believe they are at least at the same tightness level. In this work, we mainly focus on exploring and understanding the impact of data heterogeneity on the convergence bound, instead of targeting a tighter upper bound or better proof techniques. The main of purpose of Lemma 4.2 is "we trying to build the connection between convergence and the Wasserstein distance”, where Wasserstein distance helps with quantifying the degree of non-iid in the local training data of an agent.

Response to W4: Thank you for pointing out this. To our knowledge, there currently aren't any existing methods or baselines available that we can use for comparison in our study. We would be grateful for any recommendations you could provide for suitable baselines.

Response to Q1: Sorry for any confusion. "Decentralized clients" in the context of federated learning or distributed systems refer to individual nodes, devices, or entities that operate independently of a central authority or location. Each client holds its own dataset and performs computations on this data locally. To prevent any misunderstandings in the revised version, we will refrain from using the term “decentralized”.

Response to Q2: Thank you for pointing out this. We will revise it as “Hence, the appropriate method to incentivize agents should take into account not only the size of the sample, but also the potential data heterogeneity.”

Response to Q3: A common limitation in existing studies is their focus on measuring each agent's contribution by the number of samples used, thereby encouraging the use of more data samples. These approaches tend to overlook the impact of data heterogeneity. Solely using sample size to evaluate contribution may not effectively reflect the quality of the data, especially in federated learning where data heterogeneity largely affects model convergence. Hence, an incentive mechanism that accounts for data heterogeneity is essential. From the learner's perspective, our proposed mechanism facilitates more optimal model convergence compared to existing methods. For example, at the same sample size level, our model's convergence is significantly faster compared to existing mechanisms. This improved performance is largely due to our approach effectively addressing data heterogeneity. This is evidenced by the performance results shown in Figure 1.

Response to Q4: We admit that the notion of the Wasserstein distance has been applied in various fields, not just limited to federated learning. However, to our knowledge, there is no existing similar work that has specifically applied the Wasserstein distance to specifically assess the impact of data heterogeneity on the convergence bound in federated learning. In federated learning, "label shift" is the most common non-iid setting, which refers to a scenario where the distribution of labels (or output classes) in the training data varies across different clients over time. Therefore, the Wasserstein distance serves as a practical and important metric for measuring the label distribution, particularly in classification problems. This distance measures how much one distribution needs to be altered to resemble another, making it highly relevant for evaluating discrepancies in label distributions across different datasets. Apologies for any misunderstanding regarding the use of 'essential'. We will replace it with 'important'.

Response to Q5: Limited by paper space, we slightly introduce the Wasserstein distance in the definition of $\delta_k$.The Wasserstein distance is a well-known measure of the distance between two probability distributions. It is a concept derived from the field of optimal transport, where it represents the minimum "cost" required to transform one distribution into another. This metric provides a more intuitive way to compare distributions, consistent with our objective to reduce the degrees of non-iidness by adding additional samples.The 11-norm form of the Wasserstein distance is formally defined as $W_1(P, Q)= \inf _{\gamma \in \Gamma(P, Q)} \int\_{X \times Y} \|x-y\|_1 d \gamma(x, y)$, where $\|x-y\|_1$ is the l1-norm, calculating the absolute difference between points $x$ and $y$ in the distributions. We simply adapt this into a discrete distribution format, as illustrated in the definition of $\delta_k$. In our works, we mainly focus on classification problems, commonly encountered in federated learning. Therefore, the formulation of our $\delta_k()$ is defined over "I", which represents the number of classes in a classification problem.

Response to Q6: For classification problems, the support of the discrete probability distributions $p^k$ and $p^c$ is the proportion for the entire set of possible classes within the classification problem.

Response to Q7: This centralized setting refers to a scenario where data is aggregated in a single, central repository, in contrast to the distributed nature of federated learning where data is scattered across multiple clients. Typically, we would use the distribution of this ideal centralized setting $p^c$ as the iid distribution for federated learning and a benchmark to measure the degrees of non-iidness in clients' data, providing a reference point for comparing the data distribution across various decentralized clients. Owing to privacy concerns, accessing the iid distribution across agents is not possible. Thus, in federated learning, we often use the distribution $p^c$, derived from an ideal centralized setting, as the representative iid distribution. This serves as a standard for measuring the degrees of non-iidness in clients’ data, offering a basis for comparison across these distributed data sources. In practice, $p^c$ typically reflects the test distribution for performance evaluation from the learner's standpoint.

To assess the degree of non-IIDness in an agent's local training data without it being explicitly provided, one potential approach is to use statistical techniques to analyze the data's distribution. Given the definition of $\delta_k = \frac{1}{2}\sum_{i=1}^{I}|p^{(k)}(y=i) - p^{(c)}(y=i)|$, in practice, we can reasonably assume that statistical information of local datasets (especially label proportions $p^{(k)}(y=i), \forall i \in [I]$), is accessible to the learner without compromising privacy. Also, the learner can disclose the label proportions of the reference dataset or distribution $p^{(c)}(y=i), \forall i \in [I]$ to agents. This act effectively communicates a preference for iid settings to the agents. These assumptions allow for a straightforward assessment of the degrees of non-IIDness in the data.

Response to Q8: "Decreasing the degree of non-iid" implies that agents are incentivized to modify their local datasets to resemble more iid-like distributions. Specifically, this can involve incentivizing agents to contribute more data from minority classes instead of majority ones in their datasets. "A reduced cost" refers to the learner's aim to minimize the expenses incurred while motivating agents to decrease the non-iid degree of their data, thereby maximizing the learner's payoff.

Response to Q9: Apologies for missing explanations on these parameters. We will fix this in the revision. $f^* = f(w^*)$ indicates the optimal empirical risk. Then, $\overline{\mathbf{g}}\_t = \sum\_{k=1}^N p\_k \nabla F\_k(\mathbf{w}_t^k)$ represents the weighted sum of gradients of loss functions $F_k$ for each client $k$. Here, $\mathbf{w}_t^k$ are the model parameters for client $k$ at time $t$, and $p_k$ is the weight for each client. Similar to $\overline{\mathbf{g}}\_t$, \( \mathbf{g}\_t = \sum\_{k=1}^N p\_k \nabla F\_k(\mathbf{w}\_t^k, \xi\_t^k) includes a stochastic component $\xi\_t^k$, which typically represents a stochastic component such as a minibatch of data. In practice, $\mathbb{E}\mathbf{g}_t = \overline{\mathbf{g}}_t$.

Response to Q10: There is no extra difference between $L\_{x|y=i}$-Lipschitz and typical $L$-Lipschitz. In our notation, we use subscripts solely for denoting the class. More specifically, $\nabla\_{\mathbf{w}} \mathbb{E}\_{x|y=i} [\ell(x,\mathbf{w})]$ is $L_{x|y=i}$-Lipschitz continuous, i.e., $|| \nabla\_{\mathbf{w}} \mathbb{E}\_{x|y=i} [\ell(\mathbf{w}\_{t}^{k}, x)] -\nabla\_{\mathbf{w}} \mathbb{E}\_{x|y=i} [\ell(\mathbf{w}\_{t}^{k'}, x)] || \leq L\_{x|y=i} ||\mathbf{w}\_{t}^{k}-\mathbf{w}\_{t}^{k'}||$.

Response to Q11: Actually, $D_c$ is an auxiliary validation set, following the test set's data distribution. It's common to assume access to such a validation set for evaluating model performance. In our study, this set is solely used for evaluation purposes, meaning no extra information is introduced by incorporating the validation set.

Response to Q12: $\mathrm{Bound}(e)$ denotes the model's performance upper bound under agents' efforts $e$. For example, $\mathrm{Bound}(e)$ represents the upper bound as illustrated in Example 1. More details can be found in the definition of payoff functions.

Response to Q13: The ninety-ninety rule is a humorous aphorism that states: "The first 90 percent of the code accounts for the first 90 percent of the development time. The remaining 10 percent of the code accounts for the other 90 percent of the development time."

Response to Q14: Yes, the payment function $f()$ is required to be differentiable. This characteristic is essential for the concept of well-behaved utility functions, as outlined in Definition 5.1. It's quite common to assume that utility functions are well-behaved, such as being convex or smooth, when analyzing Nash equilibrium[1, 2, 3]. With this property, we can demonstrate that the best response function has a fixed point, which then serves as the equilibrium in our framework.

Response to Q15: Based on Assumption 5.1, we can determine the maximum and minimum values of $\partial f\left(e_k, e_{k^{\prime}}\right) / \partial e_k$ when $e_k=0$ and $e_k=1$, respectively. These extremal values correspond to the constants $d_k^1$ and $d_k^2$. More details can be found in the proof of Lemma B.1 of Appendix B.3.

Response to Q16: In Remark 1 of Appendix B.3, we additionally explore the existence of other common equilibriums in our context, including no one participating and free-riding. Briefly speaking, the Stackelberg game in game theory is a model describing a strategic interaction where players move sequentially rather than simultaneously. It consists of a leader and one or more followers, where the leader must anticipate how followers will respond to maximize its payoff, while followers act to maximize their own payoffs given the leader's action. Hence, the structure of the Stackelberg game is indeed well-suited to address the incentive issues in federated learning.

Response to Q17: Yes.

Response to Q18: Sorry for this typo. From the theoretical aspect [Theorem 5.3], a Nash equilibrium in our settings means that no agent can improve their utility by unilaterally changing their invested effort levels. Hence, the utility of agents could be viewed as an indicator of the equilibrium $\rightarrow$ if the utility of agents remains almost constant as the training progresses, an equilibrium is reached. As shown in Figure 3, the utilities of two randomly selected agents remain stable, indicating equilibrium. We can attribute the observed fluctuations to randomness for two reasons. Firstly, Figure 4 demonstrates that agents can achieve maximum utility despite randomness, indicating the utility function's stability. Secondly, in Remark 2 of Appendix B.3, we also discuss the consistency between randomly selecting one peer agent and the extension that takes an average over all other agents. Ideally, this would result in the utility curves being flat, represented as horizontal lines.

We want to thank the reviewer for their positive feedback and comments. We will address individual comments below.

Response to W1: Indeed, the above-mentioned statements are mild assumptions that can be reformulated as properties of utility functions. It's quite common to assume that utility functions are well-behaved, such as being convex or smooth, when analyzing Nash equilibrium [1, 2, 3]. For instance, in Definition 5.1, we formulate them as the bounds on the first-order gradient of the utility function, which are conditions that are generally easy to meet. Given this framework, discussing adversarial behaviors becomes less pertinent. Indeed, the Nash equilibrium acts as a safeguard against adversarial behaviors. It ensures that agents can maximize their utilities exclusively by exerting the optimal level of effort. This aspect highlights a significant advantage of the Nash equilibrium concept.

Response to W2: Thanks for this great question! Utilizing pre-trained weights in federated learning effectively suppresses the impact of data heterogeneity, resembling warm-start strategies or personalization. However, the influence of this heterogeneity could be reserved during continued training from these weights. It's important to highlight that theoretical analysis serves as the foundational starting point for our work. The theoretical framework might differ in the context of pre-trained weights. To integrate this scenario into our proposed model, we might need to introduce certain assumptions regarding the pre-trained weights.

Response to W3: [Pre-effort] To assess the degree of non-IIDness in an agent's local training data without it being explicitly provided, one potential approach is to use statistical techniques to analyze the data's distribution. Given the definition of $\delta_k = \frac{1}{2}\sum_{i=1}^{I}|p^{(k)}(y=i) - p^{(c)}(y=i)|$, in practice, we can reasonably assume that statistical information of local datasets (especially label proportions $p^{(k)}(y=i), \forall i \in [I]$), is accessible to the learner without compromising privacy. Also, the learner can disclose the label proportions of the reference dataset or distribution $p^{(c)}(y=i), \forall i \in [I]$ to agents. This act effectively communicates a preference for iid settings to the agents.These assumptions allow for a straightforward assessment of the degrees of non-IIDness in the data.

[Post-effort] Besides, from the perspective of the learner, in the context of a complete-information game, the learner can assess post-effort $\delta_k$ via the Nash equilibrium.

[1] One for one, or all for all: equilibria and optimality of collaboration in federated learning, ICML 2021.

[2] Mechanisms that incentivize data sharing in federated learning, arXiv preprint, 2022.

[3] Collaboration equilibrium in federated learning, SIGKDD 2022.

We want to thank the reviewer for their positive feedback and comments. We will address individual comments below.

Response to W1: We would like to clarify that the four plots presented in Section 6 comprehensively demonstrate our work's core contributions. These plots not only validate the theoretical analysis detailed in Section 4 but also effectively evaluate the proposed incentive mechanism.

Our theoretical framework forms the basis of our study, especially in validating Theorem 4.3, which is crucial for developing score functions to incentivize agents. Figures 1 and 2 empirically validate the heterogeneity in performance and the disparity among agents, consistent with our theoretical insights.

Additionally, Theorem 5.3 indicates that a Nash equilibrium leads to stable utilities against individual effort changes, as shown by the steady utilities in Figure 3, indicating equilibrium. Figure 4 further illustrates the impact of effort changes on utility, emphasizing our incentive mechanism's effectiveness. This also demonstrates the greater stability of the utility function. Despite the variation caused by random peer selection, the utility at optimal effort levels is higher on average compared to other levels.

In Appendix C, we also provide additional experimental results. Specifically, we demonstrate heterogeneous efforts using another common metric for non-iid data: the number of classes in local datasets. Additionally, we conduct evaluations using a standard data partitioning approach, where the entire dataset is evenly divided among agents, followed by sampling from these local datasets. These corresponding performance results are consistent with the previous results.

Response to W2: Given Theorem 5.3, a Nash equilibrium in our settings means that no agent can improve their utility by unilaterally changing their invested effort levels. Consequently, the utility of agents can serve as an important measure to indicate or confirm the presence of an equilibrium. As shown in Figure 3, the utilities of two randomly selected agents remain stable, which indicates an equilibrium. Specifically, the existing variation of utility mainly results from the randomness of selecting peers.

Response to W3: Thank you for highlighting this. It's possible for agents to possess similar data samples, especially when sourcing data from the internet. For example, this similarity can often occur in situations where agents collect publicly available data, such as commonly used datasets or information from widely accessed web sources. In Appendix C.2, we also extend our performance evaluation using other non-iid metrics, like the number of classes. Additionally, we consider a general setup where the entire dataset is evenly partitioned among agents, followed by sampling from these local datasets, to further validate our findings.

In response to your concern, we are conducting more experiments following the same data partitioning setup as outlined in Appendix C.2. However, we are considering a modification: instead of the uniform distribution for minority classes as used in Appendix C.2, we're looking at implementing long-tailed or exponential distributions for these classes. This change is aimed at amplifying the non-iid characteristics in our experiment. These results will be updated to the revision before the rebuttal deadline.

Response to W4: Yes, clients will resample data from the entire dataset at each round to compose their local datasets, while maintaining the same level of non-IIDness.

Response to Q1: Note that the introduced randomness (randomly selected peers) serves as an effective tool to circumvent the coordinated strategic behaviors of most agents. In Remark 2 of Appendix B.3, we also discuss the consistency between randomly selecting one peer agent and the extension that takes an average over all other agents. Ideally, in such a scenario, the utility curves for the agents would appear as horizontal lines.

Response to Q2: Utility is not dependent on training performance, as it is derived from theoretical calculations. For clarity, in this paper, the utility function is defined as $u_k(e_k) \triangleq \mathrm{Payment}_k(e_k) - \mathrm{Cost}_k(e_k) =\frac{1}{\mathrm{ Upper\_Bound}(F_c(\mathbf{w}^k)- F_c(\mathbf{w}^{k'})) } - c_k \cdot d(|\delta_k(0)- \delta_k(e_k)|)$. It represents the collective effort level of agents, which correlates more closely with their final performance. Therefore, the noise indeed affects the relative performance between two client models but would not influence the computed utility.

Thank you for your patience. We have completed the additional experiments as previously discussed, using long-tailed distributions for minority classes as outlined in Appendix C.2. The corresponding results shown in Figures 7–10 are consistent with those illustrated in Figures 1–2. The results have been updated in the revised manuscript, addressing your concerns. Thank you for your patience and valuable feedback.

Response to W1: In our paper, the term "effort $e_k$" refers to the level of effort exerted by a client in collecting additional data samples, with the primary objective of maximizing utility. In fact, agents can decrease the non-iid degree of their data by contributing their data with a preference for an IID setting. For example, agents can be incentivized to provide data samples for minority classes rather than for majority classes in their local datasets. It's common and rational to incentivize agents to offer more/high-quality data, known as data sharing. From the perspective of data-sharing, agents may exert effort to supply more data samples [1, 2]. Our work advances the field by establishing a preferred method for data collection in data-sharing. Therefore, from other perspectives, agents are incentivized to use their data strategically rather than merely contributing all their local data immediately.

Response to W2: Though it seems less practical than the incomplete game, studying complete information games is a standard and key practice that provides vital theoretical insights into strategic interactions. Besides, the complete game is reasonable because most of the complete information is available [1, 2]. In fact, agents only know the class proportion of the true central distribution, rather than full information about the true central distribution. Therefore, we believe that accessing the statistics information of the true central distribution is a mild and reasonable assumption. For example, participants generally know the upper bounds of convergence and generalization loss, with only the marginal cost remaining private. This setup also makes sense when costs, like those for data creation (e.g., autonomous driving) or labeling, can be readily estimated by all parties.

Response to W3: Thank you for pointing out this. We will fix this in the revision.

Response to W4: From the theoretical aspect [Theorem 5.3], a Nash equilibrium in our settings means that no agent can improve their utility by unilaterally changing their invested effort levels. Hence, the utility of agents could be viewed as an indicator of the equilibrium $\rightarrow$ if the utility of agents remains almost constant as the training progresses, an equilibrium is reached. As shown in Figure 3, the utilities of two randomly selected agents remain stable, which indicates an equilibrium. Note that the existing fluctuation of utility mainly results from the randomness of selecting peers.

[1] Incentive Mechanisms for Federated Learning: From Economic and Game Theoretic Perspective, IEEE TCCN, 2022.

[2] An Incentive Mechanism for Cross-Silo Federated Learning: A Public Goods Perspective, IEEE INFORCOM 2022.