Research map / Learning theory and algorithms / Prediction and decision losses

Computational Budget Should Be Considered in Data Selection

NeurIPS 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Active learning and subset selection · 0 citations (OpenAlex)

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 CADS, a compute-budget-aware data selection method that formulates subset selection as bilevel optimization solved via probabilistic reparameterization, a Hessian-free policy gradient, and a penalty-based relaxation with a fitted loss surrogate.

Problem

Existing data selection methods ignore the compute budget, even though no selection algorithm consistently beats random selection across budgets and the best data depends on how much compute is available.

Approach

Treat the compute budget as an explicit constraint in data selection: learn per-example (CADS-E) or per-source (CADS-S) sampling probabilities via policy gradients on a penalty-relaxed bilevel objective, where the inner training loss is replaced by a log-linear/cubic-spline surrogate fitted as a function of subset size.

Key results

• Bilevel-CADS on MNIST averages 92.46% across budgets (10k-100k forwards) versus 87.59% for random selection and 90.37% for PBCS.
• CADS claims up to 14.42% performance gain over baselines on vision and language benchmarks.
• CADS reports a 3-20x speedup over conventional bilevel implementations, with the speedup growing with compute budget.

Measured effects reported in the paper

Surprising findings

• Under low compute budgets the selector favors clean data sources and assigns near-zero weight to noisy ones, while larger budgets lead it to include somewhat noisier sources (e.g. 22.5% noise).
• Empirical studies cited in the paper show that sophisticated data selection methods often fail to beat random selection across settings.

Limitations

• Relies on a fitted log-linear/cubic-spline surrogate of compute-constrained training loss, whose accuracy determines method effectiveness in new domains.
• Experiments are small-scale (MNIST, CIFAR-10, GPT-2) and the broader claims are not verified at large model scale.
• Cost comparisons with other baselines are partly theoretical (cost tables) rather than measured.

Experimental setup

Datasets: MNIST CIFAR-10 DomainNet Alpaca-GPT4 Alpaca SlimOrca GPTeacher multilingual Alpaca variants

Benchmarks: MNIST CIFAR-10 DomainNet instruction tuning perplexity over 13 Alpaca-style datasets

Metrics: test accuracy validation loss perplexity wall-clock runtime speed-up factor

Baselines: Random selection PBCS Forgetting Scores GraNd EL2N Influence Functions Data Shapley Greedy Coreset

Builds on: PBCS (probabilistic bilevel coreset selection) REINFORCE ScaleBiO DARTS

Closest papers by meaning

• Compute-Constrained Data Selection (ICLR 2025 · similarity 0.87)
• Adaptive Data Optimization: Dynamic Sample Selection with Scaling Laws (ICLR 2025 · similarity 0.85)
• DsDm: Model-Aware Dataset Selection with Datamodels (ICML 2024 · similarity 0.84)
• A CLIP-Powered Framework for Robust and Generalizable Data Selection (ICLR 2025 · similarity 0.84)
• When Dynamic Data Selection Meets Data Augmentation: Achieving Enhanced Training Acceleration (ICML 2025 · similarity 0.83)
• Data Mixture Optimization: A Multi-fidelity Multi-scale Bayesian Framework (NeurIPS 2025 · similarity 0.83)