DAVED: Data Acquisition via Experimental Design for Data Markets

Charles Lu, Baihe Huang, Sai Praneeth Karimireddy, Praneeth Vepakomma, Michael Jordan, Ramesh Raskar

TL;DR

DAVED (Data Acquisition Via Experimental Design) is a novel framework that helps buyers select the most valuable training data for their specific needs without requiring labeled validation sets. By leveraging linear experimental design and federated optimization, it achieves lower prediction errors and better scalability than traditional data valuation methods, making it ideal for decentralized data marketplaces.

What Problem Does This Paper Address?

In the burgeoning world of data marketplaces, especially in sensitive fields like healthcare, a fundamental "lemon problem" exists: how does a buyer know which data points are worth purchasing before they've actually seen or used them?

Existing "data valuation" techniques (like Data Shapley) attempt to solve this but suffer from three major flaws:

  1. The Overfitting Trap: They typically rely on a small, labeled validation set to "score" training data. This leads to a phenomenon the authors call "inference after selection," where the chosen data overfits the validation set and fails to generalize to the actual test queries.
  2. Centralization Requirements: Most methods require all data to be in one place to repeatedly retrain models, which is a non-starter for privacy-conscious sellers in a decentralized market.
  3. Computational Cost: Retraining models hundreds of times to estimate data value is incredibly slow and doesn't scale to realistic datasets with hundreds of thousands of points.
Figure 1: Overview of data acquisition process between buyer and seller. A buyer has a budget to acquire training data to get a prediction on their test query. The market platform optimizes the selection of seller data to be most useful for the buyer’s query. The selected data is then used to train a regression model and make a prediction on the buyer’s test data.

Methods

The authors propose DAVED, which shifts the focus from general "data value" to targeted data acquisition.

1. Linearization via eNTK

To avoid the cost of training deep networks repeatedly, DAVED uses a linear approximation. It models the training dynamics using the empirical Neural Tangent Kernel (eNTK) or pre-trained embeddings. This allows the system to reason about how a specific training point might influence a future prediction using closed-form linear algebra.

2. V-Optimal Experimental Design

Instead of asking "how much is this data worth in general?", DAVED asks "how much will this data reduce the error on the buyer's specific (unlabeled) test query?". This is formulated as a V-optimal experimental design problem, which seeks to minimize the variance of the prediction at specific points.

3. Federated "Herding" Optimization

The resulting optimization problem is NP-hard. DAVED solves it using a "herding" variant of the Frank-Wolfe algorithm. Crucially, by using the Sherman-Morrison formula for rank-one matrix updates, the optimization can be done in a federated manner. Sellers compute gradients locally and only share low-dimensional updates, keeping the raw data private and the communication efficient ($O(d)$ per round).

Datasets

The authors evaluated DAVED across a diverse range of benchmarks:

  • Synthetic Gaussian Data: Used to rigorously test high-dimensional settings and small budget scenarios.
  • Fitzpatrick17K: A skin lesion dataset for predicting skin tone from dermatology images.
  • RSNA Pediatric Bone Age: X-ray images of infant hands used to assess bone age.
  • MIMIC-III: A massive electronic health record database used to predict hospital stay duration.
  • DrugLib Reviews: Textual drug reviews used to predict patient satisfaction ratings.

Key Insights and Ideas

  • Labels Aren't Necessary for Valuation: Perhaps the most surprising insight is that you don't need ground-truth labels for the buyer's query to value the seller's data. DAVED only needs the features (covariates) of the test set to determine which training points are most relevant.
  • The "Inference After Selection" Theorem: The authors prove that any method relying on a validation set for data selection can perform as poorly as if you threw away the training data and only used the validation set. This explains why traditional methods often underperform random selection in high-dimensional spaces.
Figure 2: Current data valuation methods overfit when data is high-dimensional or validation sets are small. A total of 1,000 seller datapoints (each with cost 1) are available in the market. Each method selects training data for various budgets to train a regression model to predict the buyer’s test data. The left plot shows that validation-based data valuation methods overfit when the data is high dimensional, while the right plot shows that they also overfit when the validation set is small. In contrast, our proposed DAVED achieves lower test error across a range of budgets of over 100 buyers.
  • Targeted is Better than General: By optimizing specifically for the buyer's current "query batch" rather than a general validation set, DAVED avoids buying irrelevant data, making it much more budget-efficient.

Key Results

  • Superior Accuracy: DAVED consistently achieved lower Mean Squared Error (MSE) than all baselines (Data Shapley, LAVA, Influence Functions, etc.) across all datasets. On the Gaussian 100K dataset, DAVED's MSE was ~0.16 compared to the next best baseline at ~0.97.
  • Massive Speedup: DAVED is orders of magnitude faster. While Shapley-based methods can take hours or days for large datasets, DAVED's single-step variant runs in seconds and its multi-step version scales linearly with the number of seller points.
  • Budget Efficiency: DAVED is particularly effective when the buyer has a very small budget (e.g., only buying 5-10 points), where it maintains low error while other methods fail to beat random baselines.
Figure 3: DAVED achieves better test error against other methods on synthetic data. For three amounts of total seller data (1K, 5K, 100K), each method is optimized to select the most valuable training datapoints from the seller to predict the buyer’s test data. Our data selection algorithm based on experimental design achieves better test MSE on the buyer’s data with fewer training points.

Limitations and Future Work

While powerful, the authors note a few areas for improvement:

  • Communication Rounds: The current iterative procedure communicates in every step. Future work could integrate "local steps" (similar to FedAvg) to reduce network overhead.
  • Formal Privacy: While the federated nature provides some privacy, the authors suggest that integrating Differential Privacy (DP) would be necessary for a production-ready decentralized market to provide formal guarantees against data leakage.
  • Model Mismatch: The method relies on a linear approximation of deep learning dynamics. While effective for fine-tuning, it might be less accurate for training models from scratch.

Summary updated

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.
BibTeX
@inproceedings{lu2024daved,
  author = {Charles Lu and Baihe Huang and Sai Praneeth Karimireddy and Praneeth Vepakomma and Michael Jordan and Ramesh Raskar},
  title = {{DAVED: Data Acquisition via Experimental Design for Data Markets}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=VXJVNdmXO4},
}
Figure