Data Distribution Valuation
Authors: Xinyi Xu
Shuaiqi Wang
Chuan-Sheng Foo
Bryan Kian Hsiang Low
Giulia Fanti
Venue: NeurIPS 2024 poster (2024)
Keywords: Data distribution valuation
Huber model
Maximum mean discrepancy
Primary area: interpretability_and_explainability
TL;DR: We propose a maximum mean discrepancy-based valuation for data distribution and utilize a game-theoretic special case.

Abstract: Data valuation is a class of techniques for quantitatively assessing the value of data for applications like pricing in data marketplaces. Existing data valuation methods define a value for a discrete dataset. However, in many use cases, users are interested in not only the value of the dataset, but that of the distribution from which the dataset was sampled. For example, consider a buyer trying to evaluate whether to purchase data from different vendors. The buyer may observe (and compare) only a small preview sample from each vendor, to decide which vendor's data distribution is most useful to the buyer and purchase. The core question is how should we compare the values of data distributions from their samples? Under a Huber characterization of the data heterogeneity across vendors, we propose a maximum mean discrepancy (MMD)-based valuation method which enables theoretically principled and actionable policies for comparing data distributions from samples. We empirically demonstrate that our method is sample-efficient and effective in identifying valuable data distributions against several existing baselines, on multiple real-world datasets (e.g., network intrusion detection, credit card fraud detection) and downstream applications (classification, regression).

Data Distribution Valuation
Xinyi Xu
Shuaiqi Wang
Department of Computer Science National University of Singapore xinyi xu@u nus. edu
Department Electrical and Computer Engineering
Carnegie Mellon University
shuaiqiw@andrew emu.eddu
Chuan-Sheng Foo
Bryan Kian Hsiang Low Department of Computer Science National University of Singapore lowkh0comp .us. edu. ag
Institute for Infocomm Research Agency for Science, Technology and Research foo _oo_chuan_s_tt shengeirr a-starr edu. sg
Giulia Fanti
Department of Electrical and Computer Engineering Carnegie Mellon University gfanti@andres cmu. edu
Abstract
Data valuation class of techniques for quantitatively assessing the value of data for applications like pricing in data marketplaces. Existing data valuation methods define value for discrete dataset. However, in many use cases, users are interested in not only the value of the dataset, but that of the distribution from which the dataset was sampled. For example, consider buyer trying to evaluate whether to purchase data from different vendors. The buyer may observe (and compare) only a small preview sample from each vendor, to decide which vendor's s data distribution is most useful to the buyer and purchase. The core question is how should we compare the values of data distributions from their samples? Under Huber characterization of the data heterogeneity across vendors, propose a maximum mean discrepancy (MMD)-based valuation method which enables theoretically principled and actionable policies for comparing data distributions from samples. We empirically demonstrate that our method is sample-efficient and effective in identifying valuable data distributions against several existing baselines, on multiple real- world datasets (e.g., network intrusion detection, credit card fraud detection) and downstream applications (classification, regression).
Introduction
Data valuation is widely-studied practice of quantifying the value of data [57]. Today, data valuation methods define a value for a discrete dataset D. i.e., fixed set of samples [24, 32). However, many emerging use cases require a data user evaluate the quality of not just dataset, but the distribution from which the data was sampled, For example, data vendors in markets like Datarade and Snowflake, financial data streams [46, 52]. information security data [22]) offer a preview the form of a sample dataset to prospective buyers [4, 11]. Similarly, enterprises selling access to generative models may offer limited preview of the output distributions prospective buyers [53]. Buyers use these sample datasets to decide whether to pay for full dataset or data stream-i.ee access to the data distribution. Concretely, the buyers would compare between different data distributions (via their respective sample datasets) to determine and select the more valuable one.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In such applications, existing dataset valuation metries are missing two components: (1) They do not formalize the value of the underlying sampling distribution, (2) nor do they provide theoretically principled and actionable policy for comparing different sampling distributions based on the sample datasets. For example, most existing data valuation techniques are designed only to value a dataset [57]. To our knowledge, there are no methods designed to value an underlying distribution.
To model this problem, we consider data buyer who wishes evaluate n. data vendors, each with their own dataset D; drawn i.i.d. from distribution P., where i E [n]. The vendors' distributions are heterogeneous, i.e., the P, can differ across vendors. Such distributional heterogeneity can arise from natural variations in data [12] or adversarial data corruption [27, 65]. The buyer's goal is to select the vendor whose data distribution closest in some sense (to be defined) to a reference distribution P which is fixed but unknown. Our goal is to provide both precise definition for the value of the vendor distribution P; with respect to P as well as a corresponding valuation for the sample dataset D; ~ P. In particular, we want precise conditions under which, given two datasets D; and D, drawn from distributions P; and Pj. respectively, we can conclude that P, > P3 + er for some user-specified ey > 0 with fixed probability. While this problem is straightforward when different vendors have the same underlying distribution, the main challenge is accounting for the heterogeneity in the data.
We thus identify three technical and modeling challenges: (i) What a suitable heterogeneity model that captures realistic data patterns, while also admitting theoretical analysis? (ii) How should one define the value of a distribution under a given heterogeneity model? (iit) Many existing data valuation methods use reference P*, either explicitly [24, 33, 55] or implicitly [1. 14). However, there are practical difficulties: (1) different data vendors may disagree on the choice of reference [70], (2) such a reference may not be available a priori [14, 56), or (3) dishonest vendors may try to overfit to the reference [2]. To address this, some works consider alternatives (to P*) based on the vendors'
distributions P.'s such as their union [60] or certain combination [66], but without theoretical analysis or justifications for their specific choices. So what is a practical alternative, and how can we theoretically justify it?
To address these challenges, we make three key choices.
(a) Heterogeneity model. We assume that each vendor's data distribution P; is a Huber model [30], which is mixture model of the unknown distribution P and arbitrary outlier distribution Q:- While the Huber model does not capture all kinds of statistical heterogeneity, mixture models both reasonable model for data heterogeneity in practice [9, 54] and have deeper roots in robust statistics [20, 40J. More importantly, the Huber model enables a direct and precise characterization of the effect of heterogeneity on the value of data (under our design choices (b) and (c) below), which has not been considered in prior works [1, 14, 66).
(b) Value of a sampling distribution. We use the negative maximum mean discrepancy (MMD) [26] between a reference distribution P and P as the value of the sampling distribution P. Then, we leverage (uniformly converging) MMD estimator [26] to derive actionable policies for comparing sampling distributions with theoretical guarantees. In other words, a buyer can compare (the values of) sampling distributions P., Py (from vendors i, i') based on the respective samples D,, Dy to determine which is more valuable, and by how much.
(c) Choice of reference data distribution and dataset. Unlike in prior works (e.g., [24, 67)), we do not specify a reference distribution outright. Instead, we consider a class of convex mixtures of vendor distributions as the reference. We first derive eиror guarantees and an actionable comparison policy for using general convex mixture of the vendors' distributions as the reference. We then propose to use the special case of uniform mixture, justified by game-theored argument, stating that the uniform strategy is worst-case optimal in a two-player zero-sum game.
These design choices are not isolated answers to each technical challenge, but collectively address these challenges (e.g.. the analytic properties of both Huber and MMD are needed to compare distributions effectively). Our specific contributions are summarized as follows:
We formulate the problem of data distribution valuation in data markets and study an MMD-based method for data distribution valuation. Under a Huber model of data heterogeneity, we show that this data valuation metric admits actionable, theoretically-gronndee policies for comparing sampling distributions from samples.

---

We derive an error guarantee (Proposition 2) and comparison policy (Theorem 1) for a general convex mixture P_ as a reference (in place of p*), thus relaxing the common assumption of knowing P We then identify the uniform mixture as game-theoretic special case for P...
We demonstrate on real-world classification (c.g., network intrusion detection) and regression (c.g., income prediction) tasks that our method is sample-efficient, and effective in identifying the most valuable sampling distributions against existing baselines. For example, on classification tasks, we observed that an MMD-based valuation method outperformed four leading valuation metrics on out of 4 classification settings (Table 2).
2 Related Work
Existing dataset valuation methods fall roughly in 2 categories: those that assume a given reference dataset, and those that do not. We defer additional discussion to App. B due to space constraints.
With given reference. Several existing methods require given reference in the form of validation set (e.g., [24, 39I) or a baseline dataset [2]. Data Shapley [24], Beta Shapley [39] and Data Banzhaf [43, 63] utilize the validation accuracy of a trained model as the value of the training data. Class-wise Shapley [55] evaluates the effects of a dataset on the in-class and out-of-class validation accuracies. Both LAVA [33] and DAVINZ [67] use a proxy for the validation performance of the training data as their value, instead of the actual validation performance, to be independent of the choice of downstream task ML model [33] or to remove the need for model training [67]. Differently, [2] assume that the buyer provides baseline dataset as the reference to calculate a relevance score used to evaluate the vendor's s data. Therefore, these methods cannot be applied without such a given reference, which can be difficult to obtain in practice [14, 56]. In contrast, our method can be applied without a given reference, by carefully constructing a reference (Sec. 4.2).
Without given reference. To relax the assumption of a given reference, [14, 60, 66] construct a reference from the data from all vendors. While the settings of [14, 60, 66] can include heterogeneity in the vendors' data, they do not explicitly formalize it and thus cannot precisely analyze its effects on data valuation. In contrast, our method, via the careful design choices of the Huber model (for heterogeneity) and MMD (for valuation). uniquely offers a precise analysis on the effect of heterogeneity on the value of data (Eq, (2)). Furthermore, these methods did not provide theoretical guarantees on the error arising from using their constructed reference in place of the ground truth (i.e., P*). In contrast, by exploiting Observation in the setting of multiple vendors and the MMD-based valuation (Eq. (1)), we provide such theoretical guarantees (e.g., Proposition 2). In different approach to relax the assumption of a given reference, [56, 70] remove the dependence on a reference; as a result they
produce counter-intuitive data values under heterogencous data (experiments in Sec. 5). The closest related work to ours is [60], which adopts the MMD2 as a valuation metric, primarily for computational reasons. However, this work does not consider data distribution valuation, nor does it describe how to compare (the values of) distributions, let alone with theoretical guarantees. This comparison (with MMD?) is expanded in App. B.2.
Table provides a comparison between our choice (MMD) and three others: the Kullback-Leibler (KL) divergence [1, 66), the Wasserstein distance (WD) [33], and squared MMD (MMD*) [60].
3 Model, Problem Statement and MMD
We consider a set of data vendors i E N == (1..... n). each with a sample dataset D; = {zi,1...., 2i,ma of size m,. where Zt, sampled i.i.d. from the distribution P. [10]. Slightly abusing notations, we write D; ~ P.. We assume the existence of an unknown ground truth distribution p*, called the test distribution [24, 32], true data distribution [1] or the task distribution [2].
Huber model. We assume that each sampling distribution P; follows a Huber model [30], defined as follows: P. = (1 e,) P* + e,Q; where E [0, 1) and Q, is a distribution that captures the heterogencity of vendor [27]. For notational simplicity, we omit the subscript i and write D, P instead of D, P., when it is clear. We adopt the Huber model because (i) it is sufficiently general to model various sources of heterogeneity [12, 1 13]; (ii) Huber models are "closed" under mixtures (i.c., mixture of Hubers is Huber model), we can define a mixture over data vendors' distributions:
3

---

Observation 1. For a mixture weight w E An - 1), define the mixture Pw == EiEN W.P.. Then, Pw = (1 - Eu) + ew Qw where &w = EiEN wie; and Qw = (1/Ew)
The mixture distribution P. (of individual P,'s) is Huber model, which is used in the theoretical results in Sec. 4.2. Define Du as the sample dataset by randomly sampling from each D, w.p. Wi: so effectively Dw ~ Pu. In particular, if w is uniform (i.e., Vi, w; = 1//n,, we denote the corresponding Pw as Pu. Dw as Du. Ew as Eu and Qu as Qu. We further expand our considerations of the Huber model to characterize data heterogeneity w.r.t existing works in App. B.3, Later, we also empirically investigate non-Huber settings where our method (in Sec. 4) remains effective (App. D.3.4).
Problem statement. Given two datasets D ~ P and D' ~ P', we seek distribution valuation function T--) and dataset valuation function v(-) which enable set of conditions under which to conclude that (PP) > T(P"), given only (DD and vDD).. Moreover, we seek a practical implementation of Y that does not require access to the ground truth distribution P as reference or any prior knowledge about the vendors (except each P, is Huber).
Existing methods cannot be easily applied to solve this problem. First, existing methods (e.g.. [24, 32] do not define T; hence, they cannot analyze the conditions under which T(P) > T(P).. In App. C, we elaborate why a dataset valuation / cannot be easily extended to a data distribution valuation T and also highlight the theoretical appeal of directly considering Y instead. Additionally, methods that explicitly require access to the reference distribution via D P (e.g., [39, 55, 67]) cannot be applied here. For other methods, additional non-trivial assumptions (e.g.. [14, Assumption 3.2], [66, Assumption 3.1]) are required; we elaborate on these in App. B.1.
3.1 Maximum Mean Discrepancy (MMD)
The MMD is an integral probability metric proposed to test if two distributions are the same. Definition 1 (MMD, [26, Definition 2)). For a class F of functions in the unit ball of the reproducing kernel Hilbert space associated with kernel function k the MMD, which is symmetric, between two distributions P, P" is d(P,, P'; F)= == sup Ex=pf(X) Ew-P' fWWF)
The MMD has a (biased) estimator for D ~ P and D' ~ P', and DD| m, DD m, å(D), D') == + Ex.'ED k(xx,
m' [26, Eq. (5)]:
2 E ((x.))DDx Dr A((1, w) + 7 Ew.w'E k(w, w/)) w/))'. Importantly, this estimator satisfies uniform convergence (Lemma 1), which is used in our theoretical results (e.g., Proposition 1). We denote with K an upper bound on the kernel A: Va, x', k(æ, x') S K. As F is associated with k and kept constant throughout, its notational dependence is suppressed.
4 MMD-based Data Distribution Valuation
distribution valuation function should intuitively reward distributions P that are "closer" to the reference distribution P*; accordingly, it should assign greater reward to datasets D ~ P that are drawn from distributions that are closer to P*. We study the following data distribution valuation:
T(P) = - d(P,
v(D) = - -d(D,D' D*)
(1)
To interpret, the value T(P) of a vendor's sampling distribution P is defined as the negated MMD between P and P*, while the value v vDD) of its sample dataset D is defined as the negated MMD) estimate between D and the reference dataset D*
On the choice of MMD. We summarize a comparison with three alternatives (i.e., KL-divergence (KL), Wasserstein Distance (WD), and MMD') in Table to highlight the suitability MMD for data distribution valuation. Despite its wide adoption. KL is difficult to estimate, and the available estimator only has asymptotic convergence guarantees [64] (rather than a simile result), which can be arbitrarily slow. Its implementation also suffers from the curse of dimensionality [59, 64]. In addition, KI. does not satisfy the triangle inequality, which our proof technique uses in Proposition 2. WD, also known the optimal transport (OT) distance [34], suffers from the curse of dimensionality, as seen in the complexity results [23] in Table 1, and is more computationally costly to evaluate than MMD. MMD? though shares similar complexity results to MMD, does not satisfy desirable analytic properties, such as the triangle inequality or the property with Huber model. This comparison over divergences expanded in App. B.2.
ww is re-dimensional probability vector in the 1 simplex.
4

---

Table 1: Comparison with KL, WD and MMD on sample and computational complexities, triangle inequality and connection with the Huber model. dim is the dimension of the random variable/data.
sample
computational
triangle inequality
Huber
KL WD
asymptotic O / m // / ( m
N.A. Omm log m) O(m²)
/ *x*
X
MMD 2
X
X
MMD
O11/ mm) m)
Omm²)
MMD is both practically and theoretically appealing for data distribution valuation. Practically, MMD has lower sample and computational complexities in the dimension of the data, which is important because the real-world datasets can be complex and have high dimension. Specifically, we leverage the uniform convergence (with sample complexity as in Table 1) of an MMD estimator to derive an actionable policy for comparing two distributions (i.e., Proposition 1, Theorem 1). Theoretically, MMD satisfies the triangle inequality, making it amenable to theoretical analysis, such as the derivation of our error guarantee (i.e., Proposition 2). Moreover, MMD pairs well with the Huber model in providing precise characterization of the effect of beterogeneity on the value of data. In contrast, existing valuation works have not established a formal analysis on the heterogeneity (w.r.t. specific choice for heterogeneity) on the value of data, elaborated in App. B.3.
Effect of heterogeneity on both the size of the outlier component e and the statistical difference d(P", Q) between Q and pa A larger and/or larger d(P", Q) decreases the value T(P.. Our choice of MMD makes this intuition precise and interpretable: By Lemma 2, for P = (1 E)P + +Q,
data valuation. Intuitively, the quality of Huber distribution P depends
T(P) ==d(pp ,Q)
Eq. (2) shows that for fixed c, P's value decreases linearly w.r.t. d(P", Q): similarly, for a fixed d(P", Q). P's value decreases linearly w.r.t. s. Importantly, Eq. (2) enables subsequent results and a theoretically justified choice for the reference (e.g.. Lemma 4 to derive Theorem in Sec. 4.2).
4.1 Data Valuation with a Ground Truth Reference
With Eq. (I), we return to the problem statement described above: given two datasets P and D' ~ P", under what conditions can we conclude that T(P) > T(P')? We first assume access to reference dataset D* p*. We then relax this assumption in Sec. 4.2.
Proposition 1. Given datasets D ~ P and D' P', let m == [D] and m' = D') Let D ~ P and m := |D" be its size. For some bias requirement Cbas 2 0 and a required decision margin εT 2 0. If vDD >> v(D' + AT,,, where the criterion margin Ar, == ST + 2/Shias + v /K/m- + v K/ml + 2 mim"
2 /K/m*). Let ó == 2exp( 2K (m++mm) where ग7 = max{m, m'}. Then, T(P) > T(P') + eT
with probability at least (1 25).
(Proof in App. A) Proposition describes the criterion margin AT. such that if v(D) - v(D') Ar. Dr.--ie i.e., the criterion is met-wa we can draw the conclusion that T(P) > T(P')+EY at confidence level of 1 25. Hence, a smaller AT,,, corresponds to an "easier" criterion to satisfy. The expression Ar. O(ET + Ehias + 1/ / / where m := min (m,m', m', ,,mm) highlights three components that are in tension: a buyer-defined decision margin ěr, bias requirement éhins from the MMD estimator (Lemma 1), and the minimum size z of the vendors' sample datasets (assuming m 2 max m,, m }) If the buyer requires a higher decision margin EY (i.e., the buyer wants to determine if P is more valuable than p' by a larger margin), then it may necessary to (i) set a lower bias requirement Ebias and/or (ii) request larger sample datasets from the vendors. In (i), suppose m remains unchanged, a lower Ebias reduces the confidence level 26 since increases as Ebias decreases. Hence, although the buyer concludes that P is more valuable than P' by a higher decision margin, the corresponding confidence level lower. In (ii), suppose bas remains unchanged, a higher minimum sample size m increases the confidence level. In other words, to satisfy the buyer's 's higher decision margin, the
In proof of Proposition 1, it is shown that the contidence level strictly increases when m' increases.
5

---

vendors need to provide larger sample datasets. This can also help the buyer increase their confidence level if the criterion is satisfied. Proposition 1 illustrates the interaction between buyer and data vendors: The buyer's requirement is represented by the decision margin, and the vendors must provide sufficiently large sample datasets to satisfy this requirement
4.2 Approximating the Reference Distribution
Previously we assumed P could be accessed as the reference. We now relax this assumption by replacing P with mixture distribution Pa over all the vendors' distributions, as defined in Observation 1. We first prove an error guarantee to generalize Proposition when using Pw instead of P We then use a game-theoretie formulation motivate the choice of the uniform mixture, Pu.
Formally, using P. as the reference (with D2 Pa)) instead of p* gives the following valuation:
f(P) = -d(P, B(D) = -d(D, Du).
(3)
Namely, f is an approximation to T (equiv. D to v), with a bounded (approximation) error as follows,
Proposition 2. Recall Ews Qw from Observation 1. Then, (P, - T(P) s swndQu,
(Proof in App. A) Proposition 2 provides an error bound from using Pw as the reference, which linearly depends Ew and Qw: A lower E; (i.e., P. has lower outlier probability) gives lower Ewi and a lower d(Q,, P*) (i.e., P''s outlier component is closer to P*) leads to lower d(Qw, P*), resulting in smaller error from using P., as the reference. Using this error guarantee, we give main result, which provides a decision criterion for concluding that for candidate vendor distributions P and P', their valuations satisfy T(P) T(P') + EY, for some user-specified decision margin Er. Unlike Proposition 1, this result does not require access to ground truth P", but instead uses a practically-realizzbbe mixture Pa.
Theorem 1. Given datasets D ~ P and D' ~ P", let m = [D] and m = D Let Dw, & be from Eq. (3) and n |uul. For some bias requirement Ebias 2 0 and a required decision margin ēr 2 O, suppose ((D) > +(D'++A4, ,r,,, where the criterion margin AT,,p == EY + 2 + v K/m- - mmw where m. max (m, m'). V KK/m + 2. K/mN + En Qw: P"]] Let 8' = 2 cxp( 2k mm))))))) Then T(P) > T(P') + ET with probability at least (1 28').
(Proof in App. A) Compared with Proposition 1, the criterion margin AT,,, has an additional term of de Qw., P"), which depends on both the size of the outlier component sw and the statistical difference d(Qu> P*)) between Qw and ps This term explicitly accounts for the statistical difference d(Pw, P*) to generalize Proposition 1: d( d.... P*) = 0 recovers Proposition 1. Importantly, this result implies that using P. (to replace P*) retains the previous analysis and interpretation: buyer's 's requirement via the decision margin can be satisfied by the vendors providing (sufficiently) large sample datasets, which empirically investigated in a comparison against existing valuation methods (Sec. 5). We highlight that Theorem exploits the closed property of Huber models (via Observation 1), the triangle inequality of MMD (via Proposition 2) and the uniform convergence of the MMD estimator. Hence, the modeling and design choices of Huber and MMD are both necessary.
4.2.1 A Game-theoretic Choice of Mixture
The above results hold for general mixture distributions Pa,, begging the question: Which mixture should one use (i.e., what w)? A game-theoretic formulation reveals that the uniform strategy is worst-case optimal, so we propose to use the uniform mixture Pt as the special case of P..
Consider the following two-player zero-sum game. A payoff matrix R consists of n rows, one corresponding each vendor index, and nz! columns, one corresponding each permutation over the vendor indices. The row player (i.c.. the agent conducting the data valuation) picks a vendor index r E N. The column player (hypothetical adversary) then adversarially chooses permutation ne over the indices in N. Hence, the action space for the row player is N and that for the column player is all possible permutations of (1, 2 .,.................. n).' The column player represents the fact that the row player
3 CCompared with Ar. Proposition 1, m = mn, then Arr,, AT, + dew P*). '...o.g. assume fixed ordering of all n! permutations.

---

lacks prior knowledge about vendors: hence it selects an index in any possible arbitrary permutation Te- Then, for a pair of actions (r, Te), the quality of the distribution P=.(r] is the row player's payoff'
Ry.0 == -d(P" Pa (ri) defined as the negated MMD between [r1 and the optimal distribution
pa (i.e., lower MMD means a higher payoff), specifying the following optimization:
max, min. Ry.
where R E Rnx((!) is the payoff matrix and max (min) denotes the row (column) player's action. strategy Srow E An - 1) (as an n-dimensional probability vector) specifies the probability with which the row player picks data vendor (at a position).
While efficient linear program solvers to Eq. (4) are available for explicitly specified R. in our setting, R is not explicitly specified due not knowing Pr, Fortunately, we show that the uniform strategy is optimal without knowing R explicitly:
Proposition 3. The optimal solution for the row player to Eq. (4) is sio = 1
(Proof in App. A) Intuitively, a uniform strategy over the vendors cannot be exploited by the column player, and thus worst-case optimal. We highlight that while uniform strategy being worst-case optimal may seem intuitive, the mathematical properties and derivations needed are less straightforward. In particular, the proof depends on the "closed" property of Huber (i.e., Observation 1) and the "linearity" of MMD applied to Huber (i.e., Eq. (2)) to exploit the strong duality of linear program. We also discuss alternative formulations to Eq. (4) in App. A.
Then, we adopt the uniform mixture Pt as the special case of Pa in Eq. (3):
î(P) = -d(,, D(D) = -d(D,
Proposition 2 and Theorem are applied directly in App. A. The uniform mixture Pu is inspired from the solutions to Eq. (4), which is game based on not having prior knowledge about the vendors. In this setting of no ground truth and no prior knowledge about the vendors, one might wonder if/how we can derive a lower bound of error to crystalize the difficulty of the problem (our Proposition gives upper bound of error for general P., and Corollary 1 is for Pv). We expand this in App. C, making references to robust statistics and mechanism design.
Empirical Results
We first compare the sample efficiency of several baselines, and then investigate the effectiveness of our method in ranking n data distributions. Additional information on experimental settings is in App. C and additional results under non-Huber settings, and on scalability are in App. D. Our code is available at http://ggituuu.oo/ii/iyyiaa
Baselines. To accommodate the existing methods which explicitly require validation set (Sec. 2). we perform some experiments using a validation set Dval ~ p This assumption is made only for empirical comparison, and subsequently relaxed. The baselines that explicitly require Deat are class-wise Shapley (CS) [55, Eq. (3)), LAVA [33] and DAVINZ [67, Eq. (3)); the baselines that do not require D are information siaiiioonnniiinn value (IG) [56, Eq. (1)), volume value (VV) [70, Eq. (2)) and MMD² [60, Eq. (1)), which implements a biased estimator of MMD? For each baseline, we adopt their official implementation if available. Note that though theoretically MMD? is obtained by squaring MMD, the estimator for MMD is not obtained by squaring the MMD estimator (elaborated in App. B), they give different results. Note that DAVINZ also includes the MMD as a specific implementation choice, linearly combined with a neural tangent kernel -based score. However, their theoretical results are specific to NTK and not MMD, while our result (e.g., Theorem 1) is MMD-specific.
Our implementation of MMD, including the radial basis function kernel, follows [42]. To implement our proposed uniform mixture Py in cases where D,'s have different sizes, we do the following: denote the minimum dataset size by m-mi = min; [De]. Then for each D,, uniformly randomly sample a subset D Di, C D; of size m.mi from D,, and use the union Du == U,D;
Datasets. We consider both classification (Cla.) and regression (Reg.) since some baselines (i.e., CS, lAVA) are specific to classification while some (i.e., IG, VV) are specific to regression. Our method is applicable to both. CaliH (resp. KingH) is housing prices dataset in California [35] (resp. in
7

---

Kings county [28]). Census15 (resp. Census17) is personal income prediction dataset from the 2015 (resp. 2017) US census. [48]. Credit7 [49] and Credit31 [3] are two credit card fraud detection datasets. TON [47] and UGR16 [45] are two network intrusion detection datasets.
Many of evaluations are conducted under Huber model, which requires matched supports of P and Q. such as MNIST, EMNIST and FaMNIST, all in |R32x32, CIFARIO and CIFARIOO 100, and Census 15 and Census17. 17. Other datasets require additional pre-processing: CaliH and KingH are standardized and pre-processed separately to be in R Additional pre-processing details in App. D. Subsequently, each P. follows a Huber: P. =
P' + eiQ (i.e., Vi, Q = Q). We also run experiments on non non-Huber settings in App. D, where our method remains effective.
ML model M. For model-specific baselines such DAVINZ and CS, in Sec. 5.2, we adopt a 2-layer convolutional neural network (CNN) for MNIST, EMNIST, FaMNIST; ResNer-18 [29] for CIFAR10 and CIFAR 100; logistic regression (LogReg) for Credit7 and Credit31, and TON and UGR 16; linear regression (LR) for CaliH and KingH, and Census15 and Census 17. Details are in App. D.
5.1 Sample Efficiency via Empirical Convergence
Our goal is to find sample-efficient policy that correctly compares T(P) vs. T(P') by comparing (D) vs. vi (D'), even if the sizes of D, D' are small. In practice, there is no direct access to P, P but only D, D'; the sizes of D, D' may not be very large. Here, we compare {u(D;)}EEN to (T())) as we vary dataset size m4-
Setting. We implement T(P.) approximated by v(D)) where DJ P. with large size m, (e.g., 10, 000 for p = MNIST vs. Q = EMNIST), Denote the values of the samples as M': = [v(D;)}eN where the sample size m. = |D,] and the approximated ground truths as v* = (v(D;))eNT in this way, V² is well-defined respectively for each comparison baseline (i.e., not MMD definition Eq. (1)). We highlight that each (i.e., each baseline) is evaluated against its corresponding v" to demonstrate the empirical convergence. This is to examine the practical applicability of each when the sizes of the provided (Di)ie are limited.
Evaluation and results. We evaluate three criteria-the the lz and to2 errors and the number of pair-wise inversions as follows, || v² V²112, 11l2,Ilumg
v" Il and inversions( v²)
(1/2) Ei.eem)) iye (D( > v(D;) A v(D)) < v(D))). In words, if the conclusion via (DD)) vs. v(D)) differs from that via u(D)) vs. v(D)), it is an inversion. For all 3 criteria, lower is better.
Fig. 1 (and Figs. 2 to 5 in App. D) demonstrate that our MMD- based method is overall (one of) the most sample-efficiert for different evaluation criteria and datasets, validating the theoretical results (Table 1) that MMD is more sample-efficient than WD.
0.8
CS
0.6
8
CS
0.6
DAVINZ
CS
# Inversions
6
DAVINZ
LAVA
0.4
DAVINZ
LAVA
0.4
MMD
LAVA
MMD
0.2
Ours
2 0.2
Ours
2MD
2
Ours
0.0
0.0
0
0.0
0.5
1.0
0.0
0.5
1.0
0.00
0.25
0.50
0.75
1.00
Sample size (in pct.)
Sample size (in pct.)
Sample size (in pct.)
Figure 1: The 3 criteria (on y-axis) for P MNIST vs. Q EMNIST. = 5, m 10, 000. r-axis shows sample size in percentage, i.e., m./m, where m is fixed to investigate how the criteria change w.r.t. m./m:: If the criteria decrease quickly w.r.t. m²/m?, it means the metric converges quickly (i.e., sample-efficient) Results averaged (standard errors bars) over 5 independent trials.
5.2 Ranking Data Distributions
Motivated by the use-case of buyer identifying the best data vendor(s), we measure our ability to rank n distributions based the values of sample datasets.
Setting. For a valuation metric v (e.g., Eq. (1)), denote the values of datasets from all vendors as = (v(D.))EN. To compare against different basclines (i.c., other definitions of v),, we define the
8

---

following common ground truth, the expected test performance S == ED.~P. [M))) Dres)) of an ML model (D;) trained on D, over a fixed test set Dieu where the expectation is over the randomness of D. Let Ç == {Gi JieN. The MI. model M is specified previously and the test set Drest from the respective P and not seen by any data vendor. Note that Dieu is used to obtain Ç for comparison purposes, and it is not to be confused with D which is required by some baselines as part of their methods.
Utilizing labels. We also extend our method to explicitly consider the label information via the conditional distributions of labels given features (i.e., Pyix), denoted as Ours cond. Other baselines such as LAVA and CS already explicitly use label information. Specifically, for D; containing paired features and labels, we fit a learner M(,)) on D, and use its predictions on Daal (thus we require D as an empirical representation of the Prix for D; and compute the MMD between the conditional distributions (more implementation details in App. D). Unlike our original method (i.e., Ours), this variant differs in exploiting the feature-label pairs in D, We relax the assumption Dval ~ P* by replacing Daal with Du, namely for the baselines needing an explicit reference, we use Dv. The resulting data values are denoted as & (the data values based Dval are denoted as v).
Evaluation metric. Here is effective if it identifies the most valuable sampling distribution, or more generally, if v preserves the ranking of Ç. In other words, the ranking of the data vendors' sampling distributions {eN is correctly identified by the values of their datasets {Di quantified via the Pearson correlation coefficient: p(v, () (higher is better). Note that we compare the rankings of different baselines instead of the actual data values which can be on different scales.
Results. We report the average and standard error over 5 independent random trials, on CIFAR CIFAR1O/CIFAT 10/IIARR TON/UGRI6, CaliH/KingH and Census15/Census, 17 in Tables 2 and respectively, and defer the others to App. D. Note that when D is unavailable (i.e., right columns), Ours cond. not applicable because the label-feature pair information is not well-defined under the Huber model (e.g., for P* = CIFARIO vs. Q CIFAR 100, the label of a CIFAR 100 image is not well-defined for model trained for CIFAR 10). The Perf(.) for Ç for classification (resp. regression) is accuracy (resp. coefficient of determination (COD)), so higher is better.
Table 2: Pearson correlations between data sample values and data distribution values for classification.
CIFARIO vs. CIFAR100
TON vs. UGRI6 p(D,C)
Baselines
((v,5)
p(D,C)
p(v,C)
LAVA
-0.924(0.01) (0.00((0001)
0.254(0.26)
-0.159(0.38)
DAVINZ
-0.437(0.10)
-0.481(0.13)
-0.201(0.26)
-0.529(0.21)
CS
0.889(0.03)
-0.874(0.02)
0.451(0.19)
0.256(0.28)
2MD
0.764(0.02)
0,563(0.01)
0.526 (0.11)
0.480(0.15)
Ours
0.763(0.02)
0.564(0.02)
(.584(0.17)
0.461(0.14)
Ours cond.
(0989().01)
N.A.
0.562(0.16)
N.A.
For classification, Table shows that our method performs well when D is available (e.g., Ours cond. is the highest for CIFARIO vs. CIFARIO0 under p(v, ()) and also when Dvat unavailable (e.g., Ours as highest for CIFARIO 10 vs. CIFARION 100 under p(D, C)). MMD performs comparably to Ours, which is expected since in theory their values differ only by square and the evaluation mainly focuses on the rank, instead of the absolute values. We also note that CS, by exploiting the label information in classification, performs competitively with Dval. but performs sub-optimally without Deal- This is because the label information in Dvai is no longer available in D., (due to D. being Huber). LAVA and DAVINZ, both exploiting the gradients of the ML model, do not perform well. The reason could be that under the Huber model, the gradients are not as informative about the values of the data. Intuitively, while the gradient of (the loss of) a data point on an ML model can be informative about the value of this data point, this reasoning is not applicable here, because the data point may not be from the same true distribution p"; The value of a gradient obtained on a CIFAR 100 image to an ML model intended for CI may not be informative about the value of this CIFAR1O0 image. We highlight that neither of LAVA and DAVINZ was originally proposed for such cases (i.e., the Huber model).

---

Table Pearson correlations between data sample values and data distribution values for regression.
CaliH vs. KingH
Censusl5 vs. Census17
Baselines
plu, 5)
p(),5)
p(v:C)
p(D,
IG
-0.00
-0.932(0.02)
VV
-0.603(0.01)
-0.707(0.01)
DAVINZ
0.852(0.03)
0.048(0.08)
0.779(0.14)
0.227(0.11)
MMD
0.872(0.03)
0.726(0.09)
0.889
0.838(0.08)
Ours
0.896(0.02)
0.767(0.04)
0.843(0.03)
0.769(0.08)
Ours cond.
0.812(0.02)
N.A.
0.848(0.06)
N.A.
For regression, Table shows that Ours and MMD continue perform well while baselines (i.e., IG and VV) that completely remove the reference perform poorly, as they cannot account for the statistical heterogeneity without a reference. Notably, DAVINZ performs competitively for when Deal is available, due to its implementation utilizing a linear combination of an NTK- score (i.e., gradient information) and MMD (similar to Ours), via auto-tuned weight between the two. We find that for classification, the WTK-based score is dominant while for regression (and available Dvat) the MMD dominant. This could be because the models are more complex for the classification tasks (e.g., ResNet-18) as compared to linear regression models for regression, so the obtained gradients are more significant (i.e., higher numerical NTK-based scores). Thus, for regression, DAVINZ produces values similar to Ours, hence the similar performance. We highlight that DAVINZ focuses on the use of NTK w.r.t. a given reference, while our method focuses on MMD without such a reference, as evidenced by Ours outperforming DAVINZ without Dval (i.e., the columns under p DD, () in Table 3).
6 Discussion
Under a Huber model of vendor heterogeneity, we propose an MMD-based data distribution valuation and derive theoretically-justife
policies for comparing distributions from their respective samples. To address the lack of access to the true reference distribution, we use convex mixture the vendors' distributions as the reference, and derive a corresponding error guarantee and comparison policy. Then, we specifically select the uniform mixture as a game-theorete choice when no prior knowledge about the vendors is assumed. Empirical results demonstrate that our method performs well in efficiently identifying the most valuable data distribution. While our theoretical results are limited to the Huber model, MMD is observed to be effective under two non-Huber settings (App. D.3.4). Extending the theory to more general heterogeneity models is an interesting direction for future study.
Acknowledgments and Disclosure of Funding
Xinyi Xu is supported by the Institute for Infocomm Research of Agency for Science, Technology and Research (A*STAR) and would like thank Peiyu Hu and Siyu Liu for their support. This research/project is supported by the National Research Foundation Singapore and DSO National Laboratories under the AI Singapore Programme (AISG Award No: AISG2-RP-2000--012, Giulia Fanti and Shuaiqi Wang were supported in part by National Science Foundation grant CCF-2338772, as well as the Sloan Foundation, Bosch, and Intel.
References
[1] Lucas Agussurja, Xinyi Xu, and Bryan Kian Hsiang Low. On the convergence of the Shapley value in parametric Bayesian learning games. Proc. ICML., 2022.
[2] Mohammad Mohammadi Amiri, Frederic Berdoz, and Ramesh Raskar. Fundamentals of task-agnostic data valuation. In Proc. AAAI, 2023.
[3] Reid A. Johnson Andrea Dal Pozzolo, Olivier Caelen and Gianluca Bontempi. Calibrating probability with undersampling for unbalanced classification. In Proc. IEEE CIDM, 2015.
10

---

[4] Santiago Andrés Azcoitia and Nikolaos Laoutaris. Try before you buy: A practical data purchasing algorithm for real-world data marketplaces. In Proc. ACM Data Economy Workshop. 2022.
[5] Maria-Florins, Balcan, Tuomas Sandholm, and Ellen Vitercik. Estimating approximate incentive compatibility. Proc. EC, pp. 867, 2019.
[6] Santiago Balseiro, Omar Besbes, and Francisco Castro. Mechanism design under approximate incentive compatibility, 2022.
[7] Yatao Bian, Yu Rong, Tingyang Xu, Jiaxiang Wu, Andreas Krause, and Junzhou Huang. Energy-based learning for cooperative games, with applications valuation problems in machine learning. In Proc. ICI.R, 2021.
[8] Avrim Blum and Paul Gölz. Incentive-compatbble kidney exchange in slightly semi-random model. In Proc. EC, 2021.
[9] Stéphane Bonhomme and Elena Manresa. Grouped patterns of heterogeneity in panel data. Econometrica, 83(3): 147-118444114, 2015.
[10] Junjie Chen, Minming Li, and Haifeng Xu. Selling data to machine learner: Pricing via costly signaling. Proc. ICMI., 2022.
[11] Lingjiao Chen, Bilge Acun, Newsha Ardalani, Yifan Sun. Feiyang Kang, Hanrui Lyu, Yongchan Kwon, Ruoxi Jia, Carole-Jean Wu, Matei Zaharia, and James Zou. Data acquisition: A new frontier in data-centric AI. arXiv:23 /37/2, 2023.
[12] Mengjie Chen, Chao Gao, and Zhao Ren. A general decision theory for Huber's e-cottmmination model. Electronic Journal of Statistics, 10(2):3752 33744,44-777, 2016. ISSN 19357524.
[13] Mengjie Chen, Chao Gao, and Zhao Ren. Robust covariance and scatter matrix estimation under Huber's contamination model. Annals of Statistics, 46(5):1932-1960, 2018.
[14] Yiling Chen, Yiheng Shen, and Shuran Zheng. Truthful data acquisition via peer prediction. In Proc. NeurlPS, 2020.
[15] Badr-Eddine Chérief-Abdellatt and Pierre Alquier. Finite sample properties of parametric MMD estimation: Robustness to misspecification and dependence. Bernoulli, 28(1):181 213, 2022.
[16] Afshar Cohen, J.S. Tapson, and A. van Schaik. Emnist: extension of mnist to handwritten letters. http://arxx: org/ h//g//b///// 100.00002000 05373, 2017.
[17] Dai, Bo Xie, Niao He, Yingyu Liang, Anant Raj, Maria-Florina Balcan, and Le Song. Scalable kernel methods via doubly stochastic gradients. In Proc. NeurIPS, volume 27. Curran Associates, Inc., 2014.
[18] Constantinos Daskalakis. Algorithmic game theory, complexity and learning lecture 1.1: The minimax theorem. tttps://itcs.sufe.et..cc 36a9f 1 00w hataaaaa00aaaaeeeeeeeee606666622 4791 -ag.-a0----0------------0000.... 2017. Lecture Notes.
sufe edu. httpa//eee.....e.ppaaaaaattteeea /b////////lla///////////
[19] Ilias Diakonikolas. Robust statistics From information theory to algorithms. ISIT 2019 Tutorial, 2019.
[20] Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In Proc. FOCS, pp. 655-664, 2016.
[21] R. J. Duffin, G. B. Dantzig, R. Duffin, Fan, L. Ford, Fulkerson, D. Gale, Goldman, I. Heller. J. B. Kruskal, H. W. Kuhn, H. D. Mills, G. L. Thompson, C. B. Tompkins, A. W. Tucker, and Wolfe. Infinite Programs, pp. 157-170. Princeton University Press, 1956.
[22] RAND Europe ENISA. Incentives and barriers to information sharing. Technical report, The European Network and Information Security Agency (ENISA), 2010.

---

[23] Aude Genevay, Lénaic Chizat, Francis Bach, Marco Cuturi, and Gabriel Peyré. Sample complexity of sinkhorn divergences. In Proc. AISTATS, volume 89, pp. 1574-1583, 2019.
[24] Amirata Ghorbani and James Zou. Data Shapley: Equitable valuation of data for machine learning. In Proc. ICML, 2019.
[25] Amirata Ghorbani, Michael Kim, and James Zou. A distributional framework for data valuation. In Proc. ICML, 2020.
[26] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13:723-775: 2012.
[27] Xiaoyi Gu, Leman Akoglu, and Alessandro Rinaldo. Statistical analysis nearest neighbor methods for anomaly detection. In Proc. NeurlPS, 2019.
[28] Harlfoxem. House sales in King County, USA. https://wxa www..a.w.....o/aa....aa.aeawae fxxmm housesalespreedctti.e 2016.
[29] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proc. CVPR, 2016.
[30] Peter J. Huber. Robust Estimation of Location Parameter. The Annals of Mathematical Statistics, 35(1 35(1):73-101, 1964.
[31] 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. In Proc. VLDB Endowment, 2018
[32] Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas J. Spanos. Towards efficient data valuation based on the Shapley value. In Proc. AISTATS, 2019.
[33] Hoang Anh Just, Feiyang Kang, Tianhao Wang, Yi Zeng, Myeongseob Ko, Ming Jin, and Ruoxi Jia. LAVA: Data valuation without pre-specified learning algorithms. In Proc. ICLR, 2023.
[34] Leonid V Kantorovich. On the translocation of masses. Journal of mathematical sciences, 133 (4):1381-1382, 2006.
[35] R. Kelley Pace and Ronald Barry. Sparse spatial autoregressions. Statistics & Probability Letters, 33(3)2291-297, 1997.
[36] Yuging Kong. Dominantly truthful peer prediction mechanisms with finite number of tasks. Journal of the ACM, 71(2), 2024.
[37] Yuqing Kong and Grant Schoenebeck. Water from two rocks: Maximizing the mutual information. In Proc. EC, pp. 177-194, 2018.
[38] Alex Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto, 2009.
[39] Yongchan Kwon and James Zou. Beta Shapley: a unified and noise-reduced data valuation framework for machine learning. In Proc. AISTATS, 2022.
[40] Kevin A. Lai, Anup B. Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In Proc. FOCS, pp. 665-6744 12 2016.
[41] Yann LeCun, Bernhard Boser, John Denker, Donnie Henderson, R. Howard, Wayne Hubbard, and Lawrence Jackel. Handwritten digit recognition with back-propagation network. In Proc. NeurlPS, 1990.
[42] Chun-Liang Li, Wei-Cheng Chang, Yu Cheng, Yiming Yang, and Barnabás Póczos. MMD GAN: Towards deeper understanding of moment matching network, In Proc. NeurlPS, 2017.
URL https:: giggthu...... hwwp://ottbrbrrraag///.C.CCCCC.
12

---

[43] Weida Li and Yaoliang Yu. Robust data valuation with weighted Banzhaf values. In Proc. NeurIPS, 2023.
[44] Yang Liu, Juntao Wang, and Yiling Chen. Surrogate scoring rules. ACM Transactions on Economics and Computation, 10, 2 2023.
[45] Gabriel
José Camacho, Roberto Magán- Carrión, Pedro García-Teodoro, and Roberto Therón. UGR' 16: new dataset for the evaluation of cyclostationarity-asse network idss. Computers and Security, 73:411 1-244, 2018. ISSN 0167-4048.
[46] Preston J. Miller and Daniel M. Chin. Using monthly data to improve quarterly model forecasts. Federal Reserve Bank of Minneapolis Quarterly Review, 20(2), 1996.
[47] Nour Moustafa. A new distributed architecture for evaluating ai based security systems at the edge: Network TON IoT datasets. Sustainable Cities and Society, 72, 2021.
[48] Muomneutrino. US census demographic data. 2019.
URL
com/
muonneutrino/use seneeettrinoosscccssueee -aw--ensss-ddmorraaaaaeee
[49] Dhanush Narayanan. Credit card fraud. URL dhanushnarayananrrcrede wawaaa/trredetttrrreeaaaaaaa--ae fraud, 2022.
[50] Sloan Nietert, Ziv Goldfeld, and Rachel Cummings, Outlier-robust optimal transport: Duality, structure, and statistical analysis. In Proc. AISTATS, pp. 11691-11719, 2022.
[51] Sloan Nietert, Rachel Cummings, and Ziv Goldfeld. Robust estimation under the wasserstein distance. arXiv preprint arXiv:2302.01237, 2023.
[52] Adamantios Ntakaris, Martin Magris, Juho Kanniainen, Moncef Gabbouj. and Alexandros Iosifidis. Benchmark dataset for mid-price forecasting limit order book data with machine learning methods. Journal of Forecasting, 37(8):852-866 2018.
[53] OpenAI. Introducing ChatGPT plus. https: coattolo/actcttttttt....... 2022.
[54] Byung-Jung Park, Yunlong Zhang, and Dominique Lord. Bayesian mixture modeling approach to account for heterogeneity in speed data. Transportation research part B: methodological, 44 (5):662-673, 2010.
[55] Stephanie Schoch, Haifeng Xu, and Yangfeng Ji. CS-Shapley: Class-wise Shapley values for data valuation classification. In Proc. NeurlPS, 2022.
[56) Rachael Hwee Ling Sim, Yehong Zhang, Mun Choon Chan, and Bryan Kian Hsiang Low, Collaborative machine learning with incentive-aware model rewards. In Proc. ICML, 2020.
[57] Rachael Hwee Ling Sim, Xinyi Xu, and Bryan Kian Hsiang Low. Data valuation in machine learning: "ingredients". strategies, and open challenges. In Proc. IJCAI, 2022. Survey Track.
(58) Rachael Hwee Ling Sim, Yehong Zhang, Trong Nghia Hoang, Xinyi Xu, Bryan Kian Hsiang Low, and Patrick Jaillet. Incentives in private collaborative machine learning. In Proc. NeurIPS, 2023.
[59] Bharath K. Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert R. G. Lanckrict. On integral probability metrics, i-divergences and binary classification, 2009.
[60] Sebastian Shenghong Tay, Xinyi Xu, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Incentivizing collaboration in machine learning via synthetic data rewards. In Proc. AAAI, 2022.
[61] John von Neumann. Zur theorie der gesellschaftsspiele. Mathematische Annalen, 100:295-320, 1928.
[62] Abraham Wald. Generalization of a theorem by v. Neumann concerning zero sum two person games. Annals of Mathematics, 46(2):281-28) 1945.
[63] Jiachen T. Wang and Ruoxi Jia. Data Banzhaf: A robust data valuation framework for machine learning, In Proc. AISTATS, 2023.
13

---

[64] Qing Wang, Sanjeev R. Kulkarni, and Sergio Verdu. Divergence estimation for multidimensional densities via n-neabest-neighbor distances. IEEE Transactions on Information Theory. 55(5): 2392-2405, 2009.
[65] Shuaiqi Wang, Jonathan Hayase, Giulia Fanti, and Sewoong Oh. Towards a defense against federated backdoor attacks under continuous training. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL httpss:/opperevieee HRcB5elyuG.
[66] Jiaheng Wei, Zuyue Fu, Yang Liu, Xingyu Li, Zhuoran Yang, and Zhaoran Wang. Sample elicitation. In Proc. AISTATS, 2021.
[67] Zhaoxuan Wu, Yao Shu, and Bryan Kian Hsiang Low. DAVINZ: Data valuation using deep neural networks at initialization. In Proc. ICML, 2022.
[68] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: novel image dataset for benchmarking machine learning algorithms. https://githut thub. cwm/calmmcccccccc conmzalandoresearch fashion-mnist 2017.
[69] Xinyi Xu. Lingjuan Lyu, Xingjun Ma, Chenglin Miao, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Gradient driven rewards to guarantee fairness in collaborative machine learning. In Proc. NeurlPS, 2021.
[70] Xinyi Xu, Zhaoxuan Wu, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Validation free and replication robust volume-based data valuation. In Proc. NeurIPS, 2021.
[71] Xinyi Xu, Thanh Lam, Chuan-Sheng Foo, and Bryan Kian Hsiang Low. Model Shapley: Equitable model valuation with black-box access. In Proc. NeurlPS, 2023.
[72] Jinsung Yoon, Sercan Arik, and Tomas Pfister. Data valuation using reinforcement learning. In Proc. ICML, 2020.
14

---

A Proofs and Derivations
A.1 Equivalent Definitions of MMD
Definition follows [26] to use the function class F. In our derivation and implementations, adopt an equivalent but more convenient form utilizing the kernel and mean embedding [26, Section 2.2]. Definition is more difficult to use with because of the sup operation. Specifically, recall that F is a class of functions in the unit ball of reproducing kernel Hilbert space (RKHS) H which is associated with the kernel k, then the following equivalence holds [26, Lemma 6]:
(6) The definition of MMD that is used in our derivation and implementation is the right hand side above. This definition is more convenient because it no longer has the unwieldy sup operation and is interpretable (i.e., resembling the square root of an expanded quadratic expression).
:(P (Exxxxx((XXxx"")
2Ex=P.Y~P' [k(X, Y)] + Ey [K(Y, Y')] 1/2
We note that throughout the paper, the class F of functions, its corresponding RKHS H. and the associated kernel are all kept constant, so their notational dependence is omitted where clear for brevity.
A.2 For Sec. 3
Proof of Observation
Proof of Observation J. Note that Pa is mixture modelldistributtion, it is a convex combination of P.' s. The expressions for EN, QN are derived as follows,
Ps Σ wi[(1 = + 2q
P
Ei) + E wie:Qi) wi(1 (11=;
iEN
P*(1
wHs
w4e,Q.)
Qu
The last step uses the fact that the entries of a probability vector sum up 1.
A.3 For Sec. 4.1
Useful lemma.
Lemma (Uniform Convergence of MMD Estimator [26, Theorem 7J). Let X ~ P.W ~ P' and
the size of X is m, the size of W is n. Then the biased MMD estimator d satisfies the following approximation guarantee:
-E2mm
{ |d(( - d(P, 2(/K/m + VK/n) + 2exp(
Prx.w
2K(m + n
where Prx,w w over the randomness of the m-sample and n-sample W.
Note that Ebins in our results (e.g., Proposition 1) corresponds to in Lemma 1.
Proof of Proposition
Proof of Proposition 1. Apply Lemma I to D ~ P and D ~ P', respectively.
2 mmm"
W.p. 2 1p where 6p == 2xxp
2k(m+m
K
K
d(P. å(D, D*) 12(
bbias
m
15

---

K
K
-T(P) S -D(D) 12(1
+
Ebias
m
K
K
T(P) 2 (D) - 12(g
+
Ebias
m
m
where the first inequality is from directly applying Lemma 1, the second inequality is from substituting the definitions in Eq. (1).
Symmetrically, w.p. 2 1 - 6p. where 6p == 2 exxp
- mn. ).
2K (m 4m
K
K
+ 21
+
Ebias
m
B
Observe that if A 2 B + er, then apply the independence assumption (between D and
D' ~ P'), w.p. 2 (1 - 8r) 5pr)). T(P) > T(P") + trr
Re-arrange the terms A > B + ST derive Cu+
K
v(D) - 2((
+ Shias] 2 u(D') + 12(1
+
+
Shins
+
gr
m
m'
m72"
K
K
v(D) 2 v(D') + 2(Ebius +
+
ter
T
To arrive at the simpler but slightly looser result in the main paper. Note that (1- 6p) 8p,) (1 8)2 2 (1-26)
Confidence level increases with m, m'. Note that equivalently.
bas m
Ebies m #2
8p 2 exp(
2K
2K (m + m
which is decreasing in m. Similarly for 8p, w.r.t. m'. As result, a higher mn implies lower 8p and thus a higher confidence level (1 (1 - 8p.).
A.4 For Sec. 4.2
Useful lemma.
Lemma 2 ([15, In proof of Lemma 3.3]). For Huber model P = (1 - P) + =Q, the MMD d'P,P*>= ==d(P*,0 QQ.
A.4.1 Results and Discussion for General Mixture P.
Error from using a reference. Sec. 4.2 describes a theoretically justified choice for reference Per be used place of P* in T in Eq. (1), and define an approximate Y d( P). Then, the valuation error [T()) - f(P) from using this reference Pat should ideally be small. This error is directly upper bounded by the MMD between Per and P*, as follows.
Lemma 3. For choice of reference Prote define ?(P) -d( d(( Pret. P) the approximate version of ((P) in Eq. (1). Then,
VP.IT(P) - ((P) S d(Piet, P*).
Proof. Apply the triangle inequality of MMD to the definitions of T and f.
[(P) T(P) = (d(P. P.) -d(P P*) < d( Prtt)
16

---

Lemma 3 implies that a better reference distribution (i.e., with a lower MMD to P*) leads to better approximate Y (i.e., with lower error). Hence, we have specifically obtained theoretical results to upper bound the MMD between our considered choices for reference: P. via Lemma 4, which be directly combined with Lemma to derive the enror guarantee, described next.
Error from using Pa as the reference. We first provide an upper bound on d(Pu. PO) in Lemma and then combine it with Lemma 3 to obtain Proposition 2. Lemma 4, The sampling distribution P. for D., satisfies d(Pw,, P*) S et,
Proof of Lemma 4. The proof is direct application of Observation 1 and Lemma 2.
L
Lemma 4 provides an upper bound on the MMD between Pa and pt, which linearly depends on ew and Qu. A lower reference.
lower d(Qw, P*) leads to smaller d(Pw, P*), making D. better
Proof of Proposition 2. It directly combines Lemma and Lemma 3.
Proof of Theurem I. Apply Lemma 4 and Lemma D P and D respectively.
1--8, 8'p where 8'p == 2 exp( W.p. 2 1
Eal MAN
2K (m-+my
K
K
T(P) = d(P,, pr - d(P. 20) 22
+ Ebins
(.,((u,,"))
m
MN
symmetrically, w.p. 2 8/pm where 8y,, == 2 expp
Sun my
2K [k(m/4xx)
K
K mn
T(P') -dpp' < ,
P.) Pu)+ PT) s B(D') 12(
+
Ebias
Ewi((Qwr PO)
m
Observe that if A B+5r- and apply the independence assumption (between Pand D' P'),
then w.p. 2 (1 - (1 8'p,). T(P) > T(P') - ST
Re-arrange the terms A 2 + Er derive C.
K
K
K m
K
P(D) - -2(
Ebian] - (ud(Qu,, 2(D)) +(D))+122)
+
+
Ebina] + Eud(Qu, P*) +
mN
mN
K
K
K
D(D) 2 D(D') 2 Bbaas +
+
2
+ +wud(Qu, P')
ter.
m
m
mn
42
To arrive at the simpler but slightly looser result in the main paper, note that
(1 - 515%))(11 8p- 2 (1 8')² -20)..
A.4.2 Results and Discussion for the Uniform Mixture Pt
As we do not make any assumptions about the prior knowledge of the vendors (c.g., some vendor i is more reputable), we adopt perspective that minimizes the worst-case (i.e., maximum) error over selecting the vendor's 's distribution the reference. In other words, we (represented below as the row player) want pick a vendor, and use the corresponding distribution as the reference to value other distributions. Hence, if we pick "good" vendor (i.e., whose distribution is close to P*). it is more desirable (i.e., higher payoff) since the approximation error (as in Proposition 2) is lower. Formally, we construct finite two-player zero-sum game in which we show that the uniform strategy worst-case optimal. Hence, we propose to use the uniform mixture Pt Σ; P. of the vendor's distributions the specific choice of reference.
17

---

A finite, two-player zero-sum game. The row player (main player) represents the buyer (the one performing valuation) and the column player (hypothetical adversary) is used to explicitly model the fact that we do not have prior knowledge or assumptions about the vendors" distributions (except each P; is a Huber).
Recall that the payoff matrix R E [Rnx(a)) for the row player (main player) is
Ry == dxarr) == -d((", Pre(r))
(7)
which is the negated MMD between P and the distribution Prolr] the r-th position of the permutation Te and hence the payoff matrix R is
d
drslll dxss3]
d21
d 2
R =
(n((n)
daa(n)
[n]
The notation is used specifically refer the position in permutation Te. and is not to be confused with indexing of the data vendors. For completeness, the payoff matrix of the column player is the negation R. (i.e., R C 0). Observe that this is finite, two-player zero-sum game.
Proposition 3: The uniform strategy is worst-case optimal. While the values of the entries in R not known explicitly, there are some properties of these values that can be exploited. We provide a constructive proof: formulate the primal and dual linear programs (LPs) for the two-player game as in Eq. (4), show that the uniform strategies lead to equal values for both LPs, and conclude that, by the strong duality, both are optimal.
Proof of Proposition 3. For the row player, the optimal strategy snw can be computed via the following LP (1) [18], the value of which is equal to the row player's payoff based on the column player's optimal response sol to yow-
max
S.t. 5 row
R b
LP
low =
Srow > 0
where > denotes element-wise 2
The dual LP LP (1) is
min z'
s.t. ST
+ 211 0 T
LP
scl
Scol
0.
By a change of variable z" = -2' and the fact that C = R. we equivalently rewrite LP (2) as follows,
max z"
s.t. Cscal > 1
LP)
Sol 1 =
Scal > 0.
Observe that LP (3) is the LP for the column player to solve for sta [18].
Our proof has the main following steps:
Verify that the uniform strategy [1/n, 1/1,,1n..../// 1/n,..., 1/m] is a feasible solution L. (1) and obtain the corresponding value 2.
18

---

2. Verify that the uniform strategy [n/(n.,, (/nn......... 1/(n)]] is a feasible solution to LP (3), obtain the corresponding value z", and translate to the value z' == to LP (2).
3. Apply the strong duality: If the values of the primal and dual LPs are equal (i.e., 2 z²), then the corresponding solutions must both be optimal.
For step 1., make of key observation that the set G of distributions is fixed, which implies that independent of the permutations Tes and the sum = Dr=1 -d(Te(rl) is thus a constant. Then, for any Te, it gives the 2x. _ so the overall value is 2 = min, 2n. = S/n. For step 2., in the r-th row of C:
[dx,(r). dxalr)- d dxm:11))
there are (n- 1)! entries/copies of each d, 15 S n. This is because out of n!! possible permutations, any particular appears the r-th position exactly (n-1)! times (since there are (n- permutations of the others). Hence, the value corresponding to the uniform strategy [1/(n!), 1/(n!), 1/(n)) for the r-th row in
n!
dx
m!
1
nn
1)d
1
n! 1=1
(n
1)!
dp)
n2!
1
S n
The third equality applies the above argument any appearing at the r-th position exactly (n - 1)! times. Since this is true for any r-th row and that it does not explicitly depend on the overall value Then, the corresponding solution to I.P (2) has z' --=-=
z" == max, z =
For step 3., apply the strong duality (since : z' 5/n) and conclude that the uniform strategies are optimal for both the row and column players.
Proposition 3 implies that the uniform strategy is the worst-case optimal approach when selecting a data vendor at the r-th position (whose distribution to use as the reference) without any prior knowledge assumptions about the data vendors (i.e., regardless of how the data vendors ordered).
Uniform mixture Pt from the uniform strategy. Since the uniform strategy is worst-case optimal, we implement it via the uniform mixture of the data vendors' distributions Pu == _ Σ, P; as the proposed reference in place of P* to define Eq. (3) as a practically tractable approximation to T (which itself cannot be used since P* is unknown). In particular, the results on bounded approximation error and actionable policy derived w.r.t. a general P. (i.c., Proposition and Theorem 1) applicable to Pa = Pu since Pu is special case of Pa, as the following corollaries.
Corollary 1. Let Ý = d(P, Pu), then VP, (T(P) T(P)) S Fud(P",Qu)-
Proof of Corollary 1. The result follows by directly applying Proposition with Su. Qu
Corollary 2. Given datasets D P and D' ~ Pl, let m := |D] and m' = D' J. Let & be from Eq. (3) where D., is specified as Dr: ((D) == -d D, Du) and mn = Dul- For some bias requirement bias > 0 and required decision margin ex 2 0, suppose i(D) > ((D)) + AT, where
'y the classic [61, Minmax Theorem], these minmax solutions for both players form Nash equilibrium.
19

---

the criterion margin I, =r + 2(Ebias + VK/m+t + VK/m' + 2VK/mmx' + Eud(Qu,P") Let 8 == 2 exp( 2K (m where m max(m, Then T(P) T(P)) +er with probability at least (1 )
Proof of Corollary 2. The result follows by directly applying Theorem with Du. Qu
Difficulties of searching over all convex mixtures w. Note that the game specified in Eq. (4) has finite action space N for the row player. Essentially, means that the row player is considering exactly one of the n data vendors as the reference, though the minmax solution suggests that the row player should adopt mixed strategy to consider all data vendors equally.
natural extension of the game is for the row player to consider all possible convex mixtures A(n 1):
max min - dddPp,Paa. WEA(n 1) IE =EM()
(8)
where Pu., == EP= Pa[rjW, is a mixture specified by a following the permutation क and [I()) denotes the set of all possible permutations of {1, (1.
From a theoretical perspective (i.c., to understand and analyze the optimal solution, if one exists, to Eq. (8)), there are some difficulties because Eq. (8) is an infinite game (because of the action space of the row player). In particular, infinite games (or semi-finite games where one player has a finite action space) are significantly harder analyze the optimality even existence of the (optimal) solution. In general, it is not guaranteed that the optimal solution(S) exist for one or both of the players [62], and in cases where the optimal solutions exist, there may be so-called duality gap [21]: The minimax theorem for the finite game implies that the optimal solutions for both players will give values that
coincide (i.e., the optimal for row player is the negated optimal for the column player), but the duality gap means that in the infinite regime, the optimal solutions may not give values that coincide, making harder to even verify if pair of solutions is optimal (since the values may not coincide even if they are indeed optimal).
Moreover, the MMD d in Eq. (8) introduces an additional difficulty since it is not guaranteed to be convex in the mixture of the models: for some X E [o, 1], Pı, P2, the convex combination of P + (1 - A)d(P*, P2) is not necessarily smaller than or equal to (P*, XP, + (1 P2). In other words, there are cases where either direction of the inequality is true. The implication is that, when searching optimizing over w E An - 1) via methods that try to "move" current solution by a small amount to arrive at new solution (or towards the optimum), it is more difficult to do so, since moving the current solution might increase or decrease the value (and is not known a priori which).
A.4.3 Additional Discussion on Approximation Error
The result on the approximation error (i.e., Proposition 2) can be useful in designing alternative approaches of finding reference, and also in considering additional desiderata (e.g., incentive compatibility [5] and truthfulness [14]).
Precisely, for any Per (e.g., Pw or Pu), if it is boundedly close to p in the MMD sense, then a bounded approximation error is available (by the triangle inequality of MMD):
d( (Pert P") S Eeer
(P,IT(P)- (P) < E
where Tre((P) d(PP, Prrt). We highlight that this precise formalization and the subsequent discussion have not been presented in related existing works (e.g., [1, 14, 60, 66)), and that this discussion is enabled by the analytic properties of Huber and MMD.
A possible optimization approach for finding a reference and its difficulties. Intuitively, a smaller approximation error is more desirable (and later we will discuss a specific such desideratum), so naturally we want to minimize it. The following objective is such example, to be optimized/minimizzed over all possible convex mixtures of the data vendors' distributions:
min sup (- wE-
(10)
p
20

---

where == wiPP is convex mixture of the data vendors' distributions as in Observation 1. The triangle inequality MMD enables simplification of Eq. (10) the minimization of an upper bound (of the original objective) instead:
min d(Pw, wEA(n-1)
From an implementation or practical perspective, this objective, unfortunately, presents a major practical difficulty in that pa is not available (which is the reason for obtaining reference in the first place). Hence, additional assumptions are required to make this objective tractable (c.g.. a validation dataset from P is available [24, 39, 63], each P; is assumed to be somewhat "close" to P [1, 14] or the union or some combination of { heN is close to P [60, 66]).
We highlight that the assumption P" is available is indeed key challenge that we aim to address (by relaxing this assumption) because in practice P is not available. Hence, exploring a suitable form of the assumption (in the sense that it is practically feasible and also enables tractable optimization of Eq. (10)) presents an interesting future direction.
Additional desiderata. We make precise the intuition that a smaller approximation error is more desirable by connecting the approximation error the so-called incentive compatibility (IC), frequently used in (truthful) mechanism designs [5, 6, 8, 14]).
Definition 2 (y-incentive compatibility). The valuation function Y is 7-incentive compatible, for some 7 2 0, if
T(P; (PolveNNo))) 2 T(P:: (Po)vEN()))))
where P3 denotes the mis-reported version of P,
In Definition 2 [6, 51, y 0 recovers the exact definition of IC. IC is an important desideratum in that it can be used to show that each vendor being truthful (i.e., not misreporting) forms an equilibrium [14] and truthfulness is another such desideratum.
Depending on the specific design, the valuation Y can have different additional dependencies. For instance, in the ideal case where pa is available, T(P) -d(P, P*) has an explicit dependence on P and it satisfies I1-IC where d == max; d( P., P*) (can be directly verified using Definition 2). On the other hand, for some ((P) == - -d(P, Pret) s.t. (rrre P*) Eztt it has a weaker IC (i.e., larger corresponding ?): satisfies IC for "he == Efe + d, by the triangle inequality of MMD. Notice that eef is directly related to the approximation error above, so this suggests that analyzing and then minimizing the approximation error to design a solution with strong IC is a promising future direction. Indeed, some preliminary empirical results (App. D.3.5) demonstrate some promise that (approximate) IC achievable in some cases.
Note that even in the idcal case where Pa is available, the exact IC is not necessarily guaranteed. This because the (truthfully reported) distribution P. by each vendor i is not guaranteed to be the same as Pt, which is often the case in practice where the data collected are not guaranteed to be directly from the ground truth distribution [24, 32, 57]. Hence, is theoretically possible that "mis-reported" P. such that d( ((P..P") < d(P.. P"), namely an improvement from P. However, such cases would be rare in practice since it is generally difficult to "move" a distribution P: (via some statistical operation) towards an unknown optimal distribution P*, as otherwise pa can obtained by simply performing such operations on given distribution P; until it reaches p*
Moreover, [36, 37, 44] have noted that, our setting of no reference/ground truth (i.c., no P*). is impossible design a mechanism that guarantees truthfulness of the data vendors, if the data vendors are not assumed be completely independent of each other. other words, without access ground truth, and if there is possibility of so-called side information among the data vendors themselves, truthful mechanism is impossible, further highlighting the difficulties of our setting (i.e., without reference).
An example of mis-reporting is injecting artificial noise.
21

---

B Additional Discussion on Related Works
B.1 Discussion on the Assumptions of Related Works and Applicability to the Problem Statement
In addition to the existing works mentioned in Sec. 2, 31, 32, 72] also share a similar dependence on given reference dataset. Consequently, it is unclear how to apply these methods without a given reference dataset.
Next, we elaborate the works that relax the assumption of a given reference and better contrast their differences from our work, specifically in how they relax this assumption.
Chen et al. [14, Assumption 3.2] require that P must follow known parametric form and the posterior of the parameters known. Chen et al. [14] assumes that each data vendor collects data from the ground truth data distribution (parametrized by some unknown parameters) and performs the analysis on whether a data vendor will report untruthfully when everyone else is reporting truthfully. Specifically, the reference is the aggregate of all vendors excluding the vendor i itself. It is unclear how heterogeneity can be formalized in their theoretical analysis, which assumes the vendors are collecting data from the same (ground truth) data distribution. [60] directly assumes that the aggregate dataset Di or the aggregate distribution P. is a sufficiently good representation of p and thus provides good reference, without formally justifying it or accounting for the cause or effect of heterogeneity. Wei et al. [66, Assumption 3.1] require that for any i, i', the densities of P. and Py must lie on the same support, which is difficult to guarantee because Q Q2 can have different supports (resulting in P, P. having different supports). [66] uses the f-divergence specifically the KI. divergence, which requires assumption that the densities of the data distributions (of all the vendors) to lie on the same support [66, Assumption 3.1]. This assumption can be difficult to satisfy in practice since the analytic expression of the density of the data distribution is often complex and unknown. To illustrate, our experiments consider heterogeneity in the form of mixture between MNIST and FAMNIST; it is unclear how satisfy the assumption that the densities of the distributions of MNIST and FAMNIST lie on the same support. Moreover, their method does not formally model heterogeneity or its effect on the value of data.
Furthermore, a similarity in these works [14, 60, 66] is how they leverage the "majority" to construct reference either implicitly or explicitly. Specifically, in [14], the reference for vendor is the aggregate of every vendor's dataset except i; in [60, 66) the reference is constructed by utilizing both the aggregate dataset D., and additionally some synthetically generated data (Tay al. [60] use the MMD-GAN while Wei et al. [66] use the f-divergence GAN). We highlight that these works did not provide a theoretical analysis on "how good"' their respective reference is, namely, what the error from using the reference instead of using the ground truth? In contrast, we answer this question via Proposition 2 and propose to use the uniformly weighted "majority" as the solution, inspired by the worst-case optimality of the uniform strategy in the two-player zero-sum game (Proposition 3).
Note that there are recent works that emphasize different aspects such as privacy [58] and without access to data [71], and hence differ from our settings.
B.2 Comparison with Alternative Distances/Divergennes
Supplementing the comparison of Table 1, we provide additional details and discussion with alternative distances/divergenees (to our adopted MMD) that have already been adopted for the purpose of data valuation.
Comparison between Ours and MMD Empirically, ours (i.c., MMD-based) and MMD [60] perform similarly across the investigated settings (including empirical convergence and ranking data distributions), which is unsurprising since theoretically the numerical values only differ by square. Although MMD² has an unbiased estimator [26, Eq. (4)] while MMD, to our knowledge, only has a biased estimator [26, Eq. (6)), this advantage does not seem significant, since the convergence results in Sec. 5.1 demonstrate similar convergences for Ours and MMD Recall that Sec. 5, we highlighted that the implemented estimator for MMD is not obtained from taking the square of that for MMD. Nevertheless, we have also tried this implementation of directly squaring the estimator for MMD to be the estimator of 2MD but did not observe significant difference in the empirical results.
22

---

On the other hand, from theoretical perspective, the difference in terms of the implications, is more significant. This is primarily due to the analytic properties of MMD, which are not also satisfied by MMD2, such as the triangle inequality, used to derive Proposition 2, and the property with Huber model (i.e., Eq. (2)) which is used to derive Lemma and Theorem 1. is an interesting future direction to explore similar results for MMD
Comparison between Ours and the Wasserstein metric. Similar to MMD, the Wasserstein metric, also known the optimal transport (OT) distance [34] also satisfies the axioms of a metric, in particular the triangle inequality. This can make the Wasserstein metric promising choice for our setting. However, MMD seems to have two important advantages -one theoretical and the other practical-: (i) Under the Huber model, MMD enables a simple and direct relationship (i.e., Eq. (2)) that precisely characterizes how the heterogeneity (formalized by Huber) of a distribution affects its value. It is unclear how or whether the Wasserstein metric can provide the same relationship. and some works [50, 51] seem to suggest the difficulties of obtaining the same relationship. (ii) The definition of the Wasserstein metric (involving taking an infimum over the couplings of distributions) makes its value difficult to obtain (compute or approximate) in practice. Indeed, LAVA's official implementation [33, Github repo] does not directly compute/approximate the 2- Wasserstein distance, but instead obtains the calibrated gradients as a surrogate [33, Sec. 3.2), which are not explicitly guaranteed to approximate the 2- dttasserstein-basede values. In contrast, our method directly approximates the MMD (with the estimator [26, Eq. (6))) with a clear theoretical guarantee (Lemma 1). In other words, though the Wasserstein metric satisfies the appealing theoretical properties, in implementation, valuation based on the Wasserstein metric is difficult to obtain directly, and instead some surrogate is obtained. Moreover, it has not yet been guaranteed that this surrogate also satisfies (possibly approximately) the same appealing theorctical properties that might make the Wasserstein metric a promising choice.
Comparison between Ours and f-divergences. The f-divergences family presents a rich choice (since it contains many specific divergences such as Kullback-Leibler, total variation and etc.) and is also adopted in existing works such as [14, Definition 4.5], [66, Algorithm 1] and [1, E1.( for the theoretical properties of the adopted f-divergence (or variant). For instance, the Kullback-Leibler (KL) divergence satisfies the required [66, Assumption 3.4] for the proposed method, while the extended KI. divergence proposed by Agussurja et al. [1, Sec. 3] enables a decomposition of the terms to simplify the analysis.
These theoretical properties notwithstanding, our adopted MMD has a clear advantage over the f-divergence with important practical implications. A commonly made assumption with using the f-divergence [(PlIQ) is the absolute continuity of P w.r.t. Q, since otherwise the division-by-zero makes the definition ill-behaved. This assumption is difficult to satisfy or even verify in practice, especially for complex and nigh-dimensional data distributions. In contrast, the sample-based definition of MMD does not require such an assumption, making its application to complex and nigh-dimensional data distributions easier (in the sense that the user does not have to worry about bufficult-to-satist assumption). Intuitively, this difference between f-divergences and most integral probability metrics (IPMs) such as MMD, that when and Q have disjoint supports, all f-divergences take on constant value; in contrast, IPMs can give "partial credit".
Another important practical implication due to the difference in the definitions of f-divergences and MMD is that: it is more direct and easier to approximate MMD (e.g., using a sample-based approach [26, Eq. (6)] and with theoretical guarantee as in Lemma 1). In contrast, the definition of the f-divergence f f(Pll) that directly depends on the density functions of P. Q adds to the difficulties of estimating in practice, as it requires estimating the density functions (or least the ratio of the density functions). This is difficult for complex and high- -imeensinaii data distributions and may require simplifying assumptions of the parametric form of the distributions (e.g.. P, Q are both multi-variate Gaussian [1] to enable a closed- form expression for KL.).
B.3 Comparison with other Characterization/Treaaaaa of Data Heterogeneity
As an additional comparison to supplement our remarks in Sec. 3 for why adopting the Huber model, we highlight a comparison with relevant existing methods in their treatment of data heterogeneity, and then further elaborate on the analysis based on the design choice of the Huber model.
23

---

Recall that the Huber model characterizes a sampling distribution P via a mixture (weighted by E) between the ground truth distribution P and some unknown distribution Q (e.g., an outlier distribution). This characterization is sufficiently general to model several sources of heterogeneity (via & and Q) [12, 13], while also having dependence on the ground truth distribution P of interest. In our setting, this modeling choice means that the sampling distributions of the different data vendors have varying "qualities" via their different dependence on the ground truth distribution P (in pathological cases where + 1, P effectively has no dependence only contains Q). This way, Huber model provides a precise yet relatively general way to characterize the differences, namely heterogeneity in the sampling distributions of the data vendors: their sampling distributions may have different dependence on P", and this dependence is made precise via E, Q. This precise characterization is important in enabling the subsequent analysis.
the ground truth distribution and
Existing works do not precisely characterize data heterogeneity. Before highlighting the analysis based on the Huber model and the theoretical appeal thereof, we first compare with some relevant existing works, which either do not characterize the heterogeneity at all [2, 33, 55, 66, 67]. or do so through simplifying assumptions [1, 14, 60].
Agussurja et al. [1, Assumption (A3)) assume that in the infinite sample regime, for the data from each data vendor, there exists a so-called uniformly consistent distinguisher. In other words, it means, for the purpose of parametric estimation (which is the setting in [1]), the sampling distribution of each vendor has the same quality, this is because with sufficient samples, each vendor individually can identify or recover the true parameters. In summary. this assumption simplifies the problem and bypasses heterogeneity by making the sampling distribution of each data vendor the same specifically w.r.t. parametric estimation (i.e., these sampling distributions are not the same in general).
Chen et al. [14, Section 3, Assumption 3.1] assume that the dataset of each vendor consists of Li.d. samples conditioned on some common unknown parameters 0. The authors also note that "This (Assumption 3.1) is definitely not assumption that would hold for arbitrarily picked parameters O and any datasets." In this way, it is unclear how the heterogeneity of the sampling distribution of each individual data vendor is precisely characterized.
While Tay et al. [60] consider the sampling distributions of the vendors to be heterogeneous, the authors do not precisely define the heterogeneity. As the treatment, Tay et al. [60, Assumption (B)] assume that the aggregate distribution (i.e., the underlying distribution of the union of the samples from all the data vendors) "approximates the true data distribution well." Note that the authors do not precisely define what it means by approximating the true data distribution well, in contrast we provide such an analysis (i.e., Proposition 2 for the general class of convex mixtures).
The (appeal of the) analysis based on the Huber model. We elaborate further on the property (e.g., Lemma 4) and the results (e.g.. Eq. (2)) based on the Huber model.
In our studied setting with multiple data vendors, the mixture model of Huber is particularly useful because a mixture of Huber distributions is also a Huber, whose parameters (i.c., s, Q) can be derived based on the parameters of the component Huber distributions, namely via Lemma 4. This makes Huber particularly appealing for the purpose of theoretical analysis. To elaborate, given data valuation function (e.g., Eq. (1)) that is well suited for Huber distributions, we can use this to evaluate the value of the distribution of single data vendor, any specified convex mixture of distributions of multiple data vendors (which is useful for the peer-prediction paradigm [14, 60, 66) and adopted in Sec. 4).
Subsequently, our designed MMD-based valuation function in Eq. (1) exploits the structural property of the Huber model (i.e., it is a mixture) to provide a precise characterization of the effect of such heterogeneity on the value of data, namely Eq. (2). In other words, Eq. (2) answers the question: "precisely how does the heterogeneity of data distribution affect its value?" This has not been achieved in prior works.
Additionally, the theoretical properties the Huber model (jointly with the MMD-based valuation) admit the results that describe an actionable policy for comparing different sampling distributions (i.e., Proposition Theorem 1). and also a game-theoretic perspective that yield the uniform mixture as the worst-case optimal Proposition 3. We highlight that such results leverage certain specific mathematical properties such as Lemma 4 and Eq. (2).
24

---

Connection to robust statisties and a possible error lower bound. We highlight that mixture models have deep roots in the field of robust statistics [19, 20, 40] where the goal is estimate some statistics (e.g., mean and covariance) of the ground truth distribution Pr. Hence, prior results obtained can shed light on our setting, method and results. For instance, [40] prove an information- thhorretc lower bound of error for mean estimation using the data collected from the mixture model (between P and some outlier distribution Q). In particular, for a sampling distribution P = (1 - =) P + +QQ, the error (of mean estimation) has lower bound that is at least linear in the proportion of the outlier distribution [40, Observation L.4]. For our setting, this result can suggest that it is impossible to obtain arbitrarily good reference P. s.t. d(P,,, P*) < EMMD for any desired EMMD 2 0 where the mixture model is as in Observation 1. This can further justify our approach of using a convex mixture P. Pu the reference, which would have "error" (i.e., d(P., P))) linear in E. (i... Lemma 4 or Corollary 1). Note that here a main difference is that we have multiple data vendors. We need consider collection of distributions {P.) and outlier distributions {Q+] where in contrast, [20, 40] consider settings with only one outlier distribution Q. This means that we need to additionally consider how to "combine" these distributions, which do via their convex mixtures as in Observation 1).
We outline an informal sketch of this idea and defer the formal treatment to future work, which requires a careful "translation" " between the settings of mean estimation and distribution estimation, see below: The results in [20, 40] are w.r.t. the f--norm of the error for mean estimation. In our setting, the error (i.e., the MMD d d(P.. P*)) is w.rt. the RKHS norm (MMD is an RKHS norm [26, Lemma 4J). Note that, for function f H. in an RKHS H. its fz-norm is dominated by its RKHS norm: IIl S Il. [17, Section 2). In other words, one can transfer the information theoretic lower bound (e.g.: [40, Observation I.4)) to our setting by using the fact that the MMD (which is an RKHS norm) dominates the fz-norm of the error of mean estimation. Informally, since the lg error of mean estimation lower bounded, and that the RKHS norm is larger than (or equal to) the fn-norm, the RKHS norm (i.e., the MMD between the any reference Pa and P*) is also lower bounded, meaning that it is impossible find arbitrarily good reference Pa.
C Questions & Answers
Due to page constraints of the main paper, we provide some additional elaboration to supplement our main paper and without which would not affect the completeness of the treatment in our main paper. We adopt the form of questions and answers for the convenience of the reader.
Q1. Why is there need for explicitly considering a valuation method for data distribution? Why not directly extend existing dataset valuation methods to data distribution valuations?
Answer: In addition to the practical use-cases outlined in Sec. which require a value of a data distribution instead of a value for a finite dataset, there are theoretical considerations for the perspective of data distribution valuation, as elaborated next.
Most existing works focus on defining a value v (D) for a fixed discrete dataset D) instead of the value ((P) for the sampling distribution P from which each individual data point in is i.i.d. sampled. Then, one might think to extend a defined/given dataset valuation v to define a value T(P) of P, such as based on the expectation of vDD over the randomness of D: For some existing/already defined ((D) R.
T(P) = (DDDu(()
(11)
Additionally, to account for the fact that D has finite size, consider the limit of this expectation as the size [ of D approaches infinity, since in the infinite sample regime, the sample statistic obtained on D would tend to the population statistic on P:
T(P)= = lim EDWPH(D) Di
(12)
Such definitions in Eq. (11) and Eq. (12) require theoretically defined understand and study the theoretical properties of the corresponding T(P), which is often not available, and also a characterization of P due the D P in the expectation, which is also not available.
To elaborate, the most commonly adopted choices of v, following [24), are defined through some empirical observations, c.g., the evaluation performance given validation set D of a fixed ML
25

---

model trained on D. While for the purpose of implementation and experiments, for thusly defined Eq. (11) can be approximated reasonably well, there are difficulties when it comes obtaining a theoretical analysis of T, primarily because the analytic expression of is difficult to obtain. This because this analytic expression of v depends on the choice of Daat, the MI model, the training procedure and etc. and can be complicated. An existing work proposes to utilize the framework of neural tangent kernel to help characterize v [67]. but nevertheless does not consider or define or explicitly characterize the sampling distribution P.
Secondly, Eq. (11) and Eq. (12) require characterization of (because of ED which has not been proposed or studied by prior works.
Therefore, instead of trying to extend the existing valuation methods defined for discrete datasets to data distributions, which would encounter the difficulties (of obtaining the analytic expression of v), adopt the perspective of considering the distributions directly and propose valuation for data distributions. The advantage of this perspective that, a valuation defined for a distribution automatically yields a valuation for dataset because the value of a distribution is essentially population statistic while the corresponding value for the dataset is the sample statistic and is well defined. In other words, we propose the perspective of "going from data distributions to datasets", because of the appeal for theoretical analysis.
Q2. What is the right interpretation of the problem statement and how it is connected to the thcoretical results of Proposition I and Theorem I?
The problem statement asks for a prescriptive solution: A result that informs the buyer, in order to make the determination that P is more valuable than P' by some amount e (i.e., this is what the buyer wants), here is what the buyer needs to observe. This is made precise by Proposition 1 and Theorem where the amount is denoted as Er. and what the buyer needs to observe that (DD) v(D) + AT. Suppose that the buyer observes that this inequality is not satisfied, then the buyer could decide not to make the decision, make the decision but with a lower confidence (i.e., larger 5), request that the vendors to provide larger sample size, as elaborated in the paragraphs following Proposition I and Theorem respectively.
We note that our results, by design, differ from inferential policy where a buyer. upon passively observing oi DDD,, ((D) and their difference v (DD))v(D), tries to infer the difference (PP-T((P)
We believe that in our motivated settings (i.e., data marketplaces), prescriptive policy is more useful, since the buyer can use it to make proactive decisions/actions (e.g.. specifying how much more valuable P than p' to purchase P. requesting larger sample from the vendor), instead of being passive observer (such as in the inferential policy).
Q3.
Why is there hypothetical column player?
The hypothetical column player is used to clearly represent the fact that the buyer (i.e., the row player) does not have prior knowledge about the vendors. Effectively, to the buyer, before having seen bought the vendors' distributions, all vendors are equivalent. Then, in this two-player game formulation, the column player (via its action space of all possible permutations) effective models this fact. The implication is that this finite, two-player zero-sum game can be analyzed without explicitly knowing the payoff matrix R to show that the uniform strategy is indeed worst-case optimal (Proposition 3).
Answer:
Q4.
Can some prior knowledge about the data vendors be used to design better solution than Pu?
Answer: In principle, yes. However, it is yet unclear precisely what form of prior knowledge to consider, and then how to exploit it to design a better solution. One possibility to build on top of the two-player game formulation is to apply a prior belief over the rankings of the vendors in terms of the qualities of their distributions and then try to solve the corresponding game. It thus forms an interesting future direction to explore.
Q5. Is the uniform mixture optimal?
Answer: The uniform strategy is worst-case optimal in the game defined as in Eq. (4), and it inspired our choice of the uniform mixture. possible extension to the infinite game version where the row player searches for some "optimal" over An - 1) (formalized via Eq. (8) and elaborated in
26

---

App. A), but it is faced with additional difficulties, as detailed in the discussion following Eq. (8). It not yet clear whether the uniform mixture would be (a part of) the optimal solution to the more complex infinite game, and thus presents an interesting exploration.
Q6. Given the setting of no ground truth, and no prior knowledge about the data vendors, intuitively it does seem that one cannot do better than the uniform strategy. Then, is there some lower bound (of error) that matches the upper bound of error (e.g., Proposition 2 or Corollary 1)?
Answer: We provide an informal discussion based on two different perspectives (one from the field of robust statistics and the other from mechanism design).
Firstly, in the field of robust statistics, a lower bound of error for some estimation problem is often studied and there is indeed literature specifically studying the Huber model. But the differences in settings make their results not directly applicable, though instructive for us. For instance, [40] derive an anformatiion-thooretii lower bound of eπror for mean estimation using data sampled from a Huber model P- == (1 P + =Q where the lower bound is at least linear in [40, Observation I.4], but does not have a result on the statistical difference between P and Q. Nevertheless, this lower bound seems to already match our upper bound (e.g. Proposition 2) w.r.t. & (i.e., linear). Two key differences in the setting are: (i) we have multiple data vendors where [40] study only one, so we need to additionally consider how to "combine" these data vendors; (ii) the result in [40] is w.r.t. the (2-norm, which is different from MMD (an RKHS norm) though there are similarities that can be used. We expand on how these differences make it difficult to directly apply the results of [20, 40], but also outline an informal sketch of how to adapt their results in App. B.3, which could be an interesting future direction.
Secondly, in the field of mechanism design where some interaction among multiple caattpple"agentt "agents" (i.c.. data vendors in our setting) is typically present, similar result (though in a different flavor from the error bound in robust statistics) is also observed. [36, 37, 44] point out that it is indeed impossible for a mechanism (e.g., a designed data valuation) to guarantee truthfulness if (i) there is no ground truth, and (ii) the data vendors are not assumed to be independent. Here truthfulness is related to the error of a valuation function where the valuation function has error (i.e., we manage to find some Pa s.t. P_, = P*), truthfulness is guaranteed. By the contra- contta--ositive of this impossibility, without making further assumptions (the precise form of which is yet unclear), in our setting, it is impossible to design valuation function that has arbitrarily low error, equivalently to find some Pa with an arbitrarily small MMD to P While this result is not quantitative as the error lower bound from robust statistics, it is useful nevertheless because it applies to setting with multiple data vendors, no prior knowledge about the data vendors and no ground truth.
We hope that our discussion here and our work can generate more interest in exploring these interesting directions (e.g.. to obtain a matching lower bound of error), and that our described framework and proposed method can provide a theoretical basis for such future explorations.
Q7. Instead of Eq. (4), why can't 't an optimizattion/sercch be performed directly over the convex mixture of P, P,'s by assuming that FE" E An - 1) s.t. P... = P
Answer: Suppose that Vi, F 0, Q + P", then it can be shown that any convex mixture of Pi's not P*, because any convex mixture necessarily contains a (mixture) component that is not p (i.e.. Qw in Observation 1). Now, suppose it is relaxed that for some i", P.- P Then the main problem reduces to finding that i' out of n vendors without having prior knowledge about the vendors, which indeed corresponds to the game described by Eq. (4). Similarly, the same game can be generalized to to finding argmin; (P"", , PP)) even if min; d(p., P*) 7 O. Essentially, in both cases (either min; d( (.P.. P*) 0 or min, d(P., P*) o 0), the same described by Eq. (4) can be instantiated for which Proposition 3 is applicable.
Regarding the direct search over Iw* E An 1), an additional discussion that suggests some additional assumptions (with yet unclear precise forms) may be necessary, is included in App. A.4.3.
Q8. (How) can this method be applied if the sample datasets of the vendors have different sizes?
Answer: Yes: Suppose that the sample datasets D,'s have different sizes, then it is possible to use the minimum size mmin of these sample datasets and uniformly randomly select subset Di,sub from each D. of size mmin so that the resulting subsets Di, 's have equal sizes. This is mentioned as an
27

---

implementation detail in Sec. 5 and hence in our experiments, w.l.o.g. we assume that the sample datasets have the same size.
Q9. Is this method still effective if the Huber model is satisfie??
Answer: While our theoretical results are specifie to the Huber model (to exploit the analytic
properties of MMD and Huber, e.g., in Proposition 2), some preliminary empirical results (in App. D) under two specific non- non-Huber settings do demonstrate that our method can remain effective even the Huber model is not satisfied.
Q10.
What are the difficulties of extending the theoretical results beyond the Huber model?
Answer: There are two main difficulties: (1) how to provide a formal treatment of the interactions of multiple vendors? with the Huber model, Observation 1 suggests that the convex mixture is one effective way. (2) how to analyze the effect of heterogeneity on the value of data? with the Huber model, Eq. (2) provides simple yet intuitive way to do so.
Q11. How is the extension "Ours cond." different?
Our method (denoted Ours) focuses on the features of the sample datasets and does not exploit the label information in these datasets. In contrast, some baselines such as (LAVA and CS) do exploit the label information. The extension (denoted Ours cond.) is to demonstrate that proposed MMD-based approach can be extended to also exploit the label information, if available. In essence, while "Ours" uses the MMD between the feature distributions, "Ours cond." uses the MMD between the conditional distributions (i.e., distribution of label conditioned on feature). The implementation details are provided in Sec. 5 and App. D.
Answer:
Q12.
What is the difference between Dust and D
Answer: Dval is included to accommodate some baselines that require it in order enable comparison. We highlight that it is an assumption that these baselines require in their works, and our method does not require D In contrast, Drest used only for the purposes of evaluation so that we can compare different baselines (i.e., valuation methods). Diest is not required to implement our method.
Q13. Why is there a need use a common ground truth Ç and what is the interpretation of being the expected test performance?
Answer: The purpose of Ç is for the evaluation and comparison of multiple methods in Sec. 5. In practice, none of the methods can have a dependence on Ç.
For its purpose of evaluation and comparison, is meant to denote a sensible and interpretable value (i.e., ground truth) for the distributions. A sensible value refers to that the ground-truth value G. for P. should make sense. For instance, data distribution P. with a high e; and high d( (P*, Q.) should not have a high ground-trume truth value Ç. An interpretable value requires Ç to be simple and directly understandable since ( will be used reference, and if it is not interpretable, then it is difficult to draw analysis of the comparison obtained using Ç as the reference.
As such, in our empirical investigation, we implement Ç as the expected test performance which is interpretable since test performance directly informs the user how well the model trained on some data performs, and it is sensible it is adopted by existing methods [25, 57, 72].
D Additional Experimental Settings and Results
D.1 Dataset Licenses and Computational Resources
MNIST [41]: Creative Commons Attribution-She Share Alike 3.0. EMNIST [16]: CCO: Public Domain.
FaMNIST [68]: The MIT License (MIT). CIFAR- 10 and CIFAR-100 [38]: The MIT License (MIT).
CaliH [35]: CCO: Public Domain. KingH [28]: CCO: Public Domain. TON [47]: CCO: Public
Domain. UGR16 [45]: CCO: Public Domain. Credit7 [49]: CCO: Public Domain. Credit31 [3]: CCO:
Public Domain. Census 15, C [48]: CCO: Public Domain.
28

---

Our experiments are run on a server with Intel(R) (c) Gold 6226R CPU @2.90GHz and 4 NVIDIA GeForce RTX 3080's (each with 10 GBs memory). We run our experiments for independent trials to report the average and standard errors.
D.2
Additional Experimental Settings
Table 4 provides an overall summary of the experimental settings.
Table 4: Datasets, used ML models M and n, Ci.
Setting
P
Q
M
n
m4
Ei
Class,
MNIST
EMNIST
CNN
5
10000
(i 1)/n
MNIST
FaMNIST
CNN
10
10000
(i 1)
CIFAR10
CIFARI00
ResNet-18 18
5
10000
(2 1)/n
Credit7
Credit31
LogReg
5000
( 1)
TON
UGR16
LogReg
5
4000
(2 1)/(4n)
Regress.
CaliH
KingH
LR
10
2000
(i 1)/n
1ensus15
Census17
LR
5
4000
(i 1)/n
Additional dataset preprocessing details. For CaliH and KingH, the pre-proeeee pre-processing passing the original (raw) data through a neural network (i.e., feature extractor) with the last layer having 10 units [1, 70]. Hence, the dimensionality after preprocessing is 10.
Credit7 has 7 features while Credit31 has 31 features, so the top 7 principal components are kept for Credit31. TON and UGR16 have the same feature space including features such as packet byte, source and destination IP addresses, but non- non-numerical features such as IP addresses are converted to one-hot encoding.
For TON and UGR16, which share the same feature space containing features such as source and destination IP addresses, packet size, network protocol and etc, adopt the one-hot encoding for non-numerical features (i.e., source and destination IPs, network protocol) and perform standard scaling of the numerical features (i.e., packet size). The dimensionality after preprocessing is 22.
ML model M specification details. For MNIST vs. EMNIST and MNIST vs. FaMNIST, standard 2-layer convoluntional neural network (CNN) adopted. For CIFARIO vs. CIFARIO0, the ResNet-18 [29] is adopted. For both Credit7 vs. Credit31, and TON vs. UGRI6, a standard logistic regression with the corresponding input sizes is adopted. The specific implementation (i.e., source code) is provided in the supplementary material for reference.
Additional implementation details on Ours cond. Different from directly computing MMD between the features, this extension of our method aims to additionally utilize the label information contained within each D; Recall that each single data point in D; is paired feature-label, so this extension aims to exploit such information. Theoretically, MMD is well-defined w.r.t. distributions, be distributions over only the features (i.e., Px) or conditional distributions the labels given need representation for Prix for D,. In
features (i.e., Prjx). For implementation, implementation, we train machine learner M, == M(D;) on D; and use it to construct the empirical representation for Py|x- Given a reference D we collect the set of predictions (denoted as (D.))) of M, on this reference, as the empirical representation of Py Subsequently. we compute the data values, namely negated MMD between (M and, the labels of D (i.e., the columns under p(v, C) in Table 2). Note that the predictions (i.e.. (Dvav)) are probability vectors in the 1-probability simplex A(C 1) for classification with C' classes, or real-values for regression. For MMD computation, a one-hot encoding of the labels in D for classification is performed; no additional processing is required for the labels for regression.
Reproducibility statement. We have included the necessary details to ensure the reproducibility of our theoretical and empirical results. Regarding theoretical results, the full set of assumptions, derivations and proofs for each theoretical result is clearly stated in either the main paper, App. A.
29

---

Regarding experiments: (i) the code to produce the experiments is included in zip file part of the supplementary material. It also contains the code and scripts to process the data used in the experiments. (ii) the processing steps and the licenses of the datasets used in the experiments, and the parameters (e.g., the choice of ML model used) that describe our experimental settings are clearly described in App. D. (iii) The information of the computational resources (i.e., hardware) used in our experiments and a set scalability results for our method are included in App. D.
D.3
Additional Experimental Results
D.3.1
Additional Results for Empirical Convergence
Figs. 3 to 5 demonstrate that our method (i.e., MMD) performs overall the best (converges the most quickly) on TON, CIFARIO and Credit7, respectively. Note that on these three datasets (i.e., CIFARIO, TON and Credit), the baseline LAVA did not complete due to known runtime eтror (see Github issue) of required package OTDD.
CS
CS
0.6
DAVINZ
DAVINZ
# inversions
20
DAVINZ
0.4
LAVA
1. error
LAVA
LAVA
MMD
MMD
MMD
0.2
10
0.2
Ours
Ours
0.0
0.0
0.0
1.0
1.0
0.0
0.5
1.0
Sample size (in pet.)
Sample size (in pct.)
Sample size (in pct.)
Figure 2: The criteria (on y-axis) for P = MNIST vs. Q FaMNIST. 10, m 10, 000 r-axis shows sample size in percentage, i.e., m,/m, where m is fixed to investigate how the criteria change w.r.t. m//m; If the criteria decrease quickly w.r.t. m,/m,. it means the metric converges quickly (i.e., sample-efficiene Averaged over 5 independent trials and the error bars reflect the standard errors.
0.6
CS
CS
6
CS
0.6
DAVINZ
DAVINZ
# Inversions
DAVINZ MMD
0.4
MMD
0.4
MMD?
4
Ours
Ours
0.2
0.2
2
0.0
0.0
0
0.0
0.5
1.0
0.0
0.5
1.0
0.00
0.25
0.50
0.75
1.00
Sample size (in pct.)
Sample size (in pct.)
Sample size (in pct.)
Figure 3: The 3 criteria (on y-axis) for p TON vs. Q UGR16. == 5, m 10, 000. 2-aaxis shows sample size percentage, i.e., m; m where m. is fixed to investigate how the criteria change w.r.t. m./m² If the criteria decrease quickly w.r.t. m²/m², it means the metric converges quickly (i.e., sample-efficient. Averaged over independent trials and the error bars reflect the standard errors.
D.3.2 Experimental Verification of Correlation between True Values vs. Distribution Errors
This experiment serves as preliminary verification on the empirical suitability of our proposed valuation in Eq. (1): Whether/how well do the measured values (i.e., f in Eq. (3)) correlate with the error levels (i.e., d(P, ))? The specific settings are as follows.
1. We consider discrete distributions for P P., Qi. We randomly generate 1-dimensional discrete (not necessarily uniform) distributions supported on the integers in [o, 10). We first generate Pa Then, for each vendor i, we randomly generate another distribution as Q, and also an E Uniform(O, 0.5) (so that the outlier is not overpowering the ground truth) for P. (1 - =. + +e
2. The error level of distribution is measured by P").
30

---

0.8
30
1.00
0.75
CS
error
CS
inversions
20
DAVINZ
DAVINZ
DAVINZ
MMD
0.50
MMD²
MMD
Ours
10
0.25
Ours
0.2
Ours
0.00
0.0
1.0
Sample size (in pct.)
Sample size (in pct.)
Sample size (in pct.)
Figure 4: The 3 criteria (on y-axis) for P CIFARIO Q CIFARIOO. 10, m 10, 000. r-axis shows sample size in percentage, i.c., m,/m", where m is fixed to investigate how the criteria change w.r.t. m If the criteria decrease quickly w.r.t. m it means the metric converges quickly (i.e., sample-efficient Averaged over 5 independent trials and the error bars reflect the standard errors.
1.5
0.8
CS
CS
CS
error
1.0
MMD
DAVINZ
eTTOX
0.6
DAVINZ
MMD?
# inversions
20
MMD²
DAVINZ
Ours
Ours
Ours
0.5
0.0
0.0
0.0
1.0
1.0
1.0
Sample size (in pet.)
Sample size (in pct.)
Sample size (in pct.)
10, m 10, 000. r-axis shows sample size in percentage, i.e., m, m, where m is fixed to investigate how the criteria change w.r.t. m If the criteria decrease quickly w.r.t. m./m;. it means the metric converges quickly (i.e., sample-efficintt). Averaged over 5 independent trials and the error bars reflect the standard errors.
Figure 5: The 3 criteria (on y-axis) for P Credit7 Q Credit31.
3. The MMD computed via the analytic expression in Eq. (6) in App. A, with radial basis function kernel k(x, æ'; ; o) exp( -1xx-=' and
1.
Note that the true value T(P.) d(P,, P*) by definition.
Correlation between obtained values and error levels. In Fig. 6, the high y2 coefficient and p-value (of fitted linear regression) indicate that the valuation scores correlate with and thus can reveal the error levels. Additionally, the more extensive results on up to n = 1000 vendors in App. D.3.2 demonstrate a consistently high Pearson correlation coefficient between the true values (i.e., negated errors) and the measured/approxiimate values.
-0.25
-0.25
Valuatioos
-0.50
Valuations
0.50
Valustions
-0.50
Valustions
-0.30
-1.00
61.8
-1.00
Aua Prappeannce
-1.00
-1.00
Jevels
Ecror levels
Error levels
Figure 6: Valuation score vs. error level distributions for n = (100, 200, 500, 1000) data vendors with randomly generated data distributions. y-axis shows the obtained evaluation (i.e., Eq. (5)), x-axis shows the error level (i.e., d( P:, P*)). Orange line is fitted linear regression, with / coefficient and p-vuuue for the significance of the independent variable (i.e., error levels): all 4 plots show 22 coefficient = 1 and p-value = 0, indicating that the fitted linear regression (valuation regressing on error level) statistically significant.
31

---

Table 5: Pearson correlation (mean and standard error over 10 independent trials) between true values and approximated values.
n vendors
mean
stderr
0.756902
0.132693
10
0.851377
0.044990
20
0.852497
0.041087
100
0.868608
0.021306
200
0.809960
0.030382
500
0.795787
0.042950
1000
0.886822
0.023642
D.3.3 Additional Results for Huber Setting
We present the remaining results for the Huber setting for Credit7/Credit31, MMIISTEMMIIST and MNIST in Tables 6 to 8, respectively. Note that the results for p(v, C) are obtained w.r.t. an available vai ~ P* as the reference. Hence, our method directly uses Dval (since it is equivalent to D' by definition) in Eq. (1) when Dval is available. Our method uses D., (i.e., Eq. (3)) when D is unavailable (i.e., the right columns). We highlight that Ours cond. is not applicable for when Dval is unavailable because the conditional distribution required is not well-defined when the reference (i.e., D is from Huber distribution.
Table Classification:
p Credit7, Q = Credit31.
Baselines
p(v,C)
p(D, ()
LAVA
0.414(0.15)
0.079(0.31)
DAVINZ
0.878(0.06)
0.099(0.15))
CS
-0.813(0.03)
-0.101(0.13)
MMD
0.849(0.03)
0.561(0.06)
Ours
0.848(0.03)
0.604(0.31)
Ours cond.
0.762(0.04)
N.A.
Table 7: Classification: p* MNIST, Q = EMNIST.
Baselines
p(v.C)
p(D,C)
LAVA
-0.543(0.07)
0.685(0.03)
DAVINZ
0.977(0.00)
0.105(0.04)
CS
0.760(0.08)
-0.984(0.00)
2MD
0.931(0.01)
0.970(0.01)
Ours
0,950(0.01)
0.984 (0.01)
Ours cond.
0.971(0.01)
N.A.
Table 8: Classification:
P MNIST, Q FaMNIST.
Baselines
p(v,5)
p(p,C)
LAVA
-0.810(0.06)
0.244(0.09)
DAVINZ
0.864(0.05)
0.113(0.13)
CS
0.314(0.13)
-0.810(0.03)
2MD
0.750(0.05)
0.740(0.05)
Ours
0.747(0.05)
0.739(0.05)
Ours cond.
0.825(0.07)
N.A.
32

---

D.3.4 Results for Non-Huber Setting
We investigate two non-Huber settings: (1) additive Gaussian noise; (2) different supports [69], which is also generalized to an interpolated setting where the interpolation is between the different supports.
Setting. (1) Additive Gaussian noise: Among = 10 vendors, the dataset D, P. == MNIST NO E, x I) where |Da] = m, = 5000 and the E s are [0, 0.02..... 00188. Note that though P MNIST, each P. is not Huber. (2) The supports of P that each vendor can sample from are different: on MNIST, vendor only collects images of digits O, while vendor 10 collects images of all 10 digits (called classimbalance [69]). Intuitively, vendor 10 has access to P its data should be the most valuable. Results. Tables 9 and 10 show that, when Dval ~ P" is available, the methods method. However, without D these methods still underperform our method, especially under additive Gaussian noise. We believe it could be because these methods were not specifically designed to account for heterogeneity (which could be caused by noise), since CS performs comparably well under the class imbalance setting where the heterogeneity is due to the supports of the vendors being different instead of random noise. In particular, we find that all baselines perform sub-optimally under the additive Gaussian noise setting and when there is no clean val available, which can be an interesting future direction. A possible reason is that the Gaussian noise is completely uncorrelated to the features and "destroys" the information in the data, rendering the valuation methods ineffective.
(i.e., DAVINZ, CS) that effectively utilize Dval can outperform
Table 9: Non-Huber: additive Gaussian noise.
Baselines
p(v,C)
p(D.C)
LAVA
-0.255(0.17)
-0.037(0.20)
DAVINZ
0.848(0.02)
-0.410(0.03)
CS
0.902(0.03)
-0.934(0.01)
MMD
-0.085(0.04)
-0.496(0.03)
Ours
0.964(0.01)
-0.16(00.06)
Ours cond.
0.892(0.04)
-0.668(0.06)
Table 10: Non-Huber: classimbalance.
Basclines
p(v,C) () p(B, Ş)
LAVA
0.439(0.26)
0.340(0.34)
DAVINZ
0.807(0.00)
0.081(0.00)
CS
0.985(0.00)
0.871(0.01)
MMD
0.780(0.00)
-0.894(0.00)
Ours
0.923(0.00)
0.557(0.01)
Ours cond.
0.989(0.00)
0.911(0.00)
Interpolated classimbalance setting. In addition to the "discrete" class imbalance setting, also investigate an interpolated setting as follows: For MNIST, n 5, m, 5000, half of D; consists of images of first 2i + 1 digits while the other half consists of images of all 10 digits. E.g.. 2500 of D3 are images of digits of 0 6 while the other 2500 are images of digits of 0 9. Effectively, each Dj contains images of all 10 digits, but in different proportions which increase as i increases from 1 to 5. For CIFAR-10, 10, n 5, m, 10000 with the same interpolation implementation. Results are in Table 11. Note that for the non-Huber setting here, since the heterogeneity is only in the supports of the data (i.e., features) and not the labels, the conditional distribution for Ours cond. is indeed well-defined and thus Ours cond. applicable here. This different from the Huber setting examined in Sec. 5.
D.3.5 Preliminary Experimental Results on Incentive Compatibility
We empirically demonstrate that mis-reporting decreases vendor's value, suggesting that IC can be satisfied (approximately), hypothesized in App. A.4.3.
33

---

Table 11: Interpolated glass-imbalance setting on MNIST (left) and CIFAR-10 10 (right).
Baselines
p(v; ()
p(D, ()
Baselines
p(v,
p(e,
LAVA
0.459(0.24)
0.195(0.26)
LAVA
0.790(0.06)
0.679(0.09)
DAVINZ
0.962(0.01)
0.706(0.04)
DAVINZ
0.498(0.25)
0.495(0.28)
CS
0.977(0.00)
0.952(0.02)
CS
0.974(0.01)
0.983(0.01)
MMD
0.839(0.05)
-0.969(0.01)
MMD
0.472(0.25)
0.285(0.03)
Ours
0.939 (0.02)
0.770(0.04)
Ours
0.931(0.11)
0.332(0.02)
Ours cond.
0.859(0.03) 0.857(0.05)
Ours cond.
0.846(0.04)
0.905(0.04)
Settings. Vendor i' E N is designated to mis-report: D. + D. + (0, llo2) for o² = 0.2, namely, vendor adds zero-mean Gaussian noise to the features of the data in Dz. This ensures d(Pr, P*) > d(Pr,. P*). For evaluation, we compute the data values (i) using Eq. (1) with a test set D P as the reference, denoted the ground truth (GT); (ii) using Eq. (3) (i.e., Ours) and Tay et al. [60, Eq. (1)) (i.e,, MMD²), respectively, with D. as the reference. We include MMD to investigate how the square affects IC (since IC of Ours can leverage the the triangle inequality of MMD that is not satisfied by MMD*).
Corresponding to the ideal case discussed in App. A.4.3, using D can achieve approximate-IC with desirable 7, In other words, GT is likely to correctly reflect the values of the vendors (including the mis-reporting i'). Hence, for Ours and MMD², if the data values are consistent with GT, that suggests that (approximate) IC is more likely to be achieved.
Results. Fig. 7 (resp. Fig. 8) plots the average and standard error over 5 independent trials of (resp.
the change data values of the n mis-reporting vendor i' E {2, 3, 4). Specifically, the change in data value (i.e., y-axis) is defined as the difference between the value of i when some i' (possibly for when no vendor is mis-reporting. IC implies a negative change (i.e., decrease) in value for the mis-reporting i', which is observed for GT, Ours, and MMD both Figs. 7 and 8.
10) vendors as we sweep the identity of the
i) is mis-reporting. and that of i
Note that the magnitude of the decrease for mis-reporting vendor i' under Ours is more significant than that under MMD hence it may be easier to identify the mis-reporting vendor from the truthful ones. This happens because the MMD is bounded by (due to the choice of RBF kernel), and the square operation makes the value for MMD2 strictly smaller in magnitude than that for MMD (i.e.. Ours), as Vz E (0, 1), x² < x. Therefore, MMD may be empirically more appealing than MMD
Change data value
Change dasta value
-0.0002
-0.0005
-0.0004
-0.0015
MMD?
MMD
Ours
-0.0020
Qurs
2.5
5.0
2.5
5.0
2.5
5.0
10
10
10
Vendor
Veador
Vendor
Vendor /
Vendor f
Vendor f
Figure 7: Change in data values for PANIIT and QEMNIST with n 5.
Figure 8: Change in data values for PANISTT and QraMNIST with n = 10.
Additional results for investigating incentive compatibility under varying settings of P, Q and presented, in Figs. and 10 and Tables 12 to 15.
Figs. 9 and 10 verify the observation that the mis-reporting vendor i' has negative change (i.c., decrease) in value. Moreover, the magnitude the decrease in value is more significant for Ours than that for MMD". The additional set of quantitative result (i.c., the Pearson correlation coefficient between the GT data values and Ours or MMD") also confirms this observation. To elaborate, take the value corresponding i' and 2MD in Table 12 example. The Pearson coefficient (i.e.,
The standard error bars visible because of the low variation across independent trials.
34

---

0.999) is between the GT data values (i.e., a vector of length n 5) and the MMD² data values (i.e.. a vector of length n 5), under the setting that i' 2 mis-reporting The results in Tables 12 15 show that the data values of both Ours and MMD are very consistent with the GT values, importantly without having D P as the reference, thus suggesting that (approximate) IC is achievable. However, caveat is that both methods are not very effective in achieving IC when i' = 1. This is precisely because Dw, ~ Pw is used as the reference place of D P as for GT, and expected (since the discussion in App. A.4.3 suggests that the worse approximate-IC for P.). Specifically, IC is empirically observed when d(P-i, P*) is small. When = 1, this not satisfied, other words di d(P-i, P*) would be large. This is because, i' = 1 is the "best" vendor in experiment settings in that Pv=1 P (i.e., = = 0). Hence, 1' = mis-reports, the remaining vendors in N \ {t') are unable catch i' = 1 because the aggregate distribution P_p P-1 1 is not very good reference (as compared to P- for i' * is mis-reporting). Intuitively, i = is not mis-reporting (i.e., 1' * 1), then P_y contains the data from Pi P*, and is thus good reference.
Overall, these empirical results suggest a promising future direction of achieving (approximate) IC, by choosing suitable metric (e.g., MMD) against carefully constructed reference (e.g., Pt).
0.0000
0,0000
Change in data valtic
Change data value
-0.0002
-0.0005
-0.0010
-0.0006
-0.0008
GI
-0.0015
GI
MMD
MMD
-0.0010
Ours
-0.0020
Ours
5
10
10
10
2.5
5.0
2.5
5.0
2.5
5.0
Vendori
Vendar i
Vendor
Vendor
Vendor i
Ventor i
Figure 9: Change in data values for PANIST and QEMNIST with n = 10.
Figure 10: Change in data values for PANIST and QFAMNIST with n 5.
Table 12: Average and standard error (over 5 independent trials) Pearson coefficients with GT for PANIST and QEMNIST with 5, rows i' = 2, 4 corresponding to Fig. 7.
i'
MMD 2
Ours
1
0.485 (0.03)
0.476 (0.03)
2
0.999 (0.00)
0.999 (0.00)
3
1.000 (0.00)
1.000 (0.00)
4
1.000 (0.00)
1.000 (0.00)
5
1,000 (0.00)
1,000 (0.00)
Table 13: Average and standard error (over 5 independent trials) of Pearson coefficients with GT for PANIST and QFAMNIST with rows i' 2, 4 corresponding to Fig. 10.
1'
MMD
Ours
0
0.515 (0.01)
0.506 (0.01)
1
1.000 (0.00)
1.000 (0.00)
2
0.999 (0.00)
0.999 (0.00)
3
0.999 (0.00)
0.999 (0.00)
4
0.997 (0.00)
0.998 (0.00)
D.4 Observed Linear Scaling w.r.t. and m
We demonstrate the scalability of our method w.r.t. the number n of vendors and the sample size m. in terms of execution time and memory (RAM and GPU).
Plots showing linear scaling. Fig. 11 observes linear scaling between time vs. m, (top left), time vs. n (bottom left), RAM vs. m, (top right) and RAM vs. n (bottom right). Crucially, this helps ensure the practical applicability of our method in terms of implementation and execution.
35

---

Table 14: Average and standard error (over 5 independent trials) of Pearson coefficients with GT for PANIST and FENNIST with n 10, rows i' 2, 3, corresponding to Fig. 9.
MMD
Ours
0
0.386 (0.01) 0.383 (0.01)
1
0.997 (0.00)
0.997 (0.00)
2
0.997 (0.00)
0.997 (0.00)
3
0.999 (0.00)
0.999 (0.00)
4
0.998 (0.00)
0.998 (0.00)
5
0,998 (0.00)
0.998 (0.00)
6
0.999 (0.00)
0.999 (0.00)
7
0.999 (0.00)
0.999 (0.00)
8
0.998 (0.00)
0.998 (0.00)
9
0.993 (0.00)
0.994 (0.00)
Table 15: Average and standard error (over 5 independent trials) of Pearson coefficients with GT for PANIIT and QEANNIST with n 10, rows i' 2, 3, corresponding to Fig.
MMD?
Ours
0.364 (0.01)
0.362 (0.01)
0.999 (0.00)
0.999 (0.00)
0.997 (0.00)
0.997 (0.00)
0.999 (0.00)
0.998 (0.00)
0.998 (0.00)
0.998 (0.00)
0.995 (0.00)
0.995 (0.00)
7
0.996 (0.00)
0.995 (0.00)
0.954 (0.01)
0.950
0.852 (0.06)
0.858 (0.05)
10
0.997 (0.00)
0.998 (0.00)
25000
MNIST CIFAR10
CPU time (seconds)
100
RAM (MBs)
20000
15000
40
10000
20
10000
20000
30000
40000 50000
10000
20000
30000
40000 50000
14000
MNIST
CPU time (seconds)
CIFARI0
50
12000
RAM (MBs)
10000
8000
30
Figure 11: Top: time and peak memory vs. m. at n = 30; Bottom: time and peak memory vs. n at 10000. MNIST CIFAR10 denotes the dataset used.
RAM, CUDA and CPU time results. We include the detailed results for RAM, CUDA, and time on MNIST (Tables 19 to 21) and CIFARIO (Tables 16 to 18), respectively.
36

---

Table 16: CUDA Memory in MBs for CIFARIO.
m4' \n
10
20
30
40
50
3000
140.598272
182.904320
222.904320
264.693248
304.847360
5000
141.556736
182.904320
222.904320
264.693248
304.847360
7000
143.563776
182.904320
222.904320
264.693248
304.847360
9000
144.983040
182.904320
222.904320
264.693248
304.847360
10000
145.862144
182.904320
222.904320
264.693248
304.847360
15000
150.258176
182.904320
222.904320
264.693248
304.847360
20000
155.048960
182.904320
222.904320
264.693248
304.847360
30000
164.999168
189.000192
222.904320
264.693248
304.847360
40000
173. 798400
205.969920
238.375936
271,930368
304.847360
50000
182.904320
222.904320
264.693248
304.847360
346.482176
Table 17: RAM in MBs for CIFAR10.
m,y AN
20
30
50
3000
7726.480469
8022.24211 242..4215 88
8602.214844
8813.792969
9256.371094
5000
8036.699215
8683. 101562
9489.097656
10134.582031
10780.066406
7000
8318.515625
1469.835934
10239.902344
11060.789062
11963.085938
9000
8628. 9609996
9815.738281
11016.425781
12092.296875
13129.046875
10000
8945.777344
10132.257812
11306.15622
12478.398438
13650.953125
15000
9444.472656
11187.527344
13286.566406
14993.
16758.398488
20000
10058. 050781
12478. 628906
45021.53325
17166. 140625
19696.039062
30000
11374.
75336.773338
18574.199219
22034.144531
25492.12109
40000
12545. 460934
17267.83205
21975.371094
26613.242188
31401
50000
13877 929688
19598.089844
25435.593750
31254.929688
$7299.406235
Table 18: CPU time in seconds for CIFAR1O.
m44 N
10
20
30
40
50
3000
40.075573
33.853308
36.099317
36.748012
38.443388
5000
32.896979
35.561858
38.386079
41.070452
44.552341
7000
34.791889
38.024787
42.796535
45.675799
50.420825
9000
37.090735
40.622674
45.164939
50.043854
55.225169
10000
36.123430
41.834278
47.907592
52.253957
57.867871
15000
38.382908
47.813846
56.015236
63.631425
72.990464
20000
42.548813
54.514572
65.067422
76.599092
89.003306
30000
46.957031
65. 156033
80.534339
97.402354
116.374963
40000
52.663162
76.029116
97.542482
120.323142
144.956402
50000
59.434006
89.602017
114.438738
146.690117
173.507339
Scalability comparison against DAVINZ. The implementation DAVINZ. also includes an MMD computation (similar to our proposed method), but additionally linearly combined with a the neural tangent kernel (NTK)-based score. While in some cases (c.g.. Table 3), DAVINZ and our proposed method perform comparably, highlight that our method is more scalable. The main reason is that the gradient computation from NTK DAVINZ requires additional memory, specifically CUDA memory due to leveraging GPU for gradient computation. See Table 22 for scalability experiment for DAVINZ with n = 10 on MNIST with standard convolutional neural network used for all MNIST-related experiments in this work.
contrast, under the same setting of n. method requires less than 0.1 GBs of CUDA memory (see the fifth row, first column of Table 19, Note that we were not able collect results for DAVINZ on more extensive settings due to hardware limitations (i.c., larger values for and Ieads to out-of-memory errors standard GPUs with
data vendors each with m, = 10000 samples, our
37

---

Table 19: CUDA memory for MNIST.
m, AN
10
20
30
40
50
3000
95.339008
138.832384
178.832384
220.621312
260.775424
5000
97.097728
138.832384
178.832384
220.621312
260.775424
7000
98.855936
138.832384
178.832384
220.621312
260.775424
9000
101.214720
138.832384
178.832384
220.621312
260.775424
10000
101.693952
138.832384
178.832384
220.621312
260.775424
15000
105.895936
138.83238
178.832384
220.621312
260.775424
20000
110.686720
138.832384
178.832384
220.621312
260.775424
30000
119.679488
143.097856
178.832384
220.621312
260.775424
40000
130.443776
162.443776
195.455488
227.238400
260.775424
50000
138. 832383
178.832384
220.621312
260.775424
302.410240
Table 20: RAM MBs for MNIST.
m4 A
10
20
30
40
50
3000
6077.753906
6148.613281
6204.640625
6332.785156
6478.375000
5000
6093.554688
6284.605469
6517.027344
6718.703125
6934.570312
7000
6122.351562
6535.925781
4628.468750
7151.273438
7438.753900
9000
6206.800781
6694.765625
7148,257812
7543.253906
7876.445312
10000
6414.144531
6872.023438
164062
7676.304688
8080.292969
15000
6665.367188 88
7210.253906
78801492188
8484.84375)
9024.613281
20000
6867.117188
7651.234375
8402.281250
9231.203122
9992.460938
30000
7205.328125
8409.937500
9653.914062
10725.601562
11970.367188
40000
7559.824219
9132.652344
10764.582031
12254.757812
13927.617188
50000
8096.402344
9891.027344
12040.925781
13953.308594
15842.777344
Table 21: CPU time in seconds for MNIST.
my \
10
20
30
40
50
3000
45.675888
23.173012
24.010044
24.685510
25.532540
5000
22.843993
24.338142
26.162306
27.275437
28.386587
7000
23.884181
25.619524
27.735549
29.385311
31.042997
9000
23.949323
26.902086
29.450777
31.600939
33.862759
10000
24.259586
27.199071
30.215128
32.577134
35.111519
15000
28.153503
30.075059
34.379974
38.391948
42.446352
20000
27.595278
34.082700
39.362670
46.231271
49.121318
30000
30.255474
38.232212
46.626252
54.726982
63.040075
40000
33.875198
44.688145
56.146300
66.236627
77.427208
50000
35.978749
50.792472
63.822176
77.274825
92.584505
10 GBs of memory and the official implementation [67, Github repo] does not implement a way to take advantage of multiple GPUs (if available) distribute the CUDA memory load.
38

---

Table 22: Maximum CUDA, RAM and time for DAVINZ with a standard convolutional neural network.
10 data vendors MNIST with
m;
maximum CUDA (in MBs)
RAM (in MBs)
CPU time (in seconds)
3000
4885.189
5201.132
50.419
5000
4885.189
6840.75
44.173
7000
4885. 189
6843.371
46,229
9000
4885.180 189
6836.921
51,436
10000
5523.673
6843.773
50.491
15000
5523.673
6926.535
56.739
20000
7118.552
7358.736 7334
68.144
30000
7118.552
8331.660
86.353
40000
7323.634
9154.773
107.132
50000
7323.634
10053,316
132.206
39

---

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: The contributions are summarized at the end of Sec. with direct references to the relevant theoretical and/or empirical results as support.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Our theoretical results require the Huber model assumption. We have also empirically investigated some non-Huber settings App. D.3.4 where our proposed method remains effective.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The derivations and proof' all the results including the main results in the main text and auxiliary/intermdiite results, are included in App. A.
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 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 proofs provided 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 reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
We provide the experimental settings in detail (in main text and in App. D and specifically include a reproducibility statement in App. D as a summary to help guide the reader find the necessary information.
Justification:
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code to reproduce the experiments included the supplementary material. The links all the used data are also included in the supplementary material.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
40

---

Answer: [Yes]
Justification: We include the details for experimental settings in Sec. 5 and additional details in App. D.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: For all results which are possibly the outcome of stochastic function, we report (i.e., either tabulate plot) the average and standard errors of multiple (e.g., least 5) independent trials.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
The compute resources used in the experiments are described in App. D. We have also investigated the computational scalability (in terms of both time and memory) of our proposed method App. (c.g., Fig. 11).
Justification:
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https http://eurrrri.cceco wttpiippp.cpppppppt http://p....ppbli/ccaiiiaeeeeeaa
Answer: [Yes]
Justification: We have taken care to ensure that our conducted research in this paper conforms, in every aspect, with the NeurIPS Code of Ethics.
Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This paper presents work whose goal is to advance the field machine learning, specifically by focusing on the value of data (distribution) for the machine learning from a statistical perspective. One possible societal impact is that our work implicitly rewards data that is similar other vendors. This could implicitly penalize vendors providing data describing marginalized populations. Studying the faimesss of our data valuation method is an interesting direction for future work.
11. Safeguards
Does the paper describe 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].
We do not the studied problem the proposed solution to pose such risks as we do not release a model or data (the models and data we used our experiments are standard and/or open-source implementations).
Justification:
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Included in App. D.
13. New Assets
41

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification: No new assests are introduced.
14. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA].
Justification: No human subjects were involved.
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: The paper does not involve crowdsourcing, nor research with human subjects.
42


Reviews:
[{"review_id": "TydgievYYu", "reviewer": "Reviewer_YGYg", "summary": "This paper addresses the problem of data distribution valuation in data markets, where buyers need to evaluate the quality of data distributions to make informed purchasing decisions. The authors formulate the problem and identify three technical challenges: heterogeneity modeling, defining the value of a sampling distribution, and choosing a reference data distribution. They make three key design choices: assuming a Huber model for data heterogeneity, using negative maximum mean discrepancy (MMD) as the value metric, and considering a class of convex mixtures of vendor distributions as the reference. The paper derives an error guarantee and comparison policy for the proposed method and demonstrates its effectiveness on real-world classification and regression tasks. Overall, this work provides a novel framework for data distribution valuation, enabling buyers to make informed decisions in data markets.", "questions": "See above.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a novel approach to data valuation by focusing on the value of the underlying data distribution from a small sample. This addresses a gap in existing methods, which typically do not formalize the value of sampling distributions or provide actionable policies for comparing them.\n\n\n2. The paper employs a Huber model to capture data heterogeneity and utilizes the maximum mean discrepancy (MMD) for evaluating sampling distributions. This combination allows for precise, theoretically grounded comparisons of data distributions and allows for sample efficient assessment of the valuation. Assuming a convex combination of the distribution as the reference they provide an error guarantee without making the common assumption of knowing the reference distribution.\n\n\n3. The authors validate their method through real-world classification and regression tasks. The demonstrated sample efficiency and effectiveness of their MMD-based valuation method, particularly its superior performance in most classification settings compared to existing metrics highlights the practical relevance and robustness of their approach.", "weaknesses": "1. Based on Theorem 1 the valuation of $D$ boils down to the samples available from it and the averaged out heterogeneity $d(Q_\\omega, P^*)$. In practice, a small sample that looks cleaner could be preferred over a bigger but noisy sample. It looks like the current results do not account for individual noise (heterogeneity), I see it in the Huber model but the theoretical results are averaging out as in Observation 1. \n\n2. The sample complexity of $O(\\frac{1}{\\sqrt{m}})$ to estimate MMD, might even be sufficient for the learning task at hand, so why would vendors be willing to show such a big sample of the dataset and by seeing samples from each vendor won’t one be able to accomplish the learning objective without even selecting a vendor and buying a larger sample from them.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer YGYg for reviewing our paper, and for appreciating the novelty of our approach and acknowledging our theoretical and empirical results.\n\nWe would like to respond to the feedback and comments as follows,\n\n> Based on Theorem 1 the valuation of $D$ boils down to the samples available from it and the averaged out heterogeneity $d(Q_\\omega, P^*)$. In practice, a small sample that looks cleaner could be preferred over a bigger but noisy sample. It looks like the current results do not account for individual noise (heterogeneity), I see it in the Huber model but the theoretical results are averaging out as in Observation 1.\n\nWe point out that our definition (Equation 1) enables a precise characterization of the individual noise (w.r.t. $\\epsilon_i, Q_i$) as in Equation 2 and in lines 190-196. Nevertheless, we acknowledge that our method leveraging the \"averaging\" and Observation 1 is not guaranteed to precisely identify the individual noise (e.g., by directly obtaining $\\epsilon_i, Q_i$). We wish to highlight that this may be theoretically difficult to do (i.e., precisely and quantitatively identifying the individual noise), because we do _not_ make the assumption of knowing the reference distribution (as recognized by the reviewer). Intuitively, without knowing what the ground truth is (i.e., the reference distribution), one cannot reliably identify the individual noise, because it is difficult to distinguish noise from signal. We provide a more technical elaboration on this perspective and highlight the theoretical difficulties in Appendix C (see Q6 in lines 1054-1087) with corroborating observations and results from other fields (i.e., robust statistics and mechanism design). Informally, our discussion implies that additional assumptions are needed in order to identify, account for or manage individual noise precisely and quantitatively, so exploring the exact form of such assumptions and the methods to do so is an important future direction (in Appendix B.3 in lines 951-977 and also in Appendix C in lines 1084-1087).\n\n> The sample complexity of $\\mathcal{O}(1/\\sqrt{m})$ to estimate MMD, might even be sufficient for the learning task at hand, so why would vendors be willing to show such a big sample of the dataset and by seeing samples from each vendor won’t one be able to accomplish the learning objective without even selecting a vendor and buying a larger sample from them.\n\nThe vendors may _not_ need to show a big sample of the dataset. As an example, the actual data need not be disclosed (in plaintext) by utilizing cryptographic approaches, such as computing MMD in a trusted execution environment (TEE). This provides a verifiable computed MMD _without_ disclosing the data. To expand on this, the vendors may each provide a relatively small public preview sample (e.g., a few hundred data points) and the interested buyers can request a \"quotation\" computed from a much larger sample dataset from the vendor in a cryptographically secure way: (i) buyer does not see the dataset; (ii) buyer can verify that the computation is correct. We note that our work aims to provide the theoretical foundations for an MMD-based data valuation, so the design for such cryptographic computations is beyond the scope of our current work.\n\nTo a prospective buyer, the computed MMD (e.g., in a TEE) with the sample size, can provide useful information to gauge the error margin for estimating the value of the data, using the sample complexity results as a guideline. Concretely, suppose that vendor $i$'s value is estimated to be $0.8$ with an error margin of $0.2$ while vendor $j$'s value is estimated to be $0.7$ with an error margin of $0.05$ because vendor $j$ supplied a larger sample. A risk-averse buyer (who cares about the worst-case scenario) may pick vendor $j$ over $i$ since the lower bound of the value for $j$ is $0.7-0.05=0.65$, greater than that ($0.8-0.2=0.6$) for vendor $i$.\n\nThat being said, in many operational data marketplaces and suppliers (e.g., Datarade, Snowflake, or the Bloomberg terminal), their business models may already account for this possible scenario and factor it into their pricing mechanism, since after all, not every buyer who expresses interest in the preview sample would eventually purchase the product (i.e., data distribution). We think that the buyers who end up purchasing the data would have stricter error requirements than what the preview sample can meet. We will incorporate the above discussion in our revision.\n\nWe thank Reviewer YGYg for the detailed feedback and hope that we have addressed your comments and improved your opinion of our work.", "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": "e0j8RGgpil", "reviewer": "Reviewer_s86g", "summary": "The valuation of data is crucial in data marketplaces. Instead of assessing the value of a specific dataset, this paper focuses on the valuation of data distribution behind the dataset itself. For example, several vendors are trying to sell different or even the same datasets, what is the best distribution to purchase when we only observe a sampled dataset? The authors model the problem of data distribution valuation and use the MMD-based method as a metric to evaluate the valuation. They provide theoretically guaranteed policies for buyers to take action and empirically demonstrate it using real-world datasets. The results indicate that the method is sample-efficient and outperforms other valuation metrics.", "questions": "1. The method used to sample from a distribution to construct a dataset can affect its valuation. Are there any empirical results or methods to overcome sampling bias?\n2. How does the accuracy of valuation change when a large number of vendors contribute to the mixed reference distribution? Also, does the valuation score reveal the relative level of two distributions or their absolute values?\n3. In Equation 1, what is the reason for giving the value function a negative term instead of taking the reciprocal?", "limitations": "I didn't see any potential negative societal impact of their work.", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* Originality: This paper is interesting as it evaluates the distribution behind a sampled dataset rather than the dataset itself. This approach is new and can be valuable when dealing with partially sampled datasets.\n* Quality: The results seem promising and support the use of MMD-based metrics for assessing data distribution.\n* Clarity: The writing and formulation are clear and easy to understand.\n* Significance: In data marketplaces, most data is only available for preview and is often sampled. Understanding the value of data distribution is beneficial for the field and users.", "weaknesses": "1. The paper's motivation is interesting and contributes to the field. However, I believe there is a missing experiment regarding ranking different error levels of distributions. Suppose we have five distributions ranging from 100% correct to 0% correct. Can the valuation score accurately rank these distributions or reveal their actual error levels? This experiment differs from directly comparing the valuation of the dataset itself. We should see a regression line, where the x-axis is the error level of distribution, while the y-axis is the valuation score.\n2. Why do the correlation scores drop when we move the dataset from CIFAR10 to CIFAR100? The description about this is not clear to me. More clarification on this will be helpful.\n3. The method of sampling from a distribution to create a dataset can influence its evaluation. Have there been any empirical findings or methods to address sampling bias? This missing experiment can justify the robustness of the valuation function.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer s86g for reviewing our paper, and for the positive feedback on the novelty of our approach, the quality of our methodology and solution, the clarity of our writing and significance of our work.\n\nWe wish to provide the following clarifications. The requested experimental results (and detailed settings) are in `response.pdf` in the global comment.\n\n> ... We should see a regression line, where the x-axis is the error level of distribution, while the y-axis is the valuation score.\n\nFigure 11 in `response.pdf` shows a relatively clear negative correlation.\n\n> Can the valuation score accurately rank these distributions or reveal their actual error levels?\"\n\nThe high $r^2$ coefficient and the $p$-value (of a fitted linear regression) indicate that the valuation scores correlate with and thus can reveal the error levels. Table 22 in `response.pdf` shows more extensive and quantitative results. \n\nRegarding settings, we follow the reviewer's suggestions as closely as possible:\n- We consider up to $1000$ vendors for generalizability. \n- The error level is by $d(P_i,P^*)$ where a low (resp. high) MMD means a low (resp. high) error, instead of the percentage-type error levels since it is not precisely defined for a distribution to be 60\\% correct. Also, our main paper (e.g., Table 2) already shows a high correlation between valuation score and machine learning accuracy.\n- We obtain the value from distributions directly, using discrete distributions and an analytic expression of MMD (from lines 547-575). This is in general not possible due to not knowing the exact analytic pdfs of data distributions (e.g., MNIST).\n\n> Why do the correlation scores drop when we move the dataset from CIFAR10 to CIFAR100? The description about this is not clear to me. More clarification on this will be helpful.\n\nWe clarify that the first two columns of Table 2 are _not_ showing results of \"moving from CIFAR10 to CIFAR100\". In our setting for Table 2, CIFAR10 is designated as $P^*$ and CIFAR100 is designated as $Q$ (lines 311-315, or Table 4 in Appendix D.2). The first (resp. second) column of Table 2 shows the correlation when a clean hold-out validation set $D_{\\text{val}}\\sim P^*$ is available (resp. unavailable). The results (Tables 2 & 3) show that the effectiveness of a valuation metric decreases without $D_{\\text{val}}$. Importantly, Ours (and MMD$^2$) experience a smaller decrease/\"drop\" and are thus preferrable in practice where $D_{\\text{val}}$ is unavailable.\n\n> The method used to sample from a distribution ... can affect its valuation. Are there any empirical results ... to overcome sampling bias?\n\nFor a fixed distribution, different sampling methods yield different sampled datasets, and thus different valuations. This is an expected and correct behavior, and in particular, the \"negative\" sampling bias can be mitigated by our proposed valuation.\n\nA \"positive\" sampling bias is when a data vendor, using knowlegde of $P^*$, to prioritize the sampling from $P^*$ in their $D_i$. This will result in a higher valuation. It is a correct behavior as $D_i$ contains more information about $P^*$ (i.e., the ground truth). A \"negative\" sampling bias is when the vendor performs sampling in a way that \"moves away\" from $P^*$ (e.g., injecting noise), then this will result in a lower valuation, as $D_i$ contains less information about $P^*$.\n\nIn practice, the positive bias is rare due to not knowing $P^*$. However, the negative bias is possible, can deteriorate the quality of the data and should be discouraged. This is precisely formalized via the so-called incentive compatibility (from mechanism design), which we investigate w.r.t. our valuation, both theoretically (Appendix A.4.3, lines 764-795) and empirically (Appendix D.3.4, lines 1235-1281). In particular, the empirical results (e.g., Table 6) verify that a vendor who injects such a negative bias by misreporting (noisy data) receives a lower valuation, demonstrating that the negative sampling bias can be mitigated.\n\n> How does the accuracy of valuation change when a large number of vendors ... ?\n\nTable 22 shows that the accuracy of valuation (measured as the Pearson correlation between obtained values and the unknown true values) remains high for up to $1000$ data vendors.\n\n> Also, does the valuation score reveal the relative level of two distributions or their absolute values?\n\nThe valuation score reveals a relative level. It can be combined with additional transformations (e.g., translation): Let $d(P_i,P^*)=0.1$, $d(P_j,P^*)=0.2$, so their values are $\\Upsilon(P_i) = -0.1$ and $\\Upsilon(P_j)=-0.2$. To obtain non-negative values, we can linearly translate by $+1$ gives $\\Upsilon(P_i)+1 = -0.1+1 = 0.9$ and $\\Upsilon(P_j)+1=-0.2+1=0.8$. Note the absolute value of MMD is bounded by the upper bound $K$ of the kernel $k$ (e.g., $K=1$ for the RBF kernel), so a translation by $+K$ ensures that all values are non-negative. While additional transformations are possible (e.g., positive scaling after translation), the transformed values should be interpreted in the specific use case that motivates the transformation.\n\n> In Equation 1, what is the reason for giving the value function a negative term instead of taking the reciprocal?\n\nTaking the negation has theoretical and practical reasons. Theoretically, it (i) preserves the triangle inequality of MMD (e.g., used in Prop. 1), and (ii) enables the precise characterization of heterogeneity in Equation 2 (lines 191-194). Practically, (i) the uniform convergence of the MMD estimator (Lemma 1 in Appendix A.2) continues to apply (which may not for the reciprocal), making the value easy to estimate, while (ii) taking the reciprocal may lead to complications (e.g., division-by-zero errors).\n\nWe thank Reviewer s86g for the comments and questions, and will incorporate the discussion and additional results in our revision. We hope that our response has clarified your questions and helped raise your opinion of our work.", "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": "c0IReKKT1q", "reviewer": "Reviewer_Sj3P", "summary": "This paper starts by highlighting the importance of accurately assessing the value of data distributions, especially in the growing data economy. To address the problem, this paper introduces a data distribution valuation method based on Maximum Mean Discrepancy (MMD) for comparing the value of data distributions from samples. This paper assumes that each vendor $i$ holds a distribution $P_i$ which follows a Huber model, and is a mixture of ground truth distribution $P^*$ and arbitrary distribution $Q_i$. Based on this assumption, the authors discuss the theoretical foundations and assumptions, providing detailed proofs and derivations for the proposed methods. The study addresses heterogeneity in data distributions and the challenges of combining multiple data vendors' datasets. Experimental results demonstrate the sample efficiency and effectiveness of the proposed methods in ranking data distributions.", "questions": "1.\tIn real-world scenarios, data distributions often encompass various complex heterogeneity factors that the Huber model may not accurately capture. Data collected from different sources often exhibit significant variability and may not follow the same distribution.\n\n2.\tThe experiment in the article for ranking data distributions involves mixing two similar datasets, which fails to adequately represent the heterogeneity between datasets provided by different vendors, thus affecting the generalizability of the results.\n\n3.\tIn real-world scenarios, some vendors may provide data samples that do not accurately reflect their true data distribution. Some malicious vendors might even forge samples (for example, using some real data as samples while the rest of dataset is synthetic or useless data). The article does not take this into account.", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThis paper provides a detailed explanation of the theoretical foundations for the valuation of data distributions, including assumptions and proofs, ensuring the rigor and completeness of the theory.\n\n2.\tThis paper studies a meaningful problem: how to compare the values of data distributions from their samples, which can help evaluate the value of data provided by different vendors.\n\n3.\tThis paper is well-organized and easy to follow. The paper introduces a novel method based on maximum mean discrepancy (MMD) for data distribution valuation, offering a fresh perspective in the field.", "weaknesses": "1.\tThis paper relies on certain assumptions, such as the Huber model of data heterogeneity, which may not always hold in real-world scenarios.\n\n2.\tThe experiment for ranking data distributions lacks generalizability.\n\n3.\tUsing data samples to represent data distribution can cause issues, such as dealing with malicious data vendors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer Sj3P for reviewing our paper, and appreciating the theoretical rigor of our work, the meaningfulness of our studied problem and the novelty and fresh perspective of our method.\n\nWe would like to address the comments and feedback as follows.\n\n> This paper relies on certain assumptions, such as the Huber model of data heterogeneity, which may not always hold in real-world scenarios. In real-world scenarios, data distributions often encompass various complex heterogeneity factors that the Huber model may not accurately capture. Data collected from different sources often exhibit significant variability and may not follow the same distribution.\n\nWe acknowledge that the assumption on the Huber model presents a theoretical limitation (line 404), and we have investigated settings where the Huber model is _not_ satisfied (i.e., additive Gaussian noise, and a class imbalance setting) where our method continues to perform well, and this is mentioned in Section 3 (lines 138-139) and Section 6 (lines 405-406). These results are deferred to the Appendix D.3.3 due to page constraints. In particular, the class imbalance setting represents the observation that \"Data collected from different sources often exhibit significant variability and may not follow the same distribution.\"\n\nNevertheless, we wish to point out that this assumption of Huber model is to ensure the theoretical tractability of analysis (e.g., Proposition 1, Equation 2), which has not been explored previously in the sense that prior works have not considered a precise form of data distribution or characterization of data heterogeneity (elaborated in Appendix B.3 in lines 909-930). Additionally, we discuss the considerations of extending beyond the Huber model (lines 1110-1114) and the opportunities for future research.\n\n> The experiment for ranking data distributions lacks generalizability. The experiment in the article for ranking data distributions involves mixing two similar datasets, which fails to adequately represent the heterogeneity between datasets provided by different vendors, thus affecting the generalizability of the results.\n\nIn our main paper, the settings for the empirical results follow the Huber model, to verify our theoretical results and method that are based on the Huber model. We acknowledge that a single formalization of data heterogeneity cannot generalize to all settings (lines 58-60), so we have also performed experiments under _non-Huber_ settings in Appendix D.3.3. To elaborate, we investigate two specific non-Huber settings for data heterogeneity: (1) with additive Gaussian noise and (2) class imbalance setting. For (1), the datasets are \"perturbed\" with additive Gaussian noise in the features. For (2), different data vendors are restricted to observe different supports of the full data distribution, which is a commonly adopted setting for data heterogeneity in distributed machine learning [68]. We also consider a continuous interpolation of (2). In these settings, our method continues to perform well, as shown in Tables 8,9 & 10 in Appendix D.3.3. Nevertheless, we acknowledge that these settings do not cover all cases of data heterogeneity in practice; extending the method and results to more settings is an important direction for future work.\n\n> Using data samples to represent data distribution can cause issues, such as dealing with malicious data vendors. In real-world scenarios, some vendors may provide data samples that do not accurately reflect their true data distribution. Some malicious vendors might even forge samples (for example, using some real data as samples while the rest of dataset is synthetic or useless data). The article does not take this into account.\n\nIndeed the consideration of incentivizing the data vendors to truthfully report their samples is of great practical importance, and it has difficulties especially in our setting which does _not_ assume to have access to a ground truth reference distribution. Formally, the notion of _incentive compatibility_ of a valuation metric can ensure that the vendors perform truthful reporting. In other words, it deters malicious vendors or discourages vendors from reporting forged samples. In our setting of data distribution valuation, if the valuation is accurate (e.g., with access to the ground truth reference distribution such as in Section 4.1), it can be shown to satisfy incentive compatibility; and if the valuation has a bounded error (e.g., without the ground truth reference distribution, but with some approximated reference distribution such as in Section 4.2), then the valuation can be said to satisfy an approximate (i.e., weaker) version of incentive compatibility. We make these precise in Appendix A.4.3 (lines 764-795), and provide preliminary empirical results in Appendix D.3.4. In our empirical investigation, the data vendor who mis-reports the samples receives a significantly lower value (Figures 6,7,8 & 9 in Appendix D.3.4). These results demonstrate that our proposed method can mitigate the issue of malicious data vendors to some extent. This discussion and the results are deferred to appendix due to page constraints and that these are not the primary focus of our work. We point out that our discussion and results are preliminary in this very important direction, which may require a separate and in-depth treatment, and hope that our preliminary results can serve as starting points for future research.\n\nWe wish to thank Reviewer Sj3P for the positive feedback and questions. We hope our response has clarified your questions and helped improve your opinion of our work.", "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 wish to thank the reviewers for reviewing our paper and providing the detailed feedback. We especially appreciate the positive feedback on the __novelty of our work__ (all reviewers), the __clarity of presentation__ (Reviewers `s86g`, `Sj3P`), and the __quality of our results__ (all reviewers).

---

We include some additional experimental results (and the detailed settings) mentioned by Reviewer `s86g` in `response.pdf`:

- Figure 11 plots the valuation scores vs. error levels of distributions and fitted linear regression, for different number of vendors.
- Table 22 tabulates the "accuracy" (measured by Pearson coefficient) of our proposed valuation scores ($\hat{\Upsilon}$ in Equation 5) with mean and standard error over $10$ independent trials for up to $1000$ vendors.

Meta-review: The paper studies the question of data valuation of a distribution when presented with a sample. The reviewers universally liked the paper and the contributions, I encourage the authors to take into account the points raised in the rebuttal and incorporate some of their new experiments into the final version of the paper.
Decision: Accept (poster)