Computational Budget Should Be Considered in Data Selection

We sincerely thank Reviewer cbM7 for the constructive feedback. Below we provide point-by-point responses:

---

S1: I notice that Section 5.2, which discusses the CIFAR-10 experiment, missing results referencing the relevant table, only the experimental setup.

Thank you for pointing this out. We will fix this in the revision.

---

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.

Thank you for this important concern. We'd like to clarify several key aspects of our approach that address this issue:

[K=2 is Sufficient for Practical Implementation]

1. 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.
2. 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: $\tilde{L}(S_i) = L(S_i) - \frac{1}{K}\sum_{j=1}^K L(S_j).$

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.

[r1] Hammersley, J. M.; Handscomb, D. C. (1964). Monte Carlo Methods. London: Methuen. ISBN 0-416-52340-4.

[Empirical Validation]

We provide empirical evidence that K=2 achieves comparable performance to larger K values:

Note: We provide an analysis of the computational overhead of CADS in our reply to reviewer TtXp.

---

W2: For Figure 7, how many subsets (K) are needed to generate sufficient sample losses for reliable interpolation and how robust this interpolation.

[Sampling Efficiency Analysis]

We conducted experiments to demonstrate that our method requires only a small number of sampling points for reliable loss estimation.

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.

Results:

The results show that performance saturates around K=5 sampling points, with diminishing returns beyond this point. This demonstrates our method's sample efficiency.

Notably, 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.

[Practical Implementation]

In practice, we recommend:

• K=5 sampling points for most applications (optimal efficiency)
• Logarithmic spacing of subset sizes for better coverage

---

W3: It's unclear of the selection of the baseline method (PBCS) or provide details on how it operates. Could the authors clarify it?

We appreciate the reviewer's request for clarification on the PBCS baseline method.

[Why We Choose PBCS as Baseline]

PBCS is selected as our primary baseline because it represents the most representative and state-of-the-art bilevel optimization approach for data selection problems.

[How it operates]

PBCS 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:

Key Formulation:

$\min_{s\in C} \Phi(s) = \mathbb{E}_{p(m|s)} \mathcal{L}(\theta^*(m))$

$\text{s.t. } \theta^*(m) \in \arg \min_\theta \hat{\mathcal{L}}(\theta; m)$

Where:

• Each training sample $i$ is assigned a Bernoulli probability $s_i$ to be included in the coreset
• Binary mask $m_i \sim \text{Bern}(s_i)$ determines actual sample selection
• Constraint set $C = \{s : 0 \preceq s \preceq 1, \|s\|_1 \leq K\}$ controls coreset size $K$

Optimization Strategy: PBCS uses a PGE to avoid expensive implicit differentiation: $\nabla_s \Phi(s) \approx \mathcal{L}(\theta^*(m)) \nabla_s \ln p(m|s)$

The algorithm alternates between:

1. Inner loop: Sample coreset from $p(m|s)$ and train model to convergence
2. Outer loop: Update probabilities $s$ using PGE based on full dataset performance

[Key Differences Between CADS and PBCS]

Our CADS framework addresses several fundamental limitations of PBCS:

1. 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.

2. 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.

3. 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.

These technical innovations enable CADS to achieve superior performance-efficiency trade-offs compared to traditional size-constrained approaches like PBCS.

---

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).

Thank you for this feedback. We'd like to clarify the concepts and identification methods below.

[Frequency Definition]

We 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.

• High-frequency data: More complex, requires more computational resources to effectively utilize.
• Low-frequency data: Simpler patterns that can be learned with less computation.

[How to Identify in Different Dataset Types]

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.

Instruction-tuning datasets: High-frequency includes complex multi-step reasoning tasks and domain-specific instructions; low-frequency represents simpler, common instruction patterns.

[r1] N. Rahaman et al. On the spectral bias of neural networks. ICML, 2018.

[r2] Wang et al., "High-Frequency Component Helps Explain the Generalization of Convolutional Neural Networks," CVPR 2020

---

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?

As detailed in Appendix B.1:

Validation Dataset Construction: The 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.

Rationale:

• Group A (low-frequency): Contains only low-frequency components (y = x + noise)
• Group B (high-frequency): Contains both low and high-frequency components, where all points from Group A could potentially appear in Group B
• Validation set: Uses Group B's generation process to capture the complete frequency spectrum, providing a comprehensive evaluation benchmark

This design ensures that the validation set represents the full complexity of the target function.

---

Q3: What is the dataset and model being used to have Figure 7?

Fig. 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.

We sincerely thank Reviewer vqnc for the constructive feedback. Below we provide point-by-point responses:

---

W1: Comparison between the proposed CADS and established baselines regarding performance and computational cost on larger dataset.

We 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.

[CADS-E Experiments on ImageNet]

Due 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.

CADS-E consistently outperforms all baselines across different computational budgets.

[CADS-S Experiments on ImageNet]

For 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.

---

W2: Additional comparison to other dataset selection methods.

We provide comprehensive computational overhead comparison across different dataset selection methods.

[Computational Overhead Framework and Notation]

We establish unified framework with key parameters:

• C: Total compute budget (training cost on full dataset)
• N: Total dataset samples
• T: Training epochs, where T = C/N

All computational overheads are measured relative to the baseline cost C of training on the full dataset.

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.

[Comparative Analysis of Dataset Selection Methods]

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$.

Traditional methods like Forgetting Scores offer moderate 1.2C cost but lack budget-aware optimization and deliver inferior effectiveness (e.g., lower accuracy in W1).

Advanced bilevel methods become prohibitively expensive (50C+), while CADS provides 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, 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.

---

W3: Other bilevel approaches as well as non-bilevel approaches should be included in the paper

Thank 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.

Regarding 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.

---

W4: Direct comparison with [67].

Thank 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.

[Differences in Research Target]

Coverage of [67]:

• Their study specifically targets LLM instruction tuning with only single-epoch training scenarios
• 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.

Our Work's Coverage:

• We propose a general CADS framework applicable to various machine learning tasks (vision, language, etc.)
• We explicitly handle data selection optimization under multi-epoch training scenarios
• We systematically address the problem that [67] acknowledged but did not handle through our bilevel optimization framework

[Complementary Technical Contributions]

The two works are actually complementary:

• [67] validates the effectiveness of simple methods in single-epoch training scenarios
• Our work addresses the multi-epoch training scenarios they left unaddressed but acknowledged as important
• Our CADS framework can effectively utilize multi-epoch training when computational budget permits, which is an extension of [67]

We sincerely thank Reviewer XuGb for the constructive feedback. Below we provide point-by-point responses:

---

W1: In Sec. 3, how to generate low-/high-frequency datasets? How to define low-/high-budget phases and the difference between them?

[How to generate dataset]

As 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.

The 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.

[Budget Phase Definition]

This 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.

---

W2: Relevance between the frequency favoritism of deep neural networks and the proposed method.

Thank you for this question. We clarify several important points:

• [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.

• [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.

---

W3: Comparison with established baselines regarding performance and computational cost on widely-used datasets (e.g., ImageNet) and general-purpose models.

We conducted comprehensive ImageNet experiments to address this concern.

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.

[CADS-E Experiments on ImageNet]

Due 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.

CADS-E consistently outperforms all baselines across different computational budgets.

[CADS-S Experiments on ImageNet]

For 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.

[Computational Cost Analysis of Established Baselines]

We establish unified framework with key parameters:

• C: Total compute budget (training cost on full dataset)
• N: Total dataset samples
• T: Training epochs, where T = C/N

All computational overheads are measured relative to the baseline cost C of training on the full dataset.

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.

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$.

Traditional 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).

Advanced bilevel methods become prohibitively expensive (50C+), while CADS provides 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, 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.

---

W4: Discuss the scalability of CADS to other bilevel optimization problems.

We actually have a successful example currently under submission that applies a CADS-like method to diffusion models, since DDPM convergence is extremely resource-intensive.

[Applicability Conditions]

CADS 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.

[Loss Estimation Accuracy]

The 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.

[Validation Framework for New Domains]

For applying CADS to other bilevel optimization problems, we propose the following validation approach:

1. 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.

2. 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.

We sincerely thank Reviewer TtXp for the constructive feedback. Below we provide point-by-point responses:

---

W1&Q4: Is it the compute budget for model training or data mining process?

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:

$\min \mathcal{L}_{val}(\theta_C(m)) \quad \text{s.t.} \quad \theta_C(m) = \text{Train}(m,C)$

where $C$ represents the computational cost for training the model on the given subsets, which equals to #iteration*batch-size.

---

W2&Q1&Q2: Why Hessians are needed in the first step, what optimality refers to in the data selection.

We think your concern is based on our statement in lines 61 to 62.

[Why Hessians are Required]

The Hessian requirement in bilevel optimization is extensively studied in prior work [r1-3]. Our bilevel formulation follows the standard structure:

• Inner: $\theta^{\*}(m) = \arg \min_{\theta} \mathcal{L}_{\text{train}}(\theta, m)$
• Outer: $\min_{m} \mathcal{L}_{\text{val}}(\theta^{\*}(m))$

To optimize the outer loop, we compute $\nabla_{m} \mathcal{L}_{\text{val}}(\theta^{*}(m))$ using chain rule:

$\nabla\_{m} \mathcal{L}\_{\text{val}}(\theta^{\*}(m)) = \nabla\_{\theta} \mathcal{L}\_{\text{val}} \cdot \nabla\_{m} \theta^{\*}(m)$

Since $\theta^{\*}(m)$ satisfies $\nabla\_{\theta} \mathcal{L}\_{\text{train}}(\theta^{\*}(m), m) = 0$, implicit differentiation calculates $\nabla_{m} \theta^{\*}(m)$ as :

$\nabla_m \nabla\_{\theta} \mathcal{L}\_{\text{train}}(\theta^{\*}(m), m)=0$,

i.e.,

$\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.$

Therefore,

$\nabla_{m} \theta^{\*}(m) = -\left[\nabla^{2}_{\theta\theta} \mathcal{L}\_{\text{train}}\right]^{-1} \cdot \nabla^{2}\_{\theta m} \mathcal{L}\_{\text{train}}$

The 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.

[Definition of Optimality]

"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.

We will include these details in the revised version if accepted.

[r1] J. Domke. Generic methods for optimization-based modeling. AISTATS, 2012.

[r2] F. Pedregosa. Hyperparameter optimization with approximate gradient. ICML, 2016.

[r3] T. Chen et al. A single-timescale method for stochastic bilevel optimization. AISTATS, 2021.

---

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?

Thank you for this question. We clarify several important points:

• [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.

• [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.

• [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.

We 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.

[r4] N. Rahaman et al. On the spectral bias of neural networks. ICML, 2018.

[r5] Z.-Q. J. Xu et al. Frequency principle: Fourier analysis sheds light on deep neural networks. arXiv, 2019.

---

W4&Q6: How the generalization of a network gets affected with the compute budget (in terms of FID scores).

We conducted additional experiments on generative models to demonstrate CADS's effectiveness across computational budgets.

[Exp 1: CADS-E on StyleGAN2]

StyleGAN2 on CIFAR-10 with varying budgets. Random baseline used fixed 25600 samples.

[Exp 2: CADS-S on DDPM]

DDPM (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.

Results validate that computational budget considerations lead to measurably better generative model performance.

---

Q3: How can one know how much time a model would need to train?

The computational budget is typically determined by task-specific constraints rather than arbitrary choices.

Determining Training Time Budget

Budget 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.

Users estimate budgets through pilot experiments, hardware profiling, or converting monetary limits to compute time.

CADS Framework Flexibility

Our 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.

Budget reflects real-world operational needs, making our approach highly relevant for production systems.

---

Q5: What computational overhead the algorithm adds on top of the computational cost of training a network?

Thank you for this important question. Our CADS algorithm's overhead consists of two components:

Linear Loss Estimator Overhead: To 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.

Core Algorithm Overhead: Algorithm 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.

Total Overhead Analysis: Total overhead = mC/A + $\gamma$MKC/T. With practical settings (m=5, K=2, M≈T), this becomes:

Total Overhead = 5C/A + 2$\gamma$C = (5/A + 2$\gamma$)C

The additional overhead over baseline training cost C is (5/A + 2$\gamma$ - 1)C.

Summary:

1. When M≈T, the total overhead is (5/A + 2$\gamma$)C
2. Overhead significantly reduced by increasing amortization factor A through reusing estimators across multiple selection tasks
3. With A=5 reuses, the additional overhead reduces to just 2$\gamma$C

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.

Thanks for addressing my concerns. My major concern regarding the overhead introduced by this paper is properly addressed. I think this is significant and should be highlighted in the main paper. This can help design the optimization strategy carefully.

Please make sure to add all the promised results and discussions from the rebuttal in the final version of the paper.