Bandit Guided Submodular Curriculum for Adaptive Subset Selection

We sincerely thank the reviewer for their time and thoughtful evaluation of our work. We are especially grateful for the encouraging remarks regarding the originality, significance, and clarity of our approach. We look forward to addressing any further questions or suggestions from the reviewer.

---

---

Discussion on Additional Related Work

InfoMax: Data Pruning by Information Maximization. ICLR-2025

• The InfoMax formulation is a direct restructuring of the Graph Cut function (as shown in their Section 3.3), which is monotone submodular, using a similarity kernel such as DINO embeddings (for image settings) or gradient scores.

• This is aligned with our work, where we are already using Graph Cut explicitly as a bandit arm in our current framework.

• The key difference is that InfoMax operates in a static setting, selecting samples over the entire dataset.

• In contrast, our method is dynamic and modular—an InfoMax-like objective can be plugged in as a bandit arm and used in batch-level pruning during training.

• This makes our method easier to deploy in real-world settings, where adaptive selection over batches is necessary for scalability.

• Importantly, our framework is modular—methods like InfoMax can be seamlessly integrated and evaluated within OnlineSubmod, offering better scalability in large-scale training pipelines.

---

D2Pruning: D2 Pruning: Message Passing for Balancing Diversity and Difficulty in Data Pruning. ICLR-2024.

• In this paper, the data subset selection problem is framed as a subgraph pruning task over the entire training dataset, represented as a graph with the similarity metric is based on embedding or feature similarity across data points.

• The pruning mechanism relies on message passing algorithms, and the selection optimization problem can be viewed as a graphical model. However, due to the heavy computational cost of message passing, this approach may required modifications for large-scale setups.

• Similar to InfoMax, this method operates at a static level, not a dynamic batch-level setting.

• As a direction for future work, it would be interesting to explore how batch-level message passing-based pruning can be adapted within a bandit arm framework, especially using diversity parameters as proposed in their paper.

---

CCS: Coverage-centric Coreset Selection for High Pruning Rates. ICLR-2023

• Like other works, CCS considers a static setting to select examples that ensure both coverage and diversity.

• A key contribution of CCS is its theoretical analysis of the pruning budget beyond which catastrophic accuracy drop can occur.

• In our revised manuscript, we plan to explore whether similar catastrophic accuracy drop effects appear at the batch level, though this is less common than in static selection setups.

In summary, while all three related works contribute valuable insights into data pruning and coreset selection, they primarily operate in static, full-dataset regimes. In contrast, our proposed method addresses batch-level adaptive pruning in a scalable and modular manner using a bandit-driven curriculum where the reward is guided by validation performance, filling a key gap in making such strategies practical for large-scale, dynamic training setups. Further our method can be easily modified to incorporate other reward strategies like forgetting score as in CCS or other metrics discussed in the above related work.

---

Second, have the authors considered evaluating their approach on much larger-scale datasets, such as those used in pre-training tasks for large language models (LLMs)?

• We thank the reviewer for this insightful suggestion. As part of our initial experiments, we had evaluated OnlineSubmod on a Pythia-70M model using OpenWebText, which represents a significantly larger-scale dataset. We were able to complete one full setup in this regime, demonstrating that our method is applicable in such settings.

• Given that GREATS is a strong baseline in our finetuning experiments, we had planned to conduct pretraining comparisons against GREATS as well. However, due to the lack of open-source code for GREATS pretraining configuration, we were unfortunately unable to include those results at this time.

• Moreover, given limited compute availability apart from finetuning experiments, we were unable to secure sufficient resources to conduct large-scale pretraining beyond the initial Pythia-70M run. That said, we plan to extend our evaluation to GPT-2 (small) and (medium) scale pretraining setups prior to the camera-ready deadline.

We hope these clarifications and additions address the reviewer’s concerns. Our primary contribution lies in proposing a novel bandit-guided curriculum learning framework that incorporates submodular subset selection for adaptive data sampling. We are grateful for the reviewer’s positive feedback on the core ideas presented.

We will revise the manuscript to explicitly incorporate the related works mentioned, which will help better position our method in relation to prior efforts and clarify its distinct contributions. We would sincerely appreciate a reconsideration of the overall score, which would be instrumental in supporting the acceptance of our paper.

We sincerely thank the reviewer for their time and thoughtful evaluation of our work on Bandit-Guided Submodular Curriculum. We are glad that the reviewer found our framing of curriculum learning as a multi-armed bandit problem both novel and principled, and that the theoretical and empirical contributions were appreciated. We're also encouraged by the positive recognition of our approach’s scalability and efficiency, as well as its performance improvements over existing methods.

We now move forward to addressing the questions raised by the reviewer

 The proposed method heavily relies on a validation-driven reward, and the authors assume access to a validation mini-batch at each time step. This raises several concerns:

• First, validation-based signals are widely used in curriculum learning and subset selection to guide model development. This includes prior work such as GREATS[1] and TracIn[2], where the validation loss (or its proxy) serves as a reliable indicator of generalization. Our approach extends this principle by using the marginal drop in validation loss as a utility function for adaptive selection, and our theoretical guarantees hinge on this consistency.

• Second, we agree that the quality and composition of the validation dataset are critical. In practice, we assume access to a relatively clean validation set — a standard assumption in most training pipelines. If the validation set contains outliers or disproportionately difficult examples, especially in early training stages, the reward signal may be noisy. To probe this, we conducted controlled experiments (see below) on CIFAR-100 where we varied the hardness of the validation samples (based on gradient norm) and observed consistent performance degradation when the validation set was biased toward difficult samples early in training.

• Lastly, while our current instantiation uses validation loss, our framework is flexible. If a clean validation set is unavailable, alternative reward signals — such as teacher model outputs, self-training confidence, or auxiliary task feedback — can be substituted with minimal change to the bandit formulation, left for future-work.

  How sensitive is the performance to the configuration of the validation dataset?   In the early stages of training, what happens if the validation dataset contains difficult samples that the model has not yet learned? A more detailed analysis of the impact of the validation dataset would make the paper more convincing.

To better understand this issue, we conducted a controlled experiment on CIFAR-100 (300 epochs) where we varied the hardness of the validation dataset. Hardness was measured via gradient norm (higher norm ∼ harder example). We compared four validation subset configurations:

• Easiest: Lowest gradient norms
• EasyHard: Easy samples early, hard samples later
• HardEasy: Hard samples early, easy samples later
• Hardest: Highest gradient norms

Each configuration was evaluated at validation subset sizes of 10%, 20%, and 30%. Below are the final test accuracies:

Findings:

• Hardest validation sets yield lower performance, particularly at smaller subset sizes, likely due to noisy or overly pessimistic reward signals early in training.
• Mixed configurations like EasyHard and HardEasy perform best, suggesting robustness to how difficult samples are distributed over time.

These results indicate that exploring how difficult samples are ordered within the validation dataset—framed through a curriculum learning perspective—could be a promising direction for future work. Nonetheless, even validation sets containing difficult examples early in training do not lead to instability or collapse.

---

We thank the reviewer again for their valuable suggestions and constructive feedback, which we will incorporate into the final version. We also appreciate their positive assessment of the paper and would be grateful for a corresponding increase in score to further support its acceptance.

---

[1][Wang et al., 2024] GREATS: Online Selection of High-Quality Data for LLM Training in Every Iteration.

[2][Pruthi et al., 2020] Estimating Training Data Influence by Tracing Gradient Descent. arXiv:2002.08484

We thank the reviewer for the thoughtful and constructive feedback. We are glad that the reviewer found our method to be technically sound, well-motivated, and empirically effective. We appreciate the reviewer's recognition of the method's clarity, practicality, and originality, and we are happy to address the concerns and questions raised:

---

On Clarity of Utility and Influence Functions:

Thank you for the suggestion. We will include a summary figure illustrating how utility and influence functions interact in the reward formulation, especially highlighting their roles in guiding the greedy sampling decisions. Along with this we will add a summary section of how such influence functions are utilised in existing literature in our final camera ready version. We agree this will significantly improve readability for non-expert audiences.

On the Complexity of Designing Submodular Arms:

In practice, we draw from a small, domain-agnostic library of well-established submodular functions—such as facility location and graph cut—that have demonstrated effectiveness across a range of tasks. These functions are not only interpretable but also align with familiar sampling heuristics like representativeness and diversity. For example, representative functions (e.g., facility location, graph cut) aim to select samples that best capture the structure of the data by covering clusters, while diversity-based functions explicitly encourage selection of dissimilar items to avoid redundancy. From a computational standpoint, we construct a similarity matrix over item gradients within each batch, which remains tractable due to the modest batch sizes typically used in training. Moreover, once the base modular function is defined, a wide range of submodular objectives can be constructed by applying concave transformations, enabling fine-grained control over the trade-off between representativeness and diversity.

On Related Work Discussion

We appreciate the recommendation to expand our discussion of related work. While we have included additional related work discussions in the Supplementary, we will revise Section 2 to more clearly position our method in relation to prior curriculum learning methods that rely on fixed or hand-crafted, model dependent or model-agnostic difficulty metrics.

---

Response to Questions raised by Reviewer

 Can you clarify the sensitivity of the method to the choice and number of submodular arms?

• If the set of submodular functions acting as arms are assumed to coming from multiple(more than 2) classes (in our case, we considered two broad classes like representative and diversity based submodular functions) and if some classes are highly skewed (i.e. some classes of submodular functions has more instantiations than others), then the submodular function arms from high frequent classes would be statistically more favoured in long term horizon by the exploration branch of the algorithm).
• In our use case we consider a well balanced setting so that both classes have equal representation. In that case, in line 4 of algorithm in exploration branch instead of uniform weightage across all arms we will sample according to the inverse weighting of the frequency of the submodular function arms to accomodate for the skewness.

---

 Can you explain the role of exploration hyperparameters and how to tune them in practice?

• As discussed in line 222 to 233 (Section 3), the exploration hyperparameters governs when to prioritize more on exploration vs exploitation, which is typically the norm in multi-arm bandit literature.
• More specifically, $\lambda(t)$ (Exploration Dampening) and $\pi(t)$ (Exploration Sharpness) function as curriculum schedulers, as they decide the ordering of the submodular function arms by tuning the exploitation/exploration tradeoff dynamically.
• If a uniformly sampled value satisfies $\zeta > \Xi_t$, the algorithm switches to exploitation mode and selects the arm that maximizes $\vartheta(a \mid B_t)$. Otherwise, an arm is sampled uniformly at random.
• Exploration focuses on trying different arms to discover potentially better or more diverse options, even if a best arm is already known. Exploitation favors reusing the previously selected arm that has performed well so far.

---

In practice, we follow different variations of $\lambda(t)$ as indicated in our ablation sections 5.3 Fig 4 and 6, one as exponentially increasing or decreasing or keeping it constant through time. The effect of different variations are discussed more broadly in Section 5.3. The usual way we followed for tuning for optimal exploration parameters was to perform grid search experiments over a discrete search space of exponentially increasing, decreasing and constant setups.

---

Thank you again for the helpful suggestions and valuable feedback, which we will incorporate in the final version. We are glad to hear your positive inclination toward accepting the paper and hope that our responses have adequately addressed your concerns.

We kindly request your support in reflecting this through an appropriate score increase to help strengthen the case for acceptance.

We thank the reviewer for their time in reviewing our submission and for providing encouraging feedback on our draft. We are pleased to know that the reviewer found our work promising both from a theoretical perspective and in terms of real-world applicability. We look forward to addressing all the questions here by:

---

Clarification on Fig 1 sampling policy accuracy gap: In Figure 1b, our primary goal is to illustrate that the blue curve—which corresponds to using representative submodular functions in the initial epochs—achieves higher accuracy earlier in training compared to the red curve, where diversity-based functions are used first. While the final accuracy at epoch 300 may appear similar, the distinction lies in the training dynamics. Notably, between epochs 200–250, the performance gap is more pronounced, indicating that scheduling representative functions early and shifting to diversity-based sampling later leads to more efficient learning. This supports our hypothesis that a predefined curriculum induced by submodular structure benefits optimization more when scheduled in a particular order. There are many possible orderings of representative and diversity-based functions; Figure 1 illustrates just one, highlighting how the choice of order affects accuracy and convergence.

---

Motivation behind choice of Submodular Functions We thank the reviewer for this feedback. We do elaborate on the rationale behind our choice of submodular functions in Appendix Section F (page 34), where we present their mathematical formulations and structural properties. This section details how each function promotes either diversity or representativeness with respect to the similarity kernel. To strengthen the motivation, we plan to add additional synthetic experiments that illustrate how diversity-focused submodular functions select varied samples, while representative functions favor prototypical examples—empirically validating the behavior of each function according to its intended category.

---

---

Addressing minor concerns over Visualization/Presentation Thank you for the detailed feedback on the presentation quality. We appreciate the suggestions and will incorporate them in the final version.

• We acknowledge that the current version may contain overly emphasized highlights. In the camera-ready version, we will adopt a more neutral and planar tone, improving overall readability and flow.
• We agree that figure consistency enhances clarity. We will standardize the styling across all figures—including color palettes, legend placement, and line widths—for better visual coherence. We will also reduce the dot size in Figure 4 to improve interpretability.
• Thank you for pointing out the inconsistency in table captions. We will fix it to non-italics for uniformity across all table captions.
• For Figure 3, we will improve line distinguishability through clearer labeling and contrast-adjusted color choices to make trends easier to follow.

---

---

Response to Questions raised by Reviewer

Effect of submodular functions indivually and simple random selection over arms

Thank you for the thoughtful question. To assess the importance of the multi-armed bandit setup, we conducted additional experiments on CIFAR-100 (10% subset, 300 epochs) under two ablations: (a) using a single fixed arm throughout training (i.e., no bandit), and (b) randomly selecting an arm at each round (i.e., no explore-exploit strategy). Results are shown below:

These results show that while some individual arms (e.g., GraphCut, FacilityLocation) perform reasonably well, others (e.g., DisparitySum) are suboptimal, making fixed-arm strategies brittle. Random arm selection does moderately well but falls short of the full model, at the same time neither random or static arm selection considers improving validation performance as a reward metric. This confirms that adaptive explore-exploit selection via the bandit improves robustness and performance over naive or static alternatives.

Difference in arm distribution between image and language training setups

This is an interesting question, while its true the underlying mechanisms are different, this final distribution over the chosen arms is more dependent on the underlying training distribution. From our experiments, we observe that Log-Deteriminant(Div.) is almost never active for LLM exps, while Graph-Cut(Rep.) is more dominant. We tested on MMLU(Sociology) subset. This indicates that, atleast for this subset, Representation seems more important that diversity for test-perplexity. We will add an ablation on this in our final revised draft.

---

Thank you again for the helpful suggestions and the important feedbacks which we will incorporate in the final version and for your reassurance given your positive inclination towards accepting the paper.

We would appreciate an appropriate increase in the score so as to get support on the paper acceptance from your end.