Improving Fairness for Data Valuation in Horizontal Federated Learning

Building large and powerful machine learning models often needs large amounts of training data. In many industry-scale applications, training data is distributed in the form of silos, that is, training data is obtained and maintained by many data owners instead of being centralized at the place of a single owner or a data center. Because of industrial competition, privacy concerns, legal restrictions, and many other possible reasons, integrating or centralizing data from different sources faces enormous resistance and is often even infeasible. Federated learning [1] is promising for training machine learning models on distributed data sources. It facilitates collaboration among a group of data owners (aka. “clients”) and, at the same time, preserves their privacy. The central idea of federated learning is to periodically aggregate local models from clients to produce a more general and capable global model.

Federated learning can be divided into two classes: horizontal federated learning and vertical federated learning [2]. Horizontal federated learning refers to the scenarios where data sets owned by different clients share the same feature space but differ in samples. Vertical federated learning refers to the scenarios where data sets owned by different clients share the same sample IDs, but have different features. In this work, we focus on the horizontal federated learning.

The success of federated learning relies on active participation by motivated data owners. The motivation of data owners partially depends on whether the collaboration and rewarding in federated learning are fair. Thus, it is essential to understand how to fairly and efficiently evaluate the contributions of data owners in federated learning [3, 4, 5, 6]. In this paper, we focus on the fairness in contribution valuation.

Shapley value [7] is a classical measure originates from cooperative game theory to fairly assess contributions by participants in a coalition. The Shapley value of a participant is defined as the expectation of the marginal contribution of the participant over all possible subsets of the other participants. Shapley value is the unique measure that satisfies the four fundamental requirements of fairness proposed by Shapley [7]: balance, symmetry, zero element and additivity (see a brief review in Section IV). Although Shapley value has many desirable properties, evaluating Shapley value in federated learning requires exhaustive retraining and evaluating the model on every subset of clients. The costs of communication and time may be prohibitive in practice [4].

To make fair evaluation of data owners practical in federated learning, some variations inspired by Shapley value were proposed. For example, Wang et al. [6] recently proposed federated Shapley value (FedSV). The key idea is to compute the Shapley values for clients in each round of training and then report the summation over all the rounds as the final results. Compared with the classical Shapley value, FedSV does not require model retraining and retains some but not all of the desirable properties for fairness.

However, FedSV faces a challenge in large scale federated learning in practice – it may create unfairness. In order to reduce communication costs, many widely used federated learning algorithms in each round select only a subset of clients to upload their local models [8, 9]. In the design of FedSV, the unselected clients are assigned with zero credit in that round. This design causes unfairness. One particular example implied by the fundamental requirements of the Shapley fairness [7] is that if two clients provide the same data and thus have the identical capability in utility contribution, then they should receive the same rewards. While in the setting of FedSV, clients with the same local data may be assigned with very different credit due to random selection in the training (see an empirical case study in Section VII-B).

The fundamental challenge of fair evaluation of data owners’ contributions in federated learning is that we have to retain fairness in pursuing efficiency. In this paper, we develop a principled approach. The general idea is intuitive and effective. We propose a novel notion of utility matrix consisting of contributions of all possible subsets of the clients over all training rounds. Obviously, with the utility matrix, even FedSV can make a fair evaluation on all clients. However, the utility matrix can only be partially observed because only a subset of clients is selected in each round. The weakness of FedSV is that it computes the Shapley values using only those observed entries in the utility matrix directly. Our idea is try to complete the missing entries of the utility matrix so that the unfairness can thus be eliminated.

Completing the unobserved entries is far from trivial. We rigorously show that the utility matrix is approximately low-rank based on a careful theoretical analysis of the similarity between contributions from different clients in successive training rounds. This theoretical insight enables us to estimate the missing entries in the utility matrix using techniques from low-rank matrix completion. With the above insights, we propose a new measure, called completed FedSV, to evaluate data owners’ contributions in federated learning. Our primary technical contributions are as follows.

1. 1.

   We propose the notion of utility matrix and prove that the matrix is approximately low-rank when the local models are Lipschitz continuous and smooth (Propositions 1 and 2).

2. 2.

   We develop a new measure for fair contribution valuation in federated learning, called completed federated Shapley value (ComFedSV), based on solving a low-rank matrix completion problem for the utility matrix.

3. 3.

   We show that if the utility matrix is well completed, then ComFedSV satisfies two desirable properties for fairness, i.e., symmetry and zero element (Theorem 1).

4. 4.

   To tackle the practical scenarios where the size of the utility matrix is too large to complete directly, we adopt a Monte-Carlo sampling method to reduce both space and time complexity (Algorithm 1).

The rest of the paper is organized as follows. Section II reviews the literature on many data valuation techniques for machine learning and federated learning. We introduce the federated learning problem as well as the algorithm for solving it in section III. In section IV, we formalize the definition of fairness for data valuation under the setting of federated learning. Section V introduces the FedSV proposed by Wang et al. [6] and shows that it may break the fairness requirement for data valuation. We propose the improved data valuation metric – ComFedSV in section VI. Specifically, section VI-A introduces the utility matrix and theoretically shows its low-rank structure, section VI-C illustrates the procedure for completing the utility matrix, section VI-D formally defines the ComFedSV and section VI-E provides an efficient algorithm for estimating the ComFedSV. Section VII includes some numerical experiments showing the fairness and effectiveness of the ComFedSV, and the appendix contains the proofs for all the theoretical results.

There are many data valuation strategies in literature, including query and view-based pricing [10, 11, 12] and data quality-based pricing [13, 14]. Limited by space, here we restrict our discussion to the related work on data valuation techniques for machine learning and federated learning, which can be broadly characterized into two categories: Shapley-value-based and non-Shapley-value-based. Please see [15] and [16] for more thorough surveys on data pricing.

In this section, we revisit the federated learning model as well as the algorithm used to optimize the model. Suppose the $i$-th data owner has training data set $D_{i}$. We consider the following distributed optimization problem.

where $w\in\mathbb{R}^{n}$ is the model parameter, $N$ is the number of data owners, and the local objective for client $i$ is

where $\ell$ is a differentiable loss function. This setting guarantees that if two clients have the identical local data sets, then they have the same local models, i.e., $D_{i}=D_{j}$ implies $F_{i}=F_{j}$.

To optimize the distributed optimization problem in Equation (1), we use the federated averaging (FedAvg) method [8], which is the first and perhaps the most widely used federated learning algorithm. In each round, FedAvg runs several steps of stochastic gradient descent in parallel on a randomly sampled subset of participants and then averages the resulting model updates via a central server. We describe one (say the $t$-th) round of the standard FedAvg algorithm.

Let $I=\{1,\dots,N\}$ denote the set of all participants. In round $t$, the FedAvg executes the following steps.

1. 1.

   The central server broadcasts the latest model $w^{t}$ to all data owners;

2. 2.

   Every data owner $i$ updates the local model by setting $w_{i}^{t}=w^{t}$ for all $i$;

3. 3.

   Every data owner $i$ performs local updates. For all $i$,

   $$w_{i}^{t+1}=w_{i}^{t}-\eta^{t}\nabla F_{i}(w_{i}^{t}),$$

   (3)

   where $\eta^{t}$ is the learning rate used in the $t$-th round.

4. 4.

   A subset $I_{t}\subseteq I$ of participants is randomly selected with uniform probability by the central server;

5. 5.

   The central server aggregates the selected local models to produce a new global model

   $$w^{t+1}=\frac{1}{|I_{t}|}\sum_{i\in I_{t}}w_{i}^{t+1}.$$

   (4)

For simplicity, here we let each client do only one step of deterministic local update, that is, $w_{k}^{t+1}=w_{k}^{t}-\eta^{t}\nabla F_{k}(w_{k}^{t})$. Our theoretical results can be generalized to an arbitrary number of stochastic local updates in each round.

Fairness is one of the most desirable properties for a data valuation metric [22, 15]. In the federated learning setting, a data valuation metric should be able to reflect how much each data owner contributes to the performance of the final model. Formally, we assume a black-box utility function $U:2^{I}\to\mathbb{R}$ such that for any subset of clients $S\subseteq I$, $U(S)$ returns a utility score of the model collaboratively trained by clients in $S$, such as the performance of the model. Let $v:I\to\mathbb{R}$ be the evaluation metric associated with the utility function $U$. Given the utility function $U$, the Shapley fairness [7] has four fundamental requirements for a metric $v$.

1. 1.

   Symmetry. For any two clients $i,j\in I$, if for any subset of clients $S\subseteq I\setminus\{i,j\}$, $U(S\cup\{i\})=U(S\cup\{j\})$, then $v(i)=v(j)$.

2. 2.

   Zero element. For any client $i\in I$, if for any subset of clients $S\subseteq I\setminus\{i\}$, $U(S\cup\{i\})=U(S)$, then $v(i)=0$.

3. 3.

   Additivity. If the utility function $U$ can be expressed as the sum of separate utility functions, namely $U=U_{1}+U_{2}$ for some $U_{1},U_{2}:2^{I}\to\mathbb{R}$, then for any client $i\in I$, $v(i)=v_{1}(i)+v_{2}(i)$, where $v_{i}$ and $v_{2}$ are the evaluation metrics associated with the utility functions $U_{1}$ and $U_{2}$, respectively.

4. 4.

   Balance. $v(S)=\sum_{i\in S}v(i)$.

Under the federated learning setting, a utility function is usually defined using the model performance on a test data set. The symmetry requires that the same contributions to the utility should receive the same evaluation, which implies that clients with same local data sets should receive same evaluation. The zero element requires that no contribution, no value is recognized. The additivity requires that if there are multiple tasks and thus multiple test data sets, then the contributions of any client with respect to the test data sets can be expressed as the sum of the contributions with respect to those different tasks and test data sets. It is worth noting that although balance is an important requirement in economics, which guarantees that the payment is fully distributed to all players, it is not relevant in the setting of this paper, since we only care about the relative contributions between clients.

It is shown [18, 22] that if the data valuation metric $v$ satisfies symmetry, zero element, and additivity, then $v$ must have the form

for some positive constant $c$. However the data valuation metric in form (5) cannot be directly applied in federated learning, because evaluation of the utility function $U$ requires retraining models [22], which is impractical in federated learning [6]. Therefore, we cannot expect any practical data valuation metric in federated learning exactly satisfies the above requirements for fairness.

To tackle this challenge, we propose $\epsilon$-Shapley fairness, a relaxation of fairness for federated learning.

In $\epsilon$-Shapley fairness, parameter $\epsilon$ is used to control the quantitative requirement on fairness.

In this section, we first review the roundly utility function and the FedSV proposed by Wang et al. [6]. Then we give a simple example showing that directly using FedSV for data valuation may cause some unfairness.

Data valuation in federated learning aims to find data sets that are important or influential to the learning task. In federated learning, the importance of a data set is reflected by how much it can improve the performance of the final model. This idea is well established under the general context of machine learning [22]. With this insight, we evaluate the importance of the data sets using the test loss of the model. More specifically, consider a typical federated learning process of $T$ rounds as described in Section III. For any $t$ $(1\leq t\leq T)$, let $u_{t}:\mathbb{R}^{n}\to\mathbb{R}$ denote the per-round utility function defined as

where $D_{c}$ is the test data set kept by the central server. Function $u_{t}(w)$ measures the model performance in round $t$ with model parameter $w$ by the decrease in loss on the test set.

For round $t$, we define the utility function $U_{t}:2^{I}\to\mathbb{R}$. For any subset of participants $S\subseteq I$, the utility created by those participants in round $t$ is defined as

The federated Shapley value [6] measures the average marginal utility over the selected clients.

If we run only one round of training and select all clients for that round, then FedSV is equivalent to the classical Shapley value. As mentioned in Section I, more often than not, the central server only selects a subset of clients in each round to reduce communication costs. We argue that simply setting the contribution of an unselected client to zero in a round causes unfairness. One quick example to demonstrate the unfairness is that two clients with the same data may receive quite different evaluations if one of them is unfortunately not selected. We formalize this circumstance in the following observation.

The following numerical example corroborates this observation.

In this section, we first design a utility matrix consisting of contributions of all subsets of clients over all rounds of training, and present the main theoretical result that the utility matrix is approximately low-rank when the local objectives are Lipschitz continuous and smooth. Then, based on a low-rank matrix completion formulation, we propose a new data evaluation method ComFedSV for federated learning. We also show that when the utility matrix can be well recovered, ComFedSV satisfies certain desirable fairness properties. Last, when the size of the utility matrix is too large, we develop a Monte-Carlo type sampling method to reduce the size of the corresponding matrix completion problem.

This section reports a series of experiments that examine how well ComFedSV can capture contributions from clients/data owners in federated learning. Our code is publicly available at the Huawei AI Gallery¹¹1https://developer.huaweicloud.com/develop/aigallery/notebook/detail?id=08da32bb-9b85-4ddb-ae6c-94a3f5102133.

In this paper, we tackle the challenging problem of data valuation in horizontal federated learning. We point out the possible unfairness in the existing data valuation method. Then, we propose a new measure ComFedSV, which is not only fair with theoretical guarantee, and also can be evaluated efficiently. We verify the fairness of our measure both theoretically and experimentally.

Our study advances the frontier in this emerging important direction. There are also many interesting future directions. For example, it is interesting to extend our methodology to vertical federated learning. As another example, under the framework of federated learning, there may exist some other properties needed for fairness in federated learning in addition to those in the Shapley fairness.