Data Acquisition via Experimental Design for Data Markets

We greatly thank the reviewer for their close reading of our work, their detailed feedback, and their enthusiastic support. We address the comments raised below.

[...] compare its performance with methods that focus on data acquisition problems

First, we want to emphasize that our method uses an unlabelled test dataset whereas the previous methods need a labeled validation dataset. In this paper, we tried to show the limitations of such data valuation approaches but we agree that comparing against other federated client selection methods will be important for more realistic decentralized market scenarios. As we note in our limitations section, adapting our methods to a realistic communication-constrained federated learning setting is an important future direction we hope to explore.

[...] distribution shift between the training and test sets

Note that we make no distributional assumptions on our data. In fact, this is one of the biggest strengths of our method. Both our derivation in Step 2 (line 149) as well as our guarantee in Theorem 2 holds for an arbitrary test dataset - it may be completely different from the training dataset. The only assumption we make is on that the conditional distribution $Y | X$ is the same i.e. the same image will have always the same label (an image with a cat will not be labeled as a cat in the test and as Felis genus in another). Our experiments show that even if there are data quality issues (as in the MIMIC dataset) our method based on this assumption has excellent performance.

Having said this, there are certainly scenarios where our assumption may be violated e.g. when we have features missing not at random (MNAR), or other heterogenous effects. Formalizing and extending our method to such scenarios is a very promising direction for future work.

[...] test data for the hospital cannot be fixed because patients are continually coming in.

In this example, the test data consists of only an individual incoming patient's X-ray which requires a prediction. The data-market platform selects the data and trains a model to predict that patient's data and only shares the final model/prediction to the patient. The selected data points are not directly shared. As correctly identified by the reviewer, this means that the procedure needs to be re-run for each new test patient.

We stress that only the model/prediction is shared and not the data selected. This is because of data privacy and IP issues. Since data is infinitely and easily copyable, it is not feasible to run a marketplace where raw data is ever shared - the buyer can easily make a copy and resell for a lower price. Thus, in our model, only the trained model/prediction is shared.

We once again thank the reviewer for their great feedback of our work.

We thank the reviewer for their comments. We agree that our exposition is dense and some derivations may be inaccessible to reader unfamiliar with experiment design. We will add a more detailed derivation in the Appendix where we will go through all the steps in more detail. Further, we will aim to rewrite in a manner such that despite some of the details being inaccessible, the high-level intuitions and resulting algorithm is accessible to all readers. Having said this, we adress the main concerns raised by the reviewer below.

Also, we would like to stress that the most useful and challenging setting for data valuation methods is when the budget is low, and the validation data size is small. This is why we focus on this setting. We believe this is a strength of our work, not a weakness - the other settings are strictly easier. With a large enough budget, even random selection can work. Similarly, if we can collect a large clean validation dataset, the need for a data market is less justified.

[...] how to get such good extractor $\phi$ and whether your evaluation results are sensitive to a poor $\phi$?

We note that our experiments on Gaussian and MIMIC data are conducted without any feature extractor. In general, it is common to use a pretrained model as a feature extractor but we will provide additional discussion of the choice of feature extractor in the final paper.

Could authors explain how to get the eq.(7) derived from the eq.(4) ?

Eq 7 is the gradient update for a single datapoint $x_j$. The seller that owns the datapoint $x_j$ can calculate its gradient using the buyer data $x_i^\text{ test }$ and the information matrix $\mathcal{I} := \sum_{j=1}^{n} w_j x_j x_j^\top$.

"our method and Data OOB do not use the validation set"

We meant that while other methods require a validation set to estimate data value, our approach (and OOB) does not use a held-out validation set to perform data selection.

Whether optimization in eq.(7) involves the test dataset?

Yes, optimization uses the unlabelled test datapoint $x^\text{ test }_i$. That is, our method is adaptive to the test data point - the train data most relevant to the specific test data is selected. While our focus was to develop a theoretically justified algorithm with provable guarantees, we hope our work will inspire future empirical work that similarly explores selection based on the feature space (including ones based on LAVA). In our current work, we compare against LAVA as described in the paper which requires class labels.

In the experiment setting, the validation set has only 100 datapoints, could authors conduct the experiments when the validation size increases ?

On our datasets, we did not find much difference with larger validation sets but we will include more experiments in the revised paper. Also note that as the size of the validation dataset increases, the motivation for trying to select additional training data decreases. Data valuation methods are most useful when the validation dataset is substantially smaller than the training dataset.

Authors consider low-budgets situations ( 1~10 datapoints ) , it will be better to provide experiments when budgets are larger ?

Our real-world experiments (Fig. 4) use a budget up to 150. We found that past this, the error did not decrease anymore - our method was already filtering out the irrelevant data and selecting the most useful ones. Note that given a high enough budget, even random selection will perform well since eventually all relevant data will get selected. Hence, we decided to focus on the low-budget case which is both the most useful and most challenging. We will add the experiments with higher budgets as well to the appendix.

We believe all the concerns raised by the reviewer are addressed above. If so, we again thank the reviewer for their detailed feedback and request them to kindly re-evaluate our work.

Thank you. I have checked the code and also run the experiments :) .

We greatly thank the reviewer for their close reading of our work, their detailed feedback, and their enthusiastic support. We address the comments raised below.

W1: The input for data acquisition task is too idealistic ...

We absolutely agree that a truly practical implementation of our method for data markets will involve a lot of very exciting large-scale database research questions including data discovery. As we show, our arguably simplistic model is still very useful to discover important data valuation methods. We hope that our work inspires the database community to integrate data valuation methods such as DAVED to develop real-world data markets.

W2: ... missing values in the train set, assumptions about data distribution may not hold true...

First, note that some assumptions on the data distribution are necessary. If the train data may be arbitrarily unrelated to the test data distribution, then the only meaningful training data selection strategy is random sampling. Further, our experiments show that when using a high-quality feature extractor, even if there are data quality issues such as missing values (as in the MIMIC dataset) or slight violations of the assumption, our method still has excellent performance.

Having said this, in practice, we imagine that there are instances where our covariate shift assumption is strongly violated - either due to features missing not at random (MNAR) as noted by the reviewer or due to other heterogeneous effects. We believe this represents excellent future research directions which we hope the data valuation community will build upon.

W3: The existence of parameter σ makes it difficult for me to clearly understand how small this lower bound is. If users have some high-quality validation data (and in practical scenarios of data markets, users should provide high-quality data as much as possible), would this lower bound be acceptable?

Let us compare two different strategies users might take. In strategy 1, they will use the validation dataset of $n_{val}$ datapoints to use Shapely value-like methods to select the training data and enjoy some performance worse than $\frac{\sigma^2 d}{n_{val}}$ according to our lower-bound.

In strategy 2, they will completely ignore the training data and simply use the $n_{val}$ validation data to directly train a linear regression model. The error achieved by this strategy is $\frac{\sigma^2 d}{n_{val}}$ (see Proposition 3.5 in Bach 2024). Comparing this to the lower bound above tells us that the user may be better off directly using their validation data to train a model, instead of submitting it to the platform which uses Shapley-value based data selection. We hope this conveys the strength of our lower bound and will include this discussion in the final version of our paper.

W4: The assumption of infinite training data in theorem 1 is not very reasonable.

The assumption that there is infinite training data is only to make the math simpler. We only assume this to guarantee that there is training data of sufficient diversity to select from with high probability. If we had very few training data points, just by random chance, we might end up in a setting where all of them are very similar, making the data selection problem easier. As shown empirically in Fig. 1, 1000 data points are sufficient to satisfy this condition in practice and for prior methods to work comparably to random selection.

W5: The application of kernelized linear regression is not well motivated.

We study the kernelized linear regression setting mostly because it is the only case that is theoretically tractable to analyze. Further, numerous past works have shown that when using a high-quality feature extractor, this kernelized linear proxy model is a good approximation of the full training process (lines 138--143). We also show this empirically in our setting by the performance of our method, and also in Appendix D.5.

We thank the reviewer for their comments and the positive evaluation of our work. We agree that the choice of feature extractor is very important. In short, how well our linear proxy model works depends on the quality of our feature extractor. If there are features that are relevant to the task but are not present in the embedding output of the extractor, then the linearity assumption would not hold. Thus, we recommend general-purpose pre-trained foundation models that can extract very broad features from the input. We will add more discussion on the sensitivity of our results to the choice of feature extractors in the final version of our paper.