Research map / Learning theory and algorithms / Prediction and decision losses
Deletion-Anticipative Data Selection with a Limited Budget
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 deletion-anticipative data selection (DADS), which chooses a training subset under a budget by maximizing expected or CVaR post-deletion data utility given anticipated owner staying probabilities, with submodularity-preserving objectives and greedy optimization.
Problem
Data subset selection under a limited budget can lose its high utility when selected data owners later request deletion (GDPR right to erasure), and learners cannot easily re-acquire data before the next acquisition cycle.
Approach
Instead of maximizing the data utility directly, the learner anticipates each owner's probability of staying (independent Bernoulli or size-dependent beta-binomial) and maximizes the expected or risk-averse (CVaR) post-deletion utility; the authors prove monotone submodularity is preserved under these pmfs so greedy algorithms remain near-optimal, and use sample average approximation to evaluate t
Key results
- EDADS outperforms DS on post-deletion validation metrics across NN-H, NN-F and NB-A when owners stay according to the probability model, with the advantage largest when fewer owners are selected or the staying probability is lower.
- Without deletions, EDADS may achieve a poorer validation metric than DS, showing a trade-off.
- RA-alpha DADS with smaller alpha improves worst-case metrics under many deletions with only a minor drop when few deletions occur.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use EDADS instead of conventional DS, anticipating independent owner deletions | NN-S, NN-H, NN-F, and NB-A · Validation sets under anticipated deletions | F1 score, accuracy, or balanced accuracy | Helped |
| Use EDADS instead of conventional DS when no owners delete their data | NN-H, NN-F, and NB-A · Validation sets with no deletions | F1 score, accuracy, or balanced accuracy | Hurt |
| Anticipate more deletions when setting the dependent staying-count distribution | EDADS on NN-H, NN-F, and NB-A · Validation sets across different numbers of deletions | Accuracy or balanced accuracy | Mixed |
| Use EDADS instead of DS with dependent deletion decisions | NN-H, NN-F, and NB-A · Validation sets under moderate and many deletions | Accuracy or balanced accuracy | Helped |
| Use RAα-DADS with a smaller α | NN-H and NN-F · Validation sets with many deletions | F1 score or accuracy | Helped |
| Use RAα-DADS with a smaller α | NN-H and NN-F · Validation sets with no deletions | F1 score or accuracy | Hurt |
Surprising findings
- Without deletions, EDADS can score worse than conventional DS, a trade-off between no-deletion and post-deletion performance.
- The greedy algorithm can be suboptimal for the expected DADS objective, as shown by toy counterexamples.
Limitations
- Reliance on sampling for some utility functions and RA-alpha DADS increases computational cost and yields only approximate solutions.
- Assumes staying probabilities are known or estimated via surveys/histories; estimation errors not studied in depth.
- Experiments assume retraining from scratch and do not account for class imbalance or fairness effects.
Experimental setup
Datasets: Synthetic 2-class dataset Heart disease dataset (Lapp 2019) Fashion MNIST Adult income dataset
Benchmarks: Heart disease (NN-H) F1 Fashion MNIST (NN-F) accuracy Adult income (NB-A) balanced accuracy
Metrics: F1 score accuracy balanced accuracy CVaR of objective
Baselines: DS (non-anticipative submodular data selection) EDADS random selection
Builds on: NN and NB submodular data selection (Wei et al. 2015) stochastic submodular maximization (Asadpour et al. 2008) CVaR formulation (Rockafellar & Uryasev 2002) greedy submodular maximization (Nemhauser et al. 1978)
Closest papers by meaning
- Towards a statistical theory of data selection under weak supervision (ICLR 2024 · similarity 0.84)
- DeRDaVa: Deletion-Robust Data Valuation for Machine Learning (AAAI 2024 · similarity 0.84)
- MaSS: Multi-attribute Selective Suppression for Utility-preserving Data Transformation from an Information-theoretic Perspective (ICML 2024 · similarity 0.83)
- Rethinking Data Shapley for Data Selection Tasks: Misleads and Merits (ICML 2024 · similarity 0.83)
- Compute-Constrained Data Selection (ICLR 2025 · similarity 0.83)
- Navigating Towards Fairness with Data Selection (AAAI 2025 · similarity 0.82)
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.