Fair and Efficient Contribution Valuation for Vertical Federated Learning
Authors: Zhenan Fan
Huang Fang
Xinglu Wang
Zirui Zhou
Jian Pei
Michael Friedlander
Yong Zhang
Venue: ICLR 2024 poster (2024)
Keywords: Vertical federated learning
Contribution valuation
Fairness
Primary area: societal considerations including fairness, safety, privacy

Abstract: Federated learning is an emerging technology for training machine learning models across decentralized data sources without sharing data. Vertical federated learning, also known as feature-based federated learning, applies to scenarios where data sources have the same sample IDs but different feature sets. To ensure fairness among data owners, it is critical to objectively assess the contributions from different data sources and compensate the corresponding data owners accordingly. The Shapley value is a provably fair contribution valuation metric originating from cooperative game theory. However, its straight-forward computation requires extensively retraining a model on each potential combination of data sources, leading to prohibitively high communication and computation overheads due to multiple rounds of federated learning. To tackle this challenge, we propose a contribution valuation metric called vertical federated Shapley value (VerFedSV) based on the classic Shapley value. We show that VerFedSV not only satisfies many desirable properties of fairness but is also efficient to compute. Moreover, VerFedSV can be adapted to both synchronous and asynchronous vertical federated learning algorithms. Both theoretical analysis and extensive experimental results demonstrate the fairness, efficiency, adaptability, and effectiveness of VerFedSV.

Published as a conference paper at ICLR 2024
FAIR AND EFFICIENT CONTRIBUTION VALUATION FOR VERTICAL FEDERATED LEARNING
Zhenan Fant*, Huang Fang', Xinglu Wang"", Zirui Zhou",JJan Pei Michael P. Friedlander!, Yong Zhang"
"University of British Columbia, {zhenanf, hgfang, mpf) ubc. ca
+Simon Fraser University, [xinglu_wang_2 ees. ffu.ca
"Huawei Technologies Canada, {zirui zhou, yong. zhang3) wwwwwei..ccom. com
ABSTRACT
Federated learning is an emerging technology for training machine learning mod- els across decentralized data sources without sharing data. Vertical federated learning, also known as feature-based federated learning, applies to scenarios where data sources have the same sample IDs but different feature sets. To en- sure fairness among data owners, it is critical to objectively assess the contribu- tions from different data sources and compensate the corresponding data owners accordingly. The Shapley value is a provably fair contribution valuation metric originating from cooperative game theory. However, its straight-forward compu- tation requires extensively retraining a model on each potential combination of data sources, leading to prohibitively high communication and computation over- heads due to multiple rounds of federated learning. To tackle this challenge, we propose a contribution valuation metric called vertical federated Shapley value (VerFedSV) based on the classic Shapley value. We show that VerFedSV not only satisfies many desirable properties of fairesss but is also efficient compute. Moreover, VerFedSV can be adapted to both synchronous and asynchronous ver- tical federated learning algorithms. Both theoretical analysis and extensive exper- imental results demonstrate the faireess, efficiency, adaptability, and effectiveness of VerFedSV.
INTRODUCTION
Creating powerful and robust machine learning models requires collecting enormous amounts of training data. However, in many industrial scenarios, training data is siloed across multiple com- panies, and data sharing is often impossible due to regulatory limits on data protection (Li et al.) 2020). Federated learning (FL for short) is an emerging machine learning framework where cen- tral server and multiple data owners, i.c., clients, collaboratively train a machine learning model without sharing their data (McMahan et al. 2017 Yang et al., 2019; Kairouz et al. 2019).
FL can further be classified into two main categories: horizontal federated learning (HFL) and vertical federated learning (VFL) (Yang et al. 2019). In HFL, various clients' data share the same feature space but have separate sample IDs. On the other hand, VFL assumes that the data owned by different clients share identical sample IDs but have distinctive features.
The success of FL depends the active participation of motivated clients. Therefore it is vital to fairly evaluate the contributions from different clients fair cooperation and reward can motivate active participation from players.
The Shapley value (Shapley 1952) is a classical metric derived from cooperative game theory that is used to appropriately assess players' contributions. The Shapley value of a player is defined as the expected marginal contribution of the player over all possible subsets of the other players. The Shap- ley value the only metric that satisfies all four requirements of Shapley's 's fairness criteria: balance, symmetry, zero element, and additivity (Dubey 1975) (see Section B.I Although the Shapley value has many desirable characteristics, its evaluation in the FL. context requires repeatedly training and evaluating models learned all possible subsets of clients. The corresponding communication and computation costs are exponential and often prohibitive in practice (Song et al., 2019: Wang et al. 2019 Fan et al. 2022).
Variants of the Shapley value make equitable data owner contribution assessment feasible in FL.. Take its application in HFL as example, Wang al. (2020) proposed a contribution valuation

---

Published as a conference paper at ICLR 2024
metric called the federated Shapley value (FedSV). The key idea is to calculate Shapley value for a client in each iteration of training and then aggregate these values over all iterations determine the final contribution of the client. Its computation does not require model retraining and retains some, but not all. of Shapley's 's fairess criteria. Fan et al. (2022) enhanced the faimess of this method by considering all data owners, including those not selected in certain training iterations. This improvement
accomplished through low-rank matrix factorization techniques. While Fan et al. (2022) focus on HFL. this paper will serve as an extension towards VFL and complete the picture of contribution valuation in FL.
Compared to HFL, adapting the Shapley value to VFL faces another challenge because of the stronger model dependency in the vertical context. More precisely, the Shapley value computa- tion requires us to form the model produced by all different subsets of clients. This requirement is easy to satisfy in HFL because the global model is defined as the additive aggregation of the local models, and thus only need to aggregate local models from different subsets of clients (Wang al. 2020). In VFL, however, the global model is the concatenation of local models that are not shared with the server. Thus, simply concatenating local models from different subsets of clients is not applicable.
In this paper, concentrate developing efficient and equitable methods for evaluating clients' contributions in VFL. We propose contribution valuation metric called the vertical federated Shap- ley value (VerFedSV), where the clients' contributions are computed at multiple time stamps during the training process. We resolve the model concatenation problem by carefully utilizing clients' em- beddings at different time stamps. We demonstrate that our design retains many desirable fairness properties and can be efficiently implemented without model retraining.
VFL algorithms can be divided into two categories: synchronous methods (Gong et al., 2016 Zhang et al. 2018 Liu et al. 2019). where periodic synchronizations among clients are required, and asyn- chronous ones (Hu al.) 2019 Gu et al. 2020; Chen et al., (020).. where clients are allowed to conduct local computation asynchronously. We show that VerFedSV applies to both synchronous and asynchronous VFL settings. Under the synchronous setting, we show that VerFedSV can be computed by leveraging some cotrrixccomlttiion techniques. Although there are many similarities between synchronous and asynchronous VFL, contribution valuation in asynchronous VFL set- ting more complicated because the contribution of a client depends on not only the relevance of the client's 's data to the training task but also the client's local computational resource. We show that the design of VerFedSV can reflect the strength of clients' local computational resources under the asynchronous setting. To the best of our knowledge, are the first to consider contributions w.r.t local computational resources.
Our contributions can be summarized as follows.
We propose vertical federated Shapley value (VerFedSV) for VFL (Equation D and Definition and show that VerFedSV satisfies many desirable properties of fairness (Theorem TT.
Under the synchronous VFL setting, we show that VerFedSV can be computed by solving low-
rank matrix completion problems for embedding matrices, which are proven to be approximately low-rank (Proposition DT. We also give an approximation guarantee of VerFedSV given the toler- ance for matrix completion (Proposition
Under the asynchronous VFL setting, we show that VerFedSV can be directly computed and can reflect the strength of clients' local computational resources (Proposition VerFedSV does not incur extra communication cost. Mcanwhile, its computational cost can be further reduced by applying the Monte-Carlo sampling methods (Section D.I.
RELATED WORK
The Shapley value (Shapley 1952) has broad applications Gul
1989p. Dubey 1975) showed that
Shapley value is the unique measure that satisfies the four fundamental requirements of fairness proposed by SShalley (1952). With rich history and broad applications. it has been extended to contribution valuation in machine learning (ML) contexts (Ghorbani & Zou, 2019 Jia et al. 2019 Kwon et al. 2021 Sim et al. 2022). For example, Beta Shapley (K & Zou 2022) is data valu- ation method tailored for ML applications, where the efficiency axiom can be relaxed and marginal contribution is affected by noisy data. Banzhaf value (Wang & Jia 2023) is another data valua- tion method that, similarly, relaxes the efficiency axiom. It innovatively introduces the concept of safety margin and addresses the randomness introduced by stochastic gradient descent. As privacy is an important aspect in MI., Wang et al. (2023) identify privacy leaks through the KNN-Shapley which offers a superior privacy-utility tradeoff. In the
value score and propose following, our discussion focuses on its application in FI..
2

---

Published as a conference paper at ICLR 2024
The concept of the Shapley value was introduced into HFL to evaluate the contribution of feder- ated participants (Song al. 2019). The trright-forwan computation of the Shapley value needs retraining the model an exponential number of times. To address this challenge, various methods have been proposed. Song et al. (019 presented two gradient- based techniques to approximate the Shapley value. Wang al. (2020) introduced the federated Shapley value, which can be determined from local model updates in each training iteration. The federated Shapley value does not need model retraining and preserves some but not all of the favorable qualities of the traditional Shap- ley value. Fan et al. 2022) enhanced the fairesss of this method by considering all data owners, including those not selected in certain training iterations. This is achieved by leveraging low-rank matrix factorization techniques. Liu et al. (2022) proposed the Guided Truncation Gradient Shapley (GTG-Shapley) approach, which reconstructs FL. models using gradient updates for Shapley value calculations, rather than retraining with varying combinations of FI. participants, thereby enhancing both computational efficiency and approximation accuracy. Cosine Gradient Shapley Value (CGSV) (Xu et al. 202T) also avoids the need for model retraining and validation processes by exploiting information available during training, that is, the alignment between the model updates uploaded by an individual agent and the aggregated model derived from all participating agents. Meanwhile, Xu et al. ) propose an incentive mechanism that rewards agents with higher contributions through a higher-quality model. However, this realization of incentives may lead to non-convergent behavior in the model. To address this, [in et al. (2023) further explore the trade-off between asymptotic performance and fairness. Our method shares similar idea in the sense of leveraging training-time information, but the difference is that we cater synchronous and asynchronous VFL scenarios. Beyond the computational challenge, Yang et al. (2022) find that the Shapley value only considers the marginal contribution on model performance and propose to enhance the Shapley value with other influencing factors, such data quality, level of cooperation, and risk factor, to assess con- tributions. Apart from its use in contribution valuation, the Shapley value has inspired an adaptive weighting mechanism (Sun et al. 2023) to enhance the robustness of FL.
Wang et al. (2019) and more recently Han et al. (202I) extended the notion of data Shapley value to VFL. As discussed before, the need for retraining the model for different subsets of clients is bottleneck of Shapley value computation in federated learning. [Wang et al.] (2019); Han et al. (202T) solved this problem by introducing model- mndee--nndeeendent utility functions, where the contribu- tion of a client does not depend on the performance of the final model, and thus does not require retraining of the model. In particular, Saricuullraaangaaaaaa et al. (2019) suggested using the situational importance (SI) (Achen 1982), which computes the difference between the embeddings with true features and expected features. However, computing SI requires knowing the expectation of each feature and can be impractical under VFL. Han et al. (2021) suggested to use the conditional mutual information (CMI) (Brown et al. 2012). which computes the tightness between the label and features. However, computing CMI requires every client to access the labels, which may also be impractical under VFL. and leak privacy. Besides the above shortcomings, the indeeeinneeendentt utility function itself may cause some fairness issues when the VFL is conducted asynchronously. Specifically, under the asyn- chronous setting, the contribution of client not only is related to the quality of the local dataset but also depends on the power of local computational resources. Model-independent utility functions cannot fully reflect a client's contribution in this scenario. (See Proposition [3 and Section 7.2 for details.) In this work, we instead use a model-dependent utility function and resolve the require- ment of retraining the model by periodically evaluating the contribution metric during the training process.
3 VERTICAL FEDERATED LEARNING
In this section, we review the standard VFI. framework. In this framework, M clients and one server collaborate to train a machine learning model on N data samples ((x; E Rd y; E {+1) [+]1)) where r; is the i-th feature vector and y; its associated label. We assume that the index i is globally shared between the server and the M clients. This assumption is reasonable, as data alignment methods in VFL protocols (Cheng et al. 2019) are routinely employed to ensure synchronization across clients. This method ensures that only samples shared by all clients retained for VFL. each identified by a unique sample ID. For simplicity, we posit that these sample IDs are the same as the global sample indices [N] = (1, N). Here, the notation [-] means the set of consecutive integers.
Under the VFL framework, every feature vector æe is distributed across M clients. Represent the
portion of the feature vector held by client m as !!!")) e (d(m)) where d(m)) specifies the feature dimension associated with client m. In other words, if we collect the feature vectors from all clients
and concatenate them, the x; will be reconstructed, ie., Is = [=]...., axd and d >M d(m). Here, [.-....]] is the concatenation operation.
3

---

Published as a conference paper at ICLR 2024
The local data set for client m is D(m) = { (m) : [Nv]] The server maintains all the labels D {yi i E [N]] The collaborative training problem can be formulated as ming,....Ow N Ei= ((1...... .ux; (2,, Uit), where 6n Rd denotes the training param- eters of the m-th client and ((.) denotes the loss function. For a wide range of models, such as linear and logistic regression, and support vector machines, the loss function has the form and f(:3)) a differentiable function for any y. For each client m, the term n!(")) can be viewed as the client's embedding of the local data point =n!") and the local model 0m To preserve privacy, clients are not allowed to share their local data set D)m)) local model g(mm) with other clients with the server.
f (f1....,@ar (2i, v:l) = f (h:; vs), where h; = - R (m)
h,() = -Om. >//"))
Instead, clients can share only their local embeddings h (m) : E [
to the server for training.
For simplicity, here we consider a binary classification problem. All of our theoretical results can be easily extended to multi-class classification problem with > classes, where 0m E [gd!")) x1 (m)
and (m!m)) = =, ((m) E TR!. Moreover, in practice, our method also works for more general local embedding functions, i.e., fm(m) g g((0 (0))))()))) where g can be a neural network with weights 6n-
We empirically verify this in Section 7
Asynchronous VFL is favorable when the strength of computational resources varies greatly across clients. This strength concerns two aspects: 1). The batch size of embeddings that a client can process influenced by its hardware (e.g., CPU/GPU) capability. 2). The upload speed influenced by its transmission power. It is reasonable to assume that (Dinh et al.] 2020) download times are negligible compared to upload times, given that downlinks tend have higher bandwidths, and the server's transmission power far exceeds that of the client.
Formally, we define the strength of clients' local computational resources that reflect the above- mentioned two factors as follows.
Definition 1. Let At > be the unit time for one iteration including the time for communication. The strength of client m's local computational resource is represented by positive integer Tm [L. such that client m can compute and upload at most Tm local embeddings during each time interval At.
4 VERTICAL FEDERATED SHAPLEY VALUE
In the following, we briefly introduce why Shapley value is fair valuation metric. The Shap- ley value is built upon a black-box utility function. Under the FL setting. this utility function outputs the performance of the collaboratively trained model. Since each evaluation of utility in- volves retraining model, we denote this utility function as Urratriin : 2 - R. It provides utility score for the model trained by any client subset S C [M] Given utility function Urreminnn the Shapley value is said to be fair because it satisfies four fundamental requirements: Symme- try, zero element, additivity, and balance (See Section [oI details). It has been shown that the only valuation metric satisfying four requirements is the Shapley value (Dubey 1975] Ghorbani & Zou 2019). Formally, the Shapley value assigned to client m, denoted by 8m. is computed by ( {m}) - (S))
8m
AT ScC(MA(m)
However, computing 8m is impractical in the FL context because the evaluation of the utility func- tion Urearrinn requires extensive model retraining (Ghorbani & Zou 2019 Wang et al. 2020]. To it computationally practical in FI. context, as discussed before, Waan et al. (2020) recently proposed the federated Shapley value (FedSV) for HFL, which computes the Shapley values for clients peri- odically during the training and then reports the summation over the periods as the final results. We extend this idea to the VFL context and define a new utility function. Suppose we pre-determine T time stamps for contribution valuation. Denote by [7] [I,.... .1,...,3 T} the set of all time stamps. At
each time E (T). we define the utility function U. 2 - IR such that for any subset of clients S C [M], the utility US) denotes the decrease in loss made by the clients in S during the time
4

---

Published as a conference paper at ICLR 2024
period [t 1, t), i.e.,
N
M
(m])
(t-1)
N
(m)
(4)
(m)
(t-
U((S) N
136
h
N
m==1
Ams
mgs
(1)
where )n._
(t)
is the local embedding of data point (mm) by client m time t. The idea behind
this definition is that if client m participates in the training during the period [t 1, 4). then we use
(m) (e)
the client's 's latest embedding
h for evaluation; otherwise, we use the previous embedding
(m)) (t-1) Then, we formally define the vertical federated Shapley value (VerFedSV).
Definition 2. Given T predetermined contribution valuation time stamps, the VerFedSV for any client m E [M] is 8m = MT En- Ese(M)M))
(U {m]) - U.(S)]
[s]
Note that computing VerFedSV does not require retraining the model due to Equation theorem D juutifiis the fairness of VerFedSV. Please refer to Section 1 for proof.
Next,
Theorem 1 (Fairness Guarantee). Define U 2( + IR as the averaged utility function spanning the entire training process, formulated as US) 1 E U.(S). The VerFedSV (Definition
satisfies four requirements on fairness (See Section B.1 for details).
COMPUTATION OF VERFEDSV UNDER SYNCHRONOUS SETTING
Almost all the synchronous VFL algorithms (Gong et al. 2016 Zhang et al. 2018 Liu et al. 2019) share the same framework: in each iteration, every chient uploads local embeddings for the same batch of data points to the server, downloads gradient information from the server, and then con- ducts local updates. The main difference among those algorithms is the scheme of local updates. For clarity, we consider the vanilla stochastic gradient descent algorithm for VFL, i.e., FedSGD (Liu et al.] (019)). It is worth mentioning that VerFedSV computation solely relies on the clients' embed- dings and is independent of the local update rule of the underlying VFL algorithm. Consequently, VerFedSV can be easily extended to other synchronous VFL algorithms.
Refer to Section A. for details on one training iteration in FeDSGD. Here, we describe how batch size is determined. The time interval between training iterations is first negotiated and determined. Then, Definition [ gives the maximum number of local embeddings T. that can be processed by client m within a single iteration. The server collects information from clients and calculates T := min(Tm. m E [M]]. The batch size is set to be no larger than т. In the following, we denote the (4)
bani- of t-th iteration as ((t), and the embedding of i-th sample for m-th clients as (h(m)
Now we show how to compute VerFedSV with the FedSGD algorithm. Under the synchronous setting, we set the time stamps for contribution valuation to be the ends of training iterations. The
key challenge in computing VerFedSV is that, in each iteration, we only have access to the lo-
cal embeddings for the current mini-batch B(t), i... (1) (( (m)m))
(t)
E [M], i B(t)
However, computing VerFedSV (Definition 2 requires all the local embeddings in each iteration,
i.e., A
(m)
(x)
mm E [M], i [M] Therefore, we want to obtain reasonable approxi-
mations for the missing local embeddings.
Embedding matrix For each client m,, we define the embedding matrix (()) E R TxN where each
element (t, i) is defined as H/(m) (n. (m) (t)
Due the mini-batch setting, we can only make par-
tial observations {7(mm) tE [T], i E B(0). We notice that the embedding matrices can be decom- posed as (m)) = Xm where θ. = (!))
e and X,, = [ (m)
(m) Note
NN
that when dm)) < minn(T,N) the embedding matrix H(m) is low-rank because rank(H (m)) < min min (rank(Om)) (aneeem))aannkn. rank(X...) < d(m)) When mm)) > min (T, N). we observe that the model matrix
O,, is approximately low-rank due to the similarity of local models between successive training
5

---

Published as a conference paper at ICLR 2024
iterations. The data matrix Xm can also be approximately low-rank due to the similarity between local data points. Our following proposition theoretically formalizes this observation. Before stat- ing the result, we first give a formal definition of approximately low-rankness, proposed by Udell & Townsend (2019).
Def. 2.1)). Let X E mR be matrix and E > 0a tolerance. The e-rank of X is defined as rank, (X min (rank (2) Z Rmxx 11 X mmmax S <) }) where I|-I|max the absolute maximum matrix entry. Consequently, k = rank, (X) signifies the minimal integer such that X can be approximated by a rank-k matrix within an e-tolerance.
Definition 3 (e-rank, (Udell & Townsend 2019
rank,(X)
The following proposition characterizes the approximate rank of the embedding matrices H(m), Proposition 1 (e-rank of the embedding matrix). Assume that the function f-:y) is L-smooth for
any label y. the local data sets are normalized, i.e., ||x]"T) ||= for all m [M] and E. [M] and the learning rate is defined as rf(*) =/t/t. 1/t. Then for any O and any m [M], ranke (H(())) S
min ddm)) [log(()) .N (D(m), gytms }} where (-,-)) is the covering number, and T is the
number of total iterations.
Low-rank matrix completion Proposition D shows that the embedding matrix is approximately low-rank. For any client m E [M]. we formulate the following bactoizattion-asse low-rank matrix completion problem to complete the embedding matrix H(m))
minimize W Wit ER (mm) Nxr
Σ
H1 - (wmm h: )) +
(|::),
IEB
where is user-specified rank parameter, À is positive regularization parameter, ||-IL= is the Frobenius norm, and w((T) and h. hi("), respectively, are the 1-th and the i-th row vectors of the matrices ((m) and (m)) The rank parameter r can be determined via Proposition |
The low-rank matrix completion model (Equation 2} was first used in completing the information for recommender systems (Koren et al. 2009). Its effectiveness has been extensively studied both
theoretically and empirically (Keshavan 20122] Sun Luo 2016). We can therefore adopt well-
established matrix- complecionn methods Yu et al. 2014 Chin et al. 2016) for solving the problem
in Equation 2
Note that the matrix completion problem (Equation 2 can be done on the client side in parallel, i.e., clients will independently complete their embedding matrices. It is known that if solve the matrix completion problem in Equation 2 using the proximal gradient method. then the computational complexity for each iteration is [2[ + N + rTN)) (Udell et al., 2016). Here, the number of steps t required by the proximal gradient method is typically considered to be small constant. We numerically show the time required for solving the matrix completion problem in Equation 2 in Section D.I
Approximation guarantee The following proposition shows that if we can obtain a factorization with a small error, i.c., H(m) x W(m) (T))T via solving Equation 2 then we can also guarantee a good approximation to the true VerFedSV.
Proposition 2 (Approximation guarantee). Define the factorization error as M EM= [[]]()))) W(m) ( Ilmax- For any client E [M]. let 8m denote the VerFedSV computed with (w(m), (m)) m E [M]], i.e., sm = MT
(H))))
1 Et= EssMMAem (T (0 u
{m1) - -i(()), where
M Ú,($)= N Σs Σ (wm ml (m))
1 N
Σ
Σ Amss
(Th )
(m)) (w)
Σ (m) mgS
(mm) ;0:
If the function f(::)) is G-Lipschitz for any label y. then 18m sm Is 2Gc for all client m E [M..
COMPUTATION OF VERFEDSV UNDER ASYNCHRONOUS SETTING
Algorithms using synchronous computation are inefficient when applied to real-world VFL tasks, especially when clients' computational resources are unbalanced. In this section, we show how to equip VerFedSV with asynchronous VFI. algorithms follows.

---

Published as a conference paper at ICLR 2024
rumber darta
CoOk
Cork
(a) Adult dataset.
(b) Web dataset.
(c) Covtype dataset.
(d) RCVI dataset.
Figure 1: Approximated e-rank of embedding matrices.
We briefly introduce the vertical asynchronous federated learning (VAFL) algorithm (Chen et al., 2020). This algorithm allows each client to run stochastic gradient algorithms without coordination with other clients. The server maintains the latest embeddings for each sample. At any time, the clients can update an embedding or query gradient from the server. Please refer to Section A.2 for the detailed training process of the VAFL algorithm.
Next, show how to compute VerFedSV with the VAFL algorithm. Under the asynchronous setting, there is no definition of training iterations from the perspective of the server. According to Definition 2 we can pre-determine T time stamps for contribution valuation. At any contribution
valuation time t E [T'] the server keeps the set of embeddings ((-11)
from t - I and H from
Here, H1 =10==(11) (1(1 (m)) (1)
m [M], i [N]]. At l 0, we initialize the server's embeddings h (m) (0)
with all zero, i.e., computed according to Equation | and Definition 2
0, Vm E [M], Vi [M]. With these embeddings, VerFedSV is
A careful reader may ask why there is no need to use matrix completion under the asynchronous set- ting. A short answer is that, under this setting, the contribution of client is related to both the quality of the local dataset and the power of local computational resources, which is reflected by the parame- ter Tm (Definition D. More precisely, at any contribution valuation time point & E [7'. for any client
m E [M]. there exists B C [N] such that only the embeddings corresponding
B are updated,
i.e.,
Vi & B, where the size of B is proportional to Tm- Then according to Equation for any S c [M]] {m), we have U.(S U
(n. (m)
(h. (mm))
(h(mm)
Vi E B, and
h
(m)
h1
(m)
(t-1)
m) U.S) = EiEB/
/ ((DSTM)
(1-1) + (1)-m)))); - ((1. (m))
(6)
+ (m(-m))(0::0m
where (h:/- (m)(())) (he)(h))0))
E (11))
Therefore, we can that the contribution of client is proportional Tms which is indeed an important feature of asynchronous VFL algorithms. Thus, if we conduct the embedding matrix completion under the synchronous setting, then we will lose this important feature, which is unfair to the clients with more powerful local computational resources.
The above discussion also suggests that VerFedSV can motivate clients to communicate the server in the asynchronous setting, i.e.. dedicating more of their local computational resources. The following proposition demonstrates that two clients with the same local datasets but different communication frequencies receive different valuations. More specifically, the one who communi- cates more with the server receives a higher valuation.
with
Proposition 3 (More work leads to more rewards). Consider simple case: we have clients I and 2 with identical local datasets where x = x² = for all E [N]. However, their communication frequencies differ: while client I consistently sends local embeddings to the server, client 2 only does with a probability of p [0, each time client I communicates.
ΣN f((0, x.)), ys) is u-stroogly convex for some μ. > and 0" is the global minimum point, 0 and O2 are initialized at O, and stop training when reach the optimum point. Then it follows that E[0j] = + and B[0g) = -f-0".
Suppose that the loss function g
Furthermore, if we only do one time of contribution valuation when the training ends, E(si] 2
E[s2] + 1-8) |10*11 1|2, where 81 and 82 are the VerFedSV for clients I and 2, respectively.
7

---

VerFedSV for similar features Besides the original clients, for each data set, we add 5 more clients whose features are identical to client but with different levels of perturbations. More precisely, for new client i .I.....)) 5). we add white Gaussian noise to (i 1)10% percent of the local features, which we denote the feature heterogeneity. Then we measure the relative difference between the Published as a conference paper at ICLR 2024
1.5
1,43
Wetested herecc
Wo Poooee Ploocc 0.5
0.10
0.75
0.32
2.00
0.00
lsatue Ietengerety
festart Interpereiyy
lesture Ieterogeneity
Testure hotenggesiiyy
(a) Adult dataset.
(b) Web dataset.
(c) Covtype dataset.
(d) RCVI dataset.
Figure 2: Relative VerFedSV difference v.s. feature heterogeneity.
7 EXPERIMENTS
We conduct extensive experiments on real-world datasets, including Adult (Zeng et al. 2008). Web (Plati 1998), Covtype (Blackard & Dean 1999), and RCVI (Lewis et al. 2004). The detailed setup is elaborated in Section
Our code submitted in the supplementary materil.
7.1 SYNCHRONOUS VERTICAL FEDERATED LEARNING
In this section, we first empirically verify that the embedding matrices are indeed approximately low-rank (Proposition TT. Next, we demonstrate that VerFedSV satisfies the fairness property under synchronous setting [Theorem TD. More precisely, we verify that clients with similar features should get similar valuations and clients with randomly generated features should get low valuations.
Rank of the embedding matrix It is required to access the full embedding matrix in order to verify its low-rankness. Thus, we set the batch size equal to the number of data points for all clients. Considering the experiment doesn't focus on scalability w.r.t the total numbers of clients M, we set M to a moderate value. For the Adult, Web, Covtype and RCVJ datasets. respectively. M = 3, 15,9, 14. Since computing the e-rank (Detinition 3) is NP-hard (Udell & Townsend 2019),, we instead compute the rank of its truncated singular value decomposition precisely, given an embedding matrix (m(m) E R for client m. let 0 2 02 2 2 a, be its ordered singular values, where p = min NT.N.. Then given e E (0, 1), we define its approximated e-rank rank, (H(1))) max(r [1, o, 0
approximation. More
There will be M rank values for M clients' embedding matrices. The histogram of these approxi- mated e-rank values is shown in Figure | where e = 10-3 the x-axis represents the approximated e-rank and the y-axis represents the number of clients with associating x-axis value of approximated e-rank. The plot shows that the embedding matrices are low-rank on all the datasets.
original client and the new clients, i.c., for any new client E {l.....5), 5), let diff, := Is-sil where s is the VerFedSV for the original client and 8; is the VerFedSV for the new client i. Wee show a plot of relative VerFedSV difference v.s. feature heterogeneity bers of clients for the Adult, Web, Covtype and RCV/ datasets are, respectively, M7 = 8, 20, 14, 19. We can see that the relative VerFedSV difference is proportional to the feature heterogeneity. Be- sides, when the feature heterogeneity is equal relative VerFedSV difference is exactly for Adult dataset, and is nearly for the Web, Covyyee and RCV/ datasets, where the inexactness is due to the Monte-Carlo sampling.
Figure 2 where the num-
0, i.e., two clients have identical features, the
VerFedSV for random features Besides the original clients. for each data set, we add 5 more clients whose features are randomly generated according to different distributions. Specifically, for the new client E (1,...,5), 5). the features are generated from Gaussian distribution with a mean equal i and variance equal to i2. Table shows the percentage of each client's VerFedSVs relative to the sum all VerFedSVs. where the numbers
clients for the Adult, Web, Covtype and RCV/ datasets are, respectively, M = 8, 20, 14, 19. As shown in table, regardless of the distributions, clients with randomly generated features receive much lower valuations than the regular clients for all the datasets.
8

---

Published as a conference paper at ICLR 2024
Table 1: Percentage of clients' VerFedSVs in the total sum of VerFedSVs.
Synchronous setting
Asynchronous setting
Adult
Web
Covtype
RCVI
Adult
Web
Covtype
RCVI
all regular clients
99.88
99.73
97.77
93.84
97.91
98.39
98.57
91.90
artificial client
0.01
0.02
0.39
1.86
0.93
0.26
0.35
1.66
artificial client
0.05
0.06
0.57
0.43
0.06
0,31
0.21
1.75
artificial client
0.03
0.06
2.37
0.33
0.36
0.22
artificial client
0.01
0.07
0.36
0.43
0.40
0.25
artificial client
0.02
0.06
1.18
0.28
0.39
1.54
20
15
prcortage Wereaay
clant
diant
(a) Adult dataset.
(b) Web dataset.
(c) Covtype dataset.
(d) RCVI dataset.
Figure VerFedSVs for clients with different communication frequencies.
7.2 ASYNCHRONOUT VERTICAL FEDERATED LEARNING
In this section, we show that VerFedSV not only satisfies the faimess property under asynchronous setting (Theorem []. but can also reflect how frequently clients report (Proposition 33. Specifically, during the training, we let clients communicate with the server at different frequencies. For all the datasets, we asynchronously train the model for 20 seconds and do the valuation every 0.04 second, i.e. there are 7 500 contribution valuation time points (Definition 2
Impact of communication frequency Besides the original clients, for each data set, we add more clients whose features are identical to client but with different levels of communication frequencies. More precisely, the new client i E {l...., 5} communicates with the server every 0.0li second, i.c., the new client has the highest communication frequency. and the new client has the lowest. We show plot in Figure of the percentage of the new clients' VerFedSVs total sum of VerFedSVs, where the numbers of clients for the Adult, Web, Covtype and RCVI datasets are, respectively, M 8, 20, 14, 19. We can see that the percentage of VerFedSV is proportional to the communication frequency.
the
VerFedSV for random features Besides the regular clients, for each data set, add 5 more clients whose features are randomly generated according to standard Gaussian distribution. They have communication frequencies such that the new client i E {1..... 5} communicates with the server every 0.01i seconds. We show in Table [ the percentage of the clients' VerFedSVs in the total sum of VerFedSVs. where the numbers clients for the Adult, Web, Covtype and RCVI datasets are, respectively, M 8, 20, 14, 19. Regardless of the communication frequencies, the clients with randomly generated features receive much lower valuations than the regular clients for all the datasets.
8 CONCLUSION AND INSIGHTS
In this paper, propose contribution valuation metric, i.e., vertical federated Shapley value (VerFedSV), V). We demonstrate theoretically and empirically that VerFedSV satisfies desirable prop- erties for fairness and is adaptable to both synchronous and asynchronous VFL settings. There are a few interesting future directions. We notice that when we keep adding clients with identical features, the total of the VerFedSV increases. This suggests that some clients may "cheat" by constructing new clients with identical features to receive unjustifiable rewards the end. One potential solution to implement secure statistical testing before FI. training and exclude clients with extremely sim- ilar datasets. It is also interesting to explore whether VerFedSV can be integrated into differentially private VFL algorithms.

---

Published as a conference paper at ICLR 2024
REFERENCES
Christopher H Achen. Interpreting and using regression, volume 29. Sage, 1982.
Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B Shah. Julia: A fresh approach to numerical computing. SIAM review, (9(1):65 98, 2017.
Jock A Blackard and Denis J Dean. Comparative accuracies of artificial neural networks and dis- criminant analysis predicting forest cover types from cartographic variables. Computers and electronics in agriculture, 24(3):331-55, 1999.
Gavin Brown, Adam Pocock, Ming-Jia Jie Zhao, and Mikel Luján. Conditional likelihood maximisa- tion: unifying framework for information theoretic feature selection. JMLR, 13:27-66 66, 2012.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM TIST, 2:27:1-27:27, 2011.
Tianyi Chen, Xiao Jin, Yuejiao Sun, and Wotao Yin. VAFL: method of vertical asynchronous federated learning. arXiv:2007.0608) 100000000601,.100 2020.
K. Cheng, T. Fan, Y. Jin, Y. Liu, T. Chen, and Q. Yang. Secureboost: A lossless federated learning 2019.
framework.
Wei-Sheng Chin, Bo-Wen Yuan, Meng- Yuan Yang. Yong Zhuang, Yu-Chin Juan, and Chih-Jen Lin. Libmf: A library for parallel matrix factorization in shared-memory systems. Mach. Learn. Res., (71)):9711299755 2016.
Canh T Dinh, Nguyen H Tran, Minh NH Nguyen, Choong Seon Hong, Wei Bao, Albert Y Zomaya, and Vincent Gramoli. Federated learning over wireless networks: Convergence analysis and resource allocation. IEEE/ACM Transactions on Networking. 29(1)339--409, 2020.
Pradeep Dubey, On the uniqueness of the shapley value. International Journal of Game Theory, (3):131-139, 1975.
Zhenan Fan, Huang Fang, Zirui Zhou, Jian Pei, Michael P Friedlander, Changxin Liu, and Yong Zhang. Improving faimess for data valuation in horizontal federated learning. In 2022 IEEE 38th International Conference Data Engineering (ICDE), pp. 2440-2453. IEÉE, 2022.
Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning. In ICML, pp. 2242-2251. PMLR, 2019.
Yanmin Gong, Yuguang Fang, and Yuanxiong Guo. Private data analytics on biomedical sensing data via distributed computation. IEEF/ACM Transactions Computational Biology and Bioin- formatics, 13:431-44 14441144,2222 2016.
Bin Gu, An Xu, Zhouyuan Huo, Cheng Deng, and Heng Huang. federated learning algorithms for multi-party vertically collaborative learning. wrXiv:2008.06233 2020.
asynchronous
Faruk Gul. Bargaining foundations of shapley value. Econometrica: Journal of the Econometric Society, pp. 81-95, 1989.
Xiao Han, Leye Wang, and Junjie Wu. Data valuation for vertical federated learning: An informationnttherret approach. UrXiv:21/2.08366 2021.
Yaochen Hu, Di Niu, Jianming Yang. and Shengping Zhou. Fdml: A collaborative machine learning framework for distributed features. KDD, 2019.
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas J Spanos. Towards efficient data valuation based the shapley value. In AISTATS, pp. 1167-1176. PMLR, 2019.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurelien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. arXiv:1912.04977. 2019.
Maurice G Kendall. A new measure of rank correlation. Biometrika, 30(1/2):81-93, 1938.
10

---

Published as a conference paper at ICLR 2024
Raghunandan Hulikal Keshavan. Efficient algorithms for collaborative filtering. Stanford Univer- sity, 2012.
Ychuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009.
Yongchan Kwon and James Zou. Beta shapley: unified and noise-reduced data valuation frame- AasAATS, work for machine learning. AISTATS, volume 151 of Proceedings of Machine Learning Re- search, pp. $780-8802. PMLR, 2022.
Yongchan Kwon, Manuel Rivas, and James Zou. Efficient computation and analysis of distribu- tional shapley values. In AISTATS, pp. 793-801. PMLR, 2021.
David Lewis, Yiming Yang. Tony Russell-Rose, and Fan Li. Rev1: new benchmark collection for text categorization research. JMLR, 5(Apr):361-39, 2004.
Li Li, Yuxi Fan, Mike Tse, and Kuo-Y Yi Lin. review applications in federated learning. Com- puters & Industrial Engineering, pp. 106854, 2020.
Xiaoqiang Lin, Xinyi Xu, See-Kiong Ng, Chuan-Sheng Foo, and Bryan Kian Hsiang Low. Fair yet asymptotically equal collaborative learning. In ICML, volume 202 of Proceedings of Machine Learming Research, pp. 21223 21259. PMLR, 2023.
Yang Liu, Yan Kang, Xinwei Zhang, Liping Li, Yong Cheng. Tianjian Chen, Mingyi Hong, and Qiang Yang. A communication efficient collaborative learning framework for distributed features. 191iv: 187, 2019.
Zelei Liu, Yuanyuan Chen, Han Yu, Yang Liu, and Li-zhen Cui. Gtg-shapley: Efficient and accurate participant contribution evaluation in federated learning. ACM TIST, (3(4):1-21, 2022.
Scott M Lundberg and Su-In Lee. A unified approach interpreting model predictions. In NeurIPS, pp. 4768 4477, 2017.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effcceenn learning of deep networks from decentralized data. In AISTATS, pp. 1273-1282. PMLR, 2017.
Nicholas Metropolis and Stanislaw Ulam. The monte carlo method. Journal of the American statis- tical association, 44(247):335- -411, 1949.
Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli. Sgd without replacement: Sharper rates for general smooth convex functions. In ICML, pp. 4703-4711. PMLR, 2019.
John Platt. Fast training of support vector machines using sequential minimal optimization. In Advances in Kernel Methods Support Vector Learning. MIT Press, January 1998.
Tyrrell Rockafellar. Convex analysis, volume 11, Princeton University Press, 1997.
LS Shapley. value for n-person games. Technical report, RAND CORP SANTA MONICA CA, 1952.
Rachael Hwee Ling Sim, Xinyi Xu, and Bryan Kian Hsiang Low. Data valuation in machine learn- ing: "ingredients" strategies, and open challenges. In IJCAI, pp. 5607-5614, ijcai.org, 2022.
Tianshu Song, Yongxin Tong, and Shuyue Wei. Profit allocation for federated learning. In IEEE TBD, pp. 2577-2586. IEEE, 2019.
Qiheng Sun, Xiang Li, Jiayao Zhang, Xiong, Weiran Liu, Jinfei Liu, Zhan Qin, and Kui Ren. Shapleyfl: Robust federated learning based on shapley value. In KDD, pp. 2096-2108 ACM, 2023.
Ruoyu Sun and Zhi-Quan Luo. Guaranteed matrix completion via non-convex factorization. 1EEE Transactions Information Theory, 62 (11111):65356666 6579, 2016.
Madeleine Udell and Alex Townsend. Why are big data matrices approximately low rank? SIAM Journal on Mathematics of Data Science, (():1444160. 2019.
Madeleine Udell, Corinne Horn, Reza Zadeh, and Stephen Boyd. Generalized low rank models. Foundations and Trends in Machine Learning, 9(1, 2016.

---

Published as a conference paper at ICLR 2024
Guan Wang, Charlie Xiaoqian Dang, and Ziye Zhou. Measure contribution of participants in feder- ated learning. IEEE TBD, pp. 2597-2604. IEEE, 2019.
Jiachen T. Wang and Ruoxi Jia. Data banzhaf: A robust data valuation framework for machine learning. In AISTATS, volume 206 of Proceedings of Machine Learning Research, pp. 6388- 6421. PMLR, 2023.
Jiachen Wang. Yuqing Zhu, Yu-Xiang Wang, Ruoxi Jia, and Prateek Mittal. Threshold KNN- shapley: A linear-time and privacy-frienlly approach to data valuation. In NewrIPS Workshop on Attributing Model Behavior at Scale, 2023.
Tianhao Wang, Johannes Rausch, Ce Zhang. Ruoxi Jia, and Dawn Song. A principled approach to data valuation for federated learning. In Federated Learning, pp. 153-167. Springer, 2020.
Xinyi Xu, Lingjuan Lyu, Xingjun Ma, Chenglin Miao, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Gradient driven rewards to guarantee fairmess in collaborative machine learning. In NeurIPS, pp. 16104-16117, 2021.
Qiang Yang. Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM TIST, 10(2):1-19, 2019.
Xun Yang, Weijie Tan, Changgen Peng, Xiang, and Kun Niu. Federated learning incentive mech- anism design via enhanced shapley value method. Wireless Communications and Mobile Com- puting, 2022.
Hsiang-Fu Fu Yu, Cho-Jui Hsieh, Si Si, and Inderjit Dhillon. Parallel matrix factorization for recom- mender systems. Knowledge and Information Systems, 41(3):793 819, 2014.
Zhi-Qiang Zeng. Hong-Bin Bin Yu, Hua-Rong Xu, Yan-Qi Xie, and Ji Gao. Fast training support vector machines using parallel sequential minimal optimization. In 2008 3rd international conference intelligent system and knowledge engineering, volume 1, pp. 997-1001. IEEE, 2008
Gong-Duo Zhang, Shen- Yi Zhao, Hao Gao, and Wu-Jun Li. Feature-distriuted svig for high- dimensional linear classification. UrXiv:180..0364 2018.
A DETAILS ON ADOPTED FEDERATED LEARNING ALGORITHM
A.1 SYNCHRONOUS SETTING
We adopt the FedSGD algorithm (Liu et al. 2019) for synchronous federated learning. In the fol- lowing, we show the sketch of one training iteration of the FedSGD. In each iteration t, the FedSGD algorithm executes the following steps:
1. The server selects a mini-batch ((t) C [N] containing the global indices of samples;
2. Each client m [M] computes local embeddings { {An
(17)
(x) e(t)) | E B("), where
(m))
e/t)
is the client's current model and sends them to the server;
3. The server computes gradient information 9 (t)
as (())))
i B(t), 11th)
ΣM (m) (2)
on!"!
and sends it to every client m E [M];
Each client m E [M] updates the local model via (((+
(!()
((()) [B(0]]
Σ
(0)(()))) (m)
2, where
iE Biy)
(*)) is the learning rate at the t-th iteration.
A.2 ASYNCHRONOUS SETTING
We follow the vertical asynchronous federated learning (VAFL) algorithm proposed by Chen et al. 2020). where the algorithm allows each client to run stochastic gradient algorithms without coordi- nation with other clients. We sketch the training process of the VAFL algorithm.
The server maintains the latest embeddings (h(m) (m) from active client m. The message contains either embedding update or gradient query.
E [N]. m E [M] and waits for a message
12

---

Published as a conference paper at ICLR 2024
Update: Client m sends the embeddings ( |
Bm3 to the server. The server then
updates its latest embeddings by h hm(m) = m/ for all i E Bm- 2. Query: Client m requests the partial gradient with respect to batch Bm. The server then sends back the client the partial gradient as
Vf(h The
M
9:
E Bm h1
h
(m))
client m keeps executing the following steps:
1. Randomly select batch Bm C [M] s.t. Bm|= Tm (Definition
I and compute local embed-
dings (h,m²) (0(m), 2x mm))
Bm)-
2. Upload embeddings (7(m))
l EiE Bm to the server.
3. Query gradient from the server and update the local model as 6m 6m
Tm [mml
EieB, I: (m)
where 7m is the local learning rate and gi is defined in Equation 3
B PROOFS OF THEORETICAL RESULTS
We first introduce some notions being used. The following special classes of functions (Nagaraj
et al. 2019) are considered.
Definition 4. Consider differentiable function f 1 I and any points x, y E R" We have the following definitions.
f is convex if satisfies
f(1) 2 f(x) + (VV()), f is p-strongly convex for some μ if satisfies
f(y) 2 f(x) + (Vf(x), y - 2) + - -1
f is G-Lipschitz, for some G 0 Of satisfies
[xx) [w)) G/| yyll2i
f is L-smooth for some L 0 if f satisfies
f 2 L|| yl12.
Meanwhile, we uses the notions of e-net and covering number (Udell & Townsend, 2019), which are widely used tools in high-dimensional probability.
Definition 5. Let K be compact subset of R= A subset NC K is called an e-net for if. for every x E K, there exists E N such that ||x v1|25
The minimum cardinality of an e-net for K is called the covering number of K and is represented by e),
B. PROOF OF THEOREM 1 FAIRNESS GUARANTEE
Formally, given utility function U, the corresponding Shapley value should satisfy four fundamen- tal requirements.
Symmetry. For any two clients i,j [M], for any subset of clients S [M] (i.j). USS USSU (i}), then 8; = 8j. Zero element. For any client E [M], if for any subset of clients S C [M] USU =
U(S), then 8; = O.
Additivity, If the utility function U can be decomposed into the sum of separate utility functions,
i.c., U = U1 + Un for some U1. U2 2[ + I, then for any client i e [M], = s + s where and 52 are the evaluation metrics associated with the utility functions Un and U2, respectively.
Balance. U((M) Eielar 8i.
It has been showed that the Shapley value, computed by
1
Σ
U(SU (m)) U(S)),
(4)
M
M-1 [S|
SC(M)(())
13

---

Published as a conference paper at ICLR 2024
the only metric that satisfies the above requirements (Dubey 1975 Ghorbani & Zou 2019).
To prove Theorem pression of the classical Shapley value, given the utility function specified by Equation and
only need show that the VerFedSV (Definition matches the
U(S) = + U.(S).
Proof. We notice that the VerFedSV can be expressed as
8m
T
Σ
(m))
Us(S)]
MT
(M
t=1
(c(M)(m)
[s|
T
U U(SSU(m)) - Σ Ur(S)
M
(M-I) |S|
T
SCMMMM
t=1
E
[U(SU {m)) - U(S),
M
(-
(C(M)((M)
which matches the expression of the classical Shapley value. The result then follows.
Another interesting property of VerFedSV is Periodic additivity. Formally, If in each iteration, the utility function U, can expressed as the sum of separate utility functions, i.c,, Ug = U3 + U2 for some U7, U? 2[M] + R, then for any client m E [M]. 8m 8 + 82 where 87 and s denotes respectively the VerFedSV computed w.r.t the utility functions U. and U,.
B.2 PROOF OF PROPOSITION 1 BOUNDS OF THE EMBEDDING MATRIX'S S C-RANK
Proof. is evident that rank, (H(()) S (an(() < d(m) for all m [M]. So only need to prove the remaining two upper bounds. First, we consider the difference between successive rows of the embedding matrix H(m), For any [T 1] and [N],
(
((()) 1
(1. (m)) (2)
h (m) ((+1)
(0(0) x (m])
(0++1) I (m))
((01)
g(++1),
x {m)))
(t())
Σ
(1) (m) (m)
|BOJ
9j zj
jEB()
$ 17 ( L.
Thus, we obtain an upper bound on rank, (f((m)) by
T-1
rank, rank.?((m) (m)))) -
17 [t.
7 (t
1, max
T 1
(e)
t=1
L log(T))
Next, consider the difference between any two columns of the embedding matrix H(m) For any t [T] and i,j E [N], we have
(m(m)) (m)
(n/ mm) (4)
(k//m)) (100
(((()) (mm)) - (B(0) z3 3mm)))))
|100|| |||1|=((m) (m²) mmm)
14

---

Published as a conference paper at ICLR 2024
It follows that
[:, H4g
Imax I
max
(m) (m)) rE[2] m || z
Let 7( = m 60 and N be an 70oy net for {
[N]). 3 We can thus conclude that
rank, (H(m)) 1 WV. By definition of the covering number, follows that
rank. (H( SN (10 : [NT), 7/1)) )
B.3 PROOF OF PROPOSITION 2
APPROXIMATION GUARANTER
Proof. Define U,Ú Ú 2|M] by U(S) = E U.(5) and Ü(S) + E U.(S). For any
C. [M], we know that
(U(S) ((S)
M
ΣΣ
Σ
Σ
Hlml
-
Σ
(w/-1) T
(w
M/
T
(m)
+
Σ
1,25 M/
t=1
1=1
mES
mis
(m (mn)
Σ
(w) (wmmm) )T 9
(mm)
mÈS
M
M
(m)
(w
(m))
1/ (m)
NT
m=1
m=1
Hlm
(m)
+
Σ
H Hmm)
NT
mgs
Σ
((m)
1 (mm)
+
TT
S GMc.
mES
mgs
Then we can obtain a bound on 1sm- 3ml by
pm
8ml
Σ
- (m))
M
M Mm
[s]
U(S)
((S)
< 2Gc.
B.4 PROOF OF PROPOSITION]3 3 MORE WORK LEADS TO MORE REWARDS
Proof. We know that 07 and 03 are the optimal variables for the following convex optimization problem mino,,0, N E. f((01, m;) + (02, ye) g + 02)
Since 8t is the unique minimizer for g(0). it follows that 07 and 05 must satisfy 01 + 82 = 0-
Denote ((()) the update for 0, the t-th iteration and d as the update for 0₂ the fth iteration. By the construction, we know that
d30)
E
8" and E
EE
1=1
15

---

Published as a conference paper at ICLR 2024
Table 2: Metadata of all data sets.
Adult
Web
Covtype
RCV1
number of training data N
48842
1 119742
581012
15564
number of features d
123
300
54
47236
number of classes I
2
2
7
53
number of clients M
8
20
14
Table 3: Hyperparameter setting under synchronous setting.
Adult
Web
Covtype
RCVI
learning rate 7
0.2
0.2
0.8
1.0
batch size T
2837
6173
2000
500
rank parameter
3
5
10
regularization parameter
0.1
0.1
0.1
0.1
Therefore, it follows that
1
E = E
0"
and
1
1=1
P 0"
E
0
E
1+ p
Now we consider VerFedSV. By definition, we have
B[81 - $2 2
8r
1 0r)
1 +
Define h =0,11] + R as h(A) = g(70)). Since j-strongly convex and 0" is the unique minimizer. it follows that h is [|l0-11--ttronll convex and monotonically non non-increasing on [0, 1]. Thus, by property of strongly convex (Rockafellar 1997). we conclude that
[ 2 [82]] +
P
(+
1 11-0) p
[s2] +
||0-112.
11+ p
C DETAILS OF EXPERIMENTAL SETUP
Data sets We use four real-world data sets, Adult (Zeng et f. 2008 Web (Platt 1998).
Cov- type (Blackard & Dean 1999.. and RCVI (Lewis et al. 2004) On each data set, by default, the literature (Achen 1982
separate the features across the largest number of chiens reported Wang et al. 2019 Han et al. 2021: Brown et al. 2012). That is, we compare with the baselines under the most challenging settings. These data cover both binary and multiclass classification problems. We summarize the metadata as well the number of clients for all the datasets in Table
Models For the Adulí, Web, and Covtype data sets, we train multinomial logistic regression mod- els, and the local embeddings are computed via a linear model. For the RCVI data set, we still the negative log- likellhodoo loss, but every client locally has 2-layer perceptron model with 32 hidden neurons and a ReLU activation function for embedding. Under both the synchronous and asynchronous settings, we can achieve the test accuracy of 85% on the Adult dataset, 94% on the Web dataset, 72% the Covtype dataset, and 83% on the RCVI dataset.
From the wehsite of LIBSVM (Chang Lin 1ibsvmt 1 /setss/
2011
https: http://wwwwcooo wttp://cee..tt.ebb.../eeeeeee..
16

---

Published as a conference paper at ICLR 2024
Table 4: Hyperparameter setting under asynchronous setting.
Adult
Web
Covtype
RCV1
learning rate
0.2
0.2
0.8
1.0
batch size
2837
6137
2000
500
communication frequency At
0.01
0.01
0.01
0.01
Monte-Carlo sampling In Section D.1 we will describe the adopted sampling method. The VerFedSV is computed exactly when the number of clients M 10, and approximately using sampling when the number of clients M > The number of randomly sampled permutations K set as M00M log(M)], where M is the number of clients.
Implementation We implement the VFL algorithms and the corresponding VerFedSV compu- tation schemes described Sections 3 and the Julia language (Bezanson et al. 2017). The implementations of both synchronous and asynchronous VFL algorithms, as well as the VerFedSV computation schemes, are attached in the supplementary material. The matrix completion problem in Equation is solved by the Julia package LowRankMode j1 (Udell et al. 2016). All the experiments are conducted on Linux server with 32 CPUs and 64 GB memory.
Hyperparameter setting (synchronous) We summarize the hyperparameters under the syn- chronous setting Table 3 where 7) and т are the learning rate and the batch size used in the FedSGD algorithm, and r and are the rank parameter and regularization parameter used in the matrix completion problem 2
Hyperparameter setting (asynchronous) We summarize the hyperparameters under the asyn- chronous setting in Table where 1) and 7 are the learning rate and the batch size used in the VAFL algorithm, and At is the communication frequency for clients.
D ADDITIONAL EXPERIMENTS AND RESULTS
D.1 COMPUTATIONAL EFFICIENCY OF VERFEDSV
We first introduce the method to efficiently estimate the VerFedSV. From Definition 2 we that the computational complexity for VerFedSV exponential in the number of chents M. The same situation appears in the computation of the classical Shapley value. How to efficiently estimate the Shapley value has been studied extensively (Ghorbani & Zoul 2019: Jia et al.] (019). Many existing methods can be adopted for the computation of VerFedS V. Here deseribe the well- known Monte- Carlo sampling method (Metropolis Ulam 1949 Ghorbani & Zou| 2019).. We can rewrite the definition VerFedSV into an equivalent formul attion using expectation,
T
8m
E
T
Σ t=1
(Ulla(m) (m}) (m)) Uu(())))
(5)
where [[[M) is the uniform distribution over all M! permutations of the of clients [M] and (m) the set clients preceding client m in permutation æ. With this formulation, we can use the Monte Carlo method to obtain an approximation of VerFedSV. More precisely, we can randomly sample K permutations Ti,..., TK and approximate VerFedSV 8m by
8m KT M U.(Tx(m) (m]) (m(T))))))
(6)
By applying Hoeffding's 's inequality, it can shown Jia et al. for some >> 0 and 8 10, where
2019 that if 2
28 log (M
T U((S)
T
R = max
min SCIM
Σ U.(S)
SCIM]
T
T t=1
t=1
then have P([sm. 8m sm15e)
17

---

Published as a conference paper at ICLR 2024
matrix compettion VerFedSV estimation
150
matrix complition VVereedV estimation
325
matris completion
250
VerFedSV estimation
120
100
t/me(Sec)
Lime(sed)
time time(sec) (sec)
90
75
100
60-
50-
50
30-
0
100
200
500
6000
8000
10000 12000
number of clients M
number of rounds T
number of data N
Figure 4: The efficiency of matrix completion and VerFedSV estimation. The left, middle, and right figures show the run time with varying numbers of clients, time-stamps, and data points respectively.
Table 5: Kendall's rank correlation between the results of SHAP and VerFedSV's.
Adult
Web
Covtype
RCV1
corr(SHAP, VerFedSVs)
1.0
0.73
0.94
0.65
corr(SHAP, Ver
1.0
0.69
0.89
0.63
corr (VerFedSVs, VerFedSVa)
1.0
0.80
0.94
0.80
In summary, the computation for estimated VerFedSV Sm requires O(TM log(M)) calls of the utility function Ug for both synchronous and asynchronous federated learning algorithms, and the computational complexity for evaluating Ug is (MMN). Moreover, according to Equation 66 the computation for estimated VerFedSVs can be parallelized. We numerically demonstrate this com- putational complexity bound the following.
In this experiment, we test the efficiency of computing VerFedSV. As we can see from Section D.I the time complexity of estimating VerFedSV is the same for both synchronous and asynchronous VFL algorithms (they only differ in the training time). So experiment under the synchronous VFL setting. We test the impact of the number of clients M, the number of time-stamps T and the number of training data N on time needed for computing VerFedSV. More precisely, we measure the time, respectively, for solving the matrix completion problem and for estimating VerFedSVs. For consistency, the VerFedSV is computed approximately using Monte Carlo regardless of the number of clients in this experiment. Since the time-varying trends are similar for all datasets, we only present the results on the Adult dataset. The result is shown in Figure 4 First, we focus on the time needed for solving the matrix completion problem in Equation 2 As we can see from Figure 4 the runtime keeps stable as the number of clients M changes and scales approximately a linearly with the number of time-stamps T and the number of training data N, which agrees with our discussion in Section 5 Next, we focus on the time needed for approximating VerFedSV. As relationship with the
illustrated in Figure g the runtime exhibits an almost muadratic-logarithme number of clients M, and nearly linear relationships with the number of time-stamps T and the volume of training data N. This observation aligns with our earlier discussion.
D.2 EFFECTIVENESS OF VERFEDSV
We evaluate the effectiveness of VerFedSV in both the synchronous and asynchronous VFL settings. In other words, we test whether VerFedSV can reflect the importance of clients' local features. We set all clients have the same communication frequency to eliminate the impact of unbalanced local computational resources. We choose SHAP (Lundberg & Lee 2017) as the baseline, which is a widely used metric for measuring feature importance in machine learning. More specifically, we first use SHAP compute the importance scores of all the features, and then for each client, ensemble the scores for all the local features. Note that SHAP cannot be directly used in the VFL task, as it requires access to all the local datasets and models and violates the VFL settings. So here we just use it as reference. We use Kendall's rank correlation (KRC) (Kendall 1938) to measure the similarity between the orderings of the scores of SHAP and VerFedSV. As by-product, also show the similarity between the scores VerFedSV in the synchronous and asynchronous settings. We show in 3a the KRCs between the results of SHAP and VerFedSV, where corr denotes the KRC, SHAP denotes the results from SHAP, VerFedSV, and VerFedSV, a, respectively, denote the results from VerFedSV in the synchronous and asynchronous settings, and the numbers of clients
the
18

---

Published as a conference paper at ICLR 2024
for the Adult, Web, Covtype and RCVI datasets are, respectively, set to M 3, 15,9. 9, 14. Note that KRC returns a value in [-,,1], where "1" means two input score lists have the identical ranking and " "-1" means the rankings are exactly reverted. The KRC between SHAP and VerFedSV are all greater than 0.6. The results indicate that VerFedSV can indeed capture the feature importance well. Moreover, the KRC between VerFedSVs and VerFedSVa a are all greater than 0.8. The results indicate that VerFedSV is consistent under both synchronous and asynchronous settings.
D.3 ABLATION STUDY ON HYPER-PARAMETTRS
Adult
Adult
0.0
304
30
30
20
30
Web
Web
044
0.55
020
015
016
008
6/8
Covtypo
Covtypo
0.58
Devistion
0.6
06
0448
030
020
15
25
RCV1
RCV1
Devistion
05-
03
Ra
Rogularisation weight A
Figure Ablation study on hyper-parameters rank r and regularization X
In this section, examine the sensitivity of VerFedSV with respect to the hyper- ppprr-paraeetess r and used in the matrix completion algorithm, and offer practical guidance for setting these hyper- parameters.
We first recap notations and motivation of matrix completion. As mentioned in Section 5, the key challenge in computing VerFedSV is that, in each iteration, for client m, we only have access to
mini-batch embedding for the current mini-batch B, i.e.,
{ h (m)
i B However, computing
VerFedSV requires full embeddings for all training points in each iteration, i.e., { (m² E [N]] where N is the number of training points. Therefore, matrix completion employed to recover the missing embeddings.
Then, we define deviation metric for the upcoming experiment. For client denote its percentage of VerFedSV relative to the total VerFedSV from all clients 8;- The computation process for VerFedSVs involves utilizing matrix completion to estimate full embeddings. Meanwhile, we com- pute a ground-truth Shapley value, wherein full embeddings are computed in each training round.
The percentage this ground-truth Shapley value for client relative to the sum is denoted as s
With representing the number of clients, the deviation metric defined as 1 -
18m 9
M
This metric necessitates that at be positive ensure it is meaningful.
19

---

Published as a conference paper at ICLR 2024
Table 6: The ground-truth percentage of Shapley value relative to the total sum, denoted by 5
Adult
Web
Covtype
RCV1
Client 46.95
57.36
55,41
81.14
Client 2
17.43
23.21
34.54
5,10
Client 3
35.62
19.43
10.55
13.86
For the experiment setup here, the number of clients M is 3. Meanwhile, since the clients equally partition the features of a dataset, each client has some contribution to the FL model. Con- sequently, we observe that the ground-truth Shapley values sot for all clients are positive (See Table 6). The other considerations for setting M = 3 include: 1) This experiment does not focus on scalability
the numbers of clients M: 2) We want avoid Monte Carlo sampling that could potentially interfere with the results. VerFedSV is computed exactly when < 10 by our default setup. The other setups remain consistent with those detailed in Table 2 and Table 3. For each pair of hyper-parameters, the ground-truth Shapley value is computed once. while VerFedSV is computed times. In each independent run, each client has the same set of features. but different random seed, so the matrix completion algorithm may give different estimations of full embeddings.
The left part of Figure illluttraess the deviation w.r.t the rank r. The median deviation of different runs is depicted by the solid line, while the shaded area represents the interquartile range (25% 75% quantiles) of deviations. Take the Adult dataset demonstrates that deviations are large for r < 5, since inadequate rank cannot accurately recover full embeddings. However, deviation decreases rapidly as r increases and stabilizes at a low value when r 2 5.
example for analysis. The figure
The default ranks (See Table 3) in the previous experiments were set based approximated rank (See Figure []. However, practice obtaining full embeddings resource-intensive due to communication costs or limited resources on the client side. Thus, approximating rank may be difficult. However, the server (with sufficient computational resources), after collecting the mini- batch embeddings, the ground -trut value as revealed by our ablation study.
test with several increasing values of r. The Shapley value will converge
The right part of Figure 5 illustrates the deviation w.r.t the hyper-parameter X. It demonstrates that the performance of VerFedSV remains relatively insensitive across wide range of À and we can safely set À 0.1 for various datasets.
20


Reviews:
[{"review_id": "7PZr4AYmRR", "reviewer": "Reviewer_skLQ", "summary": "This paper proposes a new contribution valuation metric called VerFedSV for vertical federated learning. The VerFedSV metric is based on the classic Shapley value, which is a provably fair contribution valuation metric originating from cooperative game theory. The paper shows that VerFedSV satisfies many desirable properties of fairness and is quite adaptable such that it can be applied under both synchronous and asynchronous VFL settings. The paper also provides experimental results that demonstrate the effectiveness of VerFedSV in terms of fairness and efficiency.", "questions": "Beyond the above weak points, I also have the following questions:\n\nQ1. Please explain the fairness issues caused by model-independent utility function in asynchronous scenario in details. It’s better to give an example.\n\nQ2. Is this paper the first work with model-dependent utility functions in VFL? Are there really just two related works in VFL scenario?\n\nQ3. Please give more explanation about the meaning of embedding h_i^m and how to compute it, which is more friendly to read for people not quite familiar with VFL.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1. This paper proposes a new Shapley value-based contribution valuation metric called VerFedSV for both synchronous and asynchronous vertical federated learning. \n\nS2. This paper provides a theoretical analysis of the VerFedSV metric and demonstrates its effectiveness through experimental results. \n\nS3. This paper addresses an important problem in the field of vertical federated learning, namely how to fairly value contributions from \ndifferent clients.", "weaknesses": "W1. In the last paragraph of Sec. 2, it is said that model-independent utility function itself may cause some fairness issues in asynchronous scenario and cannot fully reflect a client’s contribution. This claim seems not intuitive, it is better to give a concrete example to explain the fairness issues in detail.\n\nW2. There are missing related studies on Shapley Value in federated learning. Please conduct a more detailed literature survey.\n[1] Sunqi Heng et al. ShapleyFL: Robust Federated Learning Based on Shapley Value. KDD 2023. \n[2] Zhenan Fan et al. Fair and efficient contribution valuation for vertical federated learning. 2022. \n\nW3. In Sec. 3, there aren’t enough explanations on the meaning of embedding h_i^m. How to compute it and how it is used to compute the loss are not mentioned either.\n\nW4. It is said in Sec. 8 that VerFedSV increases when adding identical features, which may indicate the proposed method is fragile and lacking robustness in practical use, especially in asynchronous setting.\n\nW5. There are so many typos. For example, in the first paragraph of Sec. 4, the terminology “Shapley” is mistakenly written as “Sharply”, “Shaprley”, “Sharply” for so many times.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7h5qff6yqk", "reviewer": "Reviewer_n6Bm", "summary": "This paper extends the FedSV framework by Wang et al. (2020) to vertical federated learning setting. For synchronous setting, since the server does not have access to the data embeddings to the full dataset, the authors propose an approximation algorithm based on matrix completion given the low rank assumption. For asynchronous setting, since there are no definition of training iterations for the server, the time stamps for contribution valuation is pre-determined. The author conducted experiments to demonstrate the effectiveness of the proposed technique.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The idea of using matrix completion is super interesting.", "weaknesses": "The writing can be improved quite a bit. \n- For example, $d^m$ is used for denoting the feature dimension of client $m$, but $m$ here can be easily misunderstood as exponent. Better to use $d^{(m)}$. \n- Quite a few places use \"Sharpley\". \n- It's good to provide some background about matrix completion algorithm, at least in Appendix. \n- In Proposition 1, what is $D^m$? What is $\\gamma^m$? Again, $m$ can be easily misunderstood as exponent. \n- Proposition 3 can be better stated as an example instead of Proposition. \n\nI am also not too sure about the experiments.\n- What is the dimension of each dataset being used? \n- What does Table 1 supposed to tell? Is it fair to compare the Shapley value of 1 artificial client against all regular clients? \n- How to set the hyperparameters of $r$ and $\\lambda$? I think ablation study is needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GvbVoIy2Y2", "reviewer": "Reviewer_RX3e", "summary": "This paper proposes a metric for contribution valuation in vertical federated learning (VFL). The method is based on federated Shapley value and is adapted to synchronous VFL via low-rank embedding matrix completion techniques and extended to asynchronous VFL. This metric reflects both the quality of the local dataset and the power of local computational resources.", "questions": "1. In VERFEDSV, would it be inefficient to sum over all subsets $S \\subset M$?\n\n2. What is the difference between the method in section 6 and FedSV?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper is overall well-structured and the authors made good efforts in putting this paper in the literature.\n\n2. Low-rank matrix completion of the embedding matrix resolves the issue that its updates are only partially observed in the mini-batch setting. This technique facilitates the application of Shapley value in VFL.\n\n3. The proposed method VerFedSV is theoretical grounded in this work. It is important to verify that VerFedSV satisfies the criteria of balance, symmetry, zero element, and additivity. Detailed proofs and conditions are provided.\n\n4. The authors experimentally validate the methods on real-world datasets and discussed the results.", "weaknesses": "1. Given the setup, it appears that the proposed metric works well only linear models or training only the last linear layer. Although the authors mentioned that results can be extended to a multi-class classification problem and general function, little concrete explanations are provided.\n\n2. There seems be no baselines or comparison with other methods. I understand that contribution evaluation in VFL might not be well-studied before but at least Data Shapley Value can be used here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "G9IKBeU1jJ", "reviewer": "Reviewer_WWnM", "summary": "This paper seeks to assign each client a fair value in the vertical federated learning setting where clients share the same sample IDs but own different features. The paper proposes VerFedSV which consider clients’ contributions at multiple time stamps during training. VerFedSV satisfy desirable properties of fairness, can be efficiently computed without model training and extra communication cost.\nFor the synchronous setting, computing VerFedSV will require the embedding of all data points. However, only the embedding for a mini-batch is available. The paper proposed how to obtain the embedding matrix through low rank matrix completion and show that error in the estimated VerFedSV is bounded.\nFor the asynchronous setting, VerFedSV can be directly and exactly computed for the mini batch. VerFedSV will reward clients with more computational resources (batch size) and frequent communication.", "questions": "Questions\n1. What are the reasons not to use the asynchronous valuation approach (page 7, use mini-batch only) for the synchronous setting?\n2. Existing data valuation works (including those for HFL) usually use a separation validation set for the utility function. If a validation set is used, is the embedding matrix still needed? \n\n\nMinor suggestions\n* The Shapley value is often misspelled as Sharpley, Sharply, Shaprley etc\n* The paper can give some examples/explanation of models and $f$ for the reader to understand why the embedding is sufficient. E.g., what is $f$ for linear and logistic regression (in Sec. 3)\n* After proposition 1, the notation/arguments for the coverage number should be explained.\n* For VAFL, the client has to send the id of the embedding too.\n* Report N and T for the experiments", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written. The content and notations are easy to follow.\n- The study of related work is comprehensive and it is clear how the paper contrasts with prior work.\n- The assumptions (e.g., low rank embedding matrix) are sound and justified (e.g., due to similarity between local data points and during successive training).\n- The paper novelly consider data valuation in the _vertical_ federated learning setting and the _asynchronous_ setting with different local computational resources.", "weaknesses": "- The paper did not discuss or empirically compare to alternatives, e.g., why not request embedding for all data points or value based on the updated mini-batch or a separate validation set? The experiments lack comparison to a ground-truth (request all embeddings) and other baselines (VFL valuation methods).\n- The solution introduced in the work does not seem very novel after considering existing VFL literature and HFL data valuation work. Fan et al. (2022) have used low rank matrix completion to estimate utilities of subsets. In the introduction, it is mentioned that it is more challenging to compute Shapley value to VFL than HFL as it is not applicable (possible) to obtain the global model by concatenating private local models. The challenge has to be further clarified. Is the challenge resolved by using local embedding (as in other VFL work)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)