Computational Budget Should Be Considered in Data Selection
Authors: Weilin Wan
WEIZHONG ZHANG
Cheng Jin
Venue: NeurIPS 2025 poster ()
Keywords: Data Selection
Efficient Learning
Computation Budget
Resource-Constrained Learning
Primary area: deep_learning

Abstract: Data selection improves computational efficiency by choosing informative subsets of training samples. 
However, existing methods ignore the compute budget, treating data selection and importance evaluation independently of compute budget constraints. Yet empirical studies show no algorithm can consistently outperform others (or even random selection) across varying budgets. We therefore argue that compute budget must be integral to data-selection strategies, since different budgets impose distinct requirements on data quantity, quality, and distribution for effective training. 
To this end, we propose a novel Computational budget-Aware Data Selection (CADS) method and naturally formulate it into a bilevel optimization framework, where the inner loop trains the model within the constraints of the computational budget on some selected subset of training data, while the outer loop optimizes data selection based on model evaluation. 
Our technical contributions lie
in addressing two main challenges in solving this bilevel optimization problem: the expensive Hessian matrix estimation for outer-loop gradients and the computational burden of achieving inner-loop optimality during iterations. 
To solve the first issue, we propose a probabilistic reparameterization strategy and compute the gradient using a Hessian-free policy gradient estimator. To address the second challenge, we transform the inner optimization problem into a penalty term in the outer objective, further discovering that we only need to estimate the minimum of a one-dimensional loss to calculate the gradient, significantly improving efficiency. To accommodate different data selection granularities, we present two complementary CADS variants: an example-level version (CADS-E) offering fine-grained control and a source-level version (CADS-S) aggregating samples into source groups for scalable, efficient selection without sacrificing effectiveness.
Extensive experiments show that our method achieves performance gains of up to 14.42\% over baselines in vision and language benchmarks. 
Additionally, CADS achieves a 3-20× speedup compared to conventional bilevel implementations, with acceleration correlating positively with compute budget size.

Computational Budget Should Be Considered in Data Selection
Weilin Wan', Weizhong Zhang?; Cheng Jin'
CCollege of Computer Science and Artificial Intelligence, Fudan University Schooo of Data Science, Fudan University
wlwan23em. fudan. edu. en, (weizhongzhang, jc) edu.
Abstract
Data selection improves computational efficiency by choosing informative sub- sets of training samples. However, existing methods ignore the compute budget, treating data selection and importance evaluation independently of compute budget constraints. Yet empirical studies show no algorithm can consistently outperform others (or even random selection) across varying budgets. We therefore argue that compute budget must be integral to dlta-selectiion strategies, since different budgets impose distinct requirements on data quantity, quality, and distribution for effective training. To this end, we propose novel Computational budget-Aware Data Selection (CADS) method and naturally formulate into a bilevel optimiza- tion framework, where the inner loop trains the model within the constraints of the computational budget on some selected subset of training data, while the outer loop optimizes data selection based model evaluation. Our technical contribu- tions lie in addressing two main challenges in solving this bilevel optimization problem: the expensive Hessian matrix estimation for outer-loop gradients and the computational burden of achieving inner-loop optimality during iterations. To solve the first issue, propose probabilistic reparameterization strategy and compute the gradient using a Hessian-free policy gradient estimator. To address transform the inner optimization problem into a penalty
the second challenge, term in the outer objective, further discovering that we only need to estimate the minimum of one-dimensional loss calculate the gradient, significantly improv- ing efficiency. To accommodate different data selection granularities, we present two complementary CADS variants: an example-leved version (CADS-E) offering fine-grained control and source-level version (CADS-S) aggregating samples into source groups for scalable, efficient selection without sacrificing effectiveness. Extensive experiments show that our method achieves performance gains of up 14. 44.22% over baselines in vision and language benchmarks. Additionally, CADS achieves 3-20x speedup compared to conventional bilevel implementations, with acceleration correlating positively with compute budget size.
Introduction
Model training costs have been increasing rapidly, and training data accumulates time, much of it becomes redundant, This makes data selection a crucial approach to reduce computational burden and enhance model performance (52 (59). Numerous studies have tackled the challenge of selecting informative subsets of training samples, employing diverse criteria to identify the most impactful data for training (2]. Most existing methods fall into categories. The first category proposes a measurement metric and selects the top-K samples based on the scores derived from this
"Corresponinng Author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

metric [25 63 70]. Some methods further incorporate similarity measures, such as cosine similarity. to ensure diversity among the selected samples [63]. The second category aims to match certain distributions, such as gradients, embeddings, or other indicative features, to better represent the [9].
overall dataset [6 27
However, despite numerous advances in data selection methods, a critical gap remains: most ap- proaches overlook the computational budget as a key factor shaping the selection process. Empirical studies [8 |2 reveal that optimal model performance depends on balancing training data volume, model scale, and available compute budget, highlighting that data selection is inherently linked to computational constraints. Moreover, recent studies [1] 54 62 reveal that sophisticated selection strategies often fail to consistently outperform random selection across varied experimental settings. [67] further demonstrate that when computational budgets are explicitly factored in, previously effective data selection approaches rarely remain optimal. We thus argue that computational budget must be integral to duta selection strategies, as it determines the appropriate quantity, quality, and distribution of training data, making it a first-order design decision rather than a fixed hyperparameter.
Our argument is further supported by neural network learning dynamics. Models rely on different granularities of knowledge at various training stages, reflected in distinct data subsets. Rahaman et al. [50] showed that networks exhibit a spectral bias, learning low-frequency features before higher-frequency ones. Under limited computational budgets, focusing on data rich in low-frequency features can optimize learning. whereas larger budgets allow leveraging diverse, higher-frequeney information. We verify these effects empirically in Section 3
In this paper, we propose a novel Computational Budget-Aware Data Selection (CADS) method, which we naturally formulate within bilevel optimization framework. In this framework, the inner loop trains the model under the constraints of the computational budget on a selected subset of training data, while the outer loop focuses on optimizing data selection based on the evaluation of the model trained in the inner loop. Our technical contributions target two main challenges: the expensive estimation of the Hessian matrix for gradients in the outer loop and the computational burden associated with achieving optimality in the inner loop during iterations. To solve the first challenge, we introduce probabilistic reparameterization strategy and utilize a Hessian-free policy gradient estimator to compute the gradient efficiently. For the second challenge, we reformulate the inner optimization problem as a penalty term the outer objective function. Notably, we find that estimating the minimum of one-dimensional loss is sufficient for calculating the gradient, significantly enhancing computational efficiency.
To meet varying data selection demands in practice, we implement CADS in two variants addressing different operational requirements: CADS-E operates at example-level granularity for precise control, while CADS-S assigns weights to source groups for improved scalability. Experiments reveal performance improvements of up to 14.42% over baselines across vision and language tasks. CADS delivers 3-20x speedup versus conventional bilevel methods, with acceleration scaling proportionally to compute budget size.
Summary of contributions:
We highlight the crucial role of computational budget in data selection, advocating it as a first-order design factor rather than a fixed hyperparameter, thus addressing a key gap by linking data selection to computational constraints.
We propose novel bilevel optimization framework for Computational Awaget-Aware Data Sclection (CADS), where the inner loop trains the model under budget constraints on a selected data subset, and the outer loop optimizes data selection based on the trained model's evaluation.
To efficiently solve this bilevel problem, we develop techniques including probabilistic reparameterization for gradient estimation avoiding expensive Hessian computation, and reformulation of the inner problem as a penalty term in the outer objective. We further show that estimating a mie-immnsiooall loss minimum suffices for gradient calculation, greatly improving computational efficiency.
Extensive empirical evaluations demonstrate that our CADS framework achieves superior performance across multiple datasets and training settings, validating the effectiveness of computational budget-aware data selection.

---

2 Related work
2.1 Data selection
Traditional data selection methods and related concepts. Data selection methods aim to identify subsets of training samples that maximize informativeness or diversity and minimize redundancy [2]
Approaches leveraging submodular optimization and clustering have shown success in various
tasks 40 [5 61]. Coreset selection techniques specifically construct small representative subsets that
retain essential properties of the full dataset, often using importance weights or gradient similarity [26]
51
Learning-basee methods integrate selection into training through training dynamics analysis [44
59
bilevel optimization 27 74,, gradient properties [2
23]
or uncertainty measures 3 Dataset
distillation methods construct synthetic examples to compress large datasets, enabling faster or more
efficient training by matching gradient statistics [6 T0 60 68). While highly compact, distilled sets often struggle to match real-data diversity or scale with heterogencous corpora characteristic of large-scale model training. Curriculum learning [4] dynamically orders selects data according to difficulty, often progressing from easy to challenging samples (17555).
[55. A related body of work uses importance sampling and adaptive reweighting to prioritize data points that contribute most model improvement or convergence [ (6), demonstrating efficiency gains especially in large-scale or imbalanced data regimes.
Data selection for LLM fine-tuning, Unlike traditional methods, data selection for LLMs often employs simpler heuristic rules due the unprecedented scale of both models and datasets. Efficient subset selection has become crucial in LLM fine-tuning [2] 39 42 49) LIMA demonstrated strong performance with just 1,000 human-curated examples [72), while automated approaches have emerged to replace manual curation. These include natural language indicators with BlendSearch [5], semantic intention tagging [37]. model-based quality filtering 7 31, instruction difficulty metries [30], and uncertainty- driven active learning (28). Recent advances explore gradient- muadinnt-baeed techniques, including
clustered coreset selection 69 and graph methods (71. alongside simple yet effective heuristies like
sength-based prioritization
70 Novel approaches leverage small model training trajectories to guide
selection for larger models
64 and sparse autoencoders for diversity-driver selection (3]. DEITA
provides unified framework balancing quality, complexity, and diversity [34]. These methods achieve comparable or superior performance to full-dataset training while reducing computational requirements, demonstrating that strategically selected subsets can match or exceed naive scaling.
The compute-aware gap. Existing methods typically operate with predefined data budgets without considering computational constraints. Recent studies [I] 54 62 reveal that sophisticated selection strategies often fail to consistently outperform random selection across varied experimental settings. [67] further demonstrate that when computational budgets are explicitly factored in, previously effective data selection approaches rarely remain optimal. This computational perspective motivates approach to data selection that explicitly accounts for training budget constraints.
2.2 Bilevel optimization
Algorithmic advances Early work on bilevel optimization in deep learning focused on implicit as well iterative differentiation with truncated pack-propagation [38, 53 73). These methods scale poorly because they require nested
differentiation and Hessian products [12
16
45)
loops and second-order information. Stochastic variants 9 15
19
20
24] cut per-iteration cost but
still depend on Jacobian/ evaluations. Finite-difference estimators [56] 655 remove explicit
Hessians yet introduce instability. Most recently. fully first-order, penalty-based formulations [8] 29 66) recast the inner optimality conditions as constraints, eliminating higher-order order derivatives and enabling training with only standard gradients. This advancement enables bilevel algorithms to be applied to inereasingly larger-scale problems.
Practical applications Bilevel optimization has become a fundamental tool in machine learning, initially enabling hyperparameter optimization by jointly optimizing model parameters and hyperpa- rameters 14]. Key applications include learning-rate and weight-decay tuning [13 35 In neural
architecture search, DARTS frames architecture parameters as outer variables and weights as inner variables, achieving efficient architecture discovery 33 Resource-aware tasks benefit from proba-
bilistic bilevel formulations for memory coreset selection [74), and gracient-matching
3

---

methods for learning compact synthetic datasets [60]. Extending to large-scale settings, ScaleBiO applies first-order bilevel data reweighting at the scale of billions of tokens in language modeling. demonstrating improved performance with manageable computational overhead 43 These de- velopments highlight bilevel optimization's 's versatility in structuring complex learning problems. enabling efficient parameter tuning, architecture search, and data management, and suggest continued expansion into broader applications.
3
An exploratory experiment to illustrate the impact of compute constraints on data choice
Data Preference Shifts with Increasing Compute Budget
10
10a
Low Budget Regine:
High B Sugget Regime: Prefer High-rrequnnyy Data
Prefer Lon-frequancy Data
Generalizatin
100
1.0-
High Freq Data
Low-Biagget Phase
High B udget Phose
10aa
Training Stops (Compute Budget)
Figure 1: Validation loss of models trained on low- and high-fre frequency data under varying compute budgets. Two regimes emerge: low-budget favors low low-frequency data, while high-budger favors high-frequency data, showing compute's 's effect on data choice.
The spectral bias of neural networks-favoring learning low-frequency features before higher- frequency ones-has been well documented in prior work [50]. Their findings highlight that models naturally prioritize simpler, low-frequency information early in training. In this section, we build upon this insight to explore the relationship between computational budget and data selection more explicitly. To visualize this connection, we adopt a simple synthetic data generation scheme designed for interpretability.
sin(ww (where the fraction equals when x 0) with additive Gaussian noise. The low-frequency dataset (Model A) 0 points, capturing linear patterns. The high-frequency dataset (Model B) samples uniformly across the domain, preserving spectral complexity. Both datasets contain 50,000 samples each to control for size effects, isolating differences to spectral properties alone. We employ a three-layer fully connected network with ReLU activations; architectural details appear in the appendix. Figure presents validation loss trajectories across varying computational budgets. With limited compute, the low-frequency model demonstrates superior generalization. As compute increases, the high-frequency model achieves better performance, confirming the advantage of richer data when resources permit. These findings establish two distinct regimes in data preference determined by computational constraints, necessitating budget-aware data selection methods that dynamically adapt to available compute-a a central focus of this work.
Specifically, inspired by [50]. data are sampled from the function y
samples exclusively at (izz)
Methods
This section introduces Compute-Aware Data Selection (CADS), single objective that jointly optimizes (i) model parameters and (ii) both how much and which data to process under a fixed compute budget. We first formalise compute-constrainet selection as a bilevel optimization problem and review a direct policy-gradient baseline. The remainder of the section presents two CADS variants: CADS-E, operating at the example level, and CADS-S, operating the source level.

---

4.1 Compute-constrained data selection
To address the limitations of traditional data selection methods, we redefine the problem with the computational budget as an explicit constraint. Given a fixed compute limit C, we aim to identify subset of data- -along with its size that maximizes validation accuracy while ensuring that the total number of sample-processing steps does not exceed C. This can be formalized as the following bilevel optimization problem:
min Evat (0c(m))))) s.t. (m(m) mm, C)2,
where m is binary selection vector indicating which samples to include in training, and Oc represents the model parameters derived from training with budget using the selected subset m. A natural approach to this problem is bilevel optimization [22 13
38 53). To optimize m, we compute the gradient of the validation loss with respect to m, given by V (m 8h 88c 80c 8m Calculating 8m. requires assessing how model parameters vary with m, which can be approached in two ways: implicit differentiation at the optimality condition, requiring costly second-order derivatives, or unrolling the training trajectory and backpropagating, which incurs even higher computational costs. Given our emphasis on efficiency within compute constraints, both methods impractical, especially because the assumption VoLinner (0, m) 0 may not hold. The limited budget C' prevents reaching a true local minimum, leaving the inner gradient non-zero and making implicit differentiation unreliable. Inspired by (74), we propose learnable sampling distribution parameterized by s and optimize s using policy gradients instead of directly optimizing navigate the bilevel problem without relying on gradients from
16
35
80c
m. This approach allows the inner optimization under compute constraints. In this formulation, we define m E {0, 1 a binary mask selecting subset from the training corpus D, with p(m 8) representing the corresponding sampling distribution. Given a strict computational budget of C passes, our objective is identify the sampler that minimizes the expected validation loss after training for exactly C' steps on the masked data:
min Em (Caa)(00(m))) s.t. 0c(m) = Train(m, C)2
where (m)m) represents the model parameters obtained by training on the selected subset m with the fixed compute budget C. Unlike classical bilevel formulations, where the inner problem is solved to convergence, this formulation explicitly constrains training to C steps, closely matching practical real-world training scenarios.
4.2 Bilevel-CADS: policy- gradient baseline
direct yet costly way to optimize Equation 2 is to treat the selector as a stochastic policy and apply REINFORCE. The sampler is factorised over examples:
N
p(m 8)
& TT
s:) I-m
1=1
where s; E [0, is the inclusion probability for example The policy gradient of the outer objective then V. [ (0000 =
[ (m)) V. log s)]
In practice we approximate the expectation with K Monte-Carlo samples:
K
V. B
Σ
(0a(00((m)) V logp(mp 8); my ~ p(m 8)
(5)
K
Each gradient update therefore entails training K independent models for C compute units each, yielding a total cost of K x C. per outer step. With even modest values (e.g. K=5), this baseline quickly becomes prohibitive and motivates the more efficient relaxations introduced in Sections 4.3
4.3 Penalty-based single-level relaxation
To address the prohibitive computational cost of the policy gradient approach, inspired by 22 we reformulate the bilevel problem single-level optimization through penalty-basse relaxation.
5

---

Instead of repeatedly training models to exhaustion for each sampled mask, we introduce an auxiliary variable u that acts as a proxy for the fully-trainee parameters O and penalise the discrepancy between the training losses of O and u.
min C penalty (0, 8) A Ep(mlo) (rall)) a (Ciraa(0, Limn m)) 0,0
(6)
with
u = Train m: K), K C
[m
In this formulation, Ltm m) serves as a target training loss that reflects the performance of model trained for limited number of steps K under the given compute budget
Technical difficulty in solving problem (6). Unlike classical bilevel settings where the inner problem reaches (or approximates) optimality, here the target loss corresponds
intermediate, compute-constrained solution that generally does not satisfy stationary conditions (i.e., non-zero gradients). This makes direct optimization challenging; naively updating the auxiliary variable u jointly with 0 may violate the compute budget constraint or require costly iterative inner optimization. To avoid the need for explicitly unrolling K training steps for each candidate m, we approximate Cirn u. m) with scale-dependent surrogate [(m)) ). which can be efficiently estimated. In practice, (((ml is found be ape-ooapro by a log-linear function of the subset size |ml, capturing how the achievable training loss scales with computational budget. We fit this log-space interpolation using training loss measurements collected at multiple subset sizes, balancing data efficiency and approximation quality. A detailed discussion of the surrogate I(.) is provided in the appendix. Subsequently, substituting the approximation yields the single-level objective:
LoDDS 0, 8) = Eppmle)) (0) + ar afCrm (0, m) - 1( 1(mml)))
Finally, by approximating the penalty objective Cpenalty (6 with the CADS objective CADDS efficiently solve the budget-constrained minimization Problem (6)
7), we
Optimization.
Stochastic estimates of the following gradients are obtained with a single for- ward/backward pass per sampled subset:
V VoDCAD (0, s) Bp(mls) (s) VeCval + 2a 2a(m - ((Iml)) (((mm)))oouu)
(8)
V CC 0, 8) Ep(m)s) [s) [fval + a(Cmm l([ml)))² V. log s)]
(9)
Any first-order optimizer (e.g. Adam) can then update (0, 8) jointly.
4.4 CADS-E: example-level selection
In the example-level approach, CADS learns to select individual examples by assigning a parameter 8; [0, to each example i in the training corpus. We model the sampling distribution p(m[s)
as independent Bernoulli variables for each example as the same distribution defined in 3 The gradient of log pmm]s) with respect to 8; is straightforward:
log logp(m|s)
m1
(10)
as.
8;
8:
During optimization, each subset m. represents binary mask over the training examples. Algorithm 1 provides the pseudocode implementation.
4.5 CADS-S: source-level selection
In the source-level variant, instead of parameterizing selection at the level of individual samples, aggregates samples into broader source groups and assigns weights at this higher level. Specially, the dataset is partitioned into n sources {D:) - and CADS learns sampling ratio vector r E [0, 1)a. We let p(r 8) be an independent truncated Gaussian for each dimension:
A(r 88 ///))
p(r 8)
(11)
σ (1 2 +( (({-))//))

---

Algorithm CADS-E (example-level)
Algorithm 2 CADS-S (source-level)
Require: budget C, initial Oo, 80, subset count
Require: budget C. sources {D,). initial to. 90.
K
subset count K, variance
1: while not converged do
1: while not converged do
2: Sample K subsets {mxx p(mls)
2: Sample K ratio vectors (rk) ~ p(rls)
3: for each m& do
3: for each rą do
4:
Compute Lim (0. m²)
4:
Form Drr by subsampling sources
5:
Compute Lva
5:
Compute Ltrn (0, Dr.))
6:
Compute approximate loss 1([m)))
6:
Compute L (0)
7:
7:
Compute approximate loss 1((Dr,,)
8:
end for
8:
end for
9:
Estimate LCADS using 77
9:
Estimate CCADS using 7
Compute gradients VoL and V,L
10:
Compute gradients VoL and V.L
11:
Update 0 + 0 110 V
11:
Update 0 4- 0 Ve
12:
Update 8 - 1/ vL
12:
Update 8 + s n/ V.
13:
13:
Update variance <- 0.99
14:
end while return s",0" 0"
14:
end while
15:
15:
return s",
where & and & denote the standard normal PDF and CDF. This is truncated Gaussian centered s with scale a. We truncate to [0, 1] to obtain valid sampling values. The denominator normalizes the distribution, ensuring the integral equals 1 after truncation. To stabilize optimization, using o, 0.99' ap- This gradually concentrates probability mass around s leading to consistent sampling results. We visualize the distribution under different and values in the appendix. Algorithm 2 provides pseudo-code of CADS-S.
anneal
Experiments
In this section, present series of experiments aimed at rigorously evaluating the performance and robustness our proposed methods across diverse settings and conditions. Detailed experimental settings and implementation details provided in the appendix.
5.1 Small-scale validation
Our goal is verify that, under fixed compute budget of 20,000 sample usages (20 full-epoch trainings on 1,000-sample MNIST subset), Bilevel-CADS and CADS-E can identify near-optimal training subsets. Specifically, we evaluate four approaches across four initial subset sizes spanning from small to large fractions of the total 1,000 samples (200 to 800 samples); experiments under other compute budgets are presented the appendix. We compare:
Random selection: directly train and test using randomly chosen subsets at these sizes.
PBCS 774):
selects optimal subsets matching the target sizes following original paper settings, then trains and evaluates models.
Bilevel-CADS and CADS-E: start with initial subsets of similar sizes, then execute their respective algorithms to refine and obtain final subsets for model training.
As shown in Table Bilevel-CADS consistently achieves the highest accuracy across all initial subset sizes, significantly outperforming random selection and other methods. Meanwhile, Figure visualizes how the Bilevel-CADS optimization process converges to stable subset size near 500 samples regardless of the initial subset size, indicating robustness and effective subset refinement driven by the compute budget constraint.
5.2 Performance with heterogeneous data sources
Small-scale experiments on CIFAR-10. validate the effectiveness CADS-S, we conducted experiments on the CIFAR-10 dataset. Specifically, reserved 10% of the training set (5,000
7

---

CoreSet Size Convergance with Different Intiaa beations
500
Table I: Accuracy (%) comparison of different data selection methods with various initial subset sizes on MNIST.
500
600
Initial subset size
Method
Average
200
400
600
800
Thitning Epoch
100
Random
88.05
90.62
90.75
89.91
89.83
PBCS
89.81
92.14
92.64
92.98
91.89
Figure 2: Subset size evolution during opti- mization with Bilevel-CADS starting from different initial subset sizes.
CADS-E
91.48
92.28
92.34
92.90
92.25
Bilevel-CADS
92.44
92.90
92.85
93.09
92.80
Sampling Ratio Evolution (Budget: 90,000)
Sampling Ratio Evolution (Bud 135,000)
1.0-
Data Source
Sampling Ratie
Data Source
Clean Data
Clean Data
Sampling
22.5 Noise
41, 2% Nolee
22.5% Nose
45. 52. Noke
67.5% NaGe
67. 7.5 Nolee
90.2% Nolse
50.0% Noiue
50
160
100
Training Iteration
Training Iteration
Sam pling Ratio Evo pollutio (Budget: 180,000)
pling Ratio Evolution (Budget: 225,000)
1.0
1.0
0.8
Dala Source
Sumpling Ratio
0.8
Data Source Clean Date
Clenn Date
Sampling
0.6-
22.5% NaGe
2% Nolse
0.6
22.5% Nole
Nouu
5% Nolse
0.4
0.0
Training Iteration
Training Iteration
Figure 3: Evolution of the sampling ratio over training iterations under different compute budgets: 90,000, 135,000, 180,000, and 225,000 samples respectively.
samples) as a validation set and partitioned the remaining 45,000 samples into five equal groups of 9,000 each, simulating heterogeneous data sources with noise levels of 0%, 22.5%, 45, 55.0% 67.5%, and 90.0% respectively. Our objective was to assess how CADS-S performs compared to training on the single best data source, and the full dataset. The compute budget was varied between 90,000 and 225,000 sample usages.
Key Insights from Fig. 3 It clearly illustrates that, under lower compute budgets, our algorithm predominantly favors clean data, assigning near-zero weights to the noisy data sources. However, with an increase in the compute budget, the algorithm gradually elevates the weights of data sources with lower noise levels.
At compute budget of 225,000 samples, the algorithm incorporates both the clean data and data from the source with 22.5% noise, while also selecting a negligible amount (<0.1) from the source with 45% noise. This phenomenon highlights that as the compute budget expands, data containing some noise can retain significant value in the training process.
In stark contrast, data sources with noise levels greater than 60% are consistently excluded from selection, regardless of the compute budget in play. These findings suggest that as the compute budget grows, the algorithm becomes increasingly adept at leveraging noisy data, emphasizing the importance of diverse data sources in enhancing model performance.
Scaling to larger datasets To further evaluate the scalability and effectiveness of our approach, we conduct experiments on the DomainNet dataset [47], which contains over 0.5 million images across six diverse visual domains: Real, Sketch, Clipart, Painting, Infograph, and Quickdraw. Our setup
8

---

Table 2: Aceuracy (%) comparison of different data selection methods with various compute budget.
Table 3: Accuracy (%) comparison of different data selection methods with various initial subset sizes NomainNet.
Method
Compute budget
Average
Method
Initial sampling ratio (%)
Average
90,000
135,000
180,000
225,000
20
60
80
Best-source
56.31
61.59
63.72
65.08
61.65
Full-dataset
44.34
49.80
53.34
57.03
51.13
Uniform sampling
29.73
37.48
39.70
37.96
36,22
CADS-S
57.05
62.07
65,96
67.22
63.08
CADS-S
44.15
44.22
44.23
44.49
42.27
uses all domains as data sources; however, we treat the Real domain as a high-quality data source and only include a subset of 10,000 samples from it to simulate limited access to the most reliable data. The other five domains are used in full. The total compute budget allocated for training corresponds approximately to training on the full dataset for 10 epochs. Table 3 reports the test accuracy of different data selection methods under varying initial sampling ratios. Our proposed CADS-S method consistently improves over uniform sampling across all ratios. sampling ratios during the optimization process, demonstrating how CADS-5 S dynamically adjusts data source importance over epochs to better allocate the computational budget.
the evolution of
Sampling Ratio Evolution
Sempling ratin dynamics of Alpacas
1.0
202%
01%-
Sampling Rtaio
Real Clipart
Samsiin
65%
0.6
Infograph
22%
Painting
pocs
Quickdraw
30302
33000
0.2
Compusa Sudget
0.0
Figure 5: Sampling ratio dynamics of Alpaca-GPTS and Alpaca datasets under different compute budgets opti- mized by CADS-S.
100
Training Iteration
Figure 4: Sampling ratio evolution on DomainNet
5.3 Performance on instruction tuning tasks
Small-scale experiments. We evaluated our CADS-S approach on instruction fine-tuning tasks using the GPT-2 model [48). The dataset consists of two heterogencous data sources: (i) Alpaca- GPT4 [46). a high-quality dataset from GPT-4-generated instructions, from which we sample 1,000 examples to simulate the rarity of premium data sources in practical scenarios; (ii) Alpaca (57). a larger dataset containing 9,000 examples, representing standard quality data. The total compute budget varies within the range [1 x 10 5 x 10*| sample usages. Other settings remain consistent with those described in Section 5.. As shown in Tab 4 CADS-S consistently outperforms baseline methods, across all compute budgets studied. This validates the proposed method's 's ability to allocate computational resources between heterogeneous data sources to optimize model performance.
Table 4: Perplexity comparison of dif- ferent data selection methods with var- ious compute budget.
Table 5: Perplexity comparison of different data selection methods with various initial subset sizes additional datasets.
Method
Compute budget
Method
Initial sampling ratio (%)
Average
le+4
2e+4
3e+4
5e+4
20
40
60
Best-source
8.01
8.02
8.21
8.87
Full-dataset
8.26
8.01
7.90
7.77
Uniform-sampling
7.90
7.52
7.43
7.39
7.56
CADS-S
8.01
7.92
7.85
7.77
CADS-S
6.97
6.95
6.97
6.90
6.95
Scaling to additional datasets. We further evaluated CADS across 13 instruction-follovii fine-
tuning datasets, sampling 10,000 examples from each, including AlpacaGPT4 [46), SlimOrca (32). Alpaca [57], GPTeacher (58). and multilingual Alpaca variants, totaling around 130,000 samples.

---

Detailed dataset setups and preprocessing are provided in the appendix. As shown in Tab 5 our method consistently outperforms baseline approaches perplexity across different initial sampling ratios, demonstrating its robustness and wide applicability.
5.4
Computational Cost Analysis of Established Baselines
To provide clear comparison of computational efficiency, we establish a unified framework parame- terized by:
C: The total compute budget required for single, standard training run on the full dataset.
This serves as our baseline unit cost.
N: The total number of samples in the full dataset.
T: The number of training epochs, defined as T = C/N.
All computational overheads are measured relative to the baseline cost C of training on the full dataset.
Note on Pre-training Cost: For methods that require a pre- praitrdined model to compute sample-wise statisties (e.g., gradients, forgetting events), we assume the cost of obtaining this model is **0.2C** This represents standard approximation for the early-stage training necessary to yield meaningful statistics, without requiring full convergence.
Table 6: Computational Cost Analysis of Established Baselines.
Method
Total Computational Overhead
Random Selection
C (no additional cost)
Forgetting Scores
1.2C' (0.2C: for pre-training and forgetting computation + C for final training)
GraNd
1.2C (0.2C for pre-training and gradient computation + C for final training)
EL2N
1.2C (0.2C for pre-training und error compulation C for final training)
CADS (Ours)
(5/A + 2-)[C where A umortization factor
Influence Functions
2C++ O(N*) (full training expensive Hessian computations final training)
Data Shapley
11C 101C C (C for final training 10C- 1CC-10CC for Monte Carlo approximation)
Probabilistic Bilevel Optimization
50C- 100C (requires 50- 10-100 outer iterations)
Greedy Coreset
(N2/T 1)C where K coreset size
Summary: CADS achieves superior efficiency among bilevel methods with overhead (5/A + C7) With A=5 amortization, total cost reduces to 2yC, Y < 1. Traditional methods like Forgetting Scores offer moderate 1.2C cost but lack budget-aware optimization and deliver inferior effectiveness. Advanced bilevel methods become prohibitively expensive (50C+), while CADS provides an optimal balance between computational efficiency and budget-aware capabilities.
Note: The core contribution of our work is introducing computational budget constraints into coreset selection, rather than optimizing selection time alone. Once learned, coreset can be reused multiple times across different training scenarios, model architectures, and experiments. Therefore, the computational investment in coreset selection can be amortized over multiple uses, making the selection efficiency secondary consideration compared to the quality of the resulting coreset under budget constraints.
6 Conclusion
We introduced CADS, compute-aware data-selection framework that casts subset choice bilevel optimization under explicit budget constraints. By combining probabilistic reparameterizztion with a Hessian-fres policy-gradien estimator and a penalty-basee surrogate that reduces inner- loop optimization to dhe-dmensiooal loss, CADS efficiently balances data quantity, quality, and distribution. Our example-level (CADS-E) and source-level (CADS-S) variants deliver up to 14.42% accuracy gains and 3-20x speedups over fixed-budget baselines on vision and language benchmarks. Future work will extend CADS to jointly adapt model size, dataset scale, and compute budget for fully addptiv training.
10

---

Acknowledgments and Disclosure of Funding
This work supported by High-Qualin Development Project of Shanghai Municipal Commission of Economy and Informatization (Grant No. 2024-GZ1-RRG/N-220000 Al for Science Foundation of Fudan University (FudanX24A1028), and the National Nature Science Foundation of China (62472097).
References
[1] G. Alain, A. Lamb, C. Sankar, A. Courville, and Y. Bengio. Variance reduction in sgd by distributed importance sampling, arXiv preprint arXiv: /51 .66481, 2015.
[2] A. Albalak, Y. Elazar, S. M. Xie, S. Longpre, N. Lambert, X. Wang, N. Muennighoff, B. Hou,
L. Pan, H. Jeong, et al. A survey data selection for language models, 2024. URL https:/larxiv. org/abs/2402.1688
2022.
[3] T. Ash. C. Zhang, A. Krishnamurthy. J. Langford, and A. Agarwal. Deep batch active learning by diverse. uncertain gradient lower bounds. ArXiv, ahs//990.0066)) 2019.
[4] Y. Bengio, J. Louradour, R. Collobert, and J. Weston. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pages 41 48, 2009.
[5] Y. Cao, Y. Kang, and L. Sun. Instruction mining: High-quality instruction data selection for large language models, ArXiv, abs/2300.0622. 006290, 2023.
[6] G. Cazenavette, T. Wang. A. Torralba, A. A. Efros, and J.-Y. Zhu. Dataset distillation by matching training trajectories. 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10708-10717, 2022.
[7] L. Chen, Li, Yan, Wang, K. Gunaratna, V. Yadav, Tang, V. Srinivasan, T. Zhou, H. Huang, Alpagasus: Training a better alpaca with fewer data, arXiv preprint 200.::::300000701,, 2023.
[8] L. Chen, Y. Ma, and Zhang. Near-optimal first-order oracles. 2023.
convex bilevel optimization with fully
[9] T. Chen, Y. Sun, Q.-. Xiao, and W. Yin. single-timescale method for stochastic bilevel optimization. In International Conference on Artificial Intelligence and Statistics, 2021.
[10] Z. Deng and O. Russakovsky. Remember past: Distilling datasets into addressable memories for neural networks. ArXiv, 0bb/2206.00916,, 2022.
[11] Diddee and Ippolito. Chasing random: Instruction selection strategies fail to generalize. ArXiv, abs/2410.15225. 2024.
[12] Domke, Generic methods for optimization- modeling. In Artificial Intelligence and Statistics, pages 318-326. PMLR, 2012.
[13] L. Franceschi, Donini, P. Frasconi, and M. Pontil. Forward and reverse gradient- based hyperparameter optimization. In International conference on machine learning, pages 1165-1173. PMLR, 2017.
[14] L. Franceschi, Frasconi, S. Salzo, R. Grazzi, M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning, 2018.
[15] S. Ghadimi and M. Wang. Approximation methods for bilevel programming. arXiv: Optimization and Control, 2018
[16] R. Grazzi, I.. Franceschi, M. Pontil, and Salzo. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning, pages 3748-3758. PMIR, R,, 2020.
[17] G. Hacohen and D. Weinshall. On the power of curriculum learning in training deep networks. In International conference on machine learning, pages 2535 2544. PMLR, 2019.
[18] J. Hoffmann, S. Borgeaud, A. Mensch, E. Buchatskaya, T. Cai, E. Rutherford, D. d. L. Casas, L. A. Hendricks, J. Welbl, A. Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203.1 15556, 2022.
[19] M. Hong. H.-T. Wai. Z. Wang. and Z. Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. ArXiv, abs/2000.05170, 2020.
11

---

[20] K. Ji. J. Yang, and Y. Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, 2020.
[21] T. B. Johnson and C. Guestrin. Training deep models faster with robust, approximate importance sampling. In Neural Information Processing Systems, 2018.
[22] J. Kaplan, S. McCandlish, T. Henighan, T. B. Brown, B. Chess, R. Child, S. Gray, A. Radford, J. Wu, and
D. Amodci. Scaling laws for neural language models, arXiv preprint arXiv:2001.0883 2020.
[23] A. Katharopoulos and F. Fleuret. Not all samples are created equal: Deep learning with importance sampling. In International Conference on Machine Learning, 2018.
[24] P. Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A near-optimal algorithm for stochastic bilevel optimization via nombeemm In Neural Information P Processing Systems, 2021.
[25] D. Khashabi, S. Min, T. Khot, A. Sabharwal, O. Tafjord, P. Clark, and H. Hajishirzi. Unifiedqa: Crossing format boundaries with single qa system, ArXiv, abs/2005.00700, 2020.
[26] K. Killamsetty, G. Ramakrishnan, A. De. and R. Iyer. Grad-match: Gradient matching based data subset selection for efficient deep model training. In International Conference on Machine Learning, pages 5464 (6645547, PMLR, 2021.
[27] K. Killamsetty, D. Sivasubramanian, G. Ramakrishnan, R. 1. U. of Texas at Dallas, I. of Technology Bomhay Institution One, and I. Two. Glister: Generalization based data subset selection for efficient and robust learning. In AAAI Conference on Arrificial Intelligence, 2020.
[28] P.-N. Kung, F. Yin, D. Wu, K.-W. Chang, and N. Peng. Active instruction tuning: Improving cross-task generalization by training on prompt sensitive tasks. In Conference on Empirical Methods in Natural Language Processing, 2023.
[29] Kwon, Kwon, S. Wright, and R. Nowak. fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning, pages 18083-18113, PMLR, 2023.
[30] M. Li, Y. Zhang, Z. Li, J. Chen, L. Chen, N. Cheng, J. Wang, T. Zhou, and J. Xiao. From quantity to quality: Boosting Ul performance with self ceff-guided data selection for instruction tuning. In North American Chapter of the Association for Computational Linguistics, 2023.
[31] W. Lian et al. Slimorea: An open dataset of gpt-4 augmented flan reasoning traces, with verification, 2023.
[32] W. Lian, G. Wang, B. Goodson, E. Pentland, A. Cook, C. Vong, and "Teknium". Slimorca: An open dataset of gpt-4 augmented flan reasoning traces, with verification, 2023.
[33] H. Liu, K. Simonyan, and Y. Yang. Darts: Differentiable architecture search. ArXiv, abs/ 806.09055 2018.
[34] W. Liu, W. Zeng, K. He. Y. Jiang, and J. He. What makes good data for alignment? comprehensive study of automatic data selection in instruction tuning. ArXiv, 1256155521...5 2023.
[35] Lorraine, Vicol, and D. Duvenaud. Optimizing millions hyperparameters by implicit differentiation. In International conference on artificial intelligence and statistics, pages 1540-1552 15520 PMLR, 2020.
[36] I. Loshchilov and F. Hutter. Online batch selection for faster training of neural networks. abs/1511 116643,,,333,1111 2015.
ArXiv.
[37] K. Lu, H. Yuan, Z. Yuan, R. Lin, J. Lin, C. Tan, and C. Zhou. #instag: Instruction tagging for analyzing supervised fine-tuning of large language models. ArXiv, 000//3308.00744, 2023.
[38] D. Maclaurin, D. Duvenaud, and R. Adams. Gradient-bused hypepprrmcteee optimization through reversible learning. In International conference on machine learning, pages 2112-2122. PMLR, 2015.
[39] M. Marone and B. V. Durme. Data portraits: abs/2303.03919, 2023.
Recording foundation model training data. ArXiv,
[40] B. Mirzasoleiman, A. Badanidiyuru, and A. Karbasi. Fast constrained submodular maximization: Person- alized data summarization. In International Conference on Machine Learning, pages 1358-1367. PMLR, 2016.
[41] B. Mirzasoleiman, J. A. Bilmes, and J. Leskovec. Coresets for data-efficient training of machine learning models. In International Conference Machine Learning, 2019.
12

---

[42] Y. Oren, S. Sagawa. T. B. Hashimoto, and P. Liang. Distributionally robust language modeling. ArXiv, abs/1909.02066 2019.
[43] R. Pan, J. Zhang. X. Pan, R. Pi, X. Wang, and T. Zhang. Scalebio: Scalable bilevel optimization for Ilm data reweighting, arXiv preprint arXiv:2406. 19976, 2024.
[44] M. Paul, Ganguli, and G. K. Dziugaite. Deep learning on a data diet: Finding important examples early in training. Advances in neural information processing systems, 34:20596-20607, 2021.
[45] F. Pedregosa. Hyperparameter optimization with approximate gradient. International conference on machine learning, pages 737-746. PMLR, 2016.
[46] B. Peng, C. Li, P. Hc, M. Galley, and J. Gao. Instruction tuning with gpt-4. ArXiv, abx/2304.032777, 2023.
[47] X. Peng, Q. Bai, X. Xia, Z. Huang, Saenko, and B. Wang. Moment matching for multi-source domain adaptation. In Proceedings of the IEEE International Conference on Computer Vision, pages 1406-1415, 2019.
[48] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever. Language models are unsupervised multitask learners. 2019.
[49] J. W. Rae, S. Borgeaud, T. Cai, K. Millican, J. Hoffmann, F. Song. J. Aslanides, S. Henderson, R. Ring. S. Young, E. Rutherford, T. Hennigan, J. Menick, Cassirer, R. Powell, G. van den Driessche, I.. A. Hendricks, M. Rauh, P.-.. Huang, A. Glaese, Welhl, S. Dathathri, Huang, Uesato, J. F. Mellor, I. Higgins, A. Creswell, N. McAleese, A. Wu, E. Elsen, S. M. Jayakumar, E. Buchatskaya, D. Budden, E. Sutherland, K. Simonyan, M. Paganini, L. Sifre, L. Martens, X. L. Li. A. Kuncoro, A. Nematzadeh, E. Gribovskaya, D. Donato. A. Lazaridou, A. Mensch, J.-B. Lespiau, M. Tsimpoukelli, N. K. Grigorev. D. Fritz, T. Sottiaux, M. Pajarskas, T. Pohlen, Z. Gong, D. Toyama, C. de Masson Autume, Y. Li, T. Terzi, V. Mikulik, Babuschkin, A. Clark, D. de Las Casas, A. Guy, C. Jones, J. Bradbury, M. G. Johnson, B. A. Hechtman, L. Weidinger, I. Gabriel, W. S. Isaac, E. Lockhart, S. Osindero, L. Rimell, C. Dyer, O. Vinyals, K. W. Ayoub, J. Stanway. L. L. Bennett, D. Hassabis, K. Kavukcuoglu, and G. Irving. Scaling language models: Methods, analysis & insights from training gopher. ArXiv, abs/21 12.1 1446,, 2021.
[50] N. Rahaman, A. Baratin, D. Arpit. F. Dräxler, M. Lin, F. A. Hamprecht, Y. Bengio, and A. C. Courville. On the spectral bias of neural networks. In International Conference on Machine Learning, 2018
[51] O. Sener and Savarese. Active learning for convolutional neural networks: A corc-set approach. In International Conference on Learning Representations, 2018
[52] B. Settles. Active learning literature survey. 2009.
[53] A. Shaban, C.-A. Cheng, Hatch, and Boots. Truncated back- pack-propagation for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1723-177 1732. PMLR, 2019.
[54] M. Shen. Rethinking data selection for supervised fine-tuning. ArXiv, abs/2402.06094, 2024.
[55] P. Soviany, R. T. Ionescu, P. Rota, and N. Sebe. Curriculum learning: A survey. International Journal of Computer Vision, 130:1526 1565, 2021.
[56] D. Sow. K. Ji, and Y. Liang. On the convergence theory for free bilevel algorithms. In Neurul Information Processing Systems, 2021.
[57] R. Taori, I. Gulrajani, T. Zhang, Y. Dubois, Li, C. Guestrin, P. Liang, and T. B. Hashimoto. Stanford alpaca: An insllwction-followinng laaa model. /ttp::::/gttaab...c///aaaaaaaaaa 2023.
[58] Teknium. Gpteacher: General instruction dataset. httpp:///agiigggaeecc///atttttte GPTeacher-Geneen Instruct 2023. Accessed: 2025-05-07.
[59] Toneva, A. Sordoni, R. T. des Combes, A. Trischler, Y. Bengio, and G. J. Gordon. An empirical study of example forgetting during deep neural network learning. ArXiv, abs/18 hhs//882.00119) 2018.
[60] T. Wang, J.-Y. Zhu, A. Torralba, and A. A. Efros. Dataset distillation. arXiv preprint arXiv:1811.1099 2018.
[61] K. Wei, R. Iyer, and J. Bilmes. Submodularity in data subset selection and active learning. In International conference machine learning, pages 1954-1963. PMLR, 2015.
13

---

[62] T. Xia. B. Yu. K. Dang, A. Yang. Y. Wu, Y. Tian, Y. Chang, and J. Lin. Rethinking data selection at scale: Random selection is almost all you need. ArXiv, abs/2410.09335, 2024.
[63] X. Yang, S. Nie, I.. Liu, S. Gururangan, U. Kar, R. Hou, M. Khahsa, and Y. Mao. Diversity-driven data selection for language model tuning through sparse autoencoder. ArXiv, abs/2502.1405U 2025.
[64] Y. Yang, S. Mishra, J. Chiang, and B. Mirzasoleiman. Smalltolarge (s21): Scalable data selection for fine- tuning large language models by summarizing training trajectories of small models. ArXiv, abs/2403.07384, 2024.
[65] Y. Yang. P. Xiao, and K. Ji. Achieving o 1.5) complexity in hessian/faccoian--ne free stochastic bilevel optimization. ArXiv, abs/2312.03807,, 2023.
[66] M. Ye, B. Liu, S. J. Wright, Stone, and Q. Liu. Bome! bilevel optimization made easy: simple first-order approach. ArXiv, abs/2209.08709) 2022.
[67] J. O. Yin and A. M. Rush. Compute-consttraneed data selection. ArXiv, abs/2410.16208. 2024.
[68] R. Yu, S. Liu, and X. Wang. Dataset distillation: A comprehensive review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16-15507 2023.
[69] J. Zhang, Y. Qin, R. Pi, W. Zhang, R. Pan, and T. Zhang. Tagoos: Task-agnostic gradient clustered coresct selection for instruction tuning data. ArXiv, abs/2407.15235. 2024.
[70] H. Zhao, M. Andriushchenko, F. Croce, and N. Flammarion. Long is more for alignment: A simple but tough-to-beat baseline for instruction fine-tuning. ArXiv, abs/2402.04833, 2024.
[71] Y. Zhao, L. Du, X. Ding. Y. Ouyang, H. Wang, K. Xiong. J.-F. Gao, Z. Sun, D. Xu, Y. Qing. D. Li, B. Qin, and T. Liu. Beyond similarity: gradient-based graph method for instruction tuning data selection. ArXiv, abs/2502.1 11062, 2025.
[72] C. Zhou, Liu, Xu, S. Iyer, Sun, Y. Mao, X. Ma, Efrat, Yu, L. Yu, Zhang, G. Ghosh, M. Lewis, L. Zettlemoyer, and O. Levy. Lima: Less more alignment. ArXiv, abs/2305. 1206, 2023.
[73] X. Zhou, Y. Lin, R. Pi, W. Zhang, Xu, P. Cui, and T. Zhang. Model agnostic sample reweighting out-of-distribution learning. In International Conference on Machine Learning, pages 27203-27221. PMLR, 2022.
[74] X. Zhou, R. Pi, W. Zhang, Y. Lin, Z. Chen, and T. Zhang. Probabilistic bilevel coreset selection. In International conference on machine learning, pages 27287-27302. PMLR, 2022.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the main claims of the paper, including the key contributions and scope of the work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have included separate "Limitations" section in the appendix.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

The paper clearly states all assumptions for each theoretical result and provides complete and correct proofs.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
The paper provides detailed descriptions of the experimental setup.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

reproducible, they Answer: [Yes]
Justification:
we provide detailed instructions for accessing the data and code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/ public/guides. http///ooeeeeaaeiinnnnneeeeeeeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https for more details.
/ //nip. http:c/cpplllgggiuieee httgg//ddee//eubbbmiiimmmm
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper provides detailed training and test configurations in the Appendix understand the results.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All small-scale experiments have considered statistical significance. Due to computational resource limitations, large-scale experiments could not provide full statistical significance analysis.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
17

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide detailed information on the computing resources used for each experiment appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported paper (e.g., preliminary or failed experiments that didn't It make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The research fully adheres the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discuss both potential positive societal impacts and negative societal impacts of the work in the appendix.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system Iearns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not involve the release of models or datasets that pose high risk of misuse or dual-use. Therefore, no specific safeguards were necessary for responsible release.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We provide detailed information in the appendix about all existing assets used in the paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
19

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets introduced in the paper.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details the dataset/code/mmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
The paper does not involve crowdsourcing experiments or research with human subjects; therefore, no participant instructions, screenshots, compensation details applicable.
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to NeurlPS Code of Ethics, workers involved data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification; The paper does not involve research with human subjects or crowdsoureing, so there were no risks to participants and no Institutional Review Board (IRB) approvals were required.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
20

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core methods developed this research do not involve the use of large language models (LLMs) as important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
21

---

Supplemental Material: Computational Budget Should Be Considered in Data Selection
In this appendix, we provide comprehensive additional materials to supplement the main text. The contents include:
Broader impacts (Section) A discussion on the broader implications of our research.
Experimental setting and implementation details (Section R): Detailed information on the experimental settings and implementation details.
Log-linear surrogate of compute-constrained training loss (Section C): Explanation of
approximating Lrn u, m) by the scale-dependent surrogate ((m)). its log-space interpola- tion, and fitting procedure.
Visualizations on truncated Gaussian distribution (Section D): Detailed visualization on the truncated Gaussian distribution.
Additional experimental results (Section E MNIST experiments varying the total com- pute budget to compare random, PBCS, CADS-E, and Bilevel-CAAD The results show that method consistently achieves the highest accuracy (Table D).
Time efficiency analysis (Section F): Benchmarking of average training and sampling
runtimes on representative hardware.
Scalability to other bilevel optimization problems (Section G Discussion on the ap- plicability conditions, loss estimation accuracy, and validation framework for applying CADS new domains.
Limitations and future work (Section Analysis of the limitations in our current framework, and plans for future improvements.
Licenses for existing assets (Section I: Acknowledgment and respect for the licenses and terms of use of datasets and code libraries utilized in research.
A Broader impacts
This work introduces CADS, compute-awar data selection algorithm that dynamically adapts the training data budget according to available computational resources. By optimizing data efficiency relative to compute constraints, CADS significantly reduces the computational overhead of training deep learning models without sacrificing performance. This advancement enables more accessible and environmentally sustainable machine learning research and deployment, particularly in scenarios constrained by limited hardware resources. The method's potential to lower energy consumption during model training aligns with broader community efforts towards greener AI, contributing to reductions in carbon footprint and operational costs. Additionally, CADS facilitates democratization of deep learning by empowering researchers and practitioners with modest resources to train competi- tive models. However, as with any automation that accelerates model training, there exist potential risks, including the possibility of speeding up the development of models with harmful biases, privacy vulnerabilities, or malicious intent if not applied responsibly. We stress the importance of ethical use and compliance with community norms and regulatory standards when deploying such techniques. Overall, CADS represents a step forward in efficient and responsible machine learning practices, promoting sustainability and equitable access within the deep learning community.
B Experimental setting and implementation details
In this section, we detail the protocols and implementation specifics underlying all our evaluations. All experiments were run on a single machine equipped with an NVIDIA A100 80 GB GPU under CUDA 12.6 and NVIDIA driver 470.199 199.02, using PoTor 2.
22

---

B.1 Exploratory experiment on spectrum bias
To isolate the effect of spectral content on generalization, we generate two synthetic datasets with identical noise level σ = 0.1 but different frequency composition.
Data generation. We sample N 50,000 inputs for each group; for the low-frequency dataset (Group A) we set = + (N, and for the high-frequency dataset (Group B) we set y = sin (xa) + (0, A fixed validation set of 10,000 points is used to track generalization error.
Model and training. Each model is a three-layer MLP (100-100 hidden units, ReLU), We train for 160 steps using Adam (learning rate 3 10-4) and batch size 1000. After every parameter update, we compute the MSE on the validation set and log the result. The different positions on the x-axis in Figure correspond these intermediate results recorded during the training process.
B.2 Small-scale validation
We validate CADS on a reduced-scale MNIST classification task using a simple convolutional network. All experiments use fixed training set of 1,000 examples and batch size 1,000. We optimize under epoch-based budget of 20 epochs. The selection parameters initialized as s e 1, the bilevel problem with Adam for both the network parameters 0 (learning rate 5 x 10-3) and the selection weights (learning rate 5 10-2). The outer loop runs for 300 iterations with variance reduction and gradient clipping enabled.
E RIPI {0.2, 0.4, 0.6, 0.8}, 1 II is the all-ones vector. We solve
Network architecture. We employ simple convolutional model: convolutional layers with 5 x 5 kernels and channel counts {32, 64), each followed by ReLU and optional x 2 max-pooling: the feature map is flattened (4 4 64 = 1024 units) and passed through fully connected layer of 128 units with ReLU; final linear layer outputs class logits. Input normalization by fixed mean and standard deviation is applied when enabled. No dropout used.
B.3 Heterogeneous data sources: small-scale experiments CIFAR-10
We evaluate CADS-S on a grouped CIFAR-10 variant with five demographic groups and up to 90% label noise. All experiments epoch-based compute budget of 2 to 5 epochs. The selection parameter is initialized to 0.5 IPl, We solve the bilevel problem with Adam for both network parameters (learning rate x 10 10-3) and selection weights (leamiin rate x 10-3), over 100 outer iterations with variance reduction and gradient clipping. We adopt the standard ResNet-18 backbone for all runs.
the full training set (no limit) with batch size 256. We allocate
B.4 Heterogeneous data sources: scaling to larger datasets
We evaluate CADS-S on DomainNet with 6 groups using the full training and batch size 1024. We allocate an epoch-based compute budget of 10 epochs. The selection parameters E RIP) are initialized as s = v 1, V E {0.2, 0.4, 0.6, 0.8}. 1 E RI is the all-ones vector. We solve the bilevel problem with Adam for both network parameters (learning rate 10-3) and selection weights (learning rate 5 x 10-2), over 100 outer iterations with variance reduction and gradient clipping. We adopt the standard ResNet-18 backbone for all runs.
DomainNet dataset. DomainNet comprises over 0.5 million images across six visual domains: Real, Sketch, Clipart, Painting, Infograph, and Quickdraw (As shown in Fig. 6 our setup, we treat the Real domain high-quality source but include only 10,000 samples from it to simulate limited access; the other five domains are used full.
B.5 Instruction tuning tasks: small-scale experiments
We evaluated our CADS-S approach on instruction fine-tuning tasks using the GPT-2 model [48]
The dataset consists of two heterogeneous data sources: (i) Alpaca-GPT4 [46]. a high-quality dataset from
instructions, from which sample 1,000 examples to simulate the rarity
23

---

(a) Real
(b) Sketch
(c) Clipart
Ond
(d) Painting
(e) Infograph
(f) Quickdraw
Figure 6: Representative examples from the DomainNet domains: Real, Sketch, Clipart (top row);
Painting, Infograph, Quickdraw (bottom row).
of premium data sources in practical scenarios; (ii) Alpaca [57], larger dataset containing 9,000 examples, representing standard-quality data. The total compute budget varies within the range [1 x 10 5 x 104] sample usages. The selection weight s is initialized to 0.5 1 1 We solve the bilevel problem with AdamW for both model parameters 0 (learning rate 1 10 and selection weights 8 (learning rate x 10-2). We adopt the GPT-2 backbone with maximum sequence length 1024 for all runs.
Data preprocessing. Raw instruction- response samples are loaded from JSON or JSONL files and consolidated into a flat record list. A pretrained tokenizer is initialized and extended to include five special markers: padding token, end-of-sequence token, and three role-demarcation tokens (<lsystemi>, <luserl>, <lassistantis). Each record is then serialized into a single text sequence by:
1. Emitting the system token, followed by the system-level directive, and two line breaks.
2. Emitting the user token, followed by the instruction text (and any optional input), and two line breaks.
3. Emitting the assistant token, followed by the target response, and terminating with the end-of-sequence token.
The concatenated text is first tokenized without truncation measure its length; any example that exceeds the maximum allowed token count is discarded. The remaining examples are split into training, validation, and test subsets according to either explicitly provided sizes or default 90/5/5 ratio. At training time, each sequence is tokenized with truncation to the maximum length, producing token identifiers and attention masks. All token positions corresponding segments are assigned an ignore index the label sequence so that only essistant-respon contribute the loss. A bespoke collation routine then pads every batch to the length of its longest sequence, using the padding token for inputs, zeros for masks, and the ignore index for both prompt and padding positions in the labels.
the system and user tokens
B.6 Instruction tuning tasks: scaling to additional datasets
We extended our evaluation to 13 distinct instruction-following corpora, drawing ten thousand examples from each. These included the original AlpacaGPT4 benchmark (46), the SlimOrea set 32), the Alpaca collection [5]. the GPTeacher suite 58), and nine multilingual variants of the Alpaca data.
24

---

In total, approximately 130 000 samples were processed with the identical tokenization, formatting, filtering. and batch- batch-collation pipeline described above. The complete list of datasets, along with their sizes and licenses, is summarized in Table 7
Dataset
Size
License
AlpacaGPT4
46
52K
Apache-2.0
SlimOrea
32
518K
MIT
GPTeacher
58
89K
MIT
Alpaca [57
52K
Apache-2.0
Alpaca-e
52K
CC-BY-4.0
Alpaca-d
50K
Apache-2.0
Alpaca-j
52K
CC-BY.NC-SA-4.0
Alpaca-kd
50K
CC-BY-NC-4.0
Alpaca-r
30K
CC-BY-4.0
Alpaca-it
52K
CC-BY-NC-SA-400
Alpaca-f
55K
Apache-2.0
Alpaca-zh
49K
CC-BY-4.0
Alpaca-p
10
52K
CC-BY-NC-4.0
Table Summary of high-quality instruction-tuning datasets (top) and multilingual Alpaca variants
(bottom).
C Log-linear surrogate of compute-constrainee training loss
C.1 Data Collection
We collect estimates of the K-step ("compute-constraieed"" training loss Lim (0; [ml) at a range of subset sizes mm/ By default we choose nine relative fractions (0.01, 0.02, 0.05, 0.1, 0.3, 0.3, 0.5, 0.7,0.9) of the full training set (clamped to at least 50 examples on MNIST or the configured batch-size otherwise). For each size we train for total compute budget N (so that each inner training run sees roughly the same total number of gradient steps), and record the final training loss. We then summarize each size by its empirical E,
C.2 Surrogate model choice
We set 10 and fit the transformed log-loss log (1(mm] + +e) using two options:
Linear: log ((((m) + ++) = k |m] + b.
Cubic spline interpolation: fit a cubic spline through the points (Imy). log(I((m,))) (11))+2)) +c)).
yielding piecewise-cubic function f([ml). f(mm).
Bacpiiaa-ppt_ddd0 de
Instruct-
25

---

K-step Reachable Loss Approximation Comparison for All Models
10
linear (fit)
100
interpolation (fit)
ksstep reachable loss L([m)
Test data
10-1
Train data
10-2
10-3
10
10-
10-6
200
400
600
800
1000
Subset size [ml
Figure 7: All-models comparison the K-step reachable loss as a function of subset size |m]. Blue circles denote observed mean loss training subsets; gray squares denote observations held-out test subsets. Solid curves show the fitted approximation functions for each candidate model. The vertical axis is plotted on logarithmic scale.
After fitting in log-space, we recover the original-scale surrogate via ((ml)) = exp exp(f((ml) Fig- ure overlays these fitted curves on the empirical training-love measurements. The cubic spline interpolation achieves noticeably lower MSE, motivating its use when maximum fidelity is desired, while the linear surrogate offers simplicity and closed-form gradient. Since CADS never computes ml] we exclusively employ the cubic spline interpolation due to its superior fit.
C.3 Analysis of Sampling Efficiency for Loss Estimation
To evaluate the sample efficiency of our loss estimation method, we conducted an analysis to determine the minimum number of subset samples (K) required for reliable interpolation.
Experimental Design On the CIFAR-10 10 dataset with ResNet-18 18 model, we evaluated the loss estimator's performance under varying sampling densities, where K E {4, 5, 7, 8). For each value of K, we sampled K distinct subset sizes to train corresponding models, yielding K pairs of (size, tested each fitted
loss) data points. These points were used to fit the loss estimator. Subsequently, estimator on a held-out set of 100 separately sampled (size, loss) pairs to measure its interpolation accuracy.
The results, summarized in Table demonstrate that the estimator's performance improves significantly up K sampling points, after which the returns diminish. This indicates that our method is highly sample-efficient Notably, increasing K further (e.g.. K = 7) can slightly degrade performance, likely due to overfitting the estimator to a specific set of sample points, which hinders its ability to generalize to unseen subset sizes.
Results
D Visualizations on truncated Gaussian distribution
In this section we provide visual intuition for the source-level sampling prior by plotting the truncated Gaussian density p(r s) on the interval [0, for variety of center values s and scales σ. Figures g and 10 iillustrae how annealing concentrates the distribution around its mean.
26

---

s-0.0 ev0.3
5-6.0 ow2.30
Figure 8: Sampling prior p(r s) on [0, 1] for various center values 8 with scale 0.1.
a01.00 e1
1-6.43 av1
Sx ewi ES
Seb owt
Figure 9: Sampling prior p(r 8) on [0, 1] for various center values with scale = 0.05.
19
4.
p=1.00
191.00
10
13
Figure 10: Sampling prior prr s) [0, 1] for various center values with scale 0.01.
27

---

Table 8: Mean Square Error (MSE) of the loss estimator with respect the number of sampling
points (K). Performance saturates at K = 5, demonstrating high sample efficiency.
Sampling Points (K) Mean Square Error
4
0.057668
5
0.016326
6
0.018594
0.020031
8
0.017905
E
Additional experimental results
Additional result on MNIST The purpose of this experiment is investigate the effect of compute budget on data selection within the MNIST dataset. We vary the compute budget terms total forward counts (IO 000, 20 000, 50 000 and 100 000). At each budget we compare four sampling strategies-random, PBCS, CADS-E and our Bilevel-CADS, As shown Table our Bilevel-CADS consistently outperforms all baselines in all compute budgets.
Table Results on MNIST with various compute budgets.
Compute budget
Method
Average
10,000
20,000
50,000
100,000
Random
87.36
88.05
87.71
87.24
87.59
PBCS
89.61
90.48
90.96
90.41
90.37
CADS-E
90.62
91.48
92.45
93.17
91.93
Bilevel-CADS
90.70
92.44
93.09
93.61
92.46
F Time efficiency analysis
F1
Computational complexity compare to standard bilevel optimization
We compare the per-iteration cost of our single-epoch inner loop against the full-training inner loop used in bilevel-CADS, and then account for the one-time cost of fitting the loss estimator [(mm).
Let
D be the size of the training set,
Tep = O(IDl) the cost of one full epoch (one forward+backward pass),
the number of epochs used by bilevel-CADS in its inner optimizer.
K the number of subsets sampled per outer iteration,
m| the average subset size,
M the total number of outer iterations in a run.
Bilevel-CADS inner solve (per outer step)
Costistevel
K x X O(KN (P).
Our CADS-E/S inner loop (per outer step, ignoring estimator)
base.
K Tep = O(KID))
Estimator fitting overhead To fit the mapping (((ml) we train 8 models for N epochs each (As detailed in D) incurring one-time cost
Costest
8 x N x To
28

---

Amortized over M outer steps, this adds
Costest
8 N Tep
M
M
to each iteration.
Total CADS cost (amortized)
N Tep
COSTCCADS = K Top +
Top K
SN 3
M
Speed-up factor
Costbilevel
K C Tep
KN
CoSTCADS
Tep [K +
S&N
K
3
In our experiments K = and M = 100, giving
Costbilevel
COST
1/N 4/N+0.M 0.016
In practice, larger N yields even greater speed-up.
F.2 Empirical Validation
We measure end-to-end wall-clock time of bilevel-CADS and CADS-E on MNIST as function of compute budget C' (total epochs). We sweep C' over {5, 50, 100, 200, 500, 1000, 2000, 5000} and record the runtime of each method under identical hardware. Figure [T] confirms roughly linear scaling for both methods, with CADS-E exhibiting much smaller slope.
F.3 Analysis Selection Algorithm Runtime
A potential concern regarding our method is that the runtime of the selection algorithm may scale with the number sampled subsets (K), which could offset the computational efficiency gains. We address this concern by highlighting several key aspects of our approach.
Minimal Sampling for Practical Implementation Our policy gradient approach for coreset selection requires only a small number of samples (K) to ensure training stability. For instance, the comparable PBCS method 774 utilizes K 1 for all its experiments. Our results show that using K = 2 is sufficient to achieve strong performance while maintaining high computational efficiency. cases where smaller K values might lead higher gradient variance (e.g., in more complex problems), this can be mitigated using established variance reduction techniques. A common approach is to use a self-critical baseline, which adjusts the reward signal as follows:
K
((S.) L(S))
Σ C(S)). K
1
(12)
Amortized Cost of Coreset Selection It is important to emphasize that the core contribution of this work is the introduction of computational budget constraints into the coreset selection process, rather than optimizing the selection runtime itself. Once generated, a coreset is a reusable asset that can be applied across various training scenarios, different model architectures, and subsequent experiments. Consequently, the initial computational investment in the selection process is amortized over these multiple uses. This makes the selection efficiency secondary consideration compared to the quality and utility of the resulting budget-constrained coreset.
G Scalability to Other Bilevel Optimization Problems
CADS is designed to address fundamental challenge in bilevel optimization: scenarios where the inner-level problem's convergence is hindered by computational budget constraints. Many practical bilevel problems suffer from this issue, where traditional methods that assume unlimited computational resources for inner-level convergence often fall short. We have also successfully applied a CADS-like method to resource-intensive diffusion models, demonstrating its potential beyond the scope of this work. The scalability of CADS to other bilevel problems primarily depends on the following factors:
29

---

Runtime vs Compute Budget on MNIST
bilevel-CAD CADS
CADS-E
10000
Woll-cood <lock time (5)
8000
6000
4000
2000
2000
3000
5000
Compute budget (epachs)
Figure 11: Wall-clock runtime vs. compute budget C' for Ailevel-CADS (dashed) and CADS-E (solid), MNIST.
Applicability Conditions The core premise of CADS is most relevant when the inner-level op- timization is computationally expensive and cannot be fully converged. Our approach provides a framework to handle such resource-constraing scenarios, which are common in real-world applica- tions but often overlooked by conventional methods.
Loss Estimation Accuracy The effectiveness of CADS new domain hinges on the accuracy of the loss estimator. As demonstrated in our analysis of loss estimation generalization, the proposed estimator maintains relatively stable predictive performance across the diverse experimental domains explored in this paper. This stability suggests that similar performance may be achievable in other domains with comparable data characteristics.
Validation Framework for New Domains To adapt CADS to new bilevel optimization problem, we propose the following validation framework:
Loss Estimator Generalization Assessment. Before full-scale implementation, it is crucial to assess whether the data distribution characteristics of the new domain can be reliably predicted. This can be achieved by conducting experiments similar to our generalization evaluation to validate the feasibility of loss estimation.
Domain-Adaptive Estimator Design. While our current estimator is effective for data selection problems, different bilevel scenarios might benefit from specialized estimators. The architecture of the loss estimator should be tailored to the specifie requirements and data characteristics of the target domain to ensure optimal performance.
H Limitations and Future Work
Similar to existing methods, our approach based on standard training methodologies, but in the industry, large language models incorporate numerous engineering optimizations. Consequently. our budget is likely proportional to theirs, rather than perfectly aligned. For instance, in sparse mixture of experts (MoE), the budget is determined by model capacity and routing complexity, whereas measure performance by the number of forward passes. This measurement may not fully correspond with the budget metrics used in industry. However, we firmly believe that our methods are applicable in industrial contexts; we simply need to adjust the budget measurements accordingly.
I Licenses for existing assets
We rely on several public datasets and open-source libraries, and all original authors properly credited and their licenses fully respected. The vision benchmarks we employ are MNIST (public domain), CIFAR-10 (MIT License) and DomainNet (CC BY-NC-SA 4.0). Our instruction-tuning
30

---

corpora are summarized in Table 7 with licenses ranging from Apache 2.0 to various Creative Commons and MIT terms. On the software side, we build atop PyTorch and torchvision (BSD 3-Clause), SciPy (BSD), and HuggingFace Transformers (GPT-2, Apache 2.0); ResNet models are taken from torchvision (BSD 3-Clause). We confirm that every dataset and code dependency used in accordance with its license and citation requirements.
31


Reviews:
[{"review_id": "joCR1U4EwG", "reviewer": "Reviewer_TtXp", "summary": "The paper proposes a two-step algorithm to incorporate the computational budget of a training model in  their data selection procedure. It advocates to keep an eye on the compute budget during data selection and not treat it as a fixed hyper parameter. I like the hypothesis of the paper, but I have some concerns over the overall exposition and validation of the approach.", "questions": "- Why the first step needs Hessians computation?\n- How is optimality defined in the second step?\n- How can one know how much time a model would need to train? \n- It is not clear to what the compute budget refers to? Is it the compute budget for the model or the compute budget for the data mining process?\n- What computational overhead the algorithm adds on top of the computational cost of training a network?\n- Can you provide more validations on generative models showing different metrics, how they get affected by the compute budget?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper raises a very important aspect of the training process. Computation budget should be part of the training process and the data selection\n- Some initial results are shown on the MNIST dataset, and some other datasets to validate the hypothesis.\n\n\nWeakness:\n- The text did not make it clear what does compute budget refers to\n- The two-step algorithm in the introduction misses the context, like why Hessians are needed in the first step, what optimality refers to in the data selection.\n- The paper seems to be motivated based on the observation of spectral bias from Rahman et al. This is insightful but does that generalizes to different problems in machine learning?\n- Solid validation is missing, for example, how the generalization of a network gets affected with the compute budget (in terms of FID scores). \n\nOverall I think the idea is not sufficiently validated.", "was_revised": true, "final_justification": "My major concern (and other concerns) regarding the overhead introduced by this paper is properly addressed.\n\nI think the paper has a strong hypothesis, and after checking the other rebuttals and reviews from other reviewers, I feel that the paper is going to make a good contribution. \n\nI am now borderlin positive and will rely on fellow reviewers to decide whether this paper is above NeurIPS bar or not. \nWhy borderline, is due to the heavy overhead of the proposed approach. But I don't think that is a major bottleneck and future research can develop better strategies to amortize this cost.", "rebuttal": "**We sincerely thank Reviewer TtXp for the constructive feedback.** Below we provide point-by-point responses:\n\n---\n\n### **W1&Q4: Is it the compute budget for  model training or data mining process?**\n\n**The compute budget C refers specifically to model training, not data mining process.** It is defined in Section 4.1 (lines 175-181). To be precise, our method is formalized as:\n\n$\\min \\mathcal{L}_{val}(\\theta_C(m)) \\quad \\text{s.t.} \\quad \\theta_C(m) = \\text{Train}(m,C)$\n\nwhere $C$ represents the computational cost for training the model on the given subsets, which **equals to #iteration*batch-size**.\n\n\n---\n\n### **W2&Q1&Q2: Why Hessians are needed in the first step, what optimality refers to in the data selection.**\n\nWe think your concern is based on our statement in lines 61 to 62.\n\n### **[Why Hessians are Required]**\nThe Hessian requirement in bilevel optimization is extensively studied in prior work [r1-3]. Our bilevel formulation follows the standard structure:\n\n- **Inner**: $\\theta^{\\*}(m) = \\arg \\min_{\\theta} \\mathcal{L}_{\\text{train}}(\\theta, m)$ \n- **Outer**: $\\min_{m} \\mathcal{L}_{\\text{val}}(\\theta^{\\*}(m))$\n\nTo optimize the outer loop, we compute $\\nabla_{m} \\mathcal{L}_{\\text{val}}(\\theta^{*}(m))$ using chain rule: \n\n$$\\nabla\\_{m} \\mathcal{L}\\_{\\text{val}}(\\theta^{\\*}(m)) = \\nabla\\_{\\theta} \\mathcal{L}\\_{\\text{val}} \\cdot \\nabla\\_{m} \\theta^{\\*}(m)$$\n\nSince $\\theta^{\\*}(m)$ satisfies $\\nabla\\_{\\theta} \\mathcal{L}\\_{\\text{train}}(\\theta^{\\*}(m), m) = 0$, implicit differentiation calculates $\\nabla_{m} \\theta^{\\*}(m)$ as :\n\n$\\nabla_m \\nabla\\_{\\theta} \\mathcal{L}\\_{\\text{train}}(\\theta^{\\*}(m), m)=0$, \n\ni.e.,\n\n$\\nabla^2\\_{\\theta \\theta} \\mathcal{L}\\_{\\text{train}}(\\theta^{\\*}(m), m)^\\top \\nabla_{m} \\theta^{\\*}(m) + \\nabla^2\\_{\\theta m} \\mathcal{L}\\_{\\text{train}} (\\theta^{\\*}(m), m)=0.$\n\nTherefore, \n\n$$\\nabla_{m} \\theta^{\\*}(m) = -\\left[\\nabla^{2}_{\\theta\\theta} \\mathcal{L}\\_{\\text{train}}\\right]^{-1} \\cdot \\nabla^{2}\\_{\\theta m} \\mathcal{L}\\_{\\text{train}}$$\n\nThe term $\\nabla^{2}\\_{\\theta\\theta} \\mathcal{L}\\_{\\text{train}}\\in R^{d\\times d}$ is the **Hessian matrix**, making Hessian computation almost unavoidable in exact bilevel optimization as  the dimension d of $\\theta$ is always larger than 1M.\n\n### **[Definition of Optimality]**\n\n\"Optimality\" refers to standard bilevel definition: For each iteration in the outer loop, inner loop needs to find the optimal solution $\\theta^{*}(m)$ for  $\\min_{\\theta} \\mathcal{L}_{\\text{train}}(\\theta, m)$. This can lead to a huge cost since we need to perform lots of outer loop iteration for solving the bilevel problem.\n\n\nWe will include these details in the revised version if accepted. \n\n[r1] J. Domke. Generic methods for optimization-based modeling. AISTATS, 2012.\n\n[r2] F. Pedregosa. Hyperparameter optimization with approximate gradient. ICML, 2016.\n\n[r3] T. Chen et al. A single-timescale method for stochastic bilevel optimization. AISTATS, 2021.\n\n---\n\n### **W3: The paper seems to be motivated based on the observation of spectral bias from Rahman et al. This is insightful but does that generalizes to different problems in machine learning?**\n\nThank you for this question. We clarify several important points:\n\n- **[Spectral bias is universal.]** This represents a fundamental property extensively studied across ML community [r4,5]. Neural networks consistently learn low-frequency before high-frequency components across various architectures and domains.\n\n- **[Motivation extends beyond spectral bias.]** While Sec. 3 uses spectral bias as an illustration, our core argument is broader - **Models prefer different types of data during different stages of training**. Spectral bias is one well-documented instance that supports our argument. We argue that different data samples contribute knowledge of varying complexity and learning difficulty, which can be observed in various domains, such as vision, language tasks, etc. Given different budgets, we can expect the optimal coresets to be different.\n\n- **[Sec. 3 as pedagogical illustration.]** The spectral analysis serves as illustrative case study to explain underlying concepts, not sole theoretical foundation. CADS framework is agnostic to specific bias types and adapts to different domains' learning patterns.\n\nWe appreciate this question as it allows us to clarify that our contribution addresses a fundamental aspect of neural network training that extends well beyond any single type of bias.\n\n[r4] N. Rahaman et al. On the spectral bias of neural networks. ICML, 2018.\n\n[r5] Z.-Q. J. Xu et al. Frequency principle: Fourier analysis sheds light on deep neural networks. arXiv, 2019.\n\n---\n\n### **W4&Q6: How the generalization of a network gets affected with the compute budget (in terms of FID scores).**\n\nWe conducted additional experiments on generative models to demonstrate CADS's effectiveness across computational budgets.\n\n### **[Exp 1: CADS-E on StyleGAN2]**\n\nStyleGAN2 on CIFAR-10 with varying budgets. Random baseline used fixed 25600 samples.\n\n| Budget (img) | Random FID$\\downarrow$ | CADS-E  FID$\\downarrow$ | CADS Subset Size |\n| ------------ | ---------------------- | ----------------------- | ---------------- |\n| 1000k        | 34.73                  | **31.47**               | 26304            |\n| 2000k        | 17.04                  | **15.39**               | 29518            |\n| 3000k        | 12.40                  | **11.45**               | 32881            |\n| 4000k        | 9.51                   | **8.75**                | 38091            |\n\n### **[Exp 2: CADS-S on DDPM]**\n\nDDPM (EDM implementation) on CIFAR-10 with 5 noise groups (σ = 0.00, 0.01, 0.02, 0.03, 0.04). Uniform baseline uses r = [0.2, 0.2, 0.2, 0.2, 0.2]. Each group contains 10,000 images. \n\n| Budget (img) | Uniform FID$\\downarrow$ | CADS-S FID$\\downarrow$ | CADS Ratio r            |\n| ------------ | ----------------------- | ---------------------- | ----------------------- |\n| 2000k        | 49.45                   | **26.55**              | [0.97,0.08,0.01,0,0]    |\n| 4000k        | 41.69                   | **17.15**              | [1.00,0.15,0.08,0,0]    |\n| 8000k        | 35.31                   | **8.33**               | [1.00,0.12,0.05,0.02,0] |\n| 16000k       | 30.94                   | **4.09**               | [1.00,0.23,0.03,0.01,0] |\n\nResults validate that computational budget considerations lead to measurably better generative model performance.\n\n---\n\n### **Q3: How can one know how much time a model would need to train?**\n\nThe computational budget is typically determined by **task-specific constraints** rather than arbitrary choices.\n\n**Determining Training Time Budget**\n\nBudget comes from operational requirements: news recommendation systems in the industry may need updates periodically, e.g., every 20 minutes (leaving 5-10 minutes for training), cloud budgets ($10/run) convert to time via pricing.\n\nUsers estimate budgets through pilot experiments, hardware profiling, or converting monetary limits to compute time.\n\n**CADS Framework Flexibility**\n\nOur method treats budget as user-defined parameter and optimizes data selection under this constraint. Users start with rough estimates and refine through ablation studies. CADS explicitly incorporates practical constraints into optimization, unlike traditional methods ignoring computational limits.\n\nBudget reflects real-world operational needs, making our approach highly relevant for production systems.\n\n---\n\n### **Q5: What computational overhead the algorithm adds on top of the computational cost of training a network?**\n\nThank you for this important question. Our CADS algorithm's overhead consists of two components:\n\n**Linear Loss Estimator Overhead:**\nTo construct loss surrogate function l(|m|) (Section 4.3), we sample m different subset sizes. Using m=5 subset sizes, the overhead is mC where C is total compute budget. Since this function can be used in each run, this cost can be amortized across multiple runs with factor A, i.e., A is the number of runs, giving effective overhead mC/A.\n\n**Core Algorithm Overhead:**\nAlgorithm performs M iterations with K=2 Monte Carlo samples each. We let the subset sized of $\\gamma$N, where $\\gamma < 1$, resulting in computational cost $\\gamma$MKC/T, where T=C/N represents epochs in conventional training.\n\n**Total Overhead Analysis:**\nTotal overhead = mC/A + $\\gamma$MKC/T. With practical settings (m=5, K=2, M≈T), this becomes:\n\n**Total Overhead = 5C/A + 2$\\gamma$C = (5/A + 2$\\gamma$)C**\n\nThe additional overhead over baseline training cost C is **(5/A + 2$\\gamma$ - 1)C**.\n\n**Summary:**\n\n1. When M≈T, the total overhead is  (5/A + 2$\\gamma$)C\n2. Overhead significantly reduced by increasing amortization factor A through reusing estimators across multiple selection tasks\n3. With A=5 reuses, the additional overhead reduces to just 2$\\gamma$C\n\n**Note:** The core contribution of our work is introducing computational budget constraints into coreset selection, rather than optimizing selection time alone. Once learned, **a coreset can be reused multiple times** across different training scenarios, model architectures, and experiments. Therefore, the computational investment in coreset selection can be amortized over multiple uses, making the selection efficiency a secondary consideration compared to the quality of the resulting coreset under budget constraints."}, {"review_id": "G7RktLyiEs", "reviewer": "Reviewer_XuGb", "summary": "This paper demonstrates that computational budget constraints significantly impact data selection. The authors propose Computational budget-Aware Data Selection (CADS), formulating it as a bilevel optimization framework. To address two key challenges, they introduce a probabilistic reparameterization strategy and transform the inner optimization into a penalty term within the outer objective. Experimental results and analyses appropriately support the claims.", "questions": "See above weakness.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n1. This paper reveals an interesting and novel perspective on data selection.\n\n2. This paper elegantly formalizes the problem as a bilevel optimization problem.\n\n3. The proposed CADS is well-motivated, and its effectiveness is thoroughly demonstrated.\n\n## Weaknesses\n\n1. In Sec. 3, how to generate low-/high-frequency datasets? How to define low-/high-budget phases and the difference between them?\n\n2. It seems that there is no direct relevance between the frequency favoritism of deep neural networks and the proposed method. Authors need to further explain the relationship and provide more evidence to support this motivation.\n\n3. One major concern is the lack of comparison between the proposed CADS and established baselines regarding performance and computational cost on widely-used datasets (e.g., ImageNet) and general-purpose models.\n\n4. It seems that CADS is proposed in a general manner. Authors need to discuss the scalability of CADS to other bilevel optimization problems.", "was_revised": true, "final_justification": "The rebuttal has addressed most of my concerns regarding dataset generation details, budget phase definition, experimental comparison on ImageNet, and the scalability of CADS to other bilevel problems. However, the relevance between the frequency favoritism of DNNs and the proposed method remains unclear. Based on this, I will maintain my rating as borderline accept.", "rebuttal": "**We sincerely thank Reviewer XuGb for the constructive feedback.** Below we provide point-by-point responses:\n\n---\n\n### **W1: In Sec. 3, how to generate low-/high-frequency datasets? How to define low-/high-budget phases and the difference between them?**\n\n### **[How to generate dataset]**\n\nAs we described in Sec. 3, inspired by [50], the data (x,y) is sampled from the function $y = x + sin(\\pi x)/\\pi x$. The low-frequency dataset samples data exclusively at $sin(\\pi x) = 0$ points, capturing primarily the linear component y = x with additive Gaussian noise. The high-frequency dataset samples uniformly across the domain, preserving the full spectral complexity including oscillatory patterns from the $sin(\\pi x)/\\pi x$ term.\n\nThe **low-frequency** and **high-frequency** datasets in Sec. 3 represent **relative concepts** rather than strict mathematical definitions. This exploratory experiment was designed as a **proof-of-concept** to demonstrate that data preferences can shift with computational budget, which motivated our main contribution. \n\n###  **[Budget Phase Definition]**\n\nThis is simply a name we gave for easy understanding, not a rigorous definition. The distinction between **low-budget** and **high-budget phases** is determined empirically based on the intersection point of the validation loss curves in Fig. 1. The low-budget phase (0-60 steps) is where low-frequency data achieves better performance, while the high-budget phase (80+ steps) is where high-frequency data becomes superior, with a transition point around 60-80 steps.\n\n---\n\n### **W2: Relevance between the frequency favoritism of deep neural networks and the proposed method.**\n\nThank you for this question. We clarify several important points:\n\n- **[Motivation extends beyond frequency favoritism]** While Sec. 3 uses spectral bias as an illustration, our core argument is broader - **Models prefer different types of data during different stages of training**. Spectral bias is one well-documented instance that supports our argument. We argue that different data samples contribute knowledge of varying complexity and learning difficulty, which can be observed in various domains, such as vision, language tasks, etc. Given different budgets, we can expect the optimal coresets to be different.\n\n- **[Sec. 3 as pedagogical illustration]** The spectral analysis serves as illustrative case study to explain underlying concepts, not sole theoretical foundation. CADS framework is agnostic to specific bias types and adapts to different domains' learning patterns.\n\n---\n\n### **W3: Comparison with established baselines regarding performance and computational cost on widely-used datasets (e.g., ImageNet) and general-purpose models.**\n\nWe conducted comprehensive ImageNet experiments to address this concern. \n\n**Additionally**, in our main paper, we also performed experiments on DomainNet, one of the largest multi-domain datasets, comprising approximately half the scale of ImageNet. \n\n### **[CADS-E Experiments on ImageNet]**\n\nDue to computational constraints during the rebuttal period, we conducted experiments on ImageNet-100  with 10K samples using ResNet-50. We will include more results in the revised version.\n\n| Method      | Budget: 50K | Budget: 100K | Budget: 200K | Budget: 400K | Final Subset Size         |\n| ----------- | ----------- | ------------ | ------------ | ------------ | ------------------------- |\n| Forgetting  | 81.33%      | 82.39%       | 84.71%       | 86.77%       | [5000,5000,5000,5000]     |\n| EL2N        | 79.18%      | 80.79%       | 83.28%       | 84.82%       | -                         |\n| GraNd-Score | 78.35%      | 79.44%       | 82.10%       | 84.08%       | -                         |\n| Moderate    | 80.61%      | 81.70%       | 84.59%       | 86.84%       | -                         |\n| **CADS-E**  | **82.81%**  | **83.78%**   | **86.46%**   | **88.13%**   | **[4088,6320,7171,8653]** |\n\nCADS-E consistently outperforms all baselines across different computational budgets.\n\n### **[CADS-S Experiments on ImageNet]**\n\nFor CADS-S evaluation, ImageNet-1K partitioned into 5 groups with different label noise levels (0%, 2.5%, 5%, 7.5%, 10%). Experiments were conducted with computational budgets measured in epochs (full dataset traversals). For baseline methods, we combined all 5 groups into a single dataset and applied their selection algorithms to choose 20% of the total data as the training subset. \n\n| Method    | Budget: 10 epochs     | Budget: 20 epochs  | Budget: 30 epochs    | Budget: 40 epochs   |\n| -------------------------- | ------------------------------ | ------------------------------ | ------------------------------ | ------------------------------ |\n| Forgetting                 | 22.18%       | 32.87%           | 39.22%   | 42.36%     |\n| EL2N                       | 20.82%        | 31.35%             | 38.95%   | 41.61%    |\n| GraNd-Score                | 22.47%       | 32.61%            | 39.05%   | 42.79%    |\n| Moderate                   | 26.31%      | 35.06%   | 44.54%    | 49.89%    |\n| **CADS-S**                 | **31.20%**      | **42.14%**   | **50.58%**      | **56.13%**    |\n| **CADS Sampling Ratios r** | [0.85, 0.12, 0.03, 0.00, 0.00] | [0.88, 0.10, 0.02, 0.00, 0.00] | [0.92, 0.06, 0.06, 0.01, 0.00] | [0.95, 0.12, 0.02, 0.02, 0.00] |\n\n### **[Computational Cost Analysis of Established Baselines]**\n\nWe establish unified framework with key parameters:\n\n- **C**: Total compute budget (training cost on full dataset)\n- **N**: Total dataset samples  \n- **T**: Training epochs, where T = C/N\n\nAll computational overheads are measured relative to the baseline cost **C** of training on the full dataset.\n\n**Note**: For methods requiring pre-trained models, we assume the computational cost of obtaining the necessary pre-trained model is **0.2C** (20% of the full budget), which represents a reasonable approximation for early-stage model training needed to compute gradients or other sample-wise statistics.\n\n| **Method**    | **Total Computational Overhead**    |\n| -------------------------------------- | ------------------------------------------------------------ |\n| **Random Selection**    | **C** (no additional cost)    |\n| **Forgetting Scores**   | **1.2C** (0.2C for pre-training and forgetting computation + C for final training) |\n| **GraNd**         | **1.2C** (0.2C for pre-training and gradient computation + C for final training) |\n| **EL2N**        | **1.2C** (0.2C for pre-training and error computation + C for final training) |\n| **CADS (Ours)**       | **(5/A + 2$\\gamma$)C** where A is amortization factor        |\n| **Influence Functions**       | **2C + O(N²)** (full training + expensive Hessian computations + final training) |\n| **Data Shapley**     | **11C~101C** (C for final training + 10C ~ 100C for Monte Carlo approximation with 100~1000 samples) |\n| **Probabilistic Bilevel Optimization** | **50C~100C** (requires 50~100 outer iterations, each involving inner loop model training with computational cost C) |\n| **Greedy Coreset**       | **~($N^2$/T+1)C** where K is coreset size (bilevel solving for each added sample) |\n\n**Summary:** CADS achieves superior efficiency among bilevel methods with overhead **(5/A + 2$\\gamma$)C**. With A=5 amortization, total cost reduces to **2$\\gamma$C**, $\\gamma < 1$. \n\nTraditional methods like Forgetting Scores offer moderate 1.2C cost but lack budget-aware optimization and deliver inferior effectiveness (e.g., lower accuracy in the **Tables of W3**). \n\nAdvanced bilevel methods become prohibitively expensive **(50C+)**, while CADS provides optimal balance between computational efficiency and budget-aware capabilities.\n\n**Note:** The core contribution of our work is introducing computational budget constraints into coreset selection, rather than optimizing selection time alone. Once learned, **a coreset can be reused multiple times** across different training scenarios, model architectures, and experiments. Therefore, the computational investment in coreset selection can be amortized over multiple uses, making the selection efficiency a secondary consideration compared to the quality of the resulting coreset under budget constraints.\n\n---\n\n### **W4: Discuss the scalability of CADS to other bilevel optimization problems.**\n\nWe actually have a successful example currently under submission that applies  a CADS-like method to **diffusion models**, since DDPM convergence is extremely resource-intensive.\n\n### **[Applicability Conditions]**\n\nCADS is specifically designed to address a fundamental challenge in bilevel optimization: **scenarios where the inner-level problem cannot converge due to computational budget constraints**. The key insight of our approach is that many practical bilevel problems suffer from this issue, where traditional methods assume unlimited computational resources for inner-level convergence—an assumption that rarely holds in real-world applications. \n\n### **[Loss Estimation Accuracy]**\n\nThe scalability of CADS to other bilevel problems primarily depends on the **accuracy of loss estimation** in the target domain. As demonstrated in our response to reviewer **cbM7** regarding loss estimation generalization, our proposed loss estimator shows relatively stable predictive performance across the experimental domains in this work.\n\n### **[Validation Framework for New Domains]**\n\nFor applying CADS to other bilevel optimization problems, we propose the following validation approach:\n\n1. **Loss Estimator Generalization Assessment**: Conduct experiments similar to our generalization evaluation to test whether the data distribution characteristics in the new domain can be reliably predicted by a loss estimator.\n\n2. **Domain-Adaptive Estimator Design**: While our current estimator works well for data selection problems, different bilevel scenarios may benefit from **specialized estimators tailored to their specific requirements** and data characteristics."}, {"review_id": "QLNlKkcrTF", "reviewer": "Reviewer_vqnc", "summary": "The paper proposes to incorporate a computational budget into the data selection process by proposing a bilevel formulation. The formulation uses a computational constraint to train a model on the subset of the dataset in the lower level, with the upper level optimizing the selection of the subset. Apart from providing insights into how the computational budget affects the selection of data, the paper also presents technical contributions for solving the bilevel problem better than previous methods. Empirical evaluation on datasets like MNISt, DomainNet and instruction tuning tasks shows the effectiveness of the approach.", "questions": "See the weaknesses.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper addresses a crucial problem of compute-constrained data selection.\n2. While the bilevel formulation of the problem is well known the use of the probabilistic reparametrization strategy along with the insight of avoiding the training of the lower level problem to convergence can be useful for solving other bilevel problems.\n3. The paper clearly discusses the proposed enhancements to solving the bilevel problems along with the computational complexity analysis of the problem.\n\nWeaknesses\n1. The empirical evaluation section of the paper is rather weak with evaluation primarily shown on datasets like Mnist and Domainnet. This makes the paper weak since data selection is desirable on larger and more complicated datasets. It is unclear whether the results presented in the paper inform us about the success of the method on larger datasets.\n2. The computational complexity of the method is compared against other bilevel based methods for dataset selection. Adding comparison to other dataset selection methods such as Forgetting scores could be useful. \n3. Performance comparison is very limited. Other bilevel approaches as well as non-bilevel approaches should be included in the paper\n4. While the related work mentions the paper [67] a direct comparison with their approach is essential.", "was_revised": true, "final_justification": "The rebuttal and discussions have helped further clarify the importance of the paper's contributions. Thus, I maintain my rating.", "rebuttal": "**We sincerely thank Reviewer vqnc for the constructive feedback.** Below we provide point-by-point responses:\n\n---\n\n### **W1: Comparison between the proposed CADS and established baselines regarding performance and computational cost on larger dataset.**\n\nWe conducted comprehensive ImageNet experiments to address this concern. **Additionally**, in our main paper, we performed experiments on DomainNet, one of the largest multi-domain datasets.\n\n### **[CADS-E Experiments on ImageNet]**\n\nDue to computational constraints during the rebuttal period, we conducted experiments on ImageNet-100  with 10K samples using ResNet-50. We compared against established baselines including Forgetting, EL2N, GraNd-Score, and Moderate across different computational budgets.\n\n| Method      | Budget: 50K | Budget: 100K | Budget: 200K | Budget: 400K | Final Subset Size         |\n| ----------- | ----------- | ------------ | ------------ | ------------ | ------------------------- |\n| Forgetting  | 81.33%      | 82.39%       | 84.71%       | 86.77%       | [5000,5000,5000,5000]     |\n| EL2N        | 79.18%      | 80.79%       | 83.28%       | 84.82%       | -                         |\n| GraNd-Score | 78.35%      | 79.44%       | 82.10%       | 84.08%       | -                         |\n| Moderate    | 80.61%      | 81.70%       | 84.59%       | 86.84%       | -                         |\n| **CADS-E**  | **82.81%**  | **83.78%**   | **86.46%**   | **88.13%**   | **[4088,6320,7171,8653]** |\n\nCADS-E consistently outperforms all baselines across different computational budgets.\n\n### **[CADS-S Experiments on ImageNet]**\n\nFor CADS-S evaluation, ImageNet-1K partitioned into 5 groups with different label noise levels (0%, 2.5%, 5%, 7.5%, 10%). Experiments were conducted with computational budgets measured in epochs (full dataset traversals). For baseline methods, we combined all 5 groups into a single dataset and applied their selection algorithms to choose 20% of the total data as the training subset. \n\n| Method                     | Budget: 10 epochs              | Budget: 20 epochs              | Budget: 30 epochs              | Budget: 40 epochs              |\n| -------------------------- | ------------------------------ | ------------------------------ | ------------------------------ | ------------------------------ |\n| Forgetting                 | 22.18%                         | 32.87%                         | 39.22%                         | 42.36%                         |\n| EL2N                       | 20.82%                         | 31.35%                         | 38.95%                         | 41.61%                         |\n| GraNd-Score                | 22.47%                         | 32.61%                         | 39.05%                         | 42.79%                         |\n| Moderate                   | 26.31%                         | 35.06%                         | 44.54%                         | 49.89%                         |\n| **CADS-S**                 | **31.20%**                     | **42.14%**                     | **50.58%**                     | **56.13%**                     |\n| **CADS Sampling Ratios r** | [0.85, 0.12, 0.03, 0.00, 0.00] | [0.88, 0.10, 0.02, 0.00, 0.00] | [0.92, 0.06, 0.06, 0.01, 0.00] | [0.95, 0.12, 0.02, 0.02, 0.00] |\n\n---\n\n### **W2: Additional comparison to other dataset selection methods.**\n\nWe provide comprehensive computational overhead comparison across different dataset selection methods.\n\n### **[Computational Overhead Framework and Notation]**\n\nWe establish unified framework with key parameters:\n\n- **C**: Total compute budget (training cost on full dataset)\n- **N**: Total dataset samples  \n- **T**: Training epochs, where T = C/N\n\nAll computational overheads are measured relative to the baseline cost **C** of training on the full dataset.\n\n**Note**: For methods requiring pre-trained models, including Forgetting Scores, GraNd, EL2N, we assume the computational cost of obtaining the necessary pre-trained model is **0.2C** (20% of the full training budget), which represents a reasonable approximation for early-stage model training needed to compute gradients or other sample-wise statistics.\n\n### **[Comparative Analysis of Dataset Selection Methods]**\n\n| **Method**                             | **Total Computational Overhead**                             |\n| -------------------------------------- | ------------------------------------------------------------ |\n| **Random Selection**                   | **C** (no additional cost)                                   |\n| **Forgetting Scores**                  | **1.2C** (0.2C for pre-training and forgetting computation + C for final training) |\n| **GraNd**                              | **1.2C** (0.2C for pre-training and gradient computation + C for final training) |\n| **EL2N**                               | **1.2C** (0.2C for pre-training and error computation + C for final training) |\n| **CADS (Ours)**                        | **(5/A + 2$\\gamma$)C** where A is amortization factor                |\n| **Influence Functions**                | **2C + O(N²)** (full training + expensive Hessian computations + final training) |\n| **Data Shapley**                       | **11C~101C** (C for final training + 10C ~ 100C for Monte Carlo approximation with 100~1000 samples) |\n| **Probabilistic Bilevel Optimization** | **50C~100C** (requires 50~100 outer iterations, each involving inner loop model training with computational cost C) |\n| **Greedy Coreset**                     | **~($N^2$/T+1)C** where K is coreset size (bilevel solving for each added sample) |\n\n**Summary:** CADS achieves superior efficiency among bilevel methods with overhead **(5/A + 2$\\gamma$)C**. With A=5 amortization, total cost reduces to **2$\\gamma$C**, $\\gamma < 1$. \n\nTraditional methods like Forgetting Scores offer moderate 1.2C cost but lack budget-aware optimization and deliver inferior effectiveness (e.g., lower accuracy in **W1**). \n\nAdvanced bilevel methods become prohibitively expensive **(50C+)**, while CADS provides optimal balance between computational efficiency and budget-aware capabilities.\n\n**Note:** The core contribution of our work is introducing computational budget constraints into coreset selection, rather than optimizing selection time alone. Once learned, **a coreset can be reused multiple times** across different training scenarios, model architectures, and experiments. Therefore, the computational investment in coreset selection can be amortized over multiple uses, making the selection efficiency a secondary consideration compared to the quality of the resulting coreset under budget constraints.\n\n---\n\n### **W3: Other bilevel approaches as well as non-bilevel approaches should be included in the paper**\n\nThank you for this valuable feedback. Please refer to our response to **W1**, where we have provided comprehensive comparisons with numerous methods on ImageNet, demonstrating the effectiveness and efficiency of our approach across different scales and settings.\n\nRegarding other bilevel approaches: Most existing bilevel methods suffer from extremely high computational complexity with expensive second-order computations, making large-scale experiments infeasible within the rebuttal timeframe. Our paper already includes comparison with PBCS, a representative state-of-the-art bilevel method in data selection. Our CADS framework specifically addresses the computational intractability of existing bilevel approaches while maintaining their theoretical advantages through efficient approximation strategies, which aligns with our core contribution of making data selection practical under realistic computational budgets.\n\n---\n\n### **W4: Direct comparison with [67].**\n\nThank you for this question. We want to clarify that **[67] is an empirical evaluation study rather than a methodological contribution**. Their work evaluates various existing data selection methods (BM25, embedding-based, etc.) under different computational budgets and concludes that method performance varies with budget constraints. **They do not propose new algorithms or optimization frameworks**.\n\n### **[Differences in Research Target]**\n\n**Coverage of [67]:**\n\n- Their study specifically targets LLM instruction tuning with only **single-epoch training** scenarios\n- The authors explicitly acknowledge in their limitations: \"with larger compute budgets, one could reuse portions or all of the dataset for multiple epochs of training\". Their experimental design completely avoids the complexity of multi-epoch training, which is precisely the core problem our paper addresses as we expilictly incorporate the computaional budget into our formulation.\n\n**Our Work's Coverage:**\n\n- We propose a general CADS framework applicable to various machine learning tasks (vision, language, etc.)\n- We explicitly handle data selection optimization under multi-epoch training scenarios\n- We systematically address the problem that [67] acknowledged but did not handle through our bilevel optimization framework\n\n### **[Complementary Technical Contributions]**\n\nThe two works are actually complementary:\n\n- [67] validates the effectiveness of simple methods in single-epoch training scenarios\n- Our work addresses the multi-epoch training scenarios they left unaddressed but acknowledged as important\n- Our CADS framework can effectively utilize multi-epoch training when computational budget permits, which is an extension of [67]"}, {"review_id": "PJxyAP14mq", "reviewer": "Reviewer_cbM7", "summary": "The paper introduces a framework that incorporates **computational budget constraints** into data selection, presenting the Computational Budget-Aware Data Selection (CADS) method. Formulated this as a bilevel optimization problem, CADS consists of an inner loop that trains a model on a selected data subset within a defined computational budget and an outer loop that optimizes data selection based on the model's performance. \n\nThe authors address two key challenges in solving this bilevel problem: **the high computational cost of Hessian estimation and the complexity of achieving inner-loop optimality**. To overcome these, CADS employs a probabilistic reparameterization strategy with a Hessian-free policy gradient estimator and reformulates the inner optimization as a penalty term in the outer objective, requiring only a one-dimensional loss estimation for enhanced efficiency. This loss estimation is performed using a log-linear function interpolated from losses across different subset sizes.\n\nCADS is implemented in two variants: CADS-E, which enables fine-grained, example-level selection, and CADS-S, which offers group-level sampling ratio estimation. Experimental results across vision (MNIST, CIFAR10, DomainNet) and language tasks (instruction-tuning dataset) demonstrate that CADS achieves up to 14.42% performance improvements and 3–20x training speedups compared to baseline methods, showcasing its effectiveness and efficiency.", "questions": "* The definitions of low-frequency and high-frequency data are unclear, particularly how these characteristics are identified or quantified in the context of the dataset (image or instruction-tuning dataset). \n* In Section 3, how do we construct validation dataset? how it is sourced from Group A and Group B, as referenced in Appendix B.1?\n* What is the dataset and model being used to have Figure 7?", "limitations": "Yes. It's documented in their appendix (see section A and G).", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "[Strengths]\n* Quality: The first half of the paper (up to Section 5) is well-structured, effectively motivating the reader with a clear rationale for the proposed approach. However, the experimental section is less clear, making it difficult to follow the setup and key takeaways from each experiment. I notice that Section 5.2, which discusses the CIFAR-10 experiment, missing results referencing the relevant table, only the experimental setup.\n* Clarity: The mathematical formulation is clear, making the challenges easy to understand.\n\n[Weaknesses]\n* About runtime concerns, while incorporating computational budget constraints is a strength, the runtime of the selection algorithm may scale poorly with the number of subsets (K), potentially offsetting the computational efficiency gains of the method. For example, in algorithm 1, we have to sample K subsets and train K models and evaluate them to access K losses so we can interpolate.\n* Figure 7, for example in the appendix illustrates the loss estimation process. It remains unclear about sampling requirements, especially how many subsets (K) are needed to generate sufficient sample losses for reliable interpolation and how robust this interpolation.\n* It's unclear of the selection of the baseline method (PBCS) or provide details on how it operates. Could the authors clarify it?", "was_revised": true, "final_justification": "Reviewer's response during rebuttal resolved my concern to this paper.", "rebuttal": "**We sincerely thank Reviewer cbM7 for the constructive feedback.** Below we provide point-by-point responses:\n\n---\n\n### **S1: I notice that Section 5.2, which discusses the CIFAR-10 experiment, missing results referencing the relevant table, only the experimental setup.**\n\nThank you for pointing this out. We will fix this in the revision.\n\n---\n\n### **W1: About runtime concerns, while incorporating computational budget constraints is a strength, the runtime of the selection algorithm may scale poorly with the number of subsets (K), potentially offsetting the computational efficiency gains of the method.**\n\nThank you for this important concern. We'd like to clarify several key aspects of our approach that address this issue:\n\n### **[K=2 is Sufficient for Practical Implementation]**\n\n1. **Minimal K requirement**: For the policy gradient in coreset selection, a small K is always sufficient to ensure training stability. For exmaple, PBCS [74] adopts K=1 for all its experiments.  Our results in table below show that **K=2 is sufficient to achieve strong performance while maintaining computational efficiency.** \n2. **Variance reduction technique [r1]**: When dealing with more complex problems, smaller values of K may lead to higher gradient variance, and in such cases, we can leverage well-established variance reduction techniques to effectively mitigate this issue:\n      $$\\tilde{L}(S_i) = L(S_i) - \\frac{1}{K}\\sum_{j=1}^K L(S_j).$$\n     \n\n**Note:** The core contribution of our work is introducing computational budget constraints into coreset selection, rather than optimizing selection time alone. Once learned, **a coreset can be reused multiple times** across different training scenarios, model architectures, and experiments. Therefore, the computational investment in coreset selection can be amortized over multiple uses, making the selection efficiency a secondary consideration compared to the quality of the resulting coreset under budget constraints.\n\n[r1] Hammersley, J. M.; Handscomb, D. C. (1964). Monte Carlo Methods. London: Methuen. ISBN 0-416-52340-4.\n\n### **[Empirical Validation]**\n\nWe provide empirical evidence that K=2 achieves comparable performance to larger K values:\n\n| Initial subset size (same as Tab.1 in main text) | K=2        | K=5        |\n| ------------------------------------------------ | ---------- | ---------- |\n| 200     | 91.44%     | 91.48%     |\n| 400      | 92.23%     | 92.28%     |\n| 600       | 92.38%     | 92.34%     |\n| 800          | 92.88%     | 92.90%     |\n| **Average**              | **92.23%** | **92.25%** |\n\n**Note:** We provide an analysis of the computational overhead of CADS in our reply to reviewer **TtXp**. \n\n---\n\n### **W2: For Figure 7, how many subsets (K) are needed to generate sufficient sample losses for reliable interpolation and how robust this interpolation.**\n\n### **[Sampling Efficiency Analysis]**\n\nWe conducted experiments to demonstrate that our method requires only a **small number of sampling points** for reliable loss estimation. \n\n**Experiment Design:** On ResNet-18 and CIFAR-10, we evaluate loss estimators under different sampling densities K ∈ {4, 5, 6, 7, 8}. For each K, we sample K subset sizes to train models and collect K (size, loss) pairs for fitting the loss estimator. We then test each estimator on 100 separately sampled (size, loss) pairs to evaluate interpolation accuracy across different sampling densities.\n\n**Results:**\n\n| Sampling Points (K) | Mean Square Error |\n| ------------------- | ----------------- |\n| 4        | 0.057668          |\n| **5**        | **0.016326**      |\n| 6         | 0.018594          |\n| 7        | 0.020031          |\n| 8         | 0.017905          |\n\nThe results show that **performance saturates around K=5 sampling points**, with diminishing returns beyond this point. This demonstrates our method's sample efficiency.\n\nNotably, **larger K values can actually hurt performance** (as seen with K=7) due to overfitting to the specific sampled points, reducing generalization to unseen subset sizes.\n\n### **[Practical Implementation]**\n\nIn practice, we recommend:\n\n- **K=5 sampling points** for most applications (optimal efficiency)\n- **Logarithmic spacing** of subset sizes for better coverage\n\n---\n\n### **W3: It's unclear of the selection of the baseline method (PBCS) or provide details on how it operates. Could the authors clarify it?**\n\nWe appreciate the reviewer's request for clarification on the PBCS baseline method. \n\n### **[Why We Choose PBCS as Baseline]**\n\nPBCS is selected as our primary baseline because it represents the **most representative and state-of-the-art bilevel optimization approach** for data selection problems.\n\n### **[How it operates]**\n\nPBCS proposes a **probabilistic bilevel coreset selection framework** that differs fundamentally from our computational budget-aware approach. PBCS formulates coreset selection as a **continuous bilevel optimization problem** using probabilistic reparameterization:\n\n**Key Formulation:**\n\n$$\\min_{s\\in C} \\Phi(s) = \\mathbb{E}_{p(m|s)} \\mathcal{L}(\\theta^*(m))$$\n\n$$\\text{s.t. } \\theta^*(m) \\in \\arg \\min_\\theta \\hat{\\mathcal{L}}(\\theta; m)$$\n\nWhere:\n\n- Each training sample $i$ is assigned a **Bernoulli probability $s_i$** to be included in the coreset\n- Binary mask $m_i \\sim \\text{Bern}(s_i)$ determines actual sample selection\n- Constraint set $C = \\{s : 0 \\preceq s \\preceq 1, \\|s\\|_1 \\leq K\\}$ controls coreset size $K$\n\n**Optimization Strategy:**\nPBCS uses a PGE to avoid expensive implicit differentiation:\n$$\\nabla_s \\Phi(s) \\approx \\mathcal{L}(\\theta^*(m)) \\nabla_s \\ln p(m|s)$$\n\nThe algorithm alternates between:\n\n1. **Inner loop**: Sample coreset from $p(m|s)$ and train model to convergence\n2. **Outer loop**: Update probabilities $s$ using PGE based on full dataset performance\n\n### **[Key Differences Between CADS and PBCS]**\n\nOur CADS framework addresses several fundamental limitations of PBCS:\n\n1. **Computational Budget Awareness**: Unlike PBCS which treats coreset size as a fixed constraint, our CADS explicitly incorporates **computational budget $C$** as a first-class design consideration, jointly optimizing data selection and budget allocation under resource constraints.\n\n2. **Inner-loop Non-convergence Handling**: PBCS assumes the inner optimization reaches convergence ($\\theta^*(m)$), which is unrealistic under limited computational budgets. Our CADS introduces **penalty-based single-level relaxtion** and **an loss estimators** to handle scenarios where inner-loop training is incomplete.\n\n3. **Computational Efficiency**: While PBCS requires expensive bilevel optimization with full inner-loop convergence, our CADS **unfolds the bilevel structure** using penalty-based reformulation, achieving **3-20× speedup** by avoiding repeated expensive implicit inner-loop training.\n\nThese technical innovations enable CADS to achieve superior performance-efficiency trade-offs compared to traditional size-constrained approaches like PBCS.\n\n---\n\n### **Q1: The definitions of low-frequency and high-frequency data are unclear, particularly how these characteristics are identified or quantified in the context of the dataset (image or instruction-tuning dataset).**\n\nThank you for this feedback. We'd like to clarify the concepts and identification methods below.\n\n### **[Frequency Definition]**\n\nWe follow the concept of **low-frequency** and **high-frequency** given in the literature of deep learning theory [r1]. They are **relative concepts** rather than strict mathematical definitions. This exploratory experiment was designed as a **proof-of-concept** to demonstrate that data preferences can shift with computational budget, which motivated our main contribution. \n\n- **High-frequency data**: More complex, requires more computational resources to effectively utilize.\n- **Low-frequency data**: Simpler patterns that can be learned with less computation.\n\n### **[How to Identify in Different Dataset Types]**\n\n**Image datasets**: Identified through frequency domain analysis—images with rich edge details and textures contain more high-frequency components, as these represent rapid spatial variations (e.g., edges, fine patterns) that are harder for models to capture [r2]. **This can be quantified using gradient magnitude analysis (e.g., Sobel operators) or Laplacian variance to capture edge density and texture complexity.** \n\n**Instruction-tuning datasets**: High-frequency includes complex multi-step reasoning tasks and domain-specific instructions; low-frequency represents simpler, common instruction patterns.\n\n[r1] N. Rahaman et al. On the spectral bias of neural networks. ICML, 2018.\n\n[r2] Wang et al., \"High-Frequency Component Helps Explain the Generalization of Convolutional Neural Networks,\" CVPR 2020\n\n---\n\n### **Q2: In Section 3, how do we construct validation dataset? how it is sourced from Group A and Group B, as referenced in Appendix B.1?**\n\nAs detailed in Appendix B.1:\n\n**Validation Dataset Construction:**\nThe validation set follows the **same generation process as Group B**: $y = x + sin(\\pi x)/\\pi x + N(0, \\sigma^2)$, with a fixed set of 10,000 points.\n\n**Rationale:**\n\n- **Group A (low-frequency)**: Contains only low-frequency components (y = x + noise)\n- **Group B (high-frequency)**: Contains both low and high-frequency components, where all points from Group A could potentially appear in Group B\n- **Validation set**: Uses Group B's generation process to capture the complete frequency spectrum, providing a comprehensive evaluation benchmark\n\nThis design ensures that the validation set represents the full complexity of the target function.\n\n---\n\n### **Q3: What is the dataset and model being used to have Figure 7?**\n\nFig. 7 uses MNIST dataset, and the model is a lightweight CNN network. Specific architectural details are provided in Appendix B.2. **Note** that the results on CIFAR experiments in our response to **W2** also show the effectiveness of our method."}]

Author rebuttal:

Meta-review: Overall, this paper makes a timely and significant contribution by establishing computational budget as a core principle in data selection and introducing an effective algorithmic framework (CADS) to operationalize this idea. The methodological innovations are well-motivated, the empirical results are compelling, and the work has important implications for large-scale model training under practical resource constraints. It is essential that the authors address the reviewers’ concerns in the final version.
Decision: Accept (poster)