Overcoming the Combinatorial Explosion in Data Valuation

130 concepts97 papers1 proposal

Modern machine learning models are entirely dependent on the quality of their training data. However, not all data points contribute equally: some are highly informative, some are redundant, and others are actively harmful due to noise or mislabeling. To build secure data marketplaces, clean datasets, or fairly reward contributors in federated learning, we need a principled way to measure the economic or performance contribution of individual data points.

Cooperative game theory provides a mathematically rigorous framework for this problem via the Shapley value, which defines a data point's value as its average marginal contribution across all possible subsets of a dataset.

The catch is the combinatorial explosion. For a dataset of size $N$, there are $2^N$ possible subsets. Computing the exact Shapley value requires retraining a machine learning model an exponential number of times. As noted by Fan Wu et al. in their work on Scalability vs. Utility, this exponential complexity makes exact computation NP-hard and completely impractical for modern large-scale datasets. This fundamental bottleneck is echoed across applications ranging from federated learning marketplaces (Qi Li et al. in martFL) to security audits (Rui Wen et al. in Understanding Data Importance in Machine Learning Attacks).

To bypass this exponential wall, researchers have developed a suite of algorithmic shortcuts, proxy models, and statistical estimation techniques that make data valuation scalable.

The Neighborhood Shortcut: Exact Valuation via KNN Surrogates

The most direct way to defeat the $2^N$ complexity is to swap the complex machine learning model for a surrogate where marginal contributions can be computed analytically without retraining: the $K$-Nearest Neighbor (KNN) classifier.

In a foundational breakthrough, Ruoxi Jia et al. (Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms) demonstrated that the marginal contribution of a training point to a KNN model depends entirely on its distance rank relative to a test point. By sorting the dataset by distance—a process taking only $O(N \log N)$ time—the exact Shapley value can be computed recursively. The combinatorial explosion completely collapses because we no longer need to evaluate every subset; we only need to know which points are closer to the target than the point being valued.

Traditional Shapley:  [Evaluate 2^N Subsets] -> Exponential Time
KNN-Shapley:          [Sort by Distance]     -> O(N log N) Analytical Calculation

Building on this geometric intuition, researchers have pushed the boundaries of neighborhood-based valuation:

Proxy Models and Value Transferability

While KNN models offer an elegant mathematical shortcut, we often care about the value of data inside deep neural networks or large language models (LLMs). The core insight enabling this is value transferability: data quality anomalies (like mislabeling or high informational redundancy) are largely intrinsic to the data distribution itself, meaning values computed on a cheap "proxy" model will transfer effectively to an expensive target architecture.

Fan Wu et al. proved this intuition by computing KNN-Shapley values on top of frozen, pre-trained embeddings. The resulting data importance scores were orders of magnitude faster to compute than full model retraining, yet they actually outperformed traditional methods at detecting noisy labels.

This proxy paradigm has been widely adapted across different domains:

Amortized Inference and Statistical Prediction

Instead of evaluating subsets or relying on structural proxies, another direction treats data valuation as a machine learning problem in its own right: learning to predict a data point's utility.

Haifeng Sun et al. (Fast-DataShapley) proposed training a reusable neural "explainer model" that maps data points directly to their estimated Shapley values. This shifts the computational burden from a slow, iterative retraining process into a real-time inference task, achieving a 100x speedup.

Traditional Approach:  New Dataset -> [Run 2^N Retrains] -> Data Values
Amortized Approach:    New Dataset -> [Neural Explainer Inference] -> Data Values (Instant)

Alternatively, the performance landscape can be modeled statistically using Gaussian Processes (GPs). Khang-Nguyen Pham et al. developed DUPRE, which uses a GP regression framework to predict model performance across subsets. By utilizing a specialized kernel based on the Sliced Wasserstein distance to capture the similarity between different datasets, DUPRE bypasses retraining entirely. When the goal is simply to find the best data rather than valuing every single point, Xiaoqiang Lin et al. (Efficient Top-m Data Values Identification for Data Selection) demonstrated that GPs can be paired with adaptive subset evaluations to isolate the top-$m$ most valuable points with up to a 50x speedup over standard baselines.

Axiomatic Relaxations and Simultaneous Sampling

A final, powerful mathematical lever involves changing the definition of "value" itself to make it easier to estimate. The classical Shapley value enforces strict mathematical axioms (such as the efficiency axiom), which force the metric to weight all subset sizes equally. However, in machine learning, a data point's utility is often best surfaced when added to moderately sized or large subsets where the model has already established a baseline distribution.

James Y. Zou et al. (Beta Shapley) proposed relaxing the efficiency axiom to create Beta Shapley. By using a Beta distribution to reweight the importance of different subset sizes, Beta Shapley drastically reduces the statistical noise inherent in random sampling, allowing practitioners to detect harmful data points with significantly fewer model evaluations.

To optimize the sampling process itself, Weida Li et al. (One Sample Fits All) developed a framework capable of approximating multiple probabilistic values (such as Shapley, Banzhaf, and Beta Shapley values) simultaneously from a single set of random permutations.

Finally, in highly dynamic environments like data markets, Boxin Zhao et al. (Addressing Budget Allocation and Revenue Allocation...) bypassed subset evaluation entirely. They utilized an adaptive sampling process based on Online Stochastic Mirror Descent to achieve Shapley-like fairness in linear time, proving that algorithmic and mathematical reformulations can successfully tame the combinatorial explosion of data valuation.

Key Foundational Work

Data Shapley: Equitable Valuation of Data for Machine Learning (2019) — contributed 2 concept elements to this direction.
Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms (2019) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_computational_complexity_of_data_valuati_f1d99bc9,
  title = {computational complexity of data valuation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-data-valuation/rdr_f1d99bc96a104e379f49383574759bd2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_computational_complexity_of_data_valuati_f1d99bc9_v1,
  title = {computational complexity of data valuation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-data-valuation/rdr_f1d99bc96a104e379f49383574759bd2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake