Research map / Learning theory and algorithms / Prediction and decision losses
DeRDaVa: Deletion-Robust Data Valuation for Machine Learning
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 DeRDaVa, a semivalue-based data valuation that scores data sources by their expected contribution to model utility under anticipated random deletions, plus a risk-averse/seeking variant (Risk-DeRDaVa) and a 012-MCMC approximation.
Problem
Existing semivalue-based data valuation (e.g., Data Shapley) ignores anticipated data deletions, so scores may violate fairness axioms after deletions and recomputation is expensive.
Approach
Model deletions as a random staying set, robustify the fairness axioms, extend the jointly-agreed semivalue to sub-games via NPO-extension, and value each source by its expected semivalue over staying sets upfront; Risk-DeRDaVa applies C-CVaR to the utility to model risk attitudes.
Key results
- Data sources with higher staying probability receive higher DeRDaVa scores, and recomputed semivalues after simulated deletions converge to the DeRDaVa average while deviating from pre-deletion scores.
- In point addition (highest-first) experiments with Naive Bayes on Wind and 100 data sources, DeRDaVa with Banzhaf prior surpasses all baselines in expected accuracy after anticipated deletions.
- The Monte-Carlo sample bound is O(2r^2 n / eps^2 log(2n/delta)) and 012-MCMC gives an importance-sampling approximation avoiding O(3^n) exact computation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Account for anticipated deletion probabilities when valuing data sources | DeRDaVa · Data sources with different staying probabilities | DeRDaVa score | Helped |
| Account for anticipated deletions when valuing a redundant source that is more likely to stay | DeRDaVa with Banzhaf prior · Synthetic dataset with similar RED and REDD sources | valuation score | Helped |
| Select highest-scored points first | DeRDaVa with Banzhaf prior · NB-Wd, point addition | expected model performance after deletion | Helped |
| Select lowest-scored points first | DeRDaVa with Banzhaf prior · NB-Wd, point addition | expected model performance after deletion | Hurt |
| Remove highest-scored points first | DeRDaVa with Banzhaf prior · NB-Wd, point removal | expected model performance after deletion | Hurt |
| Remove lowest-scored points first | DeRDaVa with Banzhaf prior · NB-Wd, point removal | expected model performance after deletion | Helped |
| Anticipate deletions rather than use pre-deletion semivalue scores | DeRDaVa · Simulated deletions across real-world model-dataset combinations | valuation score | Helped |
| Use risk-averse C-CVaR rather than expected utility | Risk-DeRDaVa · Different staying probabilities | valuation score for high-staying-probability sources | Helped |
| Use risk-averse C-CVaR rather than expected utility | Risk-DeRDaVa · Different staying probabilities | valuation score for likely-to-delete sources | Hurt |
Surprising findings
- Data Shapley can assign equal scores to interchangeable sources that the pre-deletion axioms treat as fair, yet after deletions they should differ based on staying probability; multiplying pre-deletion semivalue by staying probability is shown to be inadequate.
- A redundant data source (RED) can receive a higher DeRDaVa score than its Banzhaf score when its staying probability is high relative to its duplicate.
Limitations
- Exact DeRDaVa computation is O(3^n) and approximations still need many samples when n is large
- Staying probabilities must be estimated from surveys/histories or reputations and may be misreported
- Risk-DeRDaVa scores are approximated by sampling because C-CVaR is non-additive
Experimental setup
Datasets: Credit Card Diabetes Wind Phoneme synthetic dataset
Benchmarks: Credit Card Diabetes Wind Phoneme
Metrics: DeRDaVa score expected model accuracy under point addition/removal Gelman-Rubin statistic
Baselines: Data Shapley Leave-One-Out Beta Shapley Data Banzhaf Random
Builds on: Data Shapley Beta Shapley Data Banzhaf semivalue
Closest papers by meaning
- OpenDataVal: a Unified Benchmark for Data Valuation (NeurIPS 2023 · similarity 0.86)
- KAIROS: Scalable Model-Agnostic Data Valuation (NeurIPS 2025 · similarity 0.84)
- Deletion-Anticipative Data Selection with a Limited Budget (ICML 2024 · similarity 0.84)
- Distributionally Robust Data Valuation (ICML 2024 · similarity 0.83)
- SAVA: Scalable Learning-Agnostic Data Valuation (ICLR 2025 · similarity 0.83)
- DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation (NeurIPS 2024 · similarity 0.83)
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.