Data Acquisition via Experimental Design for Data Markets

Authors: charles  lu
baihe  mit
  huang
sai praneeth karimireddy
vepakomma  praneeth
michael i mbzuai
  jordan
ramesh raskar mit
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 20:08:37

Abstract: The acquisition of training data is crucial for machine learning applications. Data markets can increase the supply of data, particularly in data-scarce domains such as healthcare, by incentivizing potential data providers to join the market. A major challenge for a data buyer in such a market is choosing the most valuable data points from a data seller.  Unlike prior work in data valuation, which assumes centralized data access, we propose a federated approach to the data acquisition problem that is inspired by linear experimental design. Our proposed data acquisition method achieves lower prediction error without requiring labeled validation data and can be optimized in a fast and federated procedure. The key insight of our work is that a method that directly estimates the benefit of acquiring data for test set prediction is particularly compatible with a decentralized market setting.

Main paper: 
 introduction: 
 While massive training datasets enable major machine learning breakthroughs, they remain largely inaccessible outside of large companies, motivating mechanisms for broader data access. A related point is that many data owners have become resistant to having their data collected indiscriminately without their consent or without their participation in the fruits of predictive modeling, resulting in legal challenges against prominent AI companies [16, 33] . These trends motivate the study of data marketplaces, which aim to incentivize data sharing between sellers, that provide access to data, and buyers, that pay compensation for data access [11, 1, 54] .For practical data acquisition scenarios, a data buyer has a specific goal in mind and, in particular, wants training data to predict their test data in a specified context. Accessing different datapoints may require varying prices associated with each datapoint, which may reflect heterogeneous cost, quality, or privacy levels for each datapoint [44, 40] .For example, consider a hospital that wants to make a prediction for a specific patient's X-ray. The hospital can submit this X-ray as an unlabeled test query to the marketplace, along with a budget to access relevant training data. The marketplace selects useful training data to build a model for this specific prediction task, sharing only the final prediction rather than the raw data to protect privacy. This process can be repeated for each new patient query (see Figure 1 ). However, not all X-ray images will be equally relevant. Thus, we want to select only those seller datapoints that are most useful for answering the buyer's query and fit the buyer's budget. This goal of data acquisition has motivated the development of many data-valuation techniques (e.g., [23, 29, 38, 60, 52, 39, 57, 46, 30] ). However, we argue that current data valuation techniques Figure 1 : Overview of Data Marketplace Approach. A buyer brings their test query (e.g., a patient's chest X-ray needing diagnosis) and a budget to the marketplace. DAVED selects the most relevant subset of seller training data to minimize prediction error on the buyer's specified test query while respecting budget constraints. Unlike prior methods that require labeled validation data, DAVED directly optimizes for test performance. This enables targeted, cost-effective data acquisition compared to purchasing entire datasets.are misaligned with the data acquisition problem, particularly in the context of data marketplaces. They all face at least one of the following limitations:• The selection process may not be adaptive to the buyer's (unlabeled) test queries, potentially failing to identify the most relevant data. In a data marketplace, buyers typically need to purchase only a small subset of datapoints most relevant to their test data, which may follow a significantly different distribution than the overall seller data.• When adaptive selection is implemented, these techniques rely on labeled validation data, which is often impractical. Further, when a small quantity of such data is available, the selection may overfit the validation data and result in poor performance on the test queries.• The algorithms are not scalable and typically require retraining the ML model numerous times. Hence, they are unable to select from realistic seller corpora (>100K+ datapoints).Instead, we propose data acquisition via experimental design (DAVED) method that overcomes all of these limitations. Unlike most previous work in data valuation, our approach does not require a labeled validation dataset and instead directly optimizes data selection for the buyer's unlabeled test queries.Additionally, our approach accounts for budget constraints and is able to weigh the price of each seller's datapoint against its potential benefit, simultaneously solving the budget and revenue allocation problems [64] . Moreover, it can be implemented in a federated manner, achieving lower prediction error even compared to centralized baselines.Our contributions are the following:1. Formulate the data acquisition problem for data marketplaces and demonstrate that data valuation methods make a fundamental theoretical mistake of "inference after selection" (Theorem 1).2. Design a novel, highly scalable, and distributed data selection procedure that eliminates the need for validation data by directly selecting the most cost-effective seller data to answer the buyer's test queries (Algorithm 1).3. Demonstrate state-of-the-art performance on synthetic data and medical data in various modalities (X-rays, images, and text). overfitting occurs when the validation set is too small (n = 10), resulting in worse performance than random selection. Our validation-free method (DAVED) method maintains low error in both scenarios. 
data acquisition versus data valuation: 
 In a decentralized data marketplace, data acquisition must be performed before full data access is granted to the buyer [36] . This relates to Arrow's Information Paradox [7] -sellers are unwilling to share data before payment, while buyers need to evaluate utility before purchasing. This distinction between data valuation and data acquisition for data marketplaces is also discussed in a recent data acquisition benchmark, where data value must be estimated without requiring white-box access to the seller's data (i.e., full, unrestricted access to the data) [12] .A more fundamental issue with validation-based data valuation approaches is exemplified by the Data Shapley value approach [23, 29, 38, etc.] , which measures the marginal contribution of each training datapoint's improvement to a validation metric. They are great for after-the-fact attributing the relative influence of the training data. However, they cannot be used to make decisions about which datapoints should be included in the training. This is because of, as noted earlier, the "inference after selection" issue. Using validation data to select training data leads to substantial over-fitting to the validation data.Illustrative example: Suppose that we only have a single validation datapoint. Then, it is clear that we will select training data similar to this singular datapoint, and our selection has no hope of working on the test dataset. While this clearly demonstrates overfitting in an extreme scenario, we show in Figure 2 that increasing the validation set size does not circumvent this issue. We see that other data valuation techniques have poor test prediction errors-some techniques even underperform even a random selection baseline! This clearly demonstrates overfitting. Our proposed method maintains low test error as more seller training data is selected. In Section 3, we will dig in deeper into this phenomenon and prove a very strong theoretical lower bound. We show that any approach that relies upon validation data for data selection can perform as badly as throwing away all the training data and simply training on the validation data alone! This is especially true when our budget is small compared to the dimensionality of the problem, as is likely in a data market setting -the data is typically high dimensional, and we can only select a very small fraction of the total available data. 
setup and limitations of prior methods: 
 Description of Data Acquisition Setting. As shown in Figure 1 , in our setting of data acquisition, a buyer has a budget and test data. The platform uses the buyer's data to select training datapoints from the seller that optimize buyer test error. The interaction proceeds as follows:2. The platform also has access to n datapoints from data sellers Z train = {(x j , y j )} j=1,...,n and their associated costs {c j } j=1,...,n .3. Given only the covariates X test , the platform assigns a selection weight w j to each datapoint (x j , y j ). This weight w j ∈ {0, 1} represents the discrete action of selecting datapoint j.4. The platform selects datapoints from the sellers according to w = (w 1 , . . . , w n ), trains a model f θ(w) , makes the predictions f θ(w) (X test ), and distributes c j • w j payment for each datapoint used in training.In general, we do not make i.i.d assumptions between the train and test -we expect the test queries will not be similar to the total available train data. The goal then is to pick the weights w, which minimizes the prediction error for the buyer while adhering to their budget constraint n j=1 w j c j ≤ B. This gives rise to the following problem:EQUATIONwhere l is squared loss. Here, the expectation is over the conditional label distribution of y test i |x test i , and the potential randomness of the algorithm. Note that this problem can not be solved because we do not know the targets Y test . Instead, we need to rely on a surrogate objective function (proxy) L(w). One approach to constructing such a proxy is by using validation data.Folly of Relying on Validation Data. In most data valuation methods, e.g., Data Shapley [23] , the value of data is evaluated using a labeled validation set Z val = {(x val j , y val j )} n val j=1 . Implicitly, these methods assume that the known Z val is drawn from the same distribution as the unknown Z test . Then using this validation data, scores (s 1 , . . . , s n ) are assigned to the seller training datapoints Z train . For two datapoints i, j ∈ train, the score s i > s j if the datapoint i is more valuable than j [46, 30] . More concretely, s i > s j implies that training with i would lead to a smaller validation loss than if j was used instead. Thus, these scores can used to select the most valuable datapoints.However, note that we used the validation dataset to compute the scores. Thus, selecting the top-k scores results in implicitly minimizing the validation loss i.e., all validation-based data valuation schemes implicitly optimize the following proxy loss This approach heavily relies on the quantity and quality of the validation dataset in order to generalize to the actual test dataset. In fact, we have the following minimax lower bound even when restricting ourselves to simple linear models.Theorem 1 (Informal version of Theorem A.1). Let w * denote the solution of our original problem (1) and ŵ solve (2) . Suppose that all our data Z train , Z val , Z test are drawn i.i.d. from some distribution D X,Y where D X is supported on B d R (zero-centered ball with radius R in R d ), and Y = θ ⊤ X + ε where ε is independent zero-meaned noise with variance σ 2 . For any training algorithm, when the number of training data is sufficiently large, with high probability,inf θ sup D Y |X E X test [L( ŵ) -L(w * )] ≳ σ 2 d n val .This result implies that the expected test error for any validation-based approach can in the worst-case scale as d/n val with high probability. This dependence on the dimension d and the number of validation points n val highlights that this method may be suboptimal in high-dimensional settings or when the validation dataset is small. In fact, we would get the same error scaling if we threw away the training data and trained a model θ on the n val validation datapoints alone. This explains the striking overfitting we observed earlier in Figure 2 . Furthermore, obtaining a large amount of ground-truth labeled data may be challenging in many real-world applications. Instead, we propose a validation-free approach to data acquisition based on experimental design. 
our methods and implementations: 
 We propose an alternative approach based on a proxy objective. Our key assumption is that the conditional distribution D y|x : y = f θ * (x) + ϵ is identical across Z train and Z test . This is a natural assumption in many domains -for instance, if an X-ray exhibits indicators of a specific disease, it should receive the same diagnosis regardless of whether it appears in the training or test set. Without this assumption, our problem becomes intractable since the same x j could map to arbitrarily different labels across train and test sets. Under this framework, we can reformulate our problem using V-optimal experiment design [47] .Step 1: Linearizing the problem. Our goal is to design a proxy loss function L(w) which approximates the true test loss L(w). To do this, we have to reason about how different choices of training data S ⊂ Z train could impact the prediction on a particular test datapoint in X test . This is a notoriously challenging problem for general deep learning models [9] . Instead, we use a linear approximation and model the complicated training dynamics with kernelized linear regression. We suppose we have a known feature-extractor ϕ : X → R d0 and an unknown θ * ∈ R d0 such that the data is generated asEQUATIONwhere ε is independent noise with mean zero and d 0 is the embedding dimensionality. The function ϕ(•) can be the empirical Neural Tangent Kernel (eNTK) [27, 41, 58] of the model, or even the embeddings extracted from a deep neural network such as CLIP [49] . While this may be a bad approximation in general [61] , a recent line of work has shown that such eNTK representation very closely approximates the fine-tuning dynamics of pre-trained models both theoretically [58, 42] as well as emperically [22, 63] . In fact, such linear approximations have also been used to speed up validation-based data attribution computations [46] .Step 2: Experimental design proxy. Given the assumption on our data from Eqn. (3), we can use the V-optimal experiment design framework [51, 47, 26] to define a proxy objective. First, suppose that S ⊆ (ϕ(X train ), Y train ) is the subset selected by w and then we performed least-squares regression. The resulting estimate θ(w) can be computed in closed form as θ(w) = n j=1 w j ϕ(x j )ϕ(x j ) ⊤ † ( n j=1 w j ϕ(x j )y j ) . Henceforth, we will drop the ϕ when obvious from context and simply use x. We can further use Eqn. (3) to compute the expected error on an arbitrary test query x 0 , y 0 as follows:E[( θ(w) ⊤ x 0 -y) 2 |X train , x 0 ] a1 = E[ ( θ(w) -θ * ) ⊤ x 0 + ε 2 ] a2 = x ⊤ 0 E[( θ(w) -θ * )( θ(w) -θ * ) ⊤ ]x 0 + E∥ε∥ 2 a3 = x ⊤ 0 E[ θ(w) θ(w) ⊤ ]x 0 + E∥ε∥ 2 a4 = x ⊤ 0 n j=1 w j x j x ⊤ j =:I(w) † x 0 + E∥ε∥ 2Here a 3 uses the unbiasedness of the ordinary least squares (OLS) estimator and a 4 plugs in the closed form of θ(w) and simplifies. With this, we end up with a very clean expression for the expected test error on an arbitrary point x 0 , and the matrix I(w) is known as the Fisher information matrix. While regression suffices for our use case, the procedure can be extended to general linear models. Dropping the fixed E∥ε∥ 2 , we can use this to build our proxy function LED (w) and arrive at the following optimization problemEQUATIONThis optimization objective directly measures how useful each training point would be for predicting the specified test query. The matrix I(w) captures how much information each selected datapoint provides about the test point in the embedded feature space.Note that our proxy function LED (w) can be computed using just X train , X test and does not even need access to training labels. Unfortunately, the objective in ( 4) is NP-hard to optimize [4] . We next see how to derive fast and provably good approximation algorithms for (4).Step 3: Fast approximation. To make Eq. 4 amenable to gradient-based optimization, we drop the constraint that w j ∈ {0, 1} and allow it to be a continuous positive vector i.e., w ≥ 0 and n j=1 w j c j ≤ B. With this relaxation, the proxy objective LED (w) is continuous and convex in w [10] . We then run the "herding" variant of the Frank-Wolfe algorithm [59, 37, 53, 8, 65] . To do this, define ( wt := w t /c) for any t. We start from a w0 = e 0 and iteratively update as2 wt+1 ← (1 -α t ) wt + α t e jt , where j t = arg maxEQUATIONNote that if we use the step-size α t = 1 t+1 in ( 5), w t satisfies a special property at any iteration t: wt ∈ ∆ n and further (t + 1) wt ∈ {0, 1} n .Run the procedure until the last iteration t = t o for which we still have ∥w t0 ∥ 1 ≤ B. We can adapt the theory from [8, 28] to analyze the above procedure and show the following.Theorem 2 (Informal). Let us run Frank-Wolfe herding update (5) for t 0 steps such that it is last step which satisfies ∥w t0 ∥ 1 ≤ B. We use wt0 = ((t 0 + 1)w t0 /c) as our selection vector and we would have selected t 0 datapoints. Then, under some assumptions, we haveLED (t + 1) wt0 ≤ min w∈{0,1} n , n j=1 wj cj ≤B LED (w) + O log t 0 t 0 .The above theorem shows that our continuous relaxation does not significantly affect the optimality of our result -we get O( log t0 t0 ) close to the optimal solution to the original NP-hard ( 4). If all datapoints have equal cost c, then t 0 = ⌊B/c⌋, and so our approximation quality improves as we increase the budget. While better approximation guarantees are attainable [3] , their procedure is significantly more involved and is not easily amenable to efficient federated implementations as ours is.Step 4: Efficient federated implementation. Our practical implementation directly restricts w ∈ ∆ n instead of w in the theoretical implementation above i.e., we runEQUATIONThis way w can be directly interpreted to be the sampling probability for different seller training datapoints. The bottleneck to efficiently implementing ( 6) is computing the gradient. At step t, the negative gradient can be shown to beEQUATIONThus, if we have the inverse information matrix I(w t ) † pre-computed, g j as well as the update (6) can be trivially computed by seller j using only their data x train j (and the test data). Next, we show how to efficiently maintain the inverse information matrix. Note that the update (6) has a special structure: all coordinates are shrunk, and then only a single coordinate of w t is increased. We can relate the resulting I matrices with a rank-one update as:I(w t+1 ) = (1 -α t )I(w t ) + α t x jt x ⊤ jt .Define P t := I(w t ) † . We can use the Sherman-Morrison formula [50] to compute P t+1 = I(w t+1 ) † asEQUATIONFor each round t, this update only involves the current matrix P t = I(w t ) † and the single datapoint x jt selected for the round. Thus, the seller can also locally compute this update as well as the updated cost L(w) as in Eq. ( 4) for any α t :EQUATIONAlgorithm 1 DAVED: Iterative Optimization Procedure P 0 ← (1 -λ Reg ) X ⊤ diag(w 0 ) X + λ Reg • σ X I n×n -1# Initialize P (Eq. 10) 4: for t ∈ {1, 2, . . . , T } do5: g ← -∇ L(w t )# Compute negative gradients (Eq. 7)6:j t ← arg max j ( gj /cj) # Select coordinate based on costs 7:α t ← LINE_SEARCH( L)# Find optimal step size (Eq. 9)8:w t+1 ← (1 -α t )w t + α t e jt # Shrink weights and upweight the chosen coordinate (Eq. 6)9:P t+1 ← SHERMAN_MORRISON(P t , x jt , α t )# Update inverse information matrix (Eq. 8) 10: end for 11: Output: Sample seller data according to w T ∈ ∆ n without replacement until budget B runs out. Thus, a line search can be performed to determine the optimal step size α t ∈ [0, 1] to minimize the proxy loss as. This differs from ( 5) where we used a specific choice of α t . Frank-Wolfe is known to be more stable with the line search [53, 65] . The seller can communicate this α t and x jt to the platform to compute the updated P t+1 using only O(d) communication.An additional practical consideration is that by initializing w 0 = c 1 e 1 , we have an ill-conditioned inverse information matrix P 0 . We instead use an initialization of w 0 = 1 n /n ∈ ∆ n and further add a feature-wise regularization term. This makes the initial P 0EQUATIONwhere σi = 1 n n j=1 (X ji -Xi ) 2 is the empirical standard deviation of feature i. The complete details are summarized in Algorithm 1.Single-step variant. We can also forgo the iterative process and instead linearly approximate the cost function (Eq 4) with a single step that selects the top k datapoints under the budget B,EQUATIONThis simplified version is extremely fast while still maintaining relatively good performance. 
experiments: 
 We evaluate our proposed method for data acquisition (DAVED) against common data valuation methods on both synthetic data and four real-world medical:1. Fitzpatrick17K [24] , a skin lesion dataset, where the task is to predict Fitzpatrick skin tone on a 6-point scale from dermatology images. 2. RSNA Pediatric Bone Age dataset [25] , where the task is to assess bone age (in months) from X-ray images of an infant's hand. 3. Medical Information Mart for Intensive Care (MIMIC-III) [31] , where the task is to predict the length of hospital stay from 48 attributes such as demographics, insurance, and medical conditions. 4. DrugLib reviews [34] , text reviews of drugs where the task is to predict ratings (1-10).For validation-based methods, we use a validation set of 100 datapoints.We report mean test errors over 100 buyers.For more details on the experimental setup, see Appendix C. Our code is available at this repo: https://github.com/clu5/ data-acquisition-via-experimental-design.Comparing Performance on Data with Homogeneous Costs. In Figure 3 , we evaluate our method and several other data valuation methods on varying amounts of Gaussian data with homogeneous fixed costs. Compared to other methods, both multi-and single-step versions of DAVED have lower test errors across budgets on synthetic data. This performance gap is especially large when the buyer has a small budget (around 5-10 seller training datapoints). In Figure 4 , we evaluate our method on real image and text data embedded through CLIP and GPT-2 feature representations. We observe that DAVED has better performance compared to most other baselines on all three datasets, highlighting that the proposed method is practical for embeddings of high-dimensional data. Table 1 summarizes our results on all datasets. For the Gaussian data and MIMIC datasets, we report the mean error of budgets from 1 to 10, while for the embedded datasets (RSNA, Fitzpatrick17K, DrugLib), we report the mean error of budgets from 1 to 100 in intervals of five.Comparing Performance on Data with Heterogeneous Costs. Next, we compare methods on seller data with non-homogeneous costs. We uniformly sample costs c ∈ {1, 2, 3, 4, 5} for each seller datapoint and consider two cost functions, c j = √ c and c j = c 2 , which downweights gradient of that datapoint x j (see Equation 7). To simulate heterogeneous utility across datapoints, we introduce cost-dependent label noise, ϵ ∼ N (ȳ, σ 2 ), to each datapoint ỹi := y i + βε/c j , where ȳ is the mean target value and β is the overall noise level, which we fix at 30% throughout our experiments. For these experiments, we did not evaluate Data Shapley [23] , LOO [13] , and Influence [21] that had very long runtimes. In Table 2 , we report additional mean test error across budgets 1-30 for both cost functions. We find that our DAVID method is more budget-efficient in choosing cost-effective noisy datapoints than other methods across datasets. We provide additional plots for heterogeneous costs in Appendix D.1.Comparing Runtime. In Figure 5 , we compare the optimization runtime of our data selection method on 1,000 datapoints while increasing the dimensionality of the data as well as when the dimensionality is fixed to 30, and the number of seller datapoints is increased to 100,000. Data Shapley [23] and LOO [13] took too long to run for large amounts of datapoints or high dimensional data and are not reported. In both experiments, our multi-step compares favorably to efficiency-optimized techniques such as KNN Shapley [29] while our single-step method had the fastest runtime. This demonstrates that our method can scale to marketplaces with millions of datapoints.Regularization Strength. In Appendix D.2, we vary the amount of regularization applied on the MIMIC, DrugLib, and RSNA datasets. We find that applying a moderate amount of regularization between 0.2 and 0.6 can lead to improved performance. Even when the information matrix is set to identity, i.e., λ = 1, performance on the DrugLib datasets is still reasonable. Note that for all other experiments, we do not apply any regularization.Amount of Buyer Data. In Appendix D.3, we vary how many buyer test datapoints are simultaneously optimized over on Gaussian-distributed, MIMIC, and RSNA datasets. While all buyer and seller data is sampled from the same distribution, the number of buyer datapoints still affects the optimization procedure. In general, we find that increasing the number of datapoints in the "test batch" increases For each budget constraint, we select seller datapoints until the budget is exceeded and calculate test prediction error on the buyer data. We average over 100 buyers and report the mean test error across budgets from 1 to 30. test errors. Therefore, we recommend keeping the number of test datapoints in the buyer's "query" between 1-8 for each data acquisition.Gaussian MIMIC RSNA Fitzpatrick DrugLib COST FUNCTION √ c c 2 √ c c 2 √ c c 2 √ c c 2 √ cSteps. In Appendix D.4, we vary the number of optimization steps in our method on the Gaussian-distributed and RSNA datasets. We find that more iterations generally improve prediction performance. Intuitively, one expects that selecting T points requires at least T steps of iterative optimization. We recommend setting the number of steps to be 2-5 times the desired budget for homogeneous costs.In Appendix D.6, we compare the iterative optimization procedure against a convex optimization solver [18] . We find that our iterative approach results in several orders of magnitude speedup while maintaining similar levels of test error.Finetuning versus Linear Probe. In Figure 14 , we evaluate fine-tuning versus linear probing for datapoints selected using DAVID and random selection. We find that using DAVID for fine-tuning performs similarly to linear probing results on DrugLib with BERT [17] . 
discussion: 
 While other validation-free methods exist [60, 5] , our method uniquely combines test-adaptivity, theoretical grounding, and superior empirical performance. Moreover, a major advantage of our method is that it is amenable to federated optimization requiring O(d) communication per round, making it well-suited for decentralized data marketplaces, unlike other methods that require seller data to be centralized in order to repeatedly train models to estimate data value. Additionally, our method does not require labeled data, whereas other data valuation methods assume that all datapoints come with corresponding ground-truth labels. As discussed in Section 2 and Section 3, the existing paradigm of valuing data with a validation set is suboptimal. Incidentally, the second-best performing method, Data OOB [39] , is the only other method that does not use a validation set.Limitations. However, our algorithm comes with some limitations that form exciting directions for future work. Our approach currently communicates every step. Instead, integrating local steps like in FedAvg [43] or Scaffold [35] would decrease communication costs. Further, integrating differential privacy techniques would provide formal privacy guarantees to the buyers and sellers [19] . While DAVED shows strong performance across datasets, its effectiveness depends on having a good feature extractor that captures relevant aspects of the data. We recommend using pre-trained foundation models (e.g., CLIP, GPT-2) as they can extract general-purpose features. Future work could explore adapting the feature extraction to specific domains or handling cases where key features are missing (zero-centered ball with radius R in R d ), and Y = θ ⊤ X + η where η is independent zero-meaned noise with variance σ 2 . Suppose D X and the training data X train is supported on B d R (zero-centered ball with radius R in R d ) and l is square loss, then there exist numerical constants, c 1 , c 2 , c 3 , such that:1. With probability at least 1 -exp -c 1 n val /R 2 , inf θ sup D Y |X ,X train E X test [L( ŵ) -L(w * )] ≥ c 2 σ 2 d n val . 2. If there exists κ > 0 such that λ(E x∼D X [x ⊗4 ]) ≤ κ • λ E x∼D X [x ⊗2] ⊗2 (here λ denotes the largest eigenvalue and ⊗ denotes the outer product), then for any training algorithm used by the platform, with probability at least 0.99-exp -c 1 n val /R 2 -c3κ κ+m , we have sup D Y |X ,X train L( ŵ) -L(w * ) ≥ c 2 σ 2 d n val .Proof. Let f θ (x) = θ ⊤ x and E = N (0, σ 2 ). Define the parameter space resulting from the training algorithm:Θ = θ(w) : w ∈ ∆([m]) .When n is sufficiently large, Lemma A.2 implies that there exists {θ 1 , θ 2 , . . . , θ K } ⊂ Θ such thatθ ⊤ i X val 2 ≲ δ √ n val , ∀i ∈ [K] (θ i -θ j ) ⊤ X val 2 ≍ δ √ n val , ∀i < j ∈ [K].Let P θi denote the conditional distribution D y|x of the target when the underlying model parameter is θ i , it then follows thatEQUATIONNow define Σ = E x∼D X [xx ⊤ ], by Lemma A.4, we have that with probability at least 1exp(-Ω(n val /R 2 )),EQUATIONNotice thatE X test [L( ŵ) -L(w * )] = ( θ( ŵ) -θ * ) ⊤ 2 Σ .Therefore, under the event of Eq. ( 12), Eq. ( 13) implies thatinf θ sup D Y |X ,X train E X test [L( ŵ) -L(w * )] ≥ inf θ sup D Y |X ,X train 1 2 E 1 n val ( θ( ŵ) -θ * ) ⊤ X val 2 2 ≳ c 2 σ 2 d n valThis establishes the first inequality.For the second inequality, we have that under the condition λEQUATION.By Lemma A.5, for any θ and θ * , we have that with probability at least 0.99-O κ κ+m , L( ŵ) -L(w * ) = 1 m (θ -θ * ) ⊤ X test 2 2 = 1 m m i=1 θ -θ * , x test i 2 ≥ 0.0001 • ( θ( ŵ) -θ * ) ⊤ 2 Σ ≳ c 2 σ 2 d n val .Combining this and the first inequality by union bound, we establish the second inequality. Lemma A.3 (Fano's inequality, Cover [14] ). When θ is uniformly distributed over the index set [M ], then for any estimator θ such that θ → Z → θP[ θ(Z) ̸ = θ] ≥ 1 - I(Z; θ) + log 2 log M .Lemma A.4 (Matrix-Chernoff bound, Tropp [55] ). Consider an independent sequence {X i } k i=1 of random, self-adjoint matrices in M n satisfying X i ≥ 0 and λ max (X i ) ≤ R almost surely, for each i ∈ {1, . . . , k}. Defineµ min := λ min k i=1 EX i , µ max := λ max k i=1 EX i . Then, P λ max k i=1 X i ≥ (1 + δ)µ max < n e δ (1 + δ) 1+δ µmax R for δ ≥ 0; P λ min k i=1 X i ≤ (1 -δ)µ min < n e -δ (1 -δ) 1-δ µ min R for δ ∈ [0, 1].Lemma A.5 (Paley-Zygmund inequality, Paley and Zygmund [45] ). If Z is a random variable with finite variance and Z ≥ 0 almost surely, thenP(Z > θ E[Z]) ≥ (1 -θ) 2 E[Z] 2 E[Z 2 ], ∀θ ∈ (0, 1).B Convergence Rate of Frank-Wolfe (Proof of Theorem 2Setup. We mostly follow the proof technique in Bach et al. [8] and Jaggi [28] . Recall the optimization problem for the optimal design loss Eq. ( 4):min w∈D L(w).Here, D is the scaled simplex defined by the constraints w ∈ R n ≥0 and n j=1 c j w j ≤ B. The Frank-Wolfe update on this function is then: For t = 1, 2, . . . , repeatedly perform the following steps• Compute s t = arg max u∈D ⟨∇L(w t ), w t -u⟩. • update w t+1 = (1 -α t )w t + α t s tNote that this update procedure is identical to the updates in Eq. 5. We can then define the duality gap as g(w) = sup s∈D ⟨w -s, ∇L(w)⟩.We also define the curvature constantC l = sup s,w∈D γ∈(0,1) u=(1-γ)w+γs 2 γ 2 (L(u) -L(w) -⟨u -w, ∇L(w)⟩) .We assume that the curvature constant is finite, i.e., C l < ∞. This is true for L(w) as long as both the algorithm and the true optimum are bounded away from the boundary of D -see detailed discussions on this in Ahipaşaoglu and Todd [2] . A better analysis might be able to avoid this assumption, e.g., Zhao and Freund [65] use certain homogeneity properties of L(w) to derive better assumption-free convergence rates for the FW method on D-optimal experiment design. We leave the question of adapting these results to our setting (V-optimal experiment design) for a challenging future work. Lemma B.1 (Lemma 5, [28] ). For any α ∈ (0, 1),L(w t+1 ) ≤ L(w t ) -α t g(w t ) + α 2 t 2 C l .Theorem B.2. In the Frank-Wolfe algorithm, our update algorithm in Eq. 5 uses α t = 1 t+1 . For this, we haveL(w t ) ≤ min w∈D L(w) + C l (1 + log t) 2t . Proof. Define h(w) = L(w) -min w∈D L(w). Using Lemma B.1, h(w t ) ≤ h(w t-1 ) -α t-1 g(w t-1 ) + α 2 t-1 2 C l ≤ h(w t-1 ) -α t-1 h(w t-1 ) + α 2 t-1 2 C l = (1 -α t-1 )h(w t-1 ) + α 2 t-1 2 C lHere we used the convexity of L as follows:g(w t-1 ) = sup s∈D ⟨w t-1 -s, ∇L(w t-1 )⟩ ≥ ⟨w t-1 -w * , ∇L(w t-1 )⟩ ≥ L(w t-1 ) -min w∈D L(w) .Continuing our derivation, recall we haveh(w t ) ≤ (1 -α t-1 )h(w t-1 ) + α 2 t-1 2 C l = t -1 t h(w t-1 ) + 1 2t 2 C l ≤ t -2 t h(w t-1) .t • h(w t ) ≤ (t -1)h(w t-1 ) + C l 2t .Unrolling this recursion, we gett • h(w t ) ≤ t-1 k=1 C l 2k ≤ C l (1 + log t) 2 .This yields the theorem claim.Finally, to finish the proof of Theorem 2, note that adding additional constraints only increases the loss, i.e., min w∈D L(w) ≤ min w∈D and w∈{0,1} n L(w).Hence, we showed a O(log t/t) approximation to the otherwise intractable combinatorial problem. With additional assumptions on the structure of the loss function, one can even show improved quadratic or even exponential approximations [15, 8] . Finally, we note that Frank-Wolfe is a wellknown method to efficiently approximate the optimal experiment design objective [59, 20, 2] and this also motivates using this approach in practice [2, 6] .For each buyer test point, we optimize each selection algorithm over the 1,000 seller datapoints and select the highest value data based on the validation set of 100 datapoints (our method and Data OOB do not use the validation set). For each test point, we train a linear regression model on the selected seller points and report test mean squared error (MSE) on the buyer's data and average test error over 100 buyers.For reproducibility, our full implementation is available at: https://github.com/clu5/ data-acquisition-via-experimental-design.We conduct all experiments on an Intel Xeon E5-2620 CPU with 40 cores and a Nvidia GTX 1080 Ti GPU. For implementation of baseline data valuation methods, we use the OpenDataVal package [30] version 1.2.1. We use the default hyperparameter settings for all methods except for Data Shapley (changed 100 Monte-Carlo epochs with 10 models per iteration), Influence Subsample (from 1000 to 500 models), and Data OOB (from 1, 000 to 500 models) to reduce computational runtime.In our experiments, we use the following setting of hyperparameters for DAVED:• 500 iterations for multi-step variant, 1 iteration for single-step variance • Line search for step size α ∈ (0, 0.9)• Regularization λ = 0 (unless otherwise specified)For experiments with heterogeneous costs, we uniformly sample costs c ∈ {1, 2, 3, 4, 5} for each seller datapoint and apply either h(c) = √ c or h(c) = c 2 as the cost function. Noisy labels are generated by adding Gaussian noise scaled inversely proportional to the cost, with overall noise level set to 30%.Each attribute was min-max scaled to lie in the range [0, 1].The DrugLib dataset [34] can be downloaded here https://archive.ics.uci.edu/ dataset/461/drug+review+dataset+druglib+com. The task is to predict overall patient satisfaction with a drug's side effects and effectiveness on a ten-point scale. We format each review using the following prompt template to feed GPT-2:Benefits: $BENEFITS_REVIEW Side effects: $SIDE_EFFECTS_REVIEW Comments: $COMMENTS_REVIEW where $BENEFITS_REVIEW is the corresponding portion of the drug review.1 import torch 2 from transformers import GPT2Tokenizer, GPT2Model We evaluate data selection methods on 10K synthetic Gaussian datapoints with costs randomly sampled from {1, 2, 3, 4, 5} and transformed using two cost functions: √ c (left) and c 2 (right). Each datapoint's label noise is scaled inversely with cost (ε/c j ) to simulate quality differences. DAVED achieves lower test MSE across budgets 1-30 while respecting cost constraints, demonstrating robust performance even with varying data quality and costs. Results are averaged over 100 random buyer test points. Experiments on MIMIC-III dataset (35K patients with 48 normalized clinical features) compare performance under two cost functions: √ c (left) and c 2 (right). Costs are uniformly sampled from 1, 2, 3, 4, 5 per datapoint. Label noise ε ∼ N (0, σ 2 ) is scaled by ȳ/h(c j ) where ȳ is the mean label value and h(c) is the cost function, modeling how higher-cost data has lower noise. DAVED achieves lower prediction error for length-of-stay prediction across budgets 1-30. Results averaged over 100 random test patients. Evaluation on Fitzpatrick17K dataset (15K images embedded through CLIP) under two cost functions: √ c (left) and c 2 (right). Costs sampled from 1, 2, 3, 4, 5 with noise ε ∼ N (0, σ 2 ) scaled by ȳ/h(c j ), where ȳ is the mean Fitzpatrick score and h(c) is the cost function. This scaling ensures highercost images have proportionally less label noise. DAVED achieves consistent performance while respecting heterogeneous cost constraints. Results averaged over 100 random test images. c 2 . sampled from 1, 2, 3, 4, 5 with noise ε ∼ N (0, σ 2 ) scaled by ȳ/h(c j ), where ȳ is the mean rating and h(c) is the cost function, reflecting how higher-cost reviews tend to have more reliable ratings. DAVED achieves robust rating prediction performance despite varying data quality. Results averaged over 100 random test reviews. We evaluate prediction error versus budget as λ varies from 0 (no regularization) to 1 (identity information matrix) on: MIMIC dataset (length-of-stay prediction), DrugLib reviews (rating prediction with GPT-2 embeddings), and RSNA Bone Age (age prediction from X-rays using CLIP embeddings). Moderate regularization (λ between 0.2-0.6) improves stability and performance by better conditioning the information matrix, though DAVED remains effective even without regularization.Results averaged over 100 random test points per budget level. Figure 14 : Linear models in feature space approximate full model fine-tuning. We compare BERT performance on DrugLib reviews using either full fine-tuning (which updates all model parameters) or linear probing (which only trains a linear layer on frozen embeddings) on data selected by DAVED versus random selection. The similar performance patterns between these approaches empirically validates our use of kernelized linear regression in the feature space as a proxy for the full training dynamics. This aligns with recent theoretical work showing that fine-tuning of pre-trained models is well-approximated by linear models in the empirical Neural Tangent Kernel (eNTK) regime. Since our method relies on this linear approximation for efficient data selection, these results support our choice of feature extractor ϕ and linear modeling approach. Results show test error averaged over 100 random trials using different test reviews. We compare the prediction error of Frank-Wolfe optimization with a convex optimization solver on 1, 000 datapoints sampled from 30-dimensional Gaussian distribution. Both single-step and multi-step variants of our iterative approach achieve comparable accuracy to the optimal convex solution while being significantly faster to optimize. Results averaged over 100 random trials with homogeneous costs (c j = 1). Runtime comparison between Frank-Wolfe iterative approach and convex solver for the data selection problem on 1000 datapoints from 30-dimensional Gaussian distribution. Our iterative method achieves several orders of magnitude speedup while maintaining similar levels of prediction error (see Figure 15 ). The single-step variant provides additional acceleration with minimal performance lossWe believe that AI developers face important ethical questions when acquiring data for AI development, as highlighted by recent class-action lawsuits against AI companies regarding data consent and compensation. Our work presents a scalable and decentralized approach to data acquisition that can help address these concerns. By enabling targeted selection of the most valuable datapoints, our method reduces both costs and potential privacy risks compared to broad, indiscriminate data access [44] . The decentralized nature of our approach enhances transparency and gives individual data owners more control over how their data is shared and used, while avoiding the privacy and security risks of centralizing data with brokers. However, while our method enables more efficient and privacy-preserving data transactions that could democratize access to high-quality training data, especially in domains like healthcare, several societal and technical challenges remain. These include ensuring fair compensation for data owners, preventing misuse of acquired data, and developing appropriate governance frameworks for decentralized data markets. Addressing these challenges will be crucial for the responsible development of data marketplaces that can sustainably increase the supply of training data while protecting individual privacy and data rights.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes]Justification: In the supplemental material, we provide a simplified code example and will release the full codebase in a public code repository upon acceptance.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Question: 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?Answer: [Yes]Justification: We provide details of our experimental setup in Appendix C.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: All experimental results are averaged over 100 random test trials.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: 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)?Answer: [NA] Justification: We believe this paper does not pose such risks as we do not release any new models or datasets.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We cite and provide links to all datasets used in Appendix C.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: This paper does not introduce any new datasets or models.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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: Our research does not involve crowdsourcing or human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
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: No human subjects research was conducted.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.Here, ej is the standard basis vector along axis j, and in w := w/c, the division is performed element-wise. 
 
 Appendix:  


Decision: This paper addresses the problem of selecting valuable data points in a decentralized data marketplace, particularly focusing on domains where data is scarce. The authors propose a federated data acquisition method inspired by linear experimental design, which does not require labeled validation data and instead optimizes data acquisition directly based on test set performance. The method is designed to function efficiently in a decentralized market setting, showing state-of-the-art performance on several real-world medical datasets.

Overall, all reviewers are positive about the paper, appreciating the timeliness of the research question, the novel approach, and the clear writing. There are some reservations, such as the requirement for a high-quality feature extractor, assumptions about data distribution that may not always hold true, and a limited scope regarding budget constraints in practical marketplaces. However, the strengths of the paper clearly outweigh the weaknesses. We recommend accepting the paper and encourage the authors to incorporate the reviewers' comments in their final camera-ready version.

Reviews: review: paper_summary: paper_summary: The paper introduces a new data valuation algorithm based on linear experimental design. The technique does not require a validation set and can be used in a federated setting.
strength_weakness: strength_weakness: I have reviewed this paper at ICML. I think the new revision has addressed my previous concerns. The following is my ICML review:
- The writing can be improved a bit. For example, in Section 3.3, the proof or citation for the test loss of LS estimator should be provided. In Section 3.4, I don't understand why the constraint of costs can be removed. Such derivation details are better to be explicitly written, it's okey to be in Appendix. I also don't see the benefit of using Frank-Wolfe algorithm.
- The proposed approach requires a feature extractor, and I believe the performance depends greatly on the choice of feature extractor. Afterall, the theoretical justification of this appraoch is based on the assumption that the groundtruth is a noisy linear combination of the feature, that's why the requirement of test labels can be removed. It's good to explicitly acknowledge this point.
- In Figure 3, why does the error significantly increases with full data for many curves? Are there a small portion of the data is being corrupted?

In this new revision, the author has clarified the linear model setup and the derivation is super easy to follow. The idea of using linear model as a proxy is straightforward but I am not aware of other works doing it. My remaining concern is that while this approach does not require a validation set, it requires a feature extractor. My major question is how this feature extraction can be picked in practice. I understand this is a hard question and the use of a public feature embedding is quite common in data selection techniques, therefore I will not reject the paper based on this point.
questions: questions: See weaknesses.
limitations: limitations: See weaknesses.
paper_summary: paper_summary: This paper introduces a novel method for acquiring training data in a decentralized data market without requiring labeled validation data. Based on detailed and reliable theoretical support, the authors comes to a promising conclusion that the selection methods based on validation set has the performance as bad as the models trained by validation itself. Thus, it theoretically exceeds a series of methods represented by Shapley. This approach is amendable to federated optimization and reduce prediction error, making it more suitable for decentralized markets compared to traditional centralized data valuation methods.
strength_weakness: strength_weakness: W1: The input for data acquisition task is too idealistic. In the actual data market, existing data acquisition tasks are often combined with data discovery, emphasizing the retrieval of data from environments such as data lakes that have different distributions and poor data quality. This paper simplifies the input data as datapoints, lacking consideration for issues related to data quality and failing to explain why datapoints are directly considered without integrating them into the context of the data market.

W2: Although this article provides detailed and solid theoretical deductions, some assumptions are too strong. For example, in Line 127 of Section 4: " First, we assume that the conditional distribution D_(y|x) is identical across Z^Train and Z^Test". In fact, due to the presence of a large number of missing values in the train set, assumptions about data distribution may not hold true. If these assumptions are not valid, the explanation provided in the article regarding V-optimal experiment is insufficient, which makes me confused.

W3: The proof of theorem 1 in the article is interesting, but some details need to be discussed if we want to use this conclusion to overperform methods based on Shapley Value. 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?

W4: The assumption of infinite training data in theorem 1 is not very reasonable. From my experience, the data available in the data market should be a subset of the results from the data discovery task and joinable subsets of datasets in the data lake, with its scale yet to be examined.

W5: The application of kernelized linear regression is not well motivated.
questions: questions: Q1: Is it reasonable to assume that the training data in theorem1 is infinitely large?
Q2: If the assumptions about data distribution in Line 127 of Section 4(w2) cannot hold true, how does this proof work through V-optimal experiment? Or can you explain why this assumption always holds true even with data quality problems?
limitations: limitations: Yes
paper_summary: paper_summary: This paper uses the linear experimental design to tackle the data acquisition problem.
strength_weakness: strength_weakness: 1. Overall I like this paper and take a few hours trying to understand the technical part and experimental results. But some necessary analysis and equations are simplified, not so friendly to readers who are not very familiar with the V-optimal experiment design framework and some optimization parts. Please provide some preliminaries in your work. 

2. line 136 .. suppose we have a known feature-extractor ...  how to get such good extractor $\phi$ and whether your evaluation results are sensitive to a poor $\phi$? 

3. The authors consider the low-budgets cases ( lower 50 training datapoints ) and the validation size for baselines is small. More experiment results are needed. 

4. Some parts are confusing for me, please see the questions below.
questions: questions: 1. Could authors explain how to get the eq.(7) derived from the eq.(4) ?  

2. $\textbf{confusion part:}$ How $g_i$ in eq.(7)  can be only calculated by the seller $j$ using training data $x_j^{\text{train}}$, given $x_i^{\text{test}}$ is needed( or $\mathbb{E}(x^{\text{test}})$ appears in eq.(7) ) ? 

Line 176:  "$g_i$ as well as the update (6) can be trivially computed by seller $j$ using only their data $x_j^{\text{train}}$ (and the test data). " 

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

$\textbf{Question:}$  Whether optimization in eq.(7) involves the test dataset? If it involves, I guess some baselines could also do the same process for data selection : for example,  LAVA could also only use  feature space $\mathcal{X}$ to compare $x^{\text{train}}$ and  $x^{\text{test}}$, and select data points?  If not, back to the question of the confusion part.

 It will be better to provide more details about your analysis or related works for references in the paper for better understanding. ]

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

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


————————
All my concerns have been addressed. I will raise the score.
limitations: limitations: NA
paper_summary: paper_summary: The paper focuses on the problem of data acquisition in decentralized data marketplaces. The paper claims that acquiring training data using validation-based data valuation methods can be overfitting. Thus, the paper proposes DAVED, which directly selects training data by optimizing test loss on a given test set rather than relying on the validation set. DAVED approximates the test loss trained on a subset of the training data using a linear experimental design framework and employs gradient-based optimization to compute the sampling probability of each data point, considering budget constraints and decentralized settings. Experiments on synthetic and real-world datasets are conducted to validate the advantages of DAVED.
strength_weakness: strength_weakness: (W1) Lack of comparison with data acquisition approaches.

(W2) Lack of experimental evaluation on the test data distribution.

(W3) The motivation could be better clarified.
questions: questions: (D1) The paper claims that existing data valuation methods are misaligned with the data acquisition problem and introduces DAVED to select data points based on the test set rather than the validation set. In the experiments, the paper compares DAVED with a series of data valuation methods including Influence, Data Shapley, and Data OOB, showing the advantages of DAVED. However, the paper does not discuss or compare its performance with methods that focus on data acquisition problems with or without a validation set. In addition, given that DAVED is designed for decentralized data marketplaces, the paper does not discuss or verify how it compares with existing methods in federated learning, such as [62].


(D2) The paper does not conduct experiments to analyze the impact of different test data distributions and the training data distribution. The paper should include experiments to measure the performance of DAVED under the scenario where there is a distribution shift between the training and test sets.

(D3) The paper uses an example to illustrate their setting: "the buyer may be a patient who cares about diagnosing their own chest X-ray and is willing to pay a fixed budget to access other X-ray images to train a model to have low error on their 'test set' (see Figure 1)." However, this example may be impractical as it is unlikely that a patient would train a diagnostic model themselves rather than relying on a hospital or healthcare institution. If the data acquisition is indeed for a hospital, the test data for the hospital cannot be fixed because patients are continually coming in. From my understanding, Algorithm 1 is designed for a fixed size of test data. This creates a gap between the paper's setting and real-world scenarios. The authors should either clarify this gap or explain if I have misunderstood the motivation or algorithm.
limitations: limitations: NA

Comments: title: Thank you for the pointer
comment: Thanks for the detailed rebuttal.
Thank you. I have checked the code and also run the experiments :) .
This is indeed a typo, thank you for the close reading! Equation (8) should correctly read
$$
 P_{t+1} = \frac{1}{1-\alpha_t}P_t - \frac{\alpha_t P_t x_{j_t} x^\top_{j_t} P_t}{1 - \alpha_t + \alpha_t x_{j_t}^\top P_t x_{j_t}}
$$
Note that the 1 in the denominator in the second term is now $1 - \alpha_t$. We got this by plugging in the following into the Sherman-Morrison formula:
$$
A = \big((1-\alpha_t) \mathcal{I}_t \big)^{-1} = \frac{1}{1-\alpha_t}P_t \quad \text{and } u = \alpha_t x_j \text{ , } v = x_j.
$$

Our experiments, simulations, and the rest of the code remain unchanged since they used the correct formula (without this typo).
Thanks for your response. All my previous concerns have been addressed. I will raise the score.

A quick question, if I try to use the definition of the Sherman-Morrison formula based on 

$(A+uv^T)^{-1} = A^{-1} - \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}$

Will the eq(8) should be 
$
P_{t+1}= \frac{1}{1-\alpha_t} P_t - \frac{1}{1-\alpha_t} \times \frac{\alpha_tP_tx_{j_t}x^T_{j_t}P_t}{(1-\alpha_t)+\alpha_tx_{j_t}^TP_tx_{j_t}}
$ ? 

Then is there any guideline to choose an appropriate $\alpha_t$ ?