DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation
Authors: Felipe Garrido
Benjamin Heymann
Maxime Vono
Patrick Loiseau
Vianney Perchet
Venue: NeurIPS 2024 poster (2024)
Keywords: data valuation
shapley value
approximation
Primary area: interpretability_and_explainability

Abstract: We consider the dataset valuation problem, that is the problem of quantifying the incremental gain, to some relevant pre-defined utility of a machine learning task, of aggregating an individual dataset to others.
The Shapley value is a natural tool to perform dataset valuation due to its formal axiomatic justification, which can be combined with Monte Carlo integration to overcome the computational tractability challenges. Such generic approximation methods, however, remain expensive in some cases. In this paper, we exploit the knowledge about the structure of the dataset valuation problem to devise more efficient Shapley value estimators. We propose a novel approximation, referred to as discrete uniform Shapley, which is expressed as an expectation under a discrete uniform distribution with support of reasonable size. We justify the relevancy of the proposed framework via asymptotic and non-asymptotic theoretical guarantees and illustrate its benefits via an extensive set of numerical experiments.

DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation
Felipe Garrido-Lucero
Benjamin Heymann*
Maxime Vono* Criteo AI Lab Paris, France vono@criter com Equal contribution
Inria, Fairplay joint team
Criteo Al Lab Paris, France
Palaiseau, France
felipe. garrido-lucero@in fr * Equal contribution
b. deymann@criten teo. com * Equal contribution
Patrick Loiseau
Vianney Perchet
Inria, Fairplay joint team Palaiseau, France
ENSAE, FairPlay joint team Palaiseau, France
patrick, www..o.wsssaaa..i..o....amm
vianney@ensae. fr
Abstract
We consider the dataset valuation problem, that is, the problem of quantifying the incremental gain, to some relevant pre-defined utility a machine learning task, of aggregating an individual dataset others. The Shapley value is natural tool to perform dataset valuation due to its formal axiomatic justification, which can be combined with Monte Carlo integration to overcome the computational tractability challenges. Such generic approximation methods, however, remain expensive cases. In this paper, exploit the knowledge about the structure of the dataset valuation problem to devise more efficient Shapley value estimators. We propose novel approximation, referred expressed as an expectation under discrete uniform distribution with support of reasonable size. We We justify the relevancy of the proposed framework via asymptotic and asnpssymi theoretical guarantees and illustrate its benefits via an extensive set of numerical experiments.
discrete uniform Shapley, which is
Introduction
One of the main challenges for training machine learning (ML) models with enough generalization capabilities is to access sufficiently large of labeled training data. These data often exist but commonly spread across many parties, impairing their usage in a direct and simple way. Real world examples range from the advertising industry, where different retailers hold sets of observations with either similar or complementary features from consented data about browsing and shopping habits of individual users; to the medical sector where hospitals may improve their diagnostics accuracy by sharing their data. By collaborating with each other and pooling their individual datasets together, these dataser owners could learn better ML models for their applications. Naturally, many questions raise from such collaborations. Federated learning [8, 9], for example, addresses the issues related to the practical ways that dataset owners can share their data. We consider complementary problem to the one in federated learning: measuring the additional value each party would obtain by participating the joint MI. effort. order compute or estimate compensating rewards allowing incentivize parties to share their data, a first stage that is commonly considered in the literature is to perform so-called dataset valuation [1, 42, 44).
Motivated by natural properties expected for fair valuation, different solution concepts from coopera- tive game theory [3] have been considered, the Shapley value [40] being arguably the broadly
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

studied valuation scheme in ML due to its axiomatic justification. Agarwal et al. [1] designed data marketplace and used the Shapley value to allocate the data among buyers. Tay et al. [44] considered a cooperative environment where agents can jointly train generative model, from which synthetic data are drawn and distributed to the parties according to their Shapley values. Sim et al. [42] rewarded parties based on the Shapley value and information gain model parameters. The critical challenge when using the Shapley value is its well-known computational intractability. To cope with it, [1, 44] considered Monte Carlo (MC) approximations, while [42] worked with a small set of three players. This approximation methods, however, remain expensive whenever computing the marginal contributions involve retraining. Moreover, they generic and do not use the specific structure of the dataset valuation problem at stake, leaving open the possibility to find more adapted approximations for that problem.
The Shapley value was also used in the related problem of data valuation. Data valuation measures the contribution of single data point within a dataset in the training of a given prediction model. Several solution concepts based on the Shapley value have been proposed for the data valuation problem including Data Shapley [10, 16], DShapley [11, 24], Beta Shapley [23] or CS- CS-Shapley [38], together with different MC variants to cope with the computational intractability issue. For the data valuation problem, the structure was exploited to give easier-to-comput solutions in certain cases, in particular for the k-nearest neighbor problem [12. 15, 25, 26, 35, 41, 46]. Unlike data valuation, however, dataset valuation aims quantifying the marginal contribution of whole dataset to given ML task with respect to (w..t.) the datasets brought by other dataset owners. Although data and dataset valuation are related problems, they are different and the techniques developed for data valuation cannot be used for the dataset valuation problem that we study (we further develop this point in Section 2.3).
We consider the dataset valuation problem. Following the ML literature, we model it as cooperative game whose value function relates to the considered ML task, and aim at estimating the Shapley value to measure the dataset owners contribution. We propose a new way to address the computational intractability issue of the Shapley value. Instead of relying on generic MC approximation schemes, our approximation method leverages the structure of the dataset valuation problem well as convergence result for key random variable of the problem. Our approximation behaves well in many cases, both theoretically and empirically. More specifically, our main contributions can be summarized follows:
Contributions.
1. We propose DU-Shapley ey (Definition 3), a novel Shapley value approximation that exponentially reduces the number of utility function valuations required for the computation. This is the first dataset valuation approach leveraging the specific structure of the utility function. Based on three different use-cases, we establish asymptotic and non-asymptotic theoretical guarantees for DU- Shappey,, showing notably that it converges almost surely to the Shapley value as the number of dataset owners grows.
3. We assess the benefits of the proposed methodology using extensive numerical experiments on both Shapley value approximation and dataset valuation use-cases. We show, in particular, that DU-Shapley outperforms all considered MC approximations of the Shapley value.
Additional Related Work. Cooperative game theory has been applied to solve multi-agents ML problems beyond data and dataset valuation [6, 18, 47]. In particular, the Shapley value has been used to solve several problems including variable selection [5], feature importance [7, 27, 28), or model interpretation [4]. In these problems, similarly to the data and dataset valuation problems, the computational intractability issue of the Shapley value usually addressed via MC (2, 32).
2 Problem Formulation and Main Concepts Involved
This section presents the dataset valuation problem we aim to solve, along with preliminaries including the definition and classical approximations of the Shapley value. For N and A, we denote [n] := [1. (1..., n and U(AA the uniform distribution with support on A.
2.1 Generic Model
We consider collaborative ML setting involving set I of I [Z] N dataset owners, also referred to as players in the sequel, who are willing to cooperate in order to solve a common ML
problem. Each player e I is assumed to possess an individual dataset D, {xx)), (.,)) bE()
(1)

---

where xt E X C IRd stands for feature vector, uf E )' is a label, n4 [D,] refers to the number of data points in D,, and samples are drawn independently from a player-dependent distribution p.. ie., (x))), .u) ( Ps for all j E [n.] and E I.
Our basic motivation is to quantify the incremental contribution that given player i I brings by sharing her dataset D; with other players towards solving some ML task. Hence, we are interested in scenarios in which, even though the data distribution might differ across players, they face a similar ML task, for instance the minimization of the expectation (with respect to p.) of some loss function ((Y,Y) Y), where y denotes prediction of Y. In such cases, players can usually learn from others' datasets, in the sense that given some X, the optimal prediction Y that minimizes B[E(Y, [)] is the same for all player. This holds, e.g., if the conditional distributions (or, in many cases, simply the conditional expectation) of y(*) given (0) are the same but the marginal distributions of 20) differ.
To model this problem with full generality, we assume that the players i E I collaborate in solving an ML task whose success is measured through some abstract metric u that maps any dataset real number (say, the prediction accuracy in a classification problem). With a slight abuse of notation, for any coalition of players S _ I. we define u(S) 2 =(Ds), where Ds == Us Hence, 2 + R can be seen as game- theoretical utility function that quantifies how well coalitions of players can solve the considered ML task based on the union of their datasets.
The following subsections provide three theoretical use-cases that instantiate the generic model and give specific utility functions illustrate the dataset valuation problem. Using different tools and techniques, Section 3 provides theoretical guarantees in each of them. These theoretical results are then complemented in Section 4 by numerical evidence of our proposed approach in more intricate practical problems on real data.
2.1.1 Theoretical use-case 1: Non-parametrie Regression
The first use case we shall investigate is quite generic and consists in non- pana-aarattic regression. We assume the existence of a function f such that ()) (ax + (2) with n, i.i.d., and a quadratic loss function. Without regularity assumption on f (.), learning can be arbitrarily slow; hence it is usually assumed that this mapping is Lipschitz (or at least 3-Hölder [13, 45]).
The standard estimation method of f we shall consider is called the regressogram or binning (also applied [13] to study local differential privacy within regression) and consists in learning optimal piece-wise constant functions. More precisely, given some parameter B E N-ohosen exogeneously as function of the function regularity 3, the ambient dimension d and the total number of datapoints, typically B = n n the feature space X' is partitioned into B cubic bins. The excess risk of learning f can then be decomposed into
(f) =[(())))==((())]][(=)((=(===== -(())) ((()))++B(((G) (
(1)
where / is the estimator of [(=)== the bin b. The second term in (1) being agnostic the players' datasets, the problem of measuring the contributions of the players to estimating f can be decomposed into measuring their contributions to estimating each fo. In partieular, the utility u(S) of a coalition S can be defined, and split into the sum of B sub-utilities (S) functions, as follows
E and to is any value that f can take on
u(S) = ((((((()))) {(x))
E
DEEL E((is, -((iso-D))(((EE)) =: EDELE) (S))((( 6).
where fs is the estimator of f when using the datasets of all players in S and fs.6 is the estimator Jo when using, for all players in S. the datasets of points in the bin b. Interestingly, after this reduction, the problem is decomposed into B independent sub-problems-one per bin-, where the utility is sole function of the number of data points used to estimate Sh. i.e., we can write (S) = wp (Eis ni,,)) for some function wy : N- + R. where ng is the number of data points that player i has in the bin b. This last property motivates our second theoretical use-case.
2.1.2 Theoretical use-case 2: Homogeneous case
The second theoretical setting considers a general learning problem (not necessarily restricted to regression) and supposes that all players have the same sampling distribution, i.c., it takes pt p
3

---

for all i I. This homogeneity on the players allows to reduce the problem of measuring the contribution of the players to just counting the number of data points contributed by each of them. Formally, and similarly to the previous use-case, we suppose the existence of function w N - IR such that u(S) w (iis nz).
2.1.3 Theoretical use-case 3: Heterogeneous Linear Regression Local Differential Privacy
The third theoretical setting consider is linear regression with random design and different variance of the features and labels per player. Although the setting is more general, one of the motivations behind it is standard linear regression with homogeneous data between players, but where players can purposely add noise when sharing their dataset (in order to provide Local Differential Privacy, for instance). Formally, for any E I, we consider the following linear model that generates the dataset D, of size n4:
v x! n/ where v N(0,,)), and a!!) ((aa.of for any E [mi],
(2)
with E Rd ground-truth parameter, o, positive and known, and e; the differential privacy level chosen by player i. Under the linear regression framework defined in (2), and following [8], the utility function a set S C of players is defined by the negative expected mean square error over a hold-out dataset, i.e.,
u(S) = [[[( T x TO
where the expectation is taken over the distribution Prest of hold-out testing datum Rd the sampling distributions N(O, ofa,) for all i E S, and the linear regression error distributions N(O, 27), vi E S,j E [ng], and Os stands for the generalized least square estimator defined by ûs (X3 ( ng " where Es diag((e?))es)) )ies) RR S|x(S|, The notations Xs and
Ys refer to the concatenation of (Xi)es and ies respectively, and X; Reaxd is defined by
X; = [x while Y, E Th is defined by Y, = (v) (1) ,.," ).)).
The following result provides a close-form expression for the utility function in this case:
Proposition 1. Let S be coalition of players and consider the value function as above. It follows,
-Tr Fx
(Eees("/ee)ma)
u(S) ((8) 1 where q(8)= Eies( (r\/s.) n
with the convention g(ø) 0.
In particular, considering Prest. N(O, Ia), we get u(S) -+I-9(S)
Proposition shows that, in this use-case, the utility function can be written as a function w(g(S)) of a scalar quantity (S)) that captures the datasets heterogeneity. Notice that in this use-case, if we add the homogeneity assumption that 0s/E, a /E, for all E I. then the term (SS) becomes Eies ni and, as a consequence, we get
d
((S) = w(((S)) = w (Eiss mi) = d 1+1-Eam Exes n44
Recall that, in the non-parametric regression use-case, it holds u(8) = EbEIB P(rr (S)
where (S) Eies 7i.6- Therefore, in our three uses-cases, the utility of a coalition can be summarized as the function of some scalar quantity of interest. This observation will be useful to state later our theoretical results.
2.2 Shapley Value
The Shapley value [40] is classical solution concept in cooperative game theory to fairly allocate the total gains generated by a coalition of players. Given a utility function u, the Shapley value of a player i is defined as the average marginal contribution of her dataset D, all possible subsets of (D, (Dyi)ez(()). built by aggregating the datasets of the other players. Formally, the Shapley value p of player writes
(u((u)
1
Σ
[u(P] U U(fi) u(P.)),
(4)
[I(Z)) x EE)

---

where (I) refers to the set of permutations over I and P to the set of predecessors of player i E I permutation π E II(Z). The Shapley value of player equivalently expressed as
p:(u) = - sCrA
('
S ('=1) [u(Su(i)) u(S)
(5)
The Shapley value has been commonly used in ML and cooperative game theory as it uniquely satisfies the following set of desirable properties.
1. Efficiency. E'= (a(u) u(I), i.e the sum of all Shapley values is equal to the value of I. Symmetry. for any S \ {ir, i2 u(S U {ii}) u(S {i²)), then PP (u) (P (u), i.e. whenever two players have the same marginal contributions, their Shapley values coincide.
3. Dummy If, for any S C I (+). u(S U (i) u(S), then sp:(u) 0, i.e., whenever a player has null marginal contributions, her Shapley value is zero
4. Linearity. (u( + u2) = (;(2)) + (22))) i.e., the Shapley value of sums of games is the sum of the Shapley values of the respective games.
MC approximation of the Shapley Value. Evaluating the Shapley value is unfortunately computa- tionally expensive general. As consequence, many MC approximations have been considered by sampling with replacement T terms from the sum of either (4) or (5). Regarding (4), this boils down considering the estimator
(i(u) = T ['
[u(P (() - u(P.))) ))] where Ty ~ U(I((Z)).
2.3 Data valuation vs Dataset valuation
A tentative, but naive, approach to solve the dataset valuation problem could be to run auxiliary data-valuation algorithm on all the data and to assign to each dataset the sum of the values of its datapoints. We highlight the cons of this idea on very simple, yet insightful example. Consider two datapoints Vy and 22, three datasets Dj {xi J. D2 = {22)) D3 = {I2, x2), and the following toy utility function u(D) 1 (x1, 12 E D). In data valuation, any point 222 shall have the same value, as they are identical. In particular, a naive summation would value D3 twice the value of D2. In dataset valuation, and for this toy problem hand, it is quite clear that both datasets should have the same value. Moreover, the Shapley values are 1/6 for D2 and D3 versus 2/3 for D1.
The message here is twofold. Data valuation and dataset valuation concepts and one cannot directly reduce the latter to the former. This is actually true, and this the second message, because the utility function is highly non-linear (even for the regression task).
fundamentally different
3 Discrete Uniform Shapley Value
This section introduces and studies our approximation scheme for the Shapley value. Section 3.1 shows an asymptotic property that gives the general intuition behind our approximation. The result holds for the three use-cases of Sections 2. to 2.1.3. Section 3.2 presents a general approximation methodology for dataset valuation and shows its almost surely convergence as the number of players grows for our three uses-cases. Section 3.3 studies the rate of convergence, first for the homogeneous setting (Section 2.1.2), and then leverages this result obtain similar one for the non- non-paraettric regression setting (Section 2.1.1). All proofs are postponed to the supplementary material.
3.1 Insights behind DU-Shapley
The Shapley value, by re-arranging the coalitions S C I (i) by their cardinality in the sum in (5), can be equivalently expressed as
(u) E S-u (20200 (i) u())
(7)
where 2x T1t denotes the subsets of I (i) of cardinality K. In our three uses-cases, follows that
(u) p:(w) Ex snu (22119) [w[[(S U (i))) w(q(S))]
(8)
5

---

where w. R. - R is such that u(S)= = w(((S)) for any S S I, and g(S) is the scalar quantity of interest identified in Sections 2.1.1 to 2.1.3 for each use-case:
IEies 1 ram)) Eies
for the second use-case, where, for any i I. oi/e, for the third use-case,
(()) = Eies op
(9)
and for the first use-case, ((S) is analogousty defined at every bin, with 7 =1 for all players and all bins. We remark that the definition of (()) in the first and second use-cases is not restricted to linear regression. Equation (8) explicitly reveals a key random variable, namely q(S). Interestingly, Figure suggests that gSS) converges in distribution to uniform random variable as the number of players increases (with ii.d, datasets sizes). Theorem 2 proves this result formally for any (ra)tez.
Theorem 2. Let {na. (ma:7iiie( be two sequences of positive numbers such that the following limits
lim
Σ
EE|T] 747
=
MAi
lim
1 Σ |Ei1]
(1477 - MA)² 02
1-000
1
lim T-
Σ Eil
ni?i
MBB
lim
1
Σ (E(4)
(ni HBB² o
1-000
all exist, for some constants MA. PB 8A,0B O. Let K ~ U(10, 1T), SK U(22)) Then, almost surely, g(Sg)
1400, U(I0 IJ)
q(I)
0' 1).
(D
0' USS
0' U.O
660-
6/9-
K60
400
1.0
X00
10
Figure 1: Distribution of ((S)/q(I) when S is sampled in (8) (i.e., first sample a size uniformly. then sample coalition S of size K uniformly). (left) / = 10, (middle) / = 50, (right) I= 500. We considered 10a samples for each random variable, and the third use-case with n, ~ U((100) and 0./e, U(10)) for each i E I.
3.2 Discrete Uniform Shapley value
The Shapley value re-arrangement in (7) exposes the main tool behind our approximation: it is enough to approximate the distribution the random variable Ds that takes values on the subsets of D= = D, (recall that uSS) = =(Ds)). Theorem 2, taking the example of the second use-case for intuition, indicates that these datasets have uniformly distributed numbers of points the propose to approximate Ds by taking I samples of increasing size from the pool D_, by sampling data points uniformly. This leads to the following definition of DU-Shapley for our generic model:
limit. Generalizing this intuition,
Definition 3. (DU-Shap) Shap Ley] For any i E I, the discrete uniform Shupley value (DU-Shap Ley) of the i-th player, denoted by Vs, is given by
(.(w) - (() UD.) (D((())
where (k) is a set of data points uniformly sampled without replacement from D of size kp- with ||:; 13-1) D-s).
Compared to the Shapley value defined in (5), which involves 2 terms to compute, note that DU-Shapley only involves I terms and hence it presents exponential reduction of the number of utility function evaluations. Of course, these computational savings come at the cost of some bias. The latter is precisely quantified in Section 3.3 for our first two use-cases.
By definition, DU-Shapley is random variable which depends on the sampled data points. However, whenever u(S) w(g(S)), with g(S) some scalar quantify of interest, as in our use-cases,

---

can get rid of the stochastic nature of DU-Shapley by considering / real values from well chosen intervals. particular, in our uses-cases, DU-Shapley ey boils down to:
vi(w) = -
1-1 w(a - w( w(
(10)
where
A (mm, + T-T EjEI N5m4²² Mnn + - EjEzin 23
A EjEry nmn))
q. =
and qC= = I-1 Ejezyra VZ
We remark the notation abuse as we should write vf(w o q). For simplicity, we omit the composition and only write vb(w). Equation (10) coincides exactly with Definition 3 in the first two use-cases, i.., when 7/- y for all j E I. Indeed, the random datasets ((4) have fixed size and the value function only looks at the number of data points within the coalition, we obtain,
(b((u) - Σ v(D()) U..) =(D(*))
Σ w(ID()) UD w(DD(
w (kpss + nz) - wkku-;) = (-ww).
k=
For the third use-case, Equation (10) is approximation that comes from assuming that, for any j E I (i), DD, 7 (b)) = k. F-I. which holds with high probability for large values of I, since
(7am: + Eser b5 [D, n 1
(( UD
72:, Ejervo 23 [D, DDK)
Theorem implies the following result.
Corollary 4. Let Pi and vú be, respectively, the Shapley value (5) and the DU-Shopley (10) of player i. Then, in our three uses-cases, it holds, lim li;; v 0 almost surely.
While our theoretical results are based on Equation (10) for the cases where u(S) (()())). we will see through numerical experiments that Definition 3 gives good results in more general cases.
3.3 Non-Asymptotic Theoretical Guarantees
Corollary 4 states asymptotic guarantees for DU-Shapley. In this section, we show non-asymptotia results that give the convergence rate for the first two uses-cases. Recall that in con-parametric estimation, the utility writes as u(S) E us Px) E b). and therefore, by the linearity axiom of the Shapley value, for any E I, (u) (x)())>>eEBB) (16 (P,)) E b). As a consequence, in order to estimate (u,,,, it is enough to compute each yp; (u,). In particular, the Shapley value approximation error over the whole feature space becomes a simple aggregation of the Shapley value approximation
errors over the bins. We focus firstly on bounding the bias of our method in the homogeneous use-case then extend
the non- parammemetri regression case.
As in the homogeneous use-case the utility function writes as u(S) = w(Eiez nhs), we consider the following regularity assumptions w.
R+ + R is increasing. twice continuously differentiable, and such that lim n2 (2) (n)) < oc (where (2) represents the second derivative).
H1. The function
Monotonicity is natural assumption in our framework as, the more data, the more precise the ML prediction is expected to be. The condition over the limit aims at controlling the growth behavior of the utility function and it is automatically satisfied whenever w is bounded and (()) is monotone, by the mean value theorem. Theorem 5 bounds the bias of DU-Shapley for the homogeneous use-case.
Theorem 5. Under Assumption HI, there exists a constant > 0, such that, for any E I, it holds,
Ip 24
(1 1)p2, (o2, In (I 1)) C-.)
'A similar result, albeit more technical, can be shown with the same arguments for the third use-case.
7

---

where Pi and vi, are respectively the Shapley value and the DU- DU-Shapley of player i, p-i (-ryD-il is the average dataset size of all players but i, -², = - empirical variance, and <-t measures the variability of the dataset sizes across players. Formally, is defined as Ç-i T2 |n mex where R_ maxjer y (0-b), mmx maxzeTA()) njj and T-, := == = /m n--
je 1 p-1) their
The full proof of Theorem 5 is included in Appendix C.3 and it relies on controlling the absolute value of [[w((=i)) v(( m{jees "t]]] where K U(O0,..,, 1}) and S is the random variable in (7). Using second order Taylor expansion, the problem is reduced controlling the term related to the second derivative of w by using the regularity assumptions in H1.
As advertised before, Theorem 5 can be directly generalized to the non-parametric use-case, since,
u(S) - wbb (Eres nH,b )P()))(((
) E b), for n4, (((,,)) Dj, b||-
Corollary 6. Under Assumption HI for all functions Wt. there exist constants Rs > such that, for any E I, it holds that
kgP E (1-1) (0-1,0(1 + In(T 1)) 2(-
pps 1 S Σ
bE Ebe(p)
(11)
where ii and tú are respectively the Shapley value and the DU-Shap ley of player i, and all terms are equivalently defined to Theorem 5 at each bin b E [B].
The upper bound in (11) depends on natural quantities related to the dataset valuation problem described in Section 2.1 at each bin, such as the first two moments μuií and a-i of the datasets' size distribution. More precisely, the error increases when there are some outlier players with a very small or large dataset size. This behavior is expected since, in this particular setting, the random variable inside of the Shapley value differs from a uniform random variable. As showcased in Theorem 2, the error vanishes when the number of players / tends towards infinity.
4 Numerical Experiments
We illustrate the benefits of DU-Shapley by measuring numerically three properties: (1) how well DU-Shapley approximates the Shapley value real data, (2) how many (theoretical) iterations need other methods to achieve the same accuracy level than DU-Shapley, and (3) how well DU-Shapley performs in classical dataset valuation tasks with real data. Appendix A. complements the results by complexity comparison between our method and SVARM [22] and Appendix A.2 by experiments on synthetic data. The experiments strongly suggest that DU-Shapley performs well in all tasks.
4.1
Approximating the Shapley Value in Real-World Data
We consider the real-world datasets in Mitchell et al. [32], whose details are provided in Table 3 in the appendix. To tackle these problems we consider logistic regression models and gradient-boosted decision trees (GBDT). For classification tasks, the utility function has been taken as the expected accuracy of the trained logistic regression model over hold-out testing set while for regression tasks, the utility function corresponds to the averaged MSE over a hold-out testing set. In both cases took hold-out testing set with 10% of the size of the training dataset. For each dataset, considered two worst-case scenarios for our method, namely = 10 players and / = 20 players.
Starting from the datasets in Table 3, we heterogencouully allocate datasets the players. We compare ourselves with two approaches, referred to as Shapley, for the standard MC approximation defined in (6), and MC-anti- MC-anti-Shapley that considers, in addition, antithetic sampling [32]. We compute the averaged MSE across all players between the true Shapley value and each estimator.
Since computing the marginal contributions in this experiment requires re- re-training, which is clearly not feasible for large number of epochs, we chose to restrict ourselves to 20 steps of stochastie gradient descent for logistic regression and 20 boosting iterations for GBDTs. For MC-based approaches, we considered samples to compare those approximations with the proposed methodology on a fair basis, i.c., associated to the same computational budget.
8

---

Table I depicts the results. We clearly see that, even in the worst-case scenario where the number of players is small and far from the theoretical assumptions from Section 3.3, DU-Shapley competes favorably with the MC-based methods.
Table 1: Worst-cass comparison between DU- Shapley and competitors, for real-world datasets considered Table We report the averaged MSE across all players w.r.t. the exact Shapley value.
Dataset
adult
brcast-cancer
bank
cal cal-housing
Players
10
20
10
20
10
20
10
20
DU-Shapley
2.10
6.10
3.10-a
1.10
5.10-2
4.10
1.10
3.10
MC-Shapley
1.10
4.10
3.10 -2
1.10 33
9.10 2
6.10
5.10
2.10
MC-anti-Shaples
8.10
2.10
1.10 2
8.10
8.10
4.10
3.10
1.10
Dataset
make-regression
year
Players
10
20
10
20
DU-Shapley
9.10-
2.10
1.10
7.10
MC-Shapley
4.10-1
3.10-
5.10-3
1.10
MC-anti-Shapleyy
4.10-1
2.10-1
5.10-3
1.10
4.2 Complexity of Computing the Shapley Values of all Players
We have looked at the number of iterations that DataShapley and the Improved Group Testing-Based method [46] (IGTB) require to achieve DU-Shapley's accumulated bias, formally given by
(9o (1 + log(7 - 1)) (-:)² 1/2
K.
DUbias(!) = --1
IE
(M-1)²
To do so, we have replaced
(U respectively, in the formula Section 4.1 in [16] and Equation 5 in [46], with a value function motivated from our third use-case under the homogeneity assumption / a/e for all E I. The results are illustrated in Figure 2. Remark DU-Shapley requires 2 iterations to compute all Shapley values. We observe that in all tested instances, both methods require a higher number iterations achieve the same error than DU-Shapley.
10
10a
IGTU
DuuuStuupky DU-SShapkyy
DutaShaplay DU Shappey
KGTU
10/
IGTU
DataShupley
U/
DL-Shappey
10
107
10'
11
10
19 Players
10
16
101
Players
Players
101
10a
10/1
1GT0
Datadihappey
DataShappay
10
Datathapley
DU-SShapley
DUJ-Shaprey
DL-Shapley
11/
10
107
11F
11P
10
10
10F
135
Number of Players
Number of Dlayers
Number of Players
Figure 2: Iterations required by DataShapley and the Improved Group Testing- method to 10*(2)
achieve DU-Shapley's accumulated bias with function w(ns) number of data points of the coalition S C I, and k(Z) == [log( Σier n4] is normalization factor. (top) d = 0.01, (bottom) ê = 0.1, (left) Remax = 10, (middle) Tamax 50, (right) Amax = 100.
To4l)) where ns is the
4.3 Applying DU-Shapley to dataset valuation problems
We considered non-tabular datasets used in [17], namely bbc-embedding, IMDB-embedding, both text datasets, and
image dataset. Feature embedding have been generated

---

using pretrained DistilBERT and ResNet50 models, respectively. In addition we have adapted three baselines from data valuation our setting: Leave-One-Out (LOO), DataShapley, and KNN- Shapley. Appendix B.2 gives the implementations details. For these datasets associated to classification problems, we used a multi-layer perceptron classifier as prediction model.
We have considered three dataset valuation problems, none of them needing the real Shapley values, which allows us to increase the number of players w.r.t. the experiments in Section 4.1. We investigated noisy label detection (NLD), dataset removal (DR), and dataset addition (DA) [17]. For NLD, we used as a metric the Fi-score (the larger the better). For DR, we used the testing accuracy (the lesser the better). For DA, we used the testing accuracy (the lesser the better).
We considered splitting the dataset actoss 100 players. The results summarized in Table 2. We observe that DU-Shapley has competitive results compared to classical baselines despite of the fact that none of the considered cases verifies the structural assumptions from Section 3.3. In addition, we can see that DU-Shapley tends to have similar and even better results as Data Shapley (which a MC based method). This is in line with our theory as, for larger number of players, DU-Shapley tends to better estimate the true Shapley value.
Table 2: Comparison between DU-Shapley and competitors for real-world datasets considered in [17] in Noisy label detection, Dataset Removal and Dataset Addition.
Dataset
CIFAR 10
BBC
NLD
DR
DA
NLD
DR
DA
Problem
5%
15%
5%
15%
5%
15%
5%
15%
5%
15%
5%
15%
Random
0.11
0.19
0.61
0.60
0.25
0.41
0.11
0.19
0.90
0.88
0.68
0.81
LO0
0.13
0.18
0.60
0.15
0.32
0.11
0.17
0,90
0.88
0.61
0.77
DataShapley
0.13
0.25
0.61
0.59
0.12
0.18
0.12
0.20
0.89
0.87
0.08
0.12
KNN KNN-Shapley
0.14
0.28
0.60
0.57
0.12
0.15
0.19
0.29
0.88
0.86
0.13
0.12
DU-Shapley
0.14
0.30
0.61
0.55
0.11
0.14
0.18
0.34
0.89
0.85
0.07
0.11
Dataset
IMBD
NLD
DR
DA
Problem
5%
15%
5%
15%
5%
15%
Random
0.10
0.16
0.77
0.75
0.62
0.68
0.11
0.18
0.77
0.74
0.53
0.59
DataShapley
0.17
0.28
0.75
0.69
0.36
0.33
KNN-Shapley
0.18
0.29
0.76
0.68
0.41
0.37
DU-Shapley
0.18
0.32
0.76
0.66
0.33
0.34
5 Conclusion
We model the dataset valuation problem as cooperative game and design a Shapley value ap- proximation, named DU-Shapley, that exploits the underlying structure of the utility function and exponentially reduces the number of functions valuations required for the computation. In three different uses-cases, DU OU-Shapley is proved to almost surely converge to the real Shapley value the number of players grows. Moreover, we find the rate of convergence, which depends only on natural parameters dataset valuation. Numerical experiments showease that DU-Shapley performs well in approximating the Shapley value and performing dataset valuation tasks, even when the assumptions needed for the theoretical guarantees do not hold, and it has a good complexity when computing the Shapley values of all players.
Limitations of our method. Our non-asymptotic bound for the non-parametric regression setting in Corollary 6 indicates that DU-Shapley works better when agents' datasets are regular in the sense that they have similar sizes. Hence, a limitation of our approximation that it may work poorly in settings where some players have large datasets compared to others, the distribution of the random variable within Shapley value drives apart from being uniform. Moreover, our convergence result in Theorem (for all use-cases) assume the existence of limits, which roughly requires that heterogeneity between players-in terms of both dataset size and variance- can be bounded. This also indicates that convergence may be not be guaranteed if the heterogeneity is arbitrarily high.
10

---

Acknowledgments
This research was supported in part by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project (ANR-23-PEJA-000S: and through the grant DOOM ANR- 23-CE23-0002. It was also funded by the European Union (ERC, Ocean, 101071601). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
References
[1] Anish Agarwal. Munther Dahleh, and Tuhin Sarkar. A Marketplace for Data: An Algorithmic Solution. In Proceedings of the ACM Conference on Economics and Computation, page 701-726, 2019.
[2] Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial calculation of the Shapley value based on sampling. Computers Operations Research, 3665):1726-17330, 2009.
[3] Georgios Chalkiadakis, Edith Elkind, and Michael J. Wooldridge. Computational Aspects of Cooperative Game Theory. Morgan & Claypool Publishers, 2011.
[4] Jianbo Chen, Le Song, Martin J. Wainwright, and Michael I. Jordan. L-Shapley and C-Shapley: Efficient Model Interpretation for Structured Data. In International Conference on Learning Representations, 2019.
[5] Shay Cohen, Eytan Ruppin, and Gideon Dror. Feature Selection Based the Shapley Value, In International Joint Conference on Artificial Intelligence, page 665-670,20 2005.
[6] Mingshu Cong, Han Yu, Xi Weng, and Siu Ming Yiu. A game-theoretic framework for incentive mechanism design in federated learning. Federated Learning: Privacy and Incentive, pages 205-222, 2020.
[7] Ian C. Covert, Scott Lundberg, and Su-In Lee. Understanding Global Feature Contributions with Additive Importance Measures. Advances in Neural Information Processing Systems, 2020.
[8] Kate Donahue and Jon Kleinberg. Model-sharing games: Analyzing federated learning under voluntary participation. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6): 5303-5311, May 2021. URL httpt:////ff //op:::://sss/s aaai wwwpg/iiddx...e php/ AAAI/ artiaee/eeiccceieee//// 16669.
[9] Kate Donahue and Jon Kleinberg, Optimality and Stability in Federated Learning: A Game- theoretic Approach. In Advances in Neural Information Processing Systems, volume 34, 2021.
[10] Amirata Ghorbani and James Zou. Data Shapley: Equitable Valuation of Data for Machine Learning. In International Conference on Machine Learning, 2019.
[11] Amirata Ghorbani, Michael Kim, and James Zou. A Distributional Framework For Data Valuation. In International Conference on Machine Learning. 2020.
[12] Amirata Ghorbani, James Zou, and Andre Esteva. Data shapley valuation for efficient batch active learning. In 2022 56th Asilomar Conference Signals, Systems, and Computers, pages 1466-1462. IEBE, 2022.
[13] László Györfi and Martin Kroll. On rate optimal private regression under local differential privacy. arXiv preprint arXiv:2206.001 14, 2022.
[14] Wassily Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301):13-30, 1963.
[15] Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas Spanos, and Dawn Song. Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms. Proc. VLDB Endow. 12011):160--163, 2019.

---

[16] Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas Spanos. Towards Efficient Data Valuation Based on the Shapley Value. In International Conference on Artificial Intelligence and Statistics, 2019.
[17] Kevin Jiang, Weixin Liang, James Y Zou, and Yongchan Kwon. Opendataval: unified benchmark for data valuation. Advances in Neural Information Processing Systems, 36, 2023.
[18] Jiawen Kang, Zehui Xiong, Dusit Niyato, Shengli Xie, and Junshan Zhang. Incentive mechanism for reliable federated learning: A joint optimization approach to combining reputation and contract theory. IEEE Internet of Things Journal, 616):10700-1071,, 2019.
[19] R. Kelley Pace and Ronald Barry. Sparse spatial autoregressions. Statistics & Probability Letters, 33(3):291-297, 1997.
[20] Andre Khuri, Thomas Mathew, and Daan G Nel. A test determine closeness of multivariate satterthwaite's approximation. Journal of Multivariate Analysis, 51(1):201-209 1994.
[21] Ron Kohavi. Scaling up the Accuracy of Naive-Bayes Classifiers: A Decision- Tree Hybrid. In International Conference on Knowledge Discovery and Data Mining, 1996.
[22] Patrick Kolpaczki, Viktor Bengs, Maximilian Muschalik, and Eyke Hüllermeier. Approximating the Shapley value without marginal contributions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 13246-13254 2024.
[23] Yongchan Kwon and James Zou. Beta Shaplcy: Unified and Noise-reduced Data Valuation International Conference on Artificial Intelligence and
Framework for Machine Learning Statistics, pages 8780-8802, 2022.
[24] Yongchan Kwon, Manuel A. Rivas, and James Zou. Efficient Computation and Analysis of Distributional Shapley Values In International Conference Artificial Intelligence and Statistics, pages /93-801, 2021.
[25] Weixin Liang, James Zou, and Zhou Yu. Beyond user self-reported likert scale ratings: A comparison model for automatic dialog evaluation. arXiv preprint arXiv:2005. 10716, 2020.
[26] Weixin Liang, Kai-Hui Liang, and Zhou Yu. Herald: annotation efficient method detect user disengagement in social conversations. arXiv preprint arXiv:2106.0016 2021.
[27] Scott M. Lundberg and Su-In Lee. A Unified Approach Interpreting Model Predictions. In Advances in Neural Information Processing Systems, page 4768-4777 2017.
[28] Scott M. Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M. Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. From local explanations to global understanding with explainable for trees. Nature Machine Intelligence, 2(1):56-67, 2020.
[29] Lingjuan Lyu, Xinyi Xu, Qian Wang, and Han Yu. Collaborative fairness in federated learning. Federated Learning: Privacy and Incentive, pages 189-204, 2020.
[30] Olvi L. Mangasarian, W. Nick Street, and William H. Wolberg, Breast Cancer Diagnosis and Prognosis Via Linear Programming. Operations Research, 43(4):570-577 1995.
[31] Irwin Mann and Lloyd S. Shapley. Values of Large Games, IV: Evaluating the Electoral College by Montecarlo Techniques. RAND Corporation, Santa Monica, CA, 1960.
[32] Rory Mitchell, Joshua Cooper, Eibe Frank, and Geoffrey Holmes. Sampling Permutations for Shapley Value Estimation. Journal of Machine Learning Research, 23(43):1-46, 2022.
[33] Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 62:22-31, 2014.
[34] Guillermo Owen. Multilinear Extensions of Games. Management Science, 18(5):64-7, 1972.
12

---

[35] Konstantin D Pandl, Fabian Feiland, Scott Thiebes, and Ali Sunyaev. Trustworthy machine learning for health care: scalable data valuation with the shapley value. In Proceedings of the Conference on Health, Inference, and Learning, pages 47-57, 2021.
[36] Fabian Pedregosa, Gaäl Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vander- plas, Alexandre Passos, David Coumapeau, Matthieu Brucher, Matthieu Perrot, and Edouard Duchesnay. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research, (115)):825-28300 2011.
[37] Gabriel Fernando Pivaro, Santosh Kumar, Gustavo Fraidenraich, and Claudio Ferreira Dias. On the exact and approximate eigenvalue distribution for sum of wishart matrices. IEEE Transactions on Vehicular Technology, 66(11): (0(11)105377-1544 2017.
[38] Stephanic Schoch, Haifeng Xu, and Yangfeng Ji. CS-shapley: Class-wise shapley values for data valuation in classification. In Advances in Neural Information Processing Systems, 2022.
[39] Robert J Serfling. Probability inequalities for the sum in sampling without replacement. The Annals of Statisties, pages 39 49- 1974.
[40] Lloyd S. Shapley, A Value for N-Person Games. RAND Corporation, Santa Monica, CA, 1952.
[41] Dongsub Shim, Zheda Mai, Jihwan Jeong, Scott Sanner, Hyunwoo Kim, and Jongseong Jang. Online class-incremental continual learning with adversarial shapley value. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9630-9638, 2021.
[42] Rachael Hwee Ling Sim, Yehong Zhang, Mun Choon Chan, and Bryan Kian Hsiang Low. Collaborative machine learning with incentive-aware model rewards. In Proceedings of the 37th International Conference on Machine Learning, ICML'20. 20. JMLR.org, 2020.
[43] WY Tan and RP Gupta. On approximating linear combination of central wishart matrices with positive coefficients. Communications in Statistics-Theory and Methods, 12(22):2589-2600, 1983.
[44] Sebastian Shenghong Tay, Xinyi Xu, Chuan-Sheng Foo, and Bryan Kian Hsiang Low. Incen- tivizing collaboration in machine learning via synthetic data rewards. AAAI Conference on Artificial Intelligence, 2021.
[45] Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Publishing Company, Incorporated, 1st edition, 2008. ISBN 0387790519.
[46] Jiachen T Wang, Yuqing Zhu, Yu-Xiang Wang, Ruoxi Jia, and Prateek Mittal. Threshold knn-shapley: A linear-time and privacy-friendly approach to data valuation. arXiv preprint arXiv:2308. 15709, 2023.
[47] Han Yu, Zelei Liu, Yang Liu, Tianjian Chen, Mingshu Cong, Xi Weng, Dusit Niyato, and Qiang Yang. A faireess-aware incentive scheme for federated learning. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 393-399, 2020.
A Complementary Numerical results
All experiments executed on a laptop running macOS 1 and equipped with Apple MI chip with 16GB of RAM. The minimum amount of compute was roughly 5 minutes while the maximum one roughly 10 hours.
A.1 DU-Shapley vs SVARM
We have looked at the probability at which SVARM (Theorem 4 [22]) can ensure, after I2 iterations (without considering the warm up as part of the budget), an eтror equal to DU-Shapley's ' accumulated bias. We have considered the same value function than in Section 4.2 with Nmarr E (2 10 3 10 5. 103, 104) and 100 simulations of sets of players each time. Figure 3 shows the results. We observe how SVARM cannot ensure, with high enough probability, an approximation error equal to the one of DU- Shapley.
13

---

r084 2000
pw 2023
10
Pasc 1006
04
02
Figure 3: Probability that SVARM guarantees an error equal DU-Shapley's bias
A.2 Approximating the Shapley value in Synthetic Data
consider a toy dataset valuation problem associated to our heterogeneous linear regression with local differential privacy use-case (Section 2.3) and we measure the value of coalition S with the utility function close-form from Proposition We consider d
In order to benchmark the performances of DU- Shapley. we consider four competitive approaches, relying on Monte Carlo (MC) approximation strategies [32]. The first one, referred MC-Shapley is the standard MC approximation defined in (6). The second one, coined MC-anti-Shapp
variance-reduced version of MC-Shapley that considers antithetic sampling. The third one coined Twen-Shapla stands for the multilinear extension of Owen [34] which represents the Shapley value as two nested expectations (further explained in Appendix B.3). Finally, the fourth approach, coined arthogonal-Shapplee hypersphere to draw permutations in (4) in a dependent way. To assess the performance aforementioned Shapley value estimators, we used the mean square error (MSE) averaged over all players. DU- UU-Shapley is computed exactly by using (10) while, for each MC-based estimator, we performed 25 Shapley value estimations to compute the MSE. and did it 10 times to obtain confidence intervals for the MSE.
relies on efficient permutation sampling techniques on
Figure 4 compares DU-Sh -hahpple (the horizontal line which does not depend on the sampling budget as we compute exactly) and the MC-based methods, which are computed at several different budgets. The x-axis corresponds to the sampling budget allowed to the MC-bases methods w.r.t. DU-Shapley, ie.. 10-1 means budget equal 10% one of DU-Shapley, 10" means same budget (indicated by the black vertical line), and 10a means 10 times the DU-Shapley budget. Remark that, even when the MC-methods use times the budget of DU- Shapley,, our method keeps approximating better the Shapley value.
14

---

10-1
MC Stappp
NC Ana Sroplyy
20'7
Mc. 2r1 1553249
2wen-Bughy
Oven-Stappt
Orhnn dtopley
0:tta
MSE
MSE
10m
10
10
Sammping budget wir. UwAraapy
Shmppigg budget W.r DUAShaatte
-0-
10-2
10-3
MSE
-0-1
MSE
111
10-5
10-9
10-1
10
10
10-1
10
10
Sampling budget DU-Ehapley
Samp ing budgot DU-Shapiey
Figure 4: Worst-case comparison between DU- Shapley and MC-based approximations with different budgets on synthetic datasets. From left to right, = 10 and I 20, n, U((10)), Vi I. (top) Scenario with small heterogeneity, ai/e, ~ U(10, 10)), vi E I. (bottom) scenario with high heterogeneity, os/e, U([0, 100)), Vi I.
B
Further details about numerical implementations
B.1 Datasets considered in Section 4.1.
Table 3 summarizes the real-world datasets considered in Section 4.1.
Table 3: Datasets considered in Section 4.1.
Dataset
Size
d
Task
adult [21]
48,842
107
classification
breast-cancer [30]
699
30
classification
bank [33]
45,211
16
classification
cal houuiining [19]
20,640
8
regression
make-regression [36]
1,000
10
regression
year [36]
515,345
90
regression
B.2 OpenData Val implementations
In this section describe more in detail the implementations of DataShapley, Leave-One-Our (LOO), and KNN-Shapley for our numerical results in Section 4.3.
DataShapley, applied to the dataset valuation problem, simply corresponds to the method coined MC in Section 4. Therefore, we sample datasets and output the averaged marginal contribution.
Regarding LOO, notice that corresponds to compute just one marginal contribution, usually computed on the big coalition, i.e.,
LOO, == = - u(I \ {i)).
15

---

As players' marginal contributions to large datasets tend to be small, we have preferred to sample one dataset from D and output
LOO; = u(D x(D).
Finally, regarding KNN- ANN--hapley, we refer the reader to [15], Section E.3 of the appendix who explain how to adapt the method dataset valuation.
B.3 Owen's Shapley value approximation
In Section A.2, we considered the Shapley value approximation referred as Swen-Sh as state-of-the-are competitor to DU-Shapley. We provide in the following additional details regarding Owen-Shapley. For the other competitors, we directly refer the interested reader Mitchell al. [32]. Owen [34] studied the multilinear extension of cooperative game and an alternative way to express the Shapley value. Formally, a cooperative game G = (I, u) consists on a set of players I= (1, /) and value function u 2 - I& such that, for any S C I. u corresponds to the value generated by the coalition The multilinear extension of G, denoted when considering the value function ū [0, 1| + R given by,
(I, ū), obtained
EII+ x. II I1)xs)) SCI
17)
jgs
Intuitively, ū(x1, F2,,.., 21) corresponds to the expected value of a coalition when each player i joins the coalition with probability Theorem 5 in [34] gives alternative way to compute the Shapley value (u) of player in game G, namely,
pp(u)= ./- Oū dx, (T,...,)dd = f.' Σ
1| (1-7) ((US (i)) u(S))dr
SCIVE
- E(u(E(T)UU)) - ((()(())))))(((((()(())) E U(0.0))
where (T) is random subset of I \ {i), such that, Vj E (i). is included in (T(r) with proba- bility r. In words, the Shapley value of player corresponds to her expected marginal contribution to the random set (T). when is uniformly distributed on [0, 1]. This brings alternative way to use Monte Carlo to approximate the Shapley value yo (u), coined Sween-Shaplyy. as,
T
BOwen (1) = 7 Σ u(E(T))U)) -((E))))))((())))))) (T))
where for each E {1, T}, we draw independently and uniformly in [o, 1] and then, create random set (7)) by adding each player j {i) to it with probability т.-
C
Missing proofs
C.1 Proof of Proposition
Proposition 1. Let S I be coalition of players and consider the value function u as (3).
follows,
Σ nin))
-Tr 2x0 u(S) ((S) -
where q(S) =
158
with the convention g(Ø) = 0.
Σ 2 T2 iES
In particular, considering Peest N(O, I2), we get,
u(S) +
16

---

Proof. Let S S I be a coalition of players and Xs. Ys be the concatenation of their datasets. The linear model can be rewritten in matrix form as
Ys Xs0 n1s.
where 7s is the concatenation of ( for all E and j [n,]. Take 0s (X3
where Es = diag((ef)eEs), and let ~ prest be hold-out testing datum Rd. follows,
(x 10 0s))
Σ iES
Σ
X,T
ExT
Σ iES
THE m==="x 2x;
iES
IES
=Tr ( Σ mhTT? Xi)
Σ
X (
T
Σ
X 2x²x,)
Σ m/ Tie;2X, X;
x.
YES
iES
iES
YES
Tr F.
Σ
x, Eg (x2x.))
Σ
ME m
Σ Mi x,
Σ
X, &
iES
iES
iE8
iES
Ir TE
Σ x,T ox 2x, 2x.)
x e, 2 Ej x,)
Σ
X E, Xi
iES
iES jES
iES
take expectation with respect to the different stochastic terms. Since ii. (k)
~ N(O, for any
i E k E [n.]. it holds,
E
(n, NNO. [1= 0s))
Tr ræ T
[5,T,,20 "
"ExTT iEs
(ETT= "
iES
iES
Tr rx Σ X, x Xx,
iES
Since players distributions differ on their variances, Eies X, &. 22 corresponds to semi- correlated Wishart random variable where each _x N(0, (2. PL.) In particular, the semi- correlated Wishart random variable can be approximated by central Wishart distribution [37, 43], whose precision depends the homogeneity of the coefficients 0,/e; over all E I, as showed in [20]. It follows.
Σ ExTer2x) VES
"
La
2
(g(S) d 1)
where
( =i))
((S) =
iE8
Σ Ø1
SES
With all this in mind, it follows,
E (n ( (xT(0- (0)))) Ir xT
La
1
Tr T2
(q(S)
d-1)
y(S)
d
(1))
In partieular, considering Prest. N(O,Ia), we get,
d
u(S) d (S))
17

---

C.2 Proof of Theorem 2
Theorem 2. Let (ne, Whe be two sequences of positive numbers such that the following limits
lim
n.7s =
MA,
lim
1
1
Σ (E
(147) - Ma)² = o
10000
1
1
1
lim T-sno
nin = PB.
lim
(n HBB² = o
1-000
all exist, for some constants PA PB, 0 A. 0B > O. Let K U((O,..., 1}), SK ~ U((2k)) and
:.....,)))
define q(Sk) as in (9) for the third use-case. Then, almost surely, s(Sk)/9(2)
10000 U( 1)).
Proof. Introduce, for any t, to E (0, 1) and any s>0, 0,
1 Σ
1 Σ ni7
Ma(T)= -
nt% (B([I= -
iE[T]
.E(T]
(a(t, = Σ
YB(t, = Σ
147
niy7
iES
iES
(a(l, (1(
(o,
sup 1>16
> 8
[Tt]
(B T)
RB to 5) =
sup ttta
m >8)
[[t]
By construction, (t(t, I) and (t, I) are sums of sampling without replacement of [[]] elements. Therefore, by Corollary 1.3 in [39], for s fixed, there exists I6. 10 E .N such that,
(1 to)oa
VA 2 lo and RB (1- to
RA(1, to. 8) S
IA
10
[1
[1bo] 82
In other words, for any > and large enough, almost surely, it holds,
It,
It(
pa(t) S s and
pB(l) S.s s.
[tt]
[1t]
follows,
q(S rej)
(a(1)
1 Y)(t,1) pA(1)²
[1t]
(T)
It] In(1,) (n(()
(1,
[1t]2 ma(I)² + +Pa(T)))
(1 [18
Yn(t,
HB (()
()(
Lnre Ha(1))) mB(l)
+
1
HA(!) + MB([))
which is arbitrarily small nA (1), (b( PA.BB co. Therefore, almost surely, ((5 1-000
lim IHa(())/HUB(I) = t.
The proof concludes noticing that
(T) = INA(T)2 [T(
and that K [1U] with U U).
C.3 Proof of Theorem 5
To prove Theorem 5, we need two preliminary results: Lemma which itself needs two supplemen- tary results (Lemmas I and 2), and Lemma 4, which is directly proved.
18

---

C.3.1 Technical lemmata
Lemma 1. Consider set of I values N = (ni...., n1). Let XI..... X5 and Y...... Y& denote, respectively, random samples with and without replacement from N. For any continuous and convex function J. it follows,
k
E
Yi
SB
Proof. The proof follows from [14].
Lemma 2. Let I E N, == mn E 14,, = E be their mean value and
o² Ei (m= 11)² be their variance. For k E (0,..., n], lei Se ~ U({S C C |Sa| = k)) be uniform random variable on the subsets of [I....,Iy of size k, and n.s = Lies, n be the random variable defined by the sum of the elements of Sy. Let K U({O, 11} and define 115k. Then,
Y - μK| K K k] 00
(12)
B[(Y - -uk)² K K= k]] S ko²
(13)
Proof. We prove (12) directly.
Y K k)
Σ
Σ n4
S.
Σ
Σ 74
iE
S. SLI
+ESk
k (1-1)
nu
1
iE[1
(I k))R!
(I-1)!
Σ n1
pk:
(I: - 1)!(I - k)!
(E(2)
Thus, (12) follows as B[uK| K kj pk. To prove (13), let (X.) be ks independent samples from the set N. From Lemma it holds,
( - 2K)² K k] < E
(uk - xx)
K
K =
=E
1EE (u
K
x.)) (ux-xi) |K =k
Therefore,
K K
(UXY-KK22 K= k] S
Σ
(1r - xx)
K = k
i=l ==
E
(n² (xx: +x,++xxx,))))
K |K=
(n²
(B|, K= K K + B[X,X, K K= kI)
(1²² ( +Xx + =X,,X,1))
Σ
(1e 2
x + +(+)
(1e
111
1=1 1= 1=1
3
19

---

k
18 (uu
x.)²
(n² 24²² + x22)
i=1
j=1 jyl
k B [1 x
k Var (μ - X;) = ko
)
1m1
The steps come from rearranging the terms, using the independence of X, with respect K, the independence of X,, X, for # J. and finally that E[X,] = μ and Var (X+) = =².
Lemma 3. Let I =
E IR4, and define,
0²
Σ 1=1
[n u)²
maa
max fl5s IE
R = max [24 - pa/,
T max n min n2.-
sE
aEll]
Consider Sk, nSg K, and as in Lemma 2. Let w R4 + IR a function in C², increasing, and suppose there exists E R4, such that,
I ( S n Vn vn>0,
where w(k) is the k-th derivative of w. Then, holds.
2R²,2 max
[[w((UK) w(Y)]l
2p²1 90 (1 +
Proof. The proof considers a second-order Taylor extension of w at juk to recover the expected value of ([j( ur( (Y)) Noticing that the first derivative has null expected value, the upper bound stated on the Lemma comes from bounding the expected value of the second derivative.
The Taylor-Lagrange Theorem w at puk > 0 provides,
w(y) = w(kkk) + w (Hk)( y) + ww ( (uk y)
for some between y and puk Therefore, there exists random variable T, almost surely between μ and Y, such that,
E (Y) w(rK+)) (uK Y) (2) (T)(K, r)²
where K2 corresponds to conditioned to be positive, To avoid overcharging the notation, we drop the index from K.. We observe that,
W (uK) x) = (KK) Y) K = k]
(wk) - 8) K k|] = 0,
by Lemma 2, Equation (12). Therefore,
E[w(Y (Y) w(rK)]
E (TK Y)
2
- E
(T) (uK -Y
K
(uK y)²
K "E T (uK - y)
E
2
T2
Setting I : {luK Yl b + Y)).
the previous expected value can expressed as,
To (uK x/2 = (uK Y)² 1 +
1
1
E
T (uK 2)2. 1
20

---

We deal with each term separately. Notice that, as T is almost surely between Y and pk,
1uK Y - (uK Y)
T
3
guk.
Thus,
E
(μK
Y)²
1
(uK Y)2
I
9
Σ
1
E
(uk:
Y)2 K = k
I
T
(
1ra k=
I
k²
9
(pk Y)²
E
K
K
1n
k²
9
kg²
11 k=1
k.2
9a²
$ I
(1 + In()))
Regarding the second term, denote maxiez n4 and n == mintez Thg As Kn S min(uK, YJ S
T, we have,
(nK
Y)2
(RK)2
2
(RK)2 (nK)²
r
E
I
E
II
T2
T
R²
k22
K = k
In?
22
R
PP
|lak
Yl
> 2 Elukk + Y) K =k)
1
R2
uk
[ - Y
K =k
Ina
2
R
122k
exp
T
2TT.
1=
2R
112
12k
Σ
exp
1,2
2n
2T
2R-
112
21
exp
dk
1u2n
2n
2n
1,2n
as the integral corresponds to the cumulative distribution function of an exponential random variable of parameter À = /2/ The upper bound on the theorem's 's statement is obtained when gathering all together.
Lemma 4. Let w R4 + R,, be a smooth and increasing such that
lim n² w (1()) < <x.
Then, there exists >> such that n² (2) (n)l S K.
Proof. Notice that the assumptions imply, in particular, that (n)) is bounded. We argue by contradiction. Suppose that for any m > 0, there exists such that
w ml)) > m.
Suppose the sequence (nm) converges to a point n²" Then,
2 lim nmm wl (2) (2) m=000
> lim m = co, m=+00
21

---

which is contradiction with (n)) being bounded. Therefore, necessarily (nm) has to diverge. However, this implies.
lim n 10 (2) (n))
lim n mm/ (nm)) > lim m 0o, m=-00
n 200
m=000
obtaining again a contradiction.
C.3.2 Proof of Theorem 5
We ready prove Theorem 5.
Theorem Under Assumption HI, there exists a constant 0, such that, for any E I, holds,
Ips u. (1 1)₁² (o2,(L+ In(1 1)) +
where Pp and vi are respectively the Shapley value and the DU- DU-Shopleg of player i, p_1 T-. EjErao n2 is the average dataset size of other players, o², T ΣjET(( (ng p_1)² its empirical variance, and Ç-i measures the variability of the dataset sizes across players. Formally, is defined as
S-s = R 4n max
where R_ = maxjer(() [n /1-/). n max maxjeTi(() ng and T_: minjezy
Proof. Under Assumption HI, Lemma 4 implies the existence of x > such that the value function satisfies all assumptions from Lemma 3. Theorem comes from (a) noticing that
f = [[ + m4) -Y)_))),,
1/ B[w + n4) w: w((K)_)))
where K ~ U([ 1]) and Y
n ss with (())
Sk taking values the subsets of {i) of size K,
(b) writing
1 v4l $ [1( Y n4))
w (Kp_: nt)ll + [ w(K,-))ll
and (c) applying Lemma 3 to each of the expected values, the function - w(n + n2) also satisfics HI.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Both abstract and introduction states exactly what we proved in our article.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: A limitations section included in Section 5. Moreover, all mathematical assumptions are clearly stated on the main article and discussed.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

Justification:
Assumptions are stated in each theoretical result and all proofs are included in the supplementary material. We have carefully checked the accuracy of all mathematical steps.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: At the beginning of each numerical results section we explain the used methodology and the sources of the used data. Besides, Appendix B complements these
descriptions.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
24

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
The codes included and the implementations detailed in the appendix.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (uttps://nips.cm co/
conooccyl)) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips. cc/ wtc/public///e hwwlliic/giids///eee /CsdeSuudmmmiicc iindabbissse ieiiionooiccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All details are explained in each numerical results section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
The experiments in Section 4.2 and Appendices A.I and A.2 present error
bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
25

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All details are included at the beginning of Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that NeurlPS Code of Ethics https: http:://neeuu.eeeeeeee http///uurrpccppuptieeee cctppblic//eeeeccccccccccceceect httpai//eehhccuieeellliliil
didn't I make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification:
The research conducted conformes with all points in the NeurIPS Code of
Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss potential applications in Section 1.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
26

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All creators are properly credited by citing their works.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi wwwode.hho....c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
27

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "7mA3LRNats", "reviewer": "Reviewer_C64x", "summary": "This paper proposes a general dataset valuation method which only requires N number of utility function evaluations, where N is the number of players. The approach is motivated by a homogeneous setting for linear regression, but experiments also show the effectiveness of such an approach in general settings.", "questions": "What's the specific MC estimator being used for computing Data Shapley in the experiment?", "limitations": "See weaknesses.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is easy to read and has a very clear structure. The topic is very important as existing data valuation approaches mostly focus on data point-level valuation, while this paper focus on dataset-level valuation.", "weaknesses": "I have reviewed this paper at ICML. The paper has addressed most of the issues in this revision and has a huge improvement. My remaining concerns are the following: \n\n**Computational complexity.** \nWhile DU-Shapley only requires $I$ utility function evaluations for a single data owner, if we want to evaluate all data owners it still requires $I^2$ function evaluations. This is worse than the group-testing estimator introduced in [1] (a refined version can be found in [2]), and I believe [3] has already reduced the complexity to $O(I \\log I)$. \n\nI did not verify the correctness of the results in Section 3.3, but the expressions seem to be reasonable. \n\n[1] Jia, Ruoxi, et al. \"Towards efficient data valuation based on the shapley value.\" The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019.\n\n[2] Wang, Jiachen T., and Ruoxi Jia. \"A Note on\" Towards Efficient Data Valuation Based on the Shapley Value''.\" arXiv preprint arXiv:2302.11431 (2023).\n\n[3] Li, Weida, and Yaoliang Yu. \"Faster Approximation of Probabilistic and Distributional Values via Least Squares.\" The Twelfth International Conference on Learning Representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the anonymous reviewer for the remarks and questions.\n\n1. Regarding the **computational complexity** discussion, please refer to the general answer.\n\n2. Regaring your **question**, the MC estimator used to estimate the Shapley values is the one presented in Equation (6), also coined DataShapley in the general answer or *baseline* in [1].\n\n[1] Jia, Ruoxi, et al. \"Towards efficient data valuation based on the shapley value.\" The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019.", "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": "J5kLlSH1qy", "reviewer": "Reviewer_WTCU", "summary": "The paper studies dataset evaluation with Shapley value. They assume that each dataset contains i.i.d. data points from a distribution and exploit the knowledge about the structure of the underlying data distribution to design more efficient Shapley value estimators. Based on asymptotic analysis of Shapley values of datasets, they propose an approximation of Shapley values of datasets. They prove estimation error bounds for non-asymptotic settings. The estimation accuracy is tested via numerical experiments in certain settings in comparison to other approaches. They also test the effectiveness of the approach for noisy label detection, dataset removal, and dataset addition.", "questions": "1. What’s the reason for choosing 20 SGD steps and 20 boosting iterations? Will the experiment results significantly change when the numbers increase?\n2. Could you explain the improvement in computational efficiency compared to Jia et al. 2019?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper explores a novel setting in which Shapley values are computed for datasets comprising i.i.d. data points. Leveraging the distributional structures of datasets, they propose an approximation method that reduces running time. Their theoretical analysis is novel and strong, offering valuable insights into the distribution of Shapley values for datasets under some assumptions. They show by experimental results that this approximation method outperforms other MC-based approaches with computational power is limited.", "weaknesses": "In the context of dataset evaluation, previous data point Shapley approximation methods can still be applied by treating the dataset as a single entity. The main advantage of this new approach appears to be its improved computational efficiency compared to earlier Data Shapley methods. However, the computational efficiency improvement is not thoroughly discussed or demonstrated through experiments, which primarily focus on estimation accuracy.\n\nThe theoretical analysis relies on certain distributional assumptions, potentially limiting the approach's applicability. For instance, the accuracy of the estimation seems dependent on having a large number of data providers. In contrast, previous Data Shapley approximation methods, such as those proposed by Jia et al. (2019), do not appear to require these assumptions. Furthermore, the difference in the number of retraining iterations, O(n log n) versus O(n), is not substantial.\n\nThe use cases for dataset valuation are not well articulated. Common tasks like noisy label detection, data removal, and data addition are typically considered at the data point level. It is unclear why the data needs to be removed as a set rather than individually.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the anonymous reviewer for the remarks and questions. They are all addressed in detail in the following.\n\n1. Concerning the **computational efficiency improvements** of our method, we have conducted new experiments. Please refer to the general answer for the results.\n\n2. **Distributional assumptions**. Again, we kindly ask to refer to the general answer. We remark that, although former methods can achieve a lower complexity when computing all Shapley values, our method achieves much more precise approximations.\n\n3. **Dataset valuation use-cases**. Dataset addition and removal find several applications in industrial scenarios or theoretical domains such as federated learning and collaborative learning.\n\n4. Answer to your **1st Question**. We have considered the same setting as in [1], with 20 SGD steps and 20 boosting iterations instead of 100 for speed of computations. Concerning the results sensibility to the parameters, the ranking between the methods does not depend on this choice but only the relative difference between them.\n\n5. Answer to your **2nd Question**. Please refer to our general answer.\n\n[1] https://arxiv.org/pdf/2104.12199", "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": "A7EpEgiAP2", "reviewer": "Reviewer_VRG1", "summary": "The paper proposes a novel proxy for the Shapley value (SV) which is called discrete uniform (DU) Shapley. Unlike the SV, this proxy does not suffer from the exponential complexity problem of the SV. Of course the DU Shapley, therein does not capture all information entailed in the SVs for a cooperative game. The DU Shapley are motivated and derived from the setting of dataset valuation. Dataset valuation is a similar setting to data valuation, with the difference being that not individual data points are making up the player set but collection of data points. The work studies this dataset valuation setting and the DU Shapley theoretically and performs empirical experiments illustrating the effectiveness.", "questions": "1. How does DU Shapley compare against stronger approximations like Kernel-based estimators (aka. KernelSHAP) or stratified methods like SVARM?\n2. I am a bit confused by your statement in line 305. Did you run the MC estimations on 10 or 20 subset evaluations as the computational budget? The axis description in Figure 3 also does not help.\n\n## Suggestions\nI have run a similar setup for the cal. housing experiment as you do in Section 4.1. I compute the ground-truth SVs for a 10 player dataset valuation setting. The SVs are as follows (empty-set is manually set to 0):\n- $D_1$: 0.05790964954064733\n- $D_2$: 0.06817158889611828\n- $D_3$: 0.07737767986447398\n- $D_4$: 0.08361640115201878\n- $D_5$: 0.08403403608007484\n- $D_6$: 0.08978074706995469\n- $D_7$: 0.08771940889382171\n- $D_8$: 0.08772011962276798\n- $D_9$: 0.09842460151765661\n- $D_{10}$: 0.11083578157985912\n\nThe dataset sizes are monotonically increasing from $1$ to $10$, which is inline with the papers claims in regards to the behavior of the SVs. The SVs also increasing (though not so monotonically but still increase) mainly depending on the size of the datasets. Note that for this a gradient boosted tree (as implemented in xgboost) is fitted without any HPO. I suggest to add something similar to this in an illustrative/abstract way to show how the value function behaves and make this clear to a potentially unfamiliar reader too motivate this solution better.", "limitations": "The work contains a separate limitations section.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- **Theoretical Results:** The work studies the setting of dataset valuation in a theoretical and well-substantiated manner. While I think details of 2.1.1, 2.1.2, and 2.1.3 may be deferred to the appendix to expand on 2.2 and 2.3, the theoretical analysis of the dataset valuation problem is a good contribution. Further, the theoretical results regarding DU Shapley and the mechanisms behind it (for Example Figure 1 and Figure 2) support the work well. \n- **Empirical Evaluation For Data Valuation:** While DU Shapley is not proposed for the data valuation task but rather dataset valuation, the work also contains evaluations with OpenDataVal highlighting that DU Shapley can also be applied to this setting. This is particularly interesting since these values are quite cheap to compute offering a good baseline for future work or an initial insight before applying more costly approaches.\n- **Empirical Evaluation in real-world scenarios:** The paper shows how DU Shapley seems to be a viable approach to use as a proxy stand-in compared to other sampling-based baseline methods in traditional machine learning settings. This shows that even when the assumptions made on the value function are not fulfilled the estimates are still better than estimates from alternative methods. I still think better comparisons could have been made (c.f. Weakness Section).\n- **Reproducible:** Working on a related problem with the same problem formulation, I observe the same results this paper hypothesizes and describes in its formulation. With increasing dataset size the worth of a dataset increases (though not monotonically but still increases). The proxy approach of DU Shapley seems to work very well in this setting. I suspect this also to hold for different data modalities like text or images, which could be a fruitful future research direction.", "weaknesses": "## Major Weaknesses\n- **Weak Baselines** The empirical evaluation (comparison against sampling) compares the effectiveness of DU Shapley in with subpar and not interesting baselines. The evaluation does not include the KernelSHAP [1] method for computing SVs. KernelSHAP in many areas outperforms the sampling based estimators by a large margin. Further, as the work hypothesizes and arguments strongly that the size of a dataset (and thus also the coalition size) is important to determine the worth of it, methods like SVARM [2] that are derived for this setting are also missing from the empirical comparison. Both of these methods are not compared, which might strongly alleviate the performance increase of DU Shapley compared to the current baselines.\n- **Weak Sampling Budget** It seems like the empirical evaluation comparing DU Shapley with the sampling-based black-box estimators (Section 4.1) uses a very low computational budget for the estimators. While it is true that when DU Shapley requires a very low budget, a fair comparison would want to compare the current state of the art in the same settings. However, DU Shapley is a proxy for the SV. There it is definitely interesting to also see when the state-of-the-art catches up with the proxy. While it is very obvious that the proxy DU Shapley value is much better in these very low dataset valuation settings. However, the other methods estimate the SV and might get better in a reasonable time (in terms of computational budget). This should be evaluated well with proper error/evaluation curves for different estimation budgets.\n\n## Smaller Weaknesses\n- **Too little Focus on Data Valuation vs. Dataset Valuation:** I think this work may benefit from a better high-level motivation, and looses itself in too much details (2.1.1, 2.1.2, and 2.1.3 make up 1.5 pages). These motivating examples could be shorter and placed in the appendix to make more room for a broader theoretical background delineating this works contribution from the classical data valuation setting better than the rather short intermission with Section 2.3. I would also think that actually plotting/visualizing these Dataset Valuation attribution values for a ground truth setting would help. It is not tangible how these values actually look for real-world scenarios from Section 4.2.\n\n\n## References\n- [1] https://proceedings.neurips.cc/paper/2017/file/8a20a8621978632d76c43dfd28b67767-Paper.pdf (KernelSHAP in my opinion is better explained here: https://proceedings.mlr.press/v130/covert21a.html)\n- [2] https://ojs.aaai.org/index.php/AAAI/article/view/29225", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the anonymous reviewer for the remarks, questions, and suggestion. They are all addressed in detail in the following.\n\n1. **Weak Baselines**. We thank the reviewer for the references. We have conducted experiments concerning the theoretical probability at which SVARM can guarantee an error equal to DU-Shapley's bias. Please refer to the general answer for the results.\n\n2. **Weak Sampling Budget**. We have performed extra experiments comparing our method with Monte Carlo and the improved Jia et al.'s method in [1] by looking at the number of iterations that both of them require to catch up DU-Shapley. Please refer to the general answer for the results.\n\n3. **Too little Focus on Data Valuation vs. Dataset Valuation** We agree with the reviewer that the article may benefit from a longer discussion about data valuation vs dataset valuation. We will extend this section in the final version if the article is accepted.\n\n4. Concerning your **1st Question**. Please refer to the general answer concerning SVARM. Unfortunately, due to the time of rebuttals, we have not been able to study KernelSHAP, but it will be considered in future versions of the article.\n\n5. Concerning your **2nd Question**. Both. For $I = 10$ players we have done 10 subset evaluations while for $I = 20$ players, we have done $20$.\n\n[1] Wang, Jiachen T., and Ruoxi Jia. \"A Note on\" Towards Efficient Data Valuation Based on the Shapley Value''.\" arXiv preprint arXiv:2302.11431 (2023).", "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": "ZqndPeLMSd", "reviewer": "Reviewer_Q5wB", "summary": "This paper studies the problem of dataset valuation, a variant of data valuation, where the contributions of multiple datasets, instead of single data points, to a metric such as performance of a machine learning prediction model are quantified. The authors analyze the computation of the Shapley value, where each player represents a single dataset. In this context, it is argued that the utility function (or game) is essentially determined by the size of each dataset, which is theoretically supported by three general synthetic use-cases involving piece-wise constant functions, homogeneous data distributions, and linear regression with noisy labels, related to local differential privacy. The author present \"Discrete Uniform\" Shapley values (DU-Shapley), which approximates the Shapley value under this assumption efficiently. If the assumption on the utility function is satisfied, then the method can be further simplified by constructing suitable intervals instead of sampling, where the authors show for all use-cases asymptotic convergence (for infinite number of datasets) and non-asymptotic theoretical guarantees for the first and second use-case. The authors then evaluate their approach empirically, on multiple benchmark datasets against permutation-based Monte Carlo approaches, and on OpenDataVal benchmark tasks.", "questions": "- Could you explain a bit more the intuition behind the DU-Shapley approach and Definition 3? In particular, the definition of $D^{(k)}$ is unclear to me, \"is a set of data points uniformly sampled without replacement\", it seems to me that it is the union of $k$ datasets rather than $k$ data points? If not, then $u$ is not defined for this setting? Maybe a pseudo-code algorithm would help.\n- Could you elaborate on section 3.2? I did not understand the derivation of (10) from Definition 3 using the assumption. In particular, how does (10) not depend on the sampled data points anymore from Definition 3? These seem to be two different estimators.\n- It seems that DU-Shapley has to be computed for every individual dataset separately? Could you comment on this limitation, and is there a way to circumvent it? I think this should be included in the limitations sections. Furthermore, the method then has quadratic complexity?", "limitations": "The author discuss limitations of their work, which centers around the applicability of the approach when dataset sizes and variances are strongly heterogeneous.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- Dataset valuation is an important variant of data valuation and analyzing the structural properties of the involved utility function is an important research question. \n- The paper is well-structured and the mathematical notation is precise and understandable\n- The paper presents interesting theoretical results for synthetic use-cases, which have direct consequences for the computatability\n- The empirical performance on OpenDataVal tasks is promising", "weaknesses": "- The baselines in the experimental evaluation of the Shapley value approximation are limited. The authors only consider permutation sampling (with antithetic sampling as a variant) as the main competitor. However, there exist a variety of other methods, cf. evaluations in [1], that have been applied in data valuation and outperform this approach\n- There is no evaluation, if the assumptions / structures of DU-Shapley specific to dataset valuation are apparent in real-world applications. Especially, it remains unclear if the synthetic use-cases are related to real-world applications.\n- Section 3.2 is hard to follow, especially the derivation of (10) from Definition 3. In particular, it remains unclear to me, how Definition 3 and (10) are the same estimator, and what is the intuition behind Definition 3, which is used in real-world applications.\n\n**Minor Comments**\n\n- In Table 1, it is unclear which values are bold (top-2 or best)? It seems inconsistent.\n- Related work could be improved, there are several algorithms for Shapley values, cf. the methods in [1,2,3].\n- Instead of saying \"exponentially reduce the complexity\", e.g. line 62,  it would be better to state the complexity\n\n\n[1] Li, W., & Yu, Y. (2023, October). Faster Approximation of Probabilistic and Distributional Values via Least Squares. In The Twelfth International Conference on Learning Representations.\n\n[2] Chen, H., Covert, I. C., Lundberg, S. M., & Lee, S. I. (2023). Algorithms to estimate Shapley value feature attributions. Nature Machine Intelligence, 5(6), 590-601.\n\n[3] Kolpaczki, P., Bengs, V., Muschalik, M., & Hüllermeier, E. (2024, March). Approximating the shapley value without marginal contributions. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 12, pp. 13246-13255).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the anonymous reviewer for the remarks and questions. They are all addressed in detail in the following.\n\n1. **The baselines in the experimental evaluation of the Shapley value approximation are limited**. Please remark in Table 2 that we have also considered KNN-Shapley and LOO. In addition, the experiments showed in the general answer consider the SVARM method 1], as suggered by reviewer VRG1.\n\n2. **Evaluation of the assumptions in real-world applications**. Assumptions in the article have been done specifically to being able to deduce theoretical guarantees. However, our method is not limited to these assumptions and can perform well in real-world applications as our experiments show.\n\n3. Concerning your **1st Question**. Definition 3 consists in (a) pooling all datasets $(D_j, j\\neq i)$ together to create $D_{-i}$, (b) sampling $I$ datasets from $D_{-i}$, respectively, of sizes $|D^{(k)}| = k \\cdot \\mu_{-i}$ for $k \\in (0,...,I-1)$, where $\\mu_{-i} = \\frac{1}{I-1}|D_{-i}|$, and (c) computing the average marginal contribution\n$$\\frac{1}{I}\\sum_{k=0}^I u(D^{(k)} \\cup D_i) - u(D^{(k)}).$$\nIn particular, each $D^{(k)}$ is obtained by sampling $k\\cdot\\mu_{-i}$ data points from $D_{-i}$ without replacement. Remark, therefore, that $D^{(k)}$ is not the union of $k$ datasets but a set of $k\\cdot\\mu_{-i}$ data points where each data point can come from any dataset $D_{j}$ for $j \\in \\mathcal{I}\\setminus\\{i\\}$. Moreover, data points may belong to several sets $D^{(k)}$.\nWe agree with the reviewer that a pseudo-code may help to understand DU-Shapley. Unfortunately, due to the space constraint, we have preferred to express DU-Shapley as a formula to being able to state our posterior theoretical results.\n\n4. Concerning your **2nd Question**. We thank the reviewer for this question, as it has helped us to remark that we have left an old version of Equation (10) in the article. The updated version is,\n\\begin{align*}\n\\psi_i(w) = \\frac{1}{I}\\sum_{k=0}^{I-1} w(q^{(k)}) - w(q_{-i}^{(k)}) \\text{ where } q^{(k)} := \\frac{(\\gamma_i n_i + \\frac{k}{I-1}\\sum_{j\\in \\mathcal{I}\\setminus\\{i\\}} \\gamma_j n_j)^2}{\\gamma_i^2 n_i + \\frac{k}{I-1}\\sum_{j\\in \\mathcal{I}\\setminus\\{i\\}} \\gamma_j^2 n_j} \\text{ and } q_{-i}^{(k)} := \\frac{k}{I-1}\\cdot q(\\mathcal{I}\\setminus\\{i\\}).\n\\end{align*}\nThe purpose of Equation (10) was to give an easier way to compute DU-Shapley. Remark the updated version coincides exactly with Definition 3 in the first two use-cases, i.e., when $\\gamma_j = \\gamma$ for all $j \\in \\mathcal{I}$. Indeed, as the random datasets $D^{(k)}$ have a fixed size and the value function only looks at the number of data points within the coalition, that is, $u(\\mathcal{S}) = w(\\sum_{i\\in\\mathcal{S}} n_i)$, we obtain, \n\\begin{align*}\n    \\psi_i(u) &= \\frac{1}{I}\\sum_{k=0}^{I-1} u(D^{(k)} \\cup D_i) -  u(D^{(k)}) =\\frac{1}{I}\\sum_{k=0}^{I-1} w(|D^{(k)} \\cup D_i|) -  w(|D^{(k)}|) = \\frac{1}{I}\\sum_{k=0}^{I-1} w(k\\mu_{-i} + n_i) -  w(k\\mu_{-i}) = \\psi_i(w).\n\\end{align*}\nFor the third use-case, the updated version of Equation (10) comes from assuming that, for any $j \\in \\mathcal{I}$, $|D_j \\cap D^{(k)}| = k \\cdot \\frac{n_j}{I-1}$, which holds with high probability for large values of $I$. We ensure none of the theoretical or numerical results is impacted by this typo as all of them are based on the general version given in Definition 3.\n\n5. Concerning your **last question**, please refer to the general answer.\n\n\n[1] Kolpaczki, P., Bengs, V., Muschalik, M., & Hüllermeier, E. (2024). Approximating the Shapley Value without Marginal Contributions. Proceedings of the AAAI Conference on Artificial Intelligence, 38(12), 13246-13255.", "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:
We thank the anonymous reviewers for the useful reviews. As the question concerning the complexity of computing the Shapley value of all players arose several times, we address it as a general reply. We provide several answers.

a) Approximation schemes such as Monte Carlo (DataShapley), DU-Shapley, SVARM [2], or the improved version of Jia et al.'s algorithm [1], are all based on a simple principle: a trade-off between accuracy and complexity of the approximations. In particular, even though DataShapley and the work in [1] require $O(I\log(I))$ function valuations to compute all Shapley values while our method uses $O(I^2)$, the comparison between them must be carefully done as nothing guarantees that the different methods achieve the same accuracy level. We illustrate the advantages of our method through two experiments. 

1. **Complexity comparison of DU-Shapley, DataShapley (Monte Carlo), and the improved Jia et al.'s algorithm**. We have looked at the number of iterations that DataShapley (Monte Carlo, also named the \textit{baseline} in [3]) and the method in [1] require to achieve DU-Shapley's accumulated bias (in norm-2), formally given by,
\begin{align*}
    \mathrm{DU bias}(I) := \frac{\kappa}{I-1}\sqrt{\sum_{i\in \mathcal{I}} \frac{(9\sigma_{-i}^2(1+\log(I-1)) + \zeta_{-i})^2}{(\mu_{-i})^4}},
\end{align*}
by replacing $\varepsilon = \mathrm{DU bias}(I)$, respectively, in the formula in Section 4.1 in [3] and Equation 5 in [1], for $\delta \in \{0.01,0.05,0.1\}$. Since DU-Shapley's bias depends on the value function choice (due to the constant $\kappa$), we have considered a utility function motivated from our third use-case under the homogeneity assumption $\sigma_i/\varepsilon_i = \sigma_j/\varepsilon_j$ for all $i,j \in \mathcal{I}$, given by,
\begin{align*}
\forall S \subseteq \mathcal{I}, u(S) = w(n_S) = 1 - \frac{10^{k(\mathcal{I})}}{10^{k(\mathcal{I})} + n_S},
\end{align*}
where $n_S$ is the size of the data set $D_S := \cup_{i\in S} D_i$ and $k(\mathcal{I}) := \lfloor \log(\sum_{i\in\mathcal{I}}n_{i}) \rfloor - 1$ is a normalization factor depending on the total number of data points. Finally, we have shifted the utility function so it takes only positive values and $u(\varnothing) = 0$. Since DUbias depends on the number of data points per player, for each considered value of $I$, we have simulated 20 different sets of players, each time by sampling $n_i \sim \mathrm{U}(\{1,...,n_{max}\})$ for each $i \in \mathcal{I}$ and $n_{max} \in \{10,50,100\}$. The results are illustrated in Figure 1 in the attached PDF. The rows correspond to each value of $\delta$ while the columns to each value of $n_{max}$. We observe that in all tested instances, both methods require more than $I^2$ iterations to achieve the same error than DU-Shapley. 

2. **Complexity comparison DU-Shapley and SVARM.** We have looked at the probability at which SVARM (Theorem 4 [2]) can ensure, after $I^2$ iterations (without considering the warm up as part of the budget), an error equal to DU-Shapley's accumulated bias. We have considered the same value function than in the previous experiment with $n_{max} \in (2\cdot 10^3,3\cdot 10^3,5\cdot 10^3,10^4)$ and 100 simulations of sets of players at each time. Figure 2 in the attached PDF shows the results.

b) **Approximating DU-Shapley**. It should be noted that the approximation of the Shapley value given by DU-Shapley can be leveraged further by approximating DU-Shapley itself with a coarser discrete scheme than the one specified in our method. For example, we can reduce the computing burden  from $I$ to $\sqrt{I}$ in Definition 3 by computing $\sqrt{I}$ marginal contributions only with data sets $\mathrm{D}^{(k)}$, respectively, of size $$k\cdot \frac{1}{\sqrt{I-1}}\sum_{j\in \mathcal{I}\setminus\{i\}}|\mathrm{D}_j|.$$

c) **Practical use-cases for dataset valuation**. We also point out that there are use cases where one is interested in the contribution of one specific dataset (for example, the contribution of Wikipedia to an LLM).
In this case, the relevant complexity notion is the computing cost for one player, as opposed to the computing cost for all players. 

[1] Wang, Jiachen T., and Ruoxi Jia. "A Note on" Towards Efficient Data Valuation Based on the Shapley Value''." arXiv preprint arXiv:2302.11431 (2023).

[2] Kolpaczki, P., Bengs, V., Muschalik, M., & Hüllermeier, E. (2024). Approximating the Shapley Value without Marginal Contributions. Proceedings of the AAAI Conference on Artificial Intelligence, 38(12), 13246-13255.

[3] Jia, Ruoxi, et al. "Towards efficient data valuation based on the shapley value." The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019.

Meta-review: The review for the paper were unanimously positive, and the paper should be accepted as at NeurIPS
Decision: Accept (poster)