Research map / Learning theory and algorithms / Prediction and decision losses
Towards a statistical theory of data selection under weak supervision
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.
Theory and experiments on selecting a subsample of unlabeled data using a surrogate model to predict labels, showing that biased non-reweighted selection can beat unbiased/influence-function schemes and even full-sample training.
Problem
Selecting a subset of unlabeled samples to label, then training by weighted/regularized ERM, when only a surrogate (imperfect label predictor) is available; existing methods (unbiased reweighting, leverage scores, influence functions) are asymptotically studied mostly for n much smaller than N.
Approach
Derives asymptotically optimal data selection schemes under low-dimensional asymptotics (n/N -> gamma in (0,1)) showing that optimal selection is generally biased/non-reweighting and depends on the subsampling fraction, and uses high-dimensional GLM asymptotics via Gaussian comparison to characterize selection rules.
Key results
- Non-reweighted (biased) selection often achieves lower test error than unbiased influence-function selection; the paper reports cases where selected-subset training beats full-sample training.
- For unbiased schemes with uniform x in 1D, the ratio of optimal non-reweighting to unbiased error can be below 1/30 (factor larger than 30 for alpha=4, X_M=10), showing unbounded suboptimality of unbiased subsampling.
- Plugin use of surrogate can be suboptimal; test error is insensitive to surrogate accuracy in the real-data experiment.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use biased non-reweighting subsampling instead of the best unbiased scheme | ERM data selection · Least-squares regression, low-dimensional asymptotics | asymptotic prediction error coefficient | Helped |
| Select samples using the optimal non-reweighting rule rather than random subsampling | ERM data selection · Well-specified GLMs, low-dimensional asymptotics | asymptotic error coefficient | Helped |
| Select a subset rather than use the full sample | Non-reweighting ERM · Misspecified linear and logistic regression, low-dimensional asymptotics | asymptotic test error | Helped |
| Bias selection toward uncertain (hard) samples | Data selection · Broad array of settings | test error | Helped |
| Select the hardest samples in high-dimensional settings | Data selection · High-dimensional GLMs | test error | Hurt |
| Bias selection toward easier rather than harder samples | Data selection · Certain high-dimensional cases | test error | Helped |
| Use a more accurate surrogate model | Surrogate-based data selection · Binary image classification | test error | No clear effect |
| Plug the surrogate conditional model directly into the selection rule | Plugin data selection · Imperfect-surrogate setting | risk | Hurt |
| Use data selection rather than unweighted ERM on the full sample | ERM data selection · Binary image classification | test error | Helped |
Surprising findings
- Data selection can reduce test error below full-sample ERM when the subsampling fraction is near 1 under misspecification.
- Better surrogate models do not always lead to better data selection.
Limitations
- Low-dimensional results assume the subsampling fraction is bounded away from zero and rely on asymptotic approximations.
- High-dimensional analysis restricted to convex M-estimators with linear models and Gaussian covariates.
- Minimax-optimal selection schemes are not constructed in general; plugin schemes are used in experiments.
Experimental setup
Datasets: SwAV-embedded binary image classification dataset (N=34345, p=2048) synthetic Gaussian covariates
Benchmarks: binary image classification (SwAV embeddings) synthetic GLM high-dimensional simulations
Metrics: test misclassification error asymptotic estimation error coefficient
Baselines: unbiased reweighted subsampling influence function subsampling leverage score subsampling random subsampling
Builds on: influence function subsampling leverage score subsampling Gaussian comparison inequalities
Closest papers by meaning
- Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond (ICML 2024 · similarity 0.88)
- Most Influential Subset Selection: Challenges, Promises, and Beyond (NeurIPS 2024 · similarity 0.87)
- Structural-Entropy-Based Sample Selection for Efficient and Effective Learning (ICLR 2025 · similarity 0.87)
- Enhancing Semi-Supervised Learning via Representative and Diverse Sample Selection (NeurIPS 2024 · similarity 0.86)
- Leveraging Data Symmetries to Select an Optimal Subset of Training Data under Label Noise (NeurIPS 2026 · similarity 0.86)
- Enhanced Sample Selection with Confidence Tracking: Identifying Correctly Labeled Yet Hard-to-Learn Samples in Noisy Data (AAAI 2025 · similarity 0.86)
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.