Research map / Learning theory and algorithms / Prediction and decision losses
DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DU-Shapley, a Shapley value approximation for dataset valuation that uses a discrete uniform sampling of I coalition sizes, reducing utility evaluations from 2^I to I, with asymptotic and non-asymptotic guarantees.
Problem
Computing the Shapley value for dataset valuation (quantifying the marginal gain of a whole dataset to a collaborative ML task) is computationally intractable, and generic Monte Carlo approximations remain expensive when marginal contributions require retraining.
Approach
Exploits the structure of dataset valuation utilities, which depend only on a scalar quantity q(S) that converges in distribution to uniform as players grow; approximates the Shapley value by an expectation over I coalitions of increasing size sampled uniformly without replacement, giving an exponential reduction in utility evaluations.
Key results
- On real datasets with 10 and 20 players, DU-Shapley achieves lower averaged MSE than MC-Shapley and MC-anti-Shapley in all reported cases (e.g., 2e-3 vs 1e-2 on adult with 10 players).
- In noisy label detection with 100 players on CIFAR10 (15%), DU-Shapley reaches F1 0.30 at 5% and 0.34 on BBC, competitive with DataShapley and KNN-Shapley.
- Under the homogeneous/non-parametric use-cases, DU-Shapley requires I^2 utility evaluations to compute all Shapley values, and DataShapley and IGTB need more iterations to reach the same bias.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DU-Shapley instead of MC-anti-Shapley | Shapley-value estimation · adult, 10 players | averaged MSE: 8.10^{-3} -> 2.10^{-3} | Helped |
| Use DU-Shapley instead of MC-anti-Shapley | Shapley-value estimation · adult, 20 players | averaged MSE: 2.10^{-3} -> 6.10^{-4} | Helped |
| Use DU-Shapley instead of MC-anti-Shapley | Shapley-value estimation · breast-cancer, 10 players | averaged MSE: 1.10^{-2} -> 3.10^{-3} | Helped |
| Use DU-Shapley instead of MC-anti-Shapley | Shapley-value estimation · breast-cancer, 20 players | averaged MSE: 8.10^{-4} -> 1.10^{-4} | Helped |
| Use DU-Shapley instead of MC-anti-Shapley | Shapley-value estimation · bank, 10 players | averaged MSE: 8.10^{-2} -> 5.10^{-2} | Helped |
| Use DU-Shapley instead of MC-anti-Shapley | Shapley-value estimation · bank, 20 players | averaged MSE: 4.10^{-2} -> 4.10^{-3} | Helped |
| Use DU-Shapley instead of MC-anti-Shapley | Shapley-value estimation · cal-housing, 10 players | averaged MSE: 3.10^{-2} -> 1.10^{-2} | Helped |
| Use DU-Shapley instead of MC-anti-Shapley | Shapley-value estimation · cal-housing, 20 players | averaged MSE: 1.10^{-2} -> 3.10^{-3} | Helped |
| Use DU-Shapley instead of MC-anti-Shapley | Shapley-value estimation · make-regression, 10 players | averaged MSE: 4.10^{-1} -> 9.10^{-2} | Helped |
| Use DU-Shapley instead of MC-anti-Shapley | Shapley-value estimation · make-regression, 20 players | averaged MSE: 2.10^{-1} -> 2.10^{-2} | Helped |
| Use DU-Shapley instead of MC-anti-Shapley | Shapley-value estimation · year, 10 players | averaged MSE: 5.10^{-3} -> 1.10^{-3} | Helped |
| Use DU-Shapley instead of MC-anti-Shapley | Shapley-value estimation · year, 20 players | averaged MSE: 1.10^{-3} -> 7.10^{-4} | Helped |
Surprising findings
- Even in worst-case settings with few players (I=10 or 20) far from theoretical assumptions, DU-Shapley still outperforms MC-based estimators at equal budget.
Limitations
- Performs worse when players have very heterogeneous dataset sizes, since the random variable inside the Shapley value departs from uniform.
- Convergence assumes limits exist, so guarantees may fail under arbitrarily high heterogeneity.
- Theoretical guarantees are proven only for three specific use-cases; non-asymptotic bounds cover the homogeneous and non-parametric settings.
Experimental setup
Datasets: adult breast-cancer bank cal-housing make-regression year bbc-embedding IMDB-embedding CIFAR10-embedding
Benchmarks: adult breast-cancer bank cal-housing make-regression year bbc-embedding IMDB-embedding CIFAR10-embedding
Metrics: MSE w.r.t. exact Shapley value F1-score (noisy label detection) testing accuracy (dataset removal and addition)
Baselines: MC-Shapley MC-anti-Shapley Owen-Shapley Orthogonal-Shapley SVARM IGTB DataShapley LOO KNN-Shapley
Builds on: Monte Carlo Shapley approximation antithetic sampling Owen multilinear extension DataShapley KNN-Shapley
Closest papers by meaning
- Data Shapley: Equitable Valuation of Data for Machine Learning (ICML 2019 · similarity 0.91)
- Rethinking Data Shapley for Data Selection Tasks: Misleads and Merits (ICML 2024 · similarity 0.89)
- A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values (NeurIPS 2025 · similarity 0.88)
- Faithful Group Shapley Value (NeurIPS 2025 · similarity 0.88)
- Generalized Priority-Aware Shapley Value (NeurIPS 2026 · similarity 0.87)
- shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.