Data Distribution Valuation with Incentive Compatibility

We thank Reviewer uc12 for taking the time to review our paper and providing the detailed feedback, and for recognizing that our modeling approach is natural and interesting and our main studied problem is well motivated.

We wish to provide the following clarifications.

However, the motivation of data distribution valuation is exactly the lack of samples. ... This is at odd with the authors' approach of using many samples to estimate the value of the distribuiton.

We hope to highlight that while the constraint (i.e., lack of samples) may appear to be at odds with the proposed approach (i.e., using samples to estimate the value), this is an important motivation for the specific design choice namely MMD due to its efficient sample complexity.

• [Better sample complexity.] The sample complexity of MMD (i.e., using sample MMD to estimate true MMD) is efficient, precisely $\mathcal{O}(1/ {\sqrt{m}})$ (where $m$ the size of the sample) and importantly, independent of the dimension. In contrast, the optimal transport (as discussed in Appendix B.1) has a sample complexity of $\mathcal{O} 1(1/n^{1/d})$ which suffers the curse of dimensionality (Genevay et al., 2019).

• [Faster empirical convergence.] The benefit of this efficient sample complexity is demonstrated in an empirical comparison in Appendix C.3.1 where the sample MMD converges more quickly (to the true MMD), making MMD an more practically appealing choice (than other divergence) under the constraint that only a limited-size sample is available.

This requires $P_N$ to be close to $P^*$; in other words, the noisy parts $Q_i$ in everyone's distribution cancel out when averaged (Proposition 2).

We wish to clarify that Proposition 2 does not require the assumption that $P_N$ is close to $P^*$. Instead, Proposition 2 shows the effect of the distance of $P_N$ from $P^*$. Providing a precise characterization of how the heterogeneity in the vendors (i.e., the $Q_i$'s and the $\epsilon_i$'s) affects the valuation function, is a contribution, as it has not been previously obtained: The same design choice (of using $P_N$ as a majority-based reference instead of $P^*$) has been previously adopted by Chen et al. (2020); Tay et al. (2022); Wei et al. (2021), as elaborated in Appendix B. The key distinction is that they do not provide the error guarantee (i.e., Proposition 2).

Indeed, because of the possibility that $P_N$ may be far from $P^*$, we have obtained results (in Appendix A.2.4) that are general and can be applicable to other alternative reference $P_{\text{ref}}$ (to $P_N$), should it become available by design or assumption. In this regard, these considerations do not have the limitation that $P_N$ must be close to $P^*$.

In the standard definition of IC (like in [Chen et al 2020]), a player should be disincentivized to mis-report anything.

Please refer to the general comment "Updated definition for incentive compatibility and theoretical results (in Appendix A.3)".

We wish to thank Reviewer uc12 for the taking the time to review our paper and providing the feedback, and hope that our response has clarified your raised questions and comments. Since the discussion period is drawing to the end, let us know if you have further questions and we are happy to clarify them before the discussion period ends.

We thank Reviewer s7hX for taking the time to reviewer our paper and for finding that our studied problem is meaningful and interesting.

We hope to address the comments as follows.

[On quality/setting.]

I am quite certain that manipulating the dataset would quite often lead to better metrics.

Could the reviewer please confirm that by "manipulating the dataset leading to better metrics", it means the vendor performs some careful statistical modification of the dataset to improve its value?

the alternative distribution considered is overly specific and somewhat naive, and clearly cannot represent the class of all possible manipulations

The "alternative distribution" is specified to be interpretable and intuitive, so that the empirical results can be understood and used to verify the theoretical results. A very complex "alternative distribution" can make the results and analysis difficult and thus not very useful in deriving insights.

We note that we do not claim to represent the class of all possible manipulations, in particular our empirical settings.

[On clarity.]

Please find an updated formalization of the problem statement as follows:

Denote the ground truth (i.e., optimal) distribution as $P^*$. For two data distributions $P, P'$, and the respective samples $D\sim P, D\sim P'$, design a function $\Upsilon(P) \mapsto \mathbb{R}$, and a function $\nu(D) \mapsto \mathbb{R}$, so that for a specified (given) $\epsilon_P > 0, \delta \in [0,1]$, we can derive the $\epsilon_D \geq 0$ for which the following holds with probability at least $1-\delta$: $\nu(D) \geq \nu(D') + \epsilon_D \implies \Upsilon(P) \geq \Upsilon(P') + \epsilon_P \ .$

Then, our theoretical results Proposition 1 and Theorem 1 are the solutions to this problem, with and without the assumption of $P^*$ being available, respectively.

First and foremost, please verify if Def. 1 is consistent with the standard notion of IC.

Please refer to the general comment "Updated definition for incentive compatibility and theoretical results (in Appendix A.3)".

I am curious why the problem is phrased "data valuation"? I see nothing about pricing in this work, and to me "evaluation" seems like a better fit?

We note that the term "data valuation" is a relatively common phrase in similar existing works (Ghorbani & Zou, 2019; Kwon & Zou, 2022, Amiri et al., 2022, Wang & Jia, 2023, Just et al., 2023, Wu et al., 2022, Bian et al. 2021, Jia et al. 2018; 2019, Yoon et al. 2020).

As described in Section 1, one primary motivating application of this work (and these above existing works) is to use the value of data for the pricing of data in data marketplaces such as Datarade, Snowflake (Chen et al., 2022) (reference in main paper) and (Agarwal et al., 2019, Sim et al., 2022) (references below).

We hope our response (and our updated definition of IC) have addressed your comments and helped improve your opinion of our work.

References

Agarwal, A., Dahleh, M., & Sarkar, T. (2019). A marketplace for data: An algorithmic solution. Proc. EC, 701–726.

Rachael Hwee Ling Sim, Xinyi Xu and Bryan Kian Hsiang Low. (2022) Data Valuation in Machine Learning: “Ingredients”, Strategies, and Open Challenges. IJCAI, survey track.

We wish to thank Reviewer s7hX for the taking the time to review our paper and providing the feedback, and hope that our response has clarified your questions, in particular regarding the definition of IC. Since the discussion period is drawing to the end, let us know if you have further questions and we are happy to clarify them before the discussion period ends.

We thank Reviewer c1ZW for taking the time to review our work and providing the constructive feedback and for recognizing that our studied problem is interesting and well-motivated. We wish to address the feedback and comments as follows,

MMD as a valuation doesn't reflect data distribution's performance on a proper loss function.

In (Si et al., 2023), the opposite is argued that the MMD can be used to provide a proper scoring rule (i.e., proper loss), because the continuous ranked probability score (CRPS) is a proper scoring rule, which can be shown to be a form of MMD. Specifically, in Section 2 (Background) of (Si et al., 2023):

A popular proper loss is the continuous ranked probability score (CRPS), defined for two cumulative distribution functions (CDFs) $F$ and $G$ as $\text{CRPS}(F, G) = \int (F(y) − G(y))^2 \text{d}y$ ... The above CRPS can also be rewritten as an expectation relative to the distribution $F$:

$

\text{CRPS}(F, y') = -\frac{1}{2} \mathbb{E}_F |Y - Y'| + \mathbb{E}_F |Y -y'|

$

where $Y, Y'$ are independent copies of a random variable distributed according to $F$.

And then in the last paragraph of the Section 2:

A special case of IPMs is maximum mean discrepancy (MMD) (Gretton et al., 2008), in which $\mathcal{T} ={T : \Vert T \Vert_{\mathcal{H} } ≤ 1}$ is the set of functions with a bounded norm in a reproducing kernel Hilbert space (RKHS) with norm $\Vert \cdot \Vert_{\mathcal{H}}$; the CRPS objective can be shown to be a form of MMD (Gretton et al., 2008).

In this regard, we believe that MMD is indeed connected to a proper loss function.

As to the other part of this comment:

MMD as a valuation doesn't reflect data distribution's performance on a real decision problem.

Could the reviewer elaborate on the definition of a real decision problem and its potential benefits?

In contrast divergence-based valuations correspond to the value of dataset on a proper loss.

A divergence-based valuation does not necessarily correspond to the value of dataset on a proper loss, because the result recalled by Kimpara et al., (2023), namely Theorem D.0.1 (in their Appendix D) is specific to the Bregman divergence. For data valuation, some divergences such as $f$-divergence and optimal transport have been considered (as compared and discussed in our Appendix B.1). To the best our knowledge, these divergences are not directly equivalent to the Bregman divergence, so the result in (Kimpara et al., 2023) is not immediately applicable.

I suggest the author compare the results to previous results in information elicitation. Specifically, this following paper seems relevant.

We thank the reviewer for the reference and will include in our revision. We wish to highlight the following connection and distinctions:

In (Kimpara et al., 2023), Definition 3.3 (Proper divergence) is a key component used, and indeed MMD is a stritcly proper divergence. This can be proven using Theorem 5 of (Gretton et al., 2012), which ensures $\text{MMD}(p,q) = 0 \iff p=q$, and the fact that $\text{MMD}(p,q) \geq 0$ because MMD is equivalently a norm in the Hilbert space.

The distinctions are in the goal and a technical setting where the goal of Kimpara et al., (2023) is to evaluate generative models in the discrete setting while our goal is to characterize the sampling distributions for data in the continuous setting.

Note that we are citing the conference version of the paper, which has a different ordering of the authors from that reference (arXiv-version) raised by the reviewer.

Suppose the principal has sample access to ground truth distribution, and sets it as a reference, it seems like the approach in this paper could be applied.

This corresponds to Proposition 1 in Section 4 where we make this assumption of having access to the ground truth distribution. We subsequently relax this assumption in Section 5.

Suppose all N-1 distributions have the same deterministic bias, while only one distribution is the ground truth distribution. It seems like it is impossible in this case to discover or incentivize the most valuable dataset.

We wish to highlight that our theoretical result on incentivization aims to provide a precise characterization of how the incentive compatibility is dependent on the $n$ distributions ($1$ for each of $n$ vendors), instead of trying to achieving the exact incentive guarantee for all possible cases. In the case described by the reviewer, our analysis continues to apply, the effect is that the effectiveness of the incentivization for the vendor with the ground truth distribution would be lower, and will decrease as the deterministic bias increases.

We wish to thank Reviewer c1ZW for the taking the time to review our paper and providing the feedback, and hope that our response has clarified your comments and questions. Since the discussion period is drawing to the end, let us know if you have further questions and we will be happy to clarify them before the discussion period ends.