Bandit Guided Submodular Curriculum for Adaptive Subset Selection
Authors: Prateek Chanda
Prayas Agrawal
Saral Sureka
Lokesh Reddy Polu
Atharv Kshirsagar
Ganesh Ramakrishnan
Venue: NeurIPS 2025 poster ()
Keywords: Curriculum Learning
Adaptive Subset Selection
Multi Arm Bandit
Submodular Functions
No-regret Analysis
Primary area: general_machine_learning
TL;DR: We propose an adaptive subset selection framework for supervised learning, where submodular functions quantify sample difficulty to guide curriculum learning.

Abstract: Traditional curriculum learning proceeds from easy to hard samples, yet defining a reliable notion of difficulty remains elusive. Prior work has used submodular functions to induce difficulty scores in curriculum learning. We reinterpret adaptive subset selection and formulate it as a multi-armed bandit problem, where each arm corresponds to a submodular function guiding sample selection. We introduce OnlineSubmod, a novel online greedy policy that optimizes a utility-driven reward and provably achieves no-regret performance under various sampling regimes. Empirically, OnlineSubmod outperforms both traditional curriculum learning and bi-level optimization approaches across vision and language datasets, showing superior accuracy-efficiency tradeoffs. More broadly, we show that validation-driven reward metrics offer a principled way to guide the curriculum schedule. Our code is publicly available at GitHub : https://github.com/efficiency-learning/banditsubmod/.

Bandit Guided Submodular Curriculum for Adaptive Subset Selection
Prateek Chanda" Prayas Agrawal" Saral Sureka
Lokesh Reddy Polu
Athary Kshirsagar
Ganesh Ramakrishnan
Department of Computer Science and Engineering, Indian Institute of Technology Bombay
(prateekch, prayas, ssaral
(lokeshreddypolu, atharvksagar, gonesh)@cse, witb.iita
Abstract
Traditional curriculum learning proceeds from easy to hard samples, yet defining a reliable notion of difficulty remains elusive. Prior work has used submodular functions to induce difficulty scores in curriculum learning. We reinterpret adaptive subset selection and formulate it multi-armed bandit problem, where each arm corresponds to a submodular function guiding sample selection. We introduce ONLINESUBMOD, novel online greedy policy that optimizes utility-driven ward and provably achieves no-regret performance under various sampling regimes. Empirically, ONLINESUBME outperforms both traditional curriculum learning and bi-level optimization approaches across vision and language datasets, show- ing superior -fffiiccyyf tradeoffs. More broadly, show that validation- driven reward metrics offer a principled way to guide the curriculum schedule. Our code is publicly available GitHub
Introduction
Curriculum Learning (CL), inspired by cognitive development, posits that training machine learning models by gradually exposing them to data of increasing complexity significantly enhance both learning efficiency and generalization performance [4, 59]. The underlying principle is that mastering simpler concepts first provides robust foundation for acquiring more complex ones, leading to improved convergence and a more effective exploration of the hypothesis space [19]. Empirical evidence shows CL improves model training, particularly in areas like code understanding [33], enhances graph embeddings through complexity-basee ordering [57]. mitigates catastrophic forgetting [2, 26, 50, 43], and boosts learning efficiency in reinforcement learning [34]. We first provide formal definition of Curriculum Learning.
Definition 1. (Curriculum Learning) Given a dataset U B, partitioned into disjoint batches
B, and batch difficulty score function {B.} - R20 assigning non-negative difficully scores, a batch-wie wise curriculum can be represented as permutation æ [k] + [k] over the ordered indices such that the ordered sequence
C= (B ... Bx(x)):
satisfies the monotonic difficulty score condition: d(Br()) S d(Br(+1)) Vt E (1....,k -1}.
Determining Difficulty is challenging critical challenge realizing the full potential of Currieu- lum Learning (CL) is determining the optimal sequence of batches. This is complicated by the fact
'These authors contributed equally.
htttp://github. ceaittuu..om/fffciiiee. com/efficiency -etaiiinncc-laaaingg/gaa Saariing/bnddisubmees
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

that the difficulty score, denoted as d, is typically unknown. Traditional approaches often rely on domain expertise or practitioner's knowledge assess the hardness or difficulty of samples.
Recent works, such as [19], have proposed using submodular function maximization over data batches intrinsic measure of sample difficulty. In particular, representative submodular functions representative submodular functions are used to identify easy samples, while diversity focused submodular functions are used to capture difficult ones. As a result, the CL objective is typically constructed by prioritizing diversity functions later and representative functions earlier in the training phase. However, this definition of hardness is still restrictive, as relies on fixed pretraining phase and does not account for evolving training dynamics.
Submodularr per step
Submodular per Epoch
Adaptive Subset Selection Induces CL Many adaptive subset selection methods although can be viewed forms of currieulum learning, in- cur substantial computational overhead. For in- stance, Glister [20] solves costly bilevel opti- mization involving joint subset selection and model training with validation feedback. Grad- Match [18] minimizes gradient matching error by solving complex optimization problems to approximate full-dataset gradients. Importance sampling approaches [7, 46] similarly require expensive importance score estimations. Such costs limit the scalability of advanced curricu- lum strategies, especially under resource con- straints or large datasets.
Iest Accuracy (86)
Test Accuracy
4.4
02
Repr
Rege
Dio
30 1001
150 1000
330
300
30 100
150 300 Epoch
200 307
Epoch
Figure 1: Sequential Ordering of Submodular Functions: Observations on CIFARI00: Initial training with subsets sampled using representation- based submodular functions followed by diversity results in better performance gains than the oppo- site order. (la): First 50% of steps in an epoch.
(1b): First 50% of epochs.
1.1 Our Contributions
Submodular curriculum learning via online bandits We formulate the curriculum learning problem in conjunction with the adaptive subset selection as a multi-arm bandit problem, where each arm corresponds to a submodular function that captures its unique characteristics, thereby providing a good surrogate difficulty score required for curriculum learning design.
no-regret greedy policy for adaptive subset selection We introduce ONLINESUBMOD, novel greedy uiiittybased policy that leverages feedback from validation performance-drive reward signal to adaptively guide the subset selection process. We prove that ONLINESUBMOD achieves no- regret performance under general sampling regimes, providing theoretical grounding for its learning efficiency.
Validation performance-aware reward design Unlike prior work which uses static heuristics or model-dependent metries, we define utility function based on validation sefformance-driverr reward improvements, thereby aligning curriculum progression with actual generalization objectives. Empirical improvements across modalities Through extensive experiments on large-scale language and vision benchmarks, we demonstrate that ONLINESUBMOP outperforms traditional curriculum strategies and state-of-the-art adaptive selection methods in terms of accuracy-efficiene trade-offs across diverse subset budgets and training stages.
1.2 Brief Discussion on Related Work & Limitations
Here we detail some of the recent prior work in the space of adaptive subset selection and correspond- ing limitations.
Leveraging Training Gradient information: Efficiently training robust machine learning models often involves selecting informative data subsets. GLISTER [20] directly addresses this through mixed discrete-comtinuous bi-level optimization framework, leveraging validation likelihood for robustness. The concept of adaptive data subset selection, where the subset evolves during training, explored by methodologies like coreset selection [32]. [18] tackles the problem by focusing on minimizing gradient matching error, as the quality of this matching significantly impacts con- vergence. By modeling this error as weakly submodular and using OMP [9], GradMatch achieves tighter convergence guarantees for various convex loss functions. Despite their advancements, many contemporary subset selection techniques, such as coreset selection and related methods [8], pose considerable computational burden due to their complex optimization processes.

---

Reweighting Techniques: In this context, [53] offered significant insights into strategies for selecting data subsets that focus on identifying high-qualing subsets during the training of models. As we shift towards meta-learning and weighted loss techniques, traditional methods like importance sampling, first introduced by [6], and more contemporary approaches such as focal loss proposed by [25], provide essential perspectives on weighting samples to highlight more challenging examples during training. However, all these strategies entail additional costs. We further share more detailed Related work section in Appendix G.
Notation and Problem Setup
Notation: We consider a supervised learning setup where we have a training dataset Dir {(x,, yi) J:)) with each instance independently and identically distributed (i.i.d.) according to distribution Fxxy over the feature space X' and label space Y Similarly, we have a validation dataset D Dval= = =(x3ot, -y )] also drawn i.i.d. from Pxxxy. Here, x E represents the features and y represents the labels. Let Me be model parameterized by 0 O S Rd, with θ being a compact and convex parameter space. The learning objective is minimize the empirical risk L(Me; (r) [51]. The training process unfolds over a discrete time horizon T E Z Let FF be the space of set functions, with F wab C F denoting the subspace of submodular functions.
Note: Throughout this paper, we use z to denote training instance from B, unless explicitly labeled Vval which refers validation instance. In Appendix Section B we provide an extensive notation summary. We provide here some important definitions which would be utilised in the later sections.
Definition 2 (Submodularity), Given ground set V. set function f 2 + R is submodular if for all S V and B C A V, holds that f(S U A) f(A) S f(S USSUR B) f(B).
Definition 3 (Monotonicity). A set function f 22 + R2g monotone for all B AS holds that (BB - f(A).
Definition 4 (Maximum High Value Subset). Corresponding to monotone submodular function f. the maximum high value subset of cardinality at most 3, denoted by I (3g(3) = Bope ç V, defined as: 0e argmax (B)).
BC
2.1 Problem Formulation Adaptive Subset Selection posed as Curriculum Learning
At each discrete time step E [T], we consider a mini-batch B, S Dtr upon which the model Mg is trained. Let é: Z x θ + R denote the instance-wise loss function, where Z = X ) is the instance space, and the model parameter at time t denoted by 0₂ E @. The total loss over the mini-bater B, is given by (0,) ExEB, Olz, Concurrently, we have access to validation mini-batch
BY Dva: at each time step
Gradient Matrix and Mean Gradient: Let Do. (2] [dx[B,]
Function
f(X)
Go. = 19.. ( (21).
be the batch gradient matrix at time step f, where each column 9e, (2:) = Vol(z, 0,) E Id is the sample-wise gradient of the loss function l with respect to the model parameter 0,, for all z, e B, Let ||s.| E | denote the column vector of ones. We define the per-batch gradient ( BB Σz,e6, Io, (z,) 1 Ge. 1
Representative Facility Location Graph Cut
Eiev maxjEx Sty
EiEviex 8ij .1_.eex 8ij
Diversity
Log Determinant
log det(Sx)
Disparity-Mi
min:/jex
Disparity-Sum
ΣxpJEx 5.2)
[6:]]
Table 1: Submodular functions used in arm defi-
nitions. V is the ground set, X C V, Sis denotes pairwise similarity, and Sx is the similarity submatrix. indicates the balancing factor be- tween representative and diversity nature. We also utilise mutual information variants (De- tails Appendix)
Action Space and Submodular Selection Policy. At each time step t E [T', the learner observes a mini-batch B, S Drr and must select subset of size 3 to compute gradient update. The learner chooses an action a, E o from a discrete action p(a)
space: of = (1 (()) ...., ((k)
Faub; where each fla). 2B. + is a monotone submodular function used to score subsets of B. These functions encode different sample selection criteria such as diversity, coverage,
3

---

and representativeness (see Table for examples). The selected function f(a)) is then approx- imately maximized over B, under fixed cardinality constraint produce a training subset: S, == arg max 1 (S). which is typically computed via a greedy algorithm. The model is updated using St, and the quality of the update is evaluated using utility-based reward defined on held-out validation mini-batch B _ Dval-
Specifically, let ((a (B)) be the empirical estimate of the expected reward for arm E s/
Greedy Deterministic Selection. We adopt greedy deterministic policy 2 ad that selects the arm with the highest estimated reward at each time step i.e. dz == π xBi) = arg max (a, Be).. where Ue is the utility function defined in Section 2.1.
Policy:
Regret as Performance Measure We denote by (*) the index of an optimal action, so that (i()) (B,) represents the expected utility (e.g., value of the selected subset) of an optimal submodular function p(at) when applied to mini-batch B, For each action 04 E dd, we define the optimality gap time I as A (a.) (B,) == max (0, {(a BB) (at B.)]. The cumulative regret after 7 rounds is then defined as Regret, Σe_ o., (B:) Minimizing Regret, ensures that the learner approaches the performance of the best submodular selector in hindsight. We define 0( ( B,) in Sec 2.2
Reward Utility Metric for Performance Evaluation Drawing upon the concept of training data
influence [38], we define a utility function Ui (B,, Zual) 2D x 'Daal J TR to quantify the impact
of a training mini-batch B, S Drr at time step t on a validation instance Zval E Specifically, the utility is the reduction in the loss on the validation instance after step of stochastic gradient descent:
U4 (B,, Zval) = f(Zual: O1) - EZvvll, (B.)),
(1)
where the updated parameter vector 0c+1(B:) 0, 7)e Ve Be Exeo, (lz,
First-Order Approximation of Marginal Utility Gain: We define the instance-wise conditional marginal utility gain of including the i-th training instance z; into a partially constructed mini-batch
B((0) = {zz, Zz..... 2 at time step t, with respect to validation instance Zval, as the change in
utility Ue
Aul B( Zval) (B, <0 U (2,) Zoal) - (1) Zval)
(2)
z V Vol(z,, 0,) V (B((0)))))
(3)
The approximation in the last step utilizes a first-order Taylor expansion, which is reasonable under the common assumption of a small learning rate TΙ- We defer the derivation Appendix
Second-Order Approximation and Gradient Influence: Further approximating the second term in Equation (3) using another first-order Taylor expansion around I,, obtain:
T1.e, (2.) V Vel(zval (B((()) as migo, (z:) V Vellzavl O. Th
go.
(z))
|B
<E)
ZEB
<n
1)t
9a. (z:) 9o. (Zval)
th go. (2:) Hz. (0:)(
Σ
go. (z))
(4)
15
<1)
ZEB((0
Gradient Influcnce Function(Termn
Hessian Weighted Relative Similarity (Term II)
where Hz... (0.) Vo O2) denotes the Hessian of the loss function with respect the model parameters evaluated at 02 for the validation data point Zyal-
The first term indicates the importance score of z, w.rl validation data point zual which, essence, captures the effectiveness of the gradient of the training instance towards the reduction in the validation loss. This term closely resembles the influence function proposed in [38].
Gradient Influence Function:
Relative Similarity Term The second term indicates the Hessian weighted relative similarity of the current training instance with all other training instances in the batch B <3)
Hessian Approximation Strategies The Hessian term Hz.,(O,) Equation (4) presents a major computational bottleneck due to its high cost. To alleviate this, several approximation strategies are

---

commonly employed: Cronecker-Factoree Approximation methods [54] exploit layer-wise structure and approximate the Hessian using Kronecker products; Gauss-Newton Decomposition [42] replaces the Hessian with the covariance of output gradients, assuming negligible residual; and the Identity Approzimation (29, 37] simplifies the Hessian Ia. yielding a low-cost diagonal preconditioner. In our current list of experiments, we consider Hessian to Ia as it is has been shown to be usefull with low approximation error in large scale trainings e.g. LLM settings [52]. In Appendix Section D.6, we include other Hessian Approximation strategies which we tried out along with corresponding ablation studies.
2.2 wise Expected Marginal Gain
We define the sample- wise expected marginal gain the expectation of the conditional marginal utility gain over a validation instance zt"! and a training instance z; from the partially constructed mini-
batch B <t)
E
ExtlE =.EB(())
B| = Here, due the property of permutation
invariance the samples in B.
<i) shown in Lemma 2, the inner expectation can be written
E x.88/(00)
(b)T B <() 2(a1 n.80, Io. (z)²²) ni B!
(b)
La
1 [B
1 dx 13, Go.
Hapa (0, (b)
(0))oo.
(5)
A direct greedy approach to maximize the conditional marginal gain each step by iteratively selecting the training instance z & (((() that yields the maximal local reduction in validation loss,
iee, " argmax (.(((( AM((z; B ((<() ) is computationally prohibitive. Constructing the
new subset batch S, of size from the current mini-batch B, via this exhaustive greedy maximization
starting from an empty set (B} ()(<0) = 0) incurs a computational complexity of ((1B))
To overcome the computational intractability of exact optimization, introduce relaxation that exploits the structure of submodular functions to enable efficient selection of high-value subsets. Specifically, for each submodular function arm ag Ld we compute an approximately optimal subset Sapt S B, of size at most B, chosen to maximize the submodular objective (S)) Since exact maximization of submodular functions NP-hard, we adopt a standard greedy algorithm that offers provable (1 1/e)- approximainnn guarantee under cardinality constraints.
Submodular Relaxation for Efficient Selection:
We define the overall expected marginal gain 0 e x T + IR for each submodular function arm a, E a at time step / as the expectation of the missance-wise conditional marginal gain Ali, conditioned validation instance and a training instance from the approximately optimal subset Sept:
Reward Formulation using Submodular Function Arms:
I aa, BB) = Egg eBr 2, E
A (z; |
(<1)(<1) .xaaa ag
(6)
The best arm is then selected via âg = arg max (arr) B.)). E/d
2.3 Speedup for ONLINESUBMOD
Gradient Computation Full-model gradients in deep networks are expensive to compute due to high-dimenssionaityy For vision tasks, we adopt last-layer gradients following [3], and for LLMs, we compute gradients over LoRA adapters (rank 128) in [52]. Both reduce overhead while preserving informative signals for subset selection.
ONLINESUBMOD Batch To align with batch-level baselines [18], we extend our samplewise formu- (h)
lation to the batch setting, treating each batch as unit. Let M((0) g
[..
be the matrix
of average gradients 9; for batches B, E Sr, where S. denotes the set of sampled batches at time t. The expected conditional marginal gain becomes:
( & M (b) 1ss g(z)=1)
of "M( (11s,
Isa.)
Hez
(M,²) (b) 1 1s
Other methods can be analogously adapted by substituting samples æ; with batches B;.
5

---

3 Algorithm
ONLINES UBMOD instantiates a contextual multi-armee bandit framework to adaptively select cur- riculum policies throughout training.
Algorithm 1: ONLINESCBMOD
Step: 1-2 The model receives batch B, and
chooses an arm â, at cach corresponding to a distinct submodular utility function f f 28. R20-
Input:
Total training steps
{f(a)] Candidate submodular
arms
X()), T(:): Time-varying exploration
Step: The arm selection is governed by explo-
ration threshold E. == (++*(0))=00>> parameter-
parameters
Output: 0r41: Final model parameter
ized by dime-dependent schedules X(L) and r(() that modulate the annealing from exploration exploitation. Here, A(t) (Exploration Dampen- ing) and πt) (Exploration Sharpness) act as curriculum schedulers. If uniform sample sat- isfies E, the algorithm enters Exploitation Phase and selects the arm maximizing 8(a B., otherwise, an arm is sampled uniformly at random (Exploration Phase).
for 8 1 to do
Receive batch B,
Sample ~ 2(00 1)
Threshold: E,
arg max 2 (at (3))
if
ā.
act ad
Uniform(44
otherwise
((a.) arg
(S)
Step: Once an arm â is selected, the algorithm performs approximate maximization over B, with respect (( selecting subset S(ae)-
0.41 f-
Σ 9e. (z)
(S(ag)
(()(
refurn 0T+1
Step: The model parameters O, are then updated using stochastic gradient step computed only on the selected subset.
4 Theoretical Results
In this section, present the main theoretical results of our work, focusing on regret guarantees for our best-arm selection policy. Specifically, we analyze the regret incurred by our method relative the performance of the optimal arm in hindsight. This requires (pertaining to describe properties of the exploration dynamics, utility approximation quality, and the existence of reward gap between optimal and suboptimal arms)
of structural assumptions
Assumption (a) (Constant Fractional Exploration Dampening): The exploration dampening parameter X(t) is time-invariant ((t) = where C 10.
Assumption (b) (Optimality Gap): There exists an optimality gap e such that for every suboptimal arm E of \ {a)): S e (B,).
Assumption (c) (Fractional Exploration Sharpness): The exploration sharpness parameter x(t) is bounded quantity (t) 10.
Assumption (d) (Utility Metric Approximation): The utility metrie Ue(:; satisfies the approxima- tion bound as per Theorem 2 (Appendix) with constants C(a) for each arm E af and let n. be specific constant associated with arm a such that Theorem 2 (Appendix) holds true.
Theorem (Regret Guarantees). Under Assumptions d, for all to, with probability at least
- Kep (-2tt 1.((t2)) 2)(1 + (1-
3(t
28K(2 T)
the expected instantaneous regret incurred by the arm selection policy satisfies
R[eegtt = Fs,, Fa, ear F.g (0(a) BB)) 0 [B)]]
(? +0
3/2 (max, C(a) + Cx)
V Togt
(8)
o
0
where C, is the approximation constant corresponding to the optimal arm a".

---

The theorem guarantees that, under the specified assumptions, the arm selection strategy based on maximizing the expected marginal utility gain converges the optimal arm almost surely, with
the regret decreasing at a rate combining a fast 1/t decay and a slower v log f
decay modulated by
constants related to the utility approximation and the number of arms. The presence of the optimality gap o in the denominator highlights the difficulty of distinguishing between arms when their utility values are close. We also showcase proofs in Appendix when Assumption (a) and Assumption (c) are relaxed with no constraints on the bounds of 2(-) and (T-).
4.1 Supporting Lemmas
Here we detail out Supporting Lemmas that are utilised in proofs and derivations above.
Lemma 1 (Permutation Invariance of Expected Marginal Gain). Let denote the set of all permulations over the elements of B(=0) Then the expected marginal gain <i) x(ai is invariant under any permutation π E III, ie..
E eBB(E
E 2,68
<3
(z B
EE
2.E
Al (BB(<0)), (2221
We provide the detailed derivations for all proofs in Appendix H.
5 Experimental Setup
We evaluate ONLINESUBMOD across diverse datasets to highlight its advantages in terms of both accuracy and computational efficiency. All vision-related experiments are conducted using NVIDIA x A6000 GPUs, while large language model (LLM) experiments are performed on 8 x H100 GPUs to ensure fair comparisons with all baselines. We share more details in Appendix Section D.
5.1 Finetuning Large Language Models
Pairs. We evaluate ONLINESUBMON using combinations of two LLMs: LLAMA-2 2 2B [49] and MISTRAL- 7B [16] finetuned on LESS [55], with performance assessed on MMLU and TYDIQA (Table 1). We use batch size of 16 and use 2 random validation points for computing the reward utility. We select 50% of the batch data for gradient updates during each step.
Table Performance comparison across tasks. Bold indicates best performance in each column.
Method
Eib.
TydQQ
GialNom
46.4%
61 10%
62.55 62.9%
52.1%
40.5%
40.25%
43.05
46.7%
42.95%
32. 32.35
$4.655
MasLoss
45.2%
60.2%
64.95
48.0%
59.5%
38.196
44.415
43.8%
42.615
31.15
55.4%
RhoLoss
46.4%
60.65
66.2%
49.4%
41.5%
40.2%
42.8%
46.1%
41.1%
33.7%
55.2%
SWFRT
45.8%
62:35
63.7%
47.0%
43.1%
36.8%
43.45
44.2%
42.09
32.49
$6.25%
GREATS
63.2%
62.6%
33,055
55.7%
50.9%
Zet Poplo Phlce
To. (Amaety)
TacPopkeity Socklagh
The Toplloo Chumagg
freusto Blass
Figure 2: Test perplexity dynamics LLAMA- 2- during training with various online batch selection strategies on MMLU. We evaluate on US Foreign Policy, Anatomy, Sociology and Chemistry, ONLINESUBMOD significantly outperforms baselines.
Baselines: We compare our algorithm with a variety of online batch selection algorithms:
MAX-Loss [27], which selects training data points with the highest loss values. GRADNORM
[17], which prioritizes training data points with the highest gradient norms, 3 RHO-LOss[30],
using LLaMA-3.1-888 --B--.-----B as the reference and LLaMA-2-7B as the target. SBERT. which selects batches by semantic similarity to validation data using Sentence- BERT embeddings [40].
GREATS [52] which has a similar utility metric as ours, but the optimization objective instead relies
7

---

on directly selecting samples greedily that maximizes the utility reward Eqn (4) rather than utilizing any monotone submodular characteristics.
Observations: As can be seen from the perplexity curves (Figure 8) and downstream performance (Table 1), ONLINESURROD significantly outperforms other existing baselines, thereby indicating how principled validation performance aware reward signal combined with induced submodular curriculum results in better generalization than statie heuristic based approaches.
5.2 Image Classification
We showcase the utility of our method across 5 datasets primarily CIFARIO, CIFARIO0 122.TINYMMAGEEET/331 MNIST [24] and SVHN [36]. We compare ONLINESUBMOD with:
GRADMATCH: [18], 2 CRAIG [32], GLISTER [20]. RHO-LOSS [30] and 5 BOSS
[1]. All models are trained on a ResNet backbone, 300 epochs, with 20 epochs warm-start (we provide more details regarding cold start vs warm start in Appendix Sec: C.3). We provide a detailed summary of individual baselines, comparision with more datasets and hyperparameters in Appendix D.
Performance Metrics across all baselines We work with the batch-wise variant for ONLINESUBMOD (Section 2.3) keeping in line with other methods. To compare various baselines, utilize Speedup as a relative measure of the training times for each baseline in relation to full batch training. Our goal is to identify a baseline that achieves both high speedup and high test accuracy. We evaluate on budget fractions (g. 100%) of 10%, 30% and 50%. From Table 2, observe that method significantly outperforms baselines in accuracy, with speedup extremely close the optimal speedup, obtained by MILO which relies on an expensive offline filtering step based on some assorted selection of submodular functions, contrast to our method which dynamically selects subsets in an online manner. However, this gap is minimal, while our method achieves higher accuracy. For completeness, also showcase per samplewise selection in Figure 3.
Method
Tiny ImaggeNet 30%
CIFAR-100 30%
CIFAR-10
10%
10%
30%
CRAIO (32)
4.82
0.555/2..4
0.672/5.1
0.723
0.751
0.00/667
MILO [19]
8.62
0.593/3.1
0.623/2.6
0.723/ 10.1
0.716735
0.75671995
0.22/5.8
0.952/2005
0,941/ 2.15
GRADMArCH [18]
0.526 5.92
0.581/2.62 /2.62
0.619 2.1
0.683
0.74673. 3.1
0.7537 1.5
0.22/ 4.3
0.952/ 1.95
0.941 1.48
GLISTER [20]
0.51575.5
0.563
0.22771 1.7
0.642/1.7
0.723
0.746/ 1.2
0911/4.5
0.921/ 1.7
0.926 1,3
Run--Lns Loss [30]
0,544/5
0.357/2:577
0.611/2
0.713/3.
0.748 /148/199 119
0.757 /12
0.91 2
0.915/ 166
0.941 / 1.15
BOSS
0.526/5.4
0.601 /2.9
0.221/2.15
0.717/788
0.337
0,754
0916749
0.93071
0.938/1553
ONLINESUBMOOU
8.43
8..08/3.08
0.626:2.6
0.736/9.2
0.754/33
0.758/1.92
0.92475.4
0.937
0.941/2.88
Table 2: Batchwise version performance: Accuracy vs Speedup.
+ highest accuracy 1 3rd highest accuracy.: Performance comparison across different datasets and fractions. Bold indicates the best performance in each column.
b 2nd highest accuracy
Tiny ImageNet
MNIST
SVHN
CIFAR-10
CIFAR-100
60
95
(ccuracy(5)
Accuracy
98
Accuracy
96
Accuracy (%)
90
(8)
60
40
96
94
80
20
93
10
30
50
10
30
50
10
30
50
10
30
50
10
30
50
Subset Frac
T977
Subset Frac
T877
Subset Frac
TP7T
Subset Frac
1P47
Subset Frac Tف7
GRADMATCH
CRAIG
ONLINESUBMOD
GLISTER
BOSS
RHOLOSS
RANDOM
Figure 3: Samplewise Submodular Curriculum: ONLINES UBMOD consistently achieves top-1 accuracy across all subset sizes on TINYIMAGENET, SVHN, CIFAR- 10, and CIFAR-100, and remains competitive on MNIST. Notably, it matches or outperforms all baselines at early subset fractions (10% 30%) on all datasets except MNIST.
5.3 Ablation Study results
To understand how the choice of submodular function at each step affects the model performance under Expploration/Exploiiattoo scheme, it important to understand how the underlying variables affect the overal submodular function selection and thereby model performance at each step.
8

---

A(t) 0.5
A(t) 0.3
A(t)
exp
A(t) 0.7
0.8
Term
0.8
Term
0.3
0.3
Term
0.6
0.6
Term 11
0.4
A14
0.4
Alds
0.2
0.2
0.2
0.1
0.1
0
Figure 4: Evolution of Term and Term II (Eq across training epochs on CIFAR-100 100.
Here we study the effect of the X(t) and (t). Note for time independent constants we ignore the argument inside (-).
Formally, A(t): (Exploration Dampening) mod- ulates the inertia of exploration. Larger values in- duce slower increases E, prolonging stochas- tic exploration across arms, while smaller values accelerate convergence to greedy selection. On the other hand x (t) (Exploration Sharpness) controls the curvature of the annealing sched- ule. High (t) enforces
Loods (210 292, wn-3)
Matil Landle (4 - a.
riteed)
Lept-00
186
30
30
Divateecio Eoods
MepaayMa
abrupt shift to ploitation, while low (t() yields smoother, pro- longed exploration phases. As shown in Figure 5, for any X(t), increasing т leads to a higher degree of exploitation. For effective learning, the policy must exploit frequently while retain- ing sufficient exploration to ensure coverage of the state space. æ = 1.5 offers suitable trade- off predominantly exploiting with occasional exploration whereas π = 1.0 explores too uni- formly and 0.5 almost always explores. Hence, = 1.5 emerges as the most effective choice.
Fitudd)
Figure 5: Arm selection distribution over epochs CIFAR-100 Diversity based submodular func- tions become increasingly active during training.
Distribution of Expleradion Choiees Over Time Different and
11mppllor, dmenptont
valuees
0.8 0.8
a-555
1.0
1.5
Computational overhead of Submodular Op- timization: Submodular maximization is NP- hard, but most practical solvers use the greedy algorithm, which guarantees (1 - 1/e) approx- imation [35]. Table 3 discusses the tradeoff in- curred for the submodular maximization prob- lem w.r.t overall subset selection that involves gradient computation. In our LLM fine-tuning setup on MMLU, LLAMAA-7B using LoRA of rank 128, Table 3 shows that submodular se- lection takes 0.8 ms on average. while gradient computation takes 630 ms ms-a 800x gap.
a.u
Mowe Mit we
ud mereax
a
Atd
10
HD eetan
MO wetan
Figure 6: Cumulative exploration vs. exploitation
choices over time CIFAR-100.
Computation Breakdown
Average time
Gradient Computation Submodular Maximization
630 ms
0.8 ms
Total time for Subset Selection
640 ms
Table 3: Runtime breakdown showing submodular selection adds negligible overhead.
Thus, gradient computation remains the primary bottleneck, and submodular selection adds negligible overhead.
6 Conclusion
We introduce ONLINESUBMOD, a Sandit-guided framework for online submodular subset selection that provides a principled alternative to traditional curriculum learning paradigms. By dynamically optimizing utility-driver reward function, ONLINESUBMON effectively balances the trade-off between accuracy and efficiency across diverse training budgets. Our extensive empirical evaluation demonstrates consistent gains over strong state-of-the -frt baselines on multiple benchmarks. Future work will focus on extending the proposed greedy utility metric to train neural scoring models, thereby enabling scalable and adaptive subset selection in large-scale pretraining regimes.

---

7 Acknowledgements
We thank the anonymous reviewers for their constructive feedback and insightful suggestions that helped improve the quality of this work. PC acknowledges the Microsoft Research India PhD Award and Prime Minister Research Fellowship to support this research work. GR thanks Bank of Baroda Chair Professorship. We also acknowledge the computing resources provided by the Department of Computer Science and Engineering at IIT Bombay. In addition, we are exceptionally grateful to the BhararGen Initiative for providing compute resources for conducting large scale language model experiments. Finally, we thank our colleagues and collaborators for valuable discussions and feedback throughout the course of this research process.
References
[1] Abhinab Acharya, Dayou Yu, Qi Yu, and Xumin Liu. Balancing feature similarity and label vari- ability for optimal size-aware one-shot subset selection. In Forty-first International Conference on Machine Learning.
[2] Rahaf Aljundi, Klaas Kelchtermans, and Tinne Tuytelaars. Task-free continual learning. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pages
1 11254-1 1 1263, 2019.
[3] Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. In ICLR, 2020.
[4] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pages 41-48, 2009.
[5] Andrew Bian, Joachim M Buhmann, and Andreas Krause. Guarantees for greedy maximiza- tion of non-submodulla functions with applications. In International Conference Machine Learning (ICML). pages 498-507, 507,507222 2017.
[6] Lawrence D Brown. Estimation with incompletely specified loss functions (the case of several location parameters). Journal of the American Statistical Association, 407357): 1975.
[7] Daniele Calandriello, Michal Derezinski, and Michal Valko. Sampling from k-dpp without looking at all items. Advances in Neural Information Processing Systems, 33:6889-666 66999,68890888 2020.
[8] Prateek Chanda, Shrey Modi, and Ganesh Ramakrishnan. Bayesian coreset optimization for personalized federated learning. In The Twelfth International Conference on Learning Representations.
[9] Ethan R Elenberg, Rajiv Khanna, Alexandros G Dimakis, and Sahand Negahban. Restricted strong convexity implies weak submodularity. The Annals of Statistics, 46(6B)::559-3566 2018.
[10] Kazuya Fujita, Kensuke Okada, and Kentaro Katahira. The fisher information matrix: A tutorial for calculation for decision making models. 2022.
[11] Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427 486, 2011.
[12] László Györfi, Michael Kohler, Adam Krzyzak, Harro Walk, et al. A distribution-free theory of nonparametric regression, volume 1. Springer, 2002.
[13] Nicholas Harvey, Christopher Liaw, and Tasuku Soma. Improved algorithmss for online submod- ular maximization via first-order regret bounds. Advances in Neural Information Processing Systems, 33:123-133, 2020.
BBaaratGen http://bhharatgen.tchh/
10

---

[14] Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi. Gradient methods for submodular maximization. Advances Neural Information Processing Systems, 30, 2017.
[15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and paltern recognition, pages 770-778, 2016.
[16] Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril Thomas Wang. Timothée Lacroix, and William El Sayed. Mistral 7b, 2023.
[17] Angelos Katharopoulos and François Fleuret. Not All Samples Are Created Equal: Deep Learning with Importance Sampling, In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pages 3536-2545 PMLR, 10-15 Jul 2018. Also available as ar arXiv:1803.00%%
(18) Krishnateja Killamsetty, Sivasubramanian Durga, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer. Grad-match: Gradient matching based data subset selection for efficient deep model training. In International Conference on Machine Learning, pages 5464-5474. PMLR, 2021.
[19] Krishnateja Killamsetty, Alexandre V Evfimievski, Tejaswini Pedapati, Kiran Kate, Lucian Popa, and Rishabh Iyer. Milo: Model-agnostic subset selection framework for efficient model training and tuming. arXiv preprint arXiv:2301.13287, 2023.
[20] Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glis- ter: Generalization based data subset selection for efficient and robust learning. Proceedings of the AAAI conference artificial intelligence, volume 35, pages 81 10-8118 18, 2021.
[21] Suraj Kothawade, Vishal Kaushal, Ganesh Ramakrishnan, Jeff Bilmes, and Rishabh Iyer. Prism: rich class of parameterized submodular information measures for guided data subset selection. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 10238- 10246. 2022.
[22] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[23] Yann Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
[24] Yann LeCun, Corinna Cortes, Chris Burges, et al. Mnist handwritten digit database, 2010.
[25] Tsung-Y Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer vision, pages 2980-2988, 2017.
[26] David Lopez-Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continual learning. Advances in neural information processing systems, 30, 2017.
[27] Ilya Loshchilov and Frank Hutter. Online Batch Selection for Faster Training of Neural Networks, 2015.
[28] Adyasha Maharana, Prateek Yadav, and Mohit Bansal. D2 pruning: Message passing for balancing diversity and difficulty in data pruning. arXiv preprint arXiv:2310.0793/ 2024.
[29] James Martens and Roger Grosse. Optimizing neural networks with tronecker-factordd approx- imate curvature. In International conference on machine learning, pages 2408-244 2417. PMLR, 2015.
[30] Sören Mindermann, Jan Brauner, Muhammed T Razzak, Mrinank Sharma, Andreas Kirsch, Winnie Xu, Benedikt Höltgen, Aidan N Gomez, Adrien Morisot, Sebastian Farquhar, et al. Pri- oritized training on points that are learnable, worth learning, and not yet learnt. International Conference Machine Learning, pages 15630-15649, PMLR, 2022.

---

[31] Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrak, and Andreas Krause. Fast constrained submodular maximization: Personalized data summarization. In International Conference on Machine Learning (ICML), pages 1358-1367, 2016.
[32] Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovee. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning, pages 6950-6960.
PMLR, 2020.
[33] Marwa Nair, Kamel Yamani, Lynda Said Lhadj. and Riyadh Baghdadi. Curriculum learning for small code language models. arXiv preprint arXiv:2407.10190 2024.
[34] Sanmit Narvekar, Bei Peng, Matteo Leonetti, Jivko Sinapov, Matthew E Taylor, and Peter Stone. Curriculum learning for reinforcement learning domains: A framework and survey. Journal of Machine Learning Research, 21(181::1550, 2020.
[35] George I. Nemhauser, Laurence A Wolsey, and Marshall Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming. 14:265-294 1978.
[36] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
[37] Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-leariing algorithms. arXiv preprint 1rXiv:1803, 02099, 2018.
[38] Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. Estimating training data influence by tracing gradient descent. Advances in Neural Information Processing Systems, 33:19920-19930, 2020.
[39] Michael Rawson and Radu Balan. Convergence guarantees for deep epsilon greedy policy learning. arXiv preprint arXiv:21 2021.
[40] Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert- networks. arXiv preprint arXiv: 1908. 10084, 2019.
[41] Tim Roughgarden and Joshua R Wang. An optimal algorithm for online unconstrained submod- ular maximization. arXiv preprint arXiv: TXXXvv/80600334444 2018.
[42] Levent Sagun, Utku Evei, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the hessian of over- wer-parameerried neural networks. arXiv preprint 1rXiv:1706.044555 2017.
[43] Haizhou Shi, Zihao Xu, Hengyi Wang, Weiyi Qin, Wenyuan Wang, Yibin Wang, Sayna Ebrahimi, and Hao Wang. Continual learning of large language models: A comprehensive survey, arXiv preprint arXiv:2404. 16789, 2024.
[44] Matthew Staib, Bryan Wilder, and Stefanie Jegelka. Distributionally robust submodular maxi- mization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 506-516. PMLR, 2019.
[45] Matthew Streeter, Daniel Golovin, and Andreas Krause. Online learning of assignments. Advances in neural information processing systems, 22, 2009.
[46] Shivakanth Sujit, Somjit Nath, Pedro Braga, and Samira Ebrahimi Kahou. Prioritizing samples in reinforcement leamnin with reducible loss. Advances in Neural Information Processing Systems, 36:23237-23258, 2023.
[47] Artin Tajdini. Lalit Jain, and Kevin Jamieson. Nearly minimax optimal submodular maximiza- tion with bandit feedback. Advances Neural Information Processing Systems, 37:96254- 96281, 2024.
[48] Haoru Tan, Sitong Wu, Wei Huang, Shizhen Zhao, and Xiaojuan Qi. Data pruning by information maximization. International Conference on Learning Representations, 2025.
12

---

[49] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiao- qing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zhengxu Yan, Iliann Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. IJama 2: Open Foundation and Fine-Tuned Chat Models, 2023.
[50] Gido M Van de Ven and Andreas S Tolias. Three scenarios for continual learning, arXiv preprint 1904:01900007334 2019.
[51] Vladimir Vapnik. Principles of risk minimization for learning theory. Advances in neural information processing systems, 4, 1991.
[52] Jiachen Tianhao Wang. Tong Wu, Dawn Song, Prateek Mittal, and Ruoxi Jia. Greats: Online selection of high-quality data for Ilm training in every iteration. Advances in Neural Information Processing Systems, 17:131197-131233, 2024.
[53] Kai Wei, Yuzong Liu, Katrin Kirchhoff, Chris Bartels, and Jeff Bilmes. Submodular subset selection for large-scale speech training data. In 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3311-3315. IEEE, 2014.
[54] Yikai Wu, Xingyu Zhu, Chenwei Wu, Annie Wang, and Rong Ge. Dissecting hessian: Under- standing common structure of hessian in neural networks. arXiv preprint arXiv:2010.0426.. 2020.
[55] Mengzhou Xia, Sadhika Malladi, Suchin Gururangan, Sanjeev Arora, and Danqi Chen. LESS: Selecting influential data for targeted instruction tuning. In International Conference on Machine Learning (ICML), 2024.
[56] Sifan Yang, Yuanyu Wan, and Lijun Zhang. Online nonsubmodular optimization with delayed feedback in the bandit setting. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 21992-2200X 22000, 2025.
[57] Zheng Zhang, Junxiang Wang, and Liang Zhao. Curriculum learning for graph neural networks: Which edges should we learn first. Advances in Neural Information Processing Systems, 36, 2024.
[58] Haizhong Zheng, Rui Liu, Fan Lai, and Atul Prakash. Coverage-centric coreset selection for high pruning rates. arXiv preprint arXiv:2210. 15809, 2022.
[59] Yuwei Zhou, Zirui Pan, Xin Wang, Hong Chen, Haoyang Li, Yanwen Huang, Zhixiao Xiong, Fangzhou Xiong, Peiyang Xu, Wenwu Zhu, et al. Curbench: Curriculum learning benchmark. In Forty-first International Conference Machine Learning.
13

---

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]
The main claims in the abstract and introduction are consistent with the techni- cal contributions and empirical results presented in the paper. We clearly state our proposed method, theoretical foundations, and experimental validation, and these are substantiated in the body of the work without overstatement omission.
Justification:
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
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 other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes we have discussed the limitations of our work specific portions of the paper, and have also added in Appendix
Guidelines:
The answer NA means that 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 separate "Limitations" section in 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 on 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 few datasets or with few 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 or 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 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 be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best 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 not penalize honesty concerning limitations.
3. Theory assumptions and proofs
14

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
The theoretical proofs provided in the Appendix H
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 referenced in the statement of any theorems.
The proofs 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 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 supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed 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 not)?
Answer: [Yes]
Justification:
The full codebase is provided along with the supplementary material
Guidelines:
The answer NA means that the paper does not 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.
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 a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS 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 to reproduce that algorithm.
(b) If the contribution is primarily new 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 access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
cases, in which
15

---

reproducible, they 5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: The full codebase is provided along with the supplementary material along with running instructions commands in the Readme. Further, we test our algorithm open source datasets only which we have cited sufficiently and have provided links in the codebase Readme file.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://iips.c/ppbbic quides/CodeSubmissioooollo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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 reproduce the results. See the NeurlPS code and data submission guidelines (https: Sttpubicgggiid//Codduuuuumnnie
for more details.
The authors should provide instructions on data access and preparation, including how 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 in supplemental material (appended to the paper) 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 understand the results?
Answer: [Yes]
Justification:
All specific training details are specified in the Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: Yes]
Justification:
We report std error of most our results over runs per baseline on average.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

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.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma emror bars, but one should state it. 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 error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: All specific training and compute details are specified in the Appendix D Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:://cerrip..ccppppicletttltd
Answer: [Yes]
Justification:
Yes we have reviewed the Code of Ethics Guidelines.
Guidelines:
The answer NA means that the authors have 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 is special consid- eration due to laws or regulations their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: We have not discussed any potential societal impacts (neither positive nor negative). We do hope that since able to show significant efficiency improvement both across different modalities (cspecially in LLM settings) this may siginificant potential impact for Large scale L.LM training.
Guidelines:
17

---

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.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications,
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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: In this work, are not releasing any generative models or new datasets.
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 we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators 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:
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 used and, possible, include a 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.
18

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswitheode. www.ithoood..cmmaatsttttttt com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information 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: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemoodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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. Crowdsoureing 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 details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper doess not involve crowdsourcing nor research with human subjects.
Including this information 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 the NeurIPS Code of Ethics, workers involved in data collection, curation, or 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
Question: 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 the requirements of your country institution) were obtained?
Answer: [NA]
Justification: [NA]
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.
19

---

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 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: Our paper's methodology is not involved in LLM usage and nor is the experi- mental pipeline.
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 our LLM policy (ttp:://eeiiisccccooooerrece/ess for what should or should not be described.
20

---

Supplementary Material: Bandit Guided Submodular Curriculum for Adaptive Subset Selection
Contents
Appendices
A Organization of the Appendix
22
Notation Summary
22
Implementation Details
22
C.I Details ahout model architectures used
22
C.2 Details submodular functions implementation
23
C33 Gradient Computation
23
C.4 Evaluation metrics
24
D Experimental Setup Details
25
D.I Software and Hardware
25
D.2
Language Model Experiments
D.3
Vision Model Experiments
25
D.4
Baseline Training Detuils
26
D.5
Comparison between DINO and Gradient-Basd Features for Submodular Selection
27
Fisher Information Matrix
E
Additional Experiments
28
E.1
Sensitivity of Validation Dataset Configuration
28
F.2
Effect of Suhmodular Functions Individually RANDOM Selection
28
F.3
Additional Experiments on Vision datasets
30
E.4
Additional Experiments on Large Language Models
31
F Details of Submodular Function used in all training settings Diversity based Submodular Function Representative based Submodular Function
32
................................
32
F2
G
Additional Related Work
33
G.1
Online Submodular Maximization
33
G.2
Pruning Mechanisms
34
H
Main Theoretical Results
35
H.1
Proof for permutation invariance of Expected Marginal Gain
................................
35
H.2
Theorem: Copaccty-Controlli
Risk Convergence Theorem
35
H.3
No-Regret Bounds under Constant X6-)
35
H.4
Regret bounds in the case of growing with time exploration dampening function
39
I Broader Impact
42
21

---

Supplementary Material: Bandit Guided Submodular Curriculum for Adaptive Subset Selection
A Organization of the Appendix
The appendix is organized follows. Section provides summary of the impact of work.Section provides a summary of the notation used throughout the paper. Section H presents main theoretical results. Section outlines the experimental setup and implementation details for both vision and language model tasks. Section discusses additional related work. Section describes the various submodular functions employed in our experiments.
B
Notation Summary
Table 4: Table of Notations
Topic
Notation
Explanation
D Prain
Entire Training Set consisting of n instances
Data
D Dval
Entire Validation Set consisting of instances
(sub)Sets
2i
i-th training instance in a batch
Indices
B,
Denotes the full sized t-th step train minibatch: { [8.
Byat
Denotes the full sized f-th step validation minibatch
Denotes the f-th step minibatch being constructed uptil -;
B((+i)
i.c. { )=1
Optimal subset obtained when submodular function f(a)) is applied
Sopt
(at)
0"
Optimal model parameter (vector)
0,
Model parameter 7th step
Parameters
0,+1
Model parameter at 1) step
Strongly convex instance-wise loss function
C:
Total loss over mini-batch
Loss Function
Utility metric capturing validation loss drop for a particular validation data point
(B; 2)
U.( Byal)
Aggregated utility metric validation set
(Exploration Dampening) modulates the inertia of explo- ration
x(t)
Hyperparams
Reward function
E,
Exploration
Exploration-exppootaaie exploitation threshold
dii Tepe
Diversity/nepresenaaivee function subsets Random sample for trade-off (Exploration Sharpness) controls the curvature of the anneal- ing schedule rule
sub?
( ~ Uniform(0.) 1)
(1)
C
Implementation Details
C.1 Details about model architectures used
Vision Model Architecture Details:
The ResNet18 model [15] architecture begins with basic block, which composed of two main sections. The first section consists of a convolution layer followed by batch normalization layer, and then ReLU activation function. The second section similarly comprises a convolution layer followed by batch normalization. This entire busic block is repeated twice for each of the four layers in the network. These layers progress with input dimensions of [64, 128, 256, 512] to form the complete ResNet18 8 architecture.
22

---

Language Model Architecture Details
The LLaMA-2-78 2-BB model is a decoder-only transformer comprising approximately 7 billion param- eters. It includes 32 transformer layers, each built with pre-normalization using RMSNorm and employing the SwiGLU activation function. The self-attention mechanism uses multi-head causal attention with 32 heads and hidden dimensionality of 4096. Rotary positional embeddings (RoPE) are applied to the query and key vectors within each attention head. The model begins with learned token embedding layer and concludes with a tied output projection layer to predict the next token. Mistral-7B-vO. is architecturally similar to -LaMA-2-7B. also featuring 32 transformer layers and a 4096-dimensional hidden state, but introduces several Sificiency-focusee modifications. It uses grouped-query attention (GQA) with 8 query groups across 32 heads, improving inference throughput. Furthermore, Mistral replaces full causal attention with sliding-window attention to handle long contexts more efficiently. As with LLaMA, it utilizes RoPE for positional encoding and SwiGLU activations. These optimizations maintain strong modeling performance while enabling greater scalability in both training and inference settings.
C.2 Details submodular functions implementation
We provide detailed formulations of the specific submodular functions employed as arms in our experiments in Section F. From an implementation standpoint, each submodular arm operates on a similarity kernel computed over the set of instances within a given batch. This kernel, typically represented as symmetric positive semi-definite matrix, encodes pairwise affinities between samples based on their embedding representations (e.g., cosine similarity or RBF kernel). Once the similarity structure is established, any submodular function can be instantiated over this ground set such as facility location, log-determinant, or graph-cut diversity, representativeness property being optimized.
derriins-ddppddiing on the desired coverage,
To operationalize this, we leverage the Submod1 i library* an open open-source framework maintained by the Decile organization", which provides efficient and modular implementations of a wide family of submodular functions. The library supports both dense and sparse similarity representations and includes greedy well as lazy-greedy optimization routines, enabling scalable computation even for large batch sizes.
C.3 Gradient Computation
Computing full-model gradients in modern deep networks is computationally prohibitive due to the extremely high dimensionality of parameter ppaces-often exceeding billions of parameters for large vision or language models. Moreover, for the purpose of subset selection, what is typically required not the full parameter gradient but an informative proxy that captures the relative contribution of individual samples to the model's 's training dynamics.
Following this motivation, we adopt -rradeet approximations that preserve discriminative signal while substantially reducing computational cost. Specifically, for vision models, we compute gradients only with respect to the last linear classification layer, as in [3]. This choice leverages the empirical observation that gradients in earlier layers are highly correlated and redundant, and that last-layer gradients retain sufficient information to distinguish hard, redundant, or noisy samples based on their contribution to the decision boundary.
For large language models (LLMs), computing full backpropagation across all transformer layers is infeasible. We therefore restrict gradient computation to Low-Rand Adaptation (LoRA) adapter parameters (rank 128), following the setup of [52]. This approach not only reduces memory and compute overhead by several orders of magnitude but also captures localized curvature information relevant the fine-tuning instruction-followin low-dimensional subspace most sensitive to task adaptation, their gradients provide a faithful and low-noise estimate of per-sample learning signals.
objective. Since LoRA adapters are trained in the
Importantly, both approximations maintain gradient informativeness under the assumption that the selected subspace (last layer or adapter) spans the most discriminative directions of parameter updates. Prior empirical evidence (see [3, 52]) shows that subset selection, influence estimation, and sample
hww.://wwdddii.rddddddddeeeee.oo https://decile..rgg/
23

---

reweighting methods computed in these reduced spaces closely match those computed with full gradients. In our experiments, we verify that this approximation incurs negligible performance degradation while providing up to 30x faster per-batch computation. Thus, the proposed gradient computation scheme achieves favorable balance between computational efficiency and fidelity of learning signal for submodular subset selection.
Warm-starting Data Selection, A common challenge in data subset selection methods lies in the instability of carly-stage gradients. During the initial epochs of training, model parameters are far from any local minimum, and per-sample gradients tend to be highly noisy and uninformative. Consequently, performing subset selection too early can result in biased or suboptimal subsets that fail to represent the underlying data distribution learning dynamics. To mitigate this issue, for the image experiments, we conduct a warm-start strategy, wherein the model is first trained for a small number of epochs on the full dataset before invoking any subset selection procedure.
Concretely, for each algorithm considered in this paper (i.e., ONLINESUBMOD GRADMATCHI, GRADMATCHPH, CRAIG, CRAIGPB, and GLISTER.). we include a warm-start variant. Let 7 denote the total number of training epochs and & the subset size. We define two quantities: Ty (the number of full- hill-training epochs prior subset selection) and T. (the number of epochs during which subset selection is active). We set these in proportion as T- kT, T T.k where n is the total number of training samples and x E (0, 1] is the fraction of total training epochs used for subset selection. This parametrization ensures that the effective compute budget remains comparable across methods, while allowing early-stage training to stabilize the model representation before adaptive data selection begins.
n
Empirically, we observe that performing a few epochs of full-data warm-up (Ty) consistently improves convergence stability and downstream accuracy across all subset selection algorithms. The warm- start phase enables the gradient space form meaningful geometry, allowing the submodular or gradient-based selection objectives to more accurately identify informative and diverse samples. In contrast, starting selection from random initialization often leads to premature overfitting or unstable subset composition due to noisy or poorly conditioned gradients.
Setting Ty too large, however, diminishes the benefit of subset selection, as the model effectively performs full training with minimal adaptive sampling. In this limit, the behavior approaches that of the full-batch baseline with early stopping. which we include as control setting our experiments. Thus, the warm-start scheme provides a principled balance between computational efficiency and representational stability the benefits of subset-based training while ensuring robust and smooth convergence.
C.4 Evaluation metries
For image classification experiments, we report the standard test accuracy as the primary performance metric, measured as the proportion of correctly classified samples on the held-out validation or test split. This metric provides direct and interpretable indicator of the model's generalization performance under different subset selection strategies.
Image Classification:
In addition to accuracy, we evaluate the computational efficiency of our method by comparing the total training time required to reach convergence across different selection policies. To ensure fair comparison, all other hyperparameters- inclsddin optimizer configuration, learning rate schedule, batch size, and data augmentations-art held fixed across runs. The only varying factor is the subset selection mechanism applied each training step.
We define the speedup metric with respect to the baseline model trained using full-batch selection (i.c., without any submodular or adaptive sampling). Formally, if Tiull denotes the wall-clock training time for the full-batch model and Tsub denotes the time under our submodular selection strategy, Thu.
the speedup is given by Speedup = Tus A higher speedup thus indicates a more efficient training regime, achieved without sacrificing downstream accuracy. practice, we observe consistent gains in training submodular objective, confirming that adaptive selection substantially reduces redundant gradient computations while maintaining comparable predictive performance.
in the range of 3x-8xx 111-8xxeepp depending on the dataset and the choice of
24

---

D Experimental Setup Details
D.1 Software and Hardware
Vision Experiments All experiments were conducted using Python 3.10.13 and PyTorch 2.1.2 Our proposed methods, ONLINESUBMOD and ONLINESURMOD-Bacch along with their corresponding ablations, were trained on NVIDIA RTX A6000 GPUs (48 GB). Baseline methods, including RHO-LOSS and BOSS, were also trained using the same GPU configuration to ensure comparability.
For reference, a typical training run of our ResNet 8- 8-based model on an RTX A6000 consists of 300 epochs, with each epoch averaging approximately one minute (excluding certain baselines). Model checkpointing is employed to retain only the best-performing model based on validation accuracy, as well as the final model. Running multiple training jobs concurrently on the same GPU incurs only slight overhead in training time due to resource contention.
D.2 Language Model Experiments
We experiment for the LLM finetuning setup using RANDOM subset of datasets from MMLU, and TydiQA. We choose Sociology, Policy, History, Anatomy, ML, Ehics, Genetics, High School Biology, High School Chemistry. All language model experiments, including both our proposed methods and the baselines, were conducted using 8 NVIDIA H100 GPUs. Additionally, Weights & Biases (WandB) wwandb was used to manage and monitor experiments. For all experiments we take batch size of 16, initial learning rate of 2c-5 using adam optimizer with default state, finetuned on 10% of LESS[55] version of WebTet.
Additional Experiment Results: For MMLU we also showcase additional experiments on LLaMa2- 7b and Mistral-7b for TydiQA, later in the appendix.
Mathematical definitions of the submodular objectives used as arms are provided in Appendix For this experiment, each arm is mutual information variant of a classical submodular function, designed to maximize (X; Q) = f(X) + f(Q) s(X U Q), where X is the candidate training set, Q is the validation set, and f base submodular function (Facility-Location,, Graph-Cut, or Log-De bog-Determinat)..
We mutual information forms to ensure the selected subset is explicitly conditioned the current validation set, making the acquisition process adaptive to the downstream task. Features for X and Q derived either from Contence-BERi embeddings or from gradient vectors, with the latter shown to yield better alignment with specifcc error signals and improved selection performance.
D.3 Vision Model Experiments
The experimental setup was configured evaluate the proposed method on several datasets, including CIFAR-10, CIFAR-100 100, Tiny- me2geNe and SVHN. The data module used batch size of 128, with four workers for data loading. The model architecture employed was ResNet18 [15], and the training followed curriculum-baser mode, progressively utilizing 10%, 30%, and 50% of the training data. The optimizer used was SGD with a learning rate of 0.05, momentum of 0.9, weight decay of 0.0005, and Nesterov momentum enabled.
For all our settings (across different baselines and dataset), we consider ResNet18 [15] as our primary model with the following architecture and training details:
In our training setup, employed batch-wise Nesterov accelerated gradient descent with batch size of 128. The optimization configuration included a learning rate of 0.05 and a momentum of 0.9, alongside cosine- aonnaliann scheduler.
Across all dataset comparisons, we set the submodular function budget to 10%, 30%, and 50% of the entire batch size.
We conduct experiments across a range of standard vision benchmarks. For the MNIST dataset, we use 60,000 training instances, 10,000 test instances, and 10,000 validation instances, with training proceeding until full convergence, typically around 200 epochs. On CIFAR-
Dataset Specifies.
/itis///
25

---

10, we use 50,000 training instances, 10,000 test instances, and 10,000 validation instances, with models trained for up to 300 epochs. For CIFAR- we similarly use 50,000 training examples spread across 100 classes (500) per class), and a validation set of 10,000 examples (100 per class). The SVHN dataset comprises 73.257 training images across 10 classes with variable class frequencies, and validation set of 26,032 images distributed proportionally. Finally, for TINYIMAGENET we use 100,000 training images across 200 classes (500 per class), and a validation set of 10,000 images (50 per class), covering the same label space as the training data.
D.4 Baseline Training Details
We compare our method ONLINESUBMOD with several state of the art baselines for our experiments:
MAX-Loss [27]: Within each training batch, the loss is computed for every example. A fixed fraction (e.g.. top-K%) of samples with the highest per-example loss selected for gradient computation and model update. This assumes that high-loss samples are currently mis- mis-predicted and could contribute the most to updating the decision boundary.
GRADNORM [17]: The 2a norm of each example's 's per-sample gradient i.e. || [o is com- puted, and subset with the highest norms is selected for each batch. This prioritizes examples inducing the largest parameter updates under the current model, helping direct learning toward sensitive or uncertain regions.
RHO-Loss [30]: Each example's reducible loss is estimated as the difference between the current model's loss and its irreducible loss, the latter approximated by small auxiliary model trained on held-out clean data. Examples with high reducible loss are selected, as they are considered learnable but not yet learned, making them useful for continued training. For LLM experiments, we use L -anei------nntuuuu ruct as our auxiliary model. For image experiments, we begin by training an irreducible model the specific task for 100 epochs. Subsequently, we precompute the irreducible losses for the training set, which are required for the target model training. During the target model training phase, we train the model for 300 epochs across the CIFAR- 10, CIFAR- 100, SVHN, and TINY TIAGENTT datasets, using subset ratios of 0.1, 0.3, and 0.5. We employ the ResNet-18 architecture for both the irreducible model and the target model. For training, we use the SGD optimizer with Nesterov accelerated gradient descent, a batch size of 128, and the following configuration: a learning rate of 0.05, momentum of 0.9, and a cosine-ane cosine-annealine annealing scheduler. One observation we made is that RHO Loss converges to reasonably good accuracy within a few epochs, but further training does not significantly improve performance, and it fails to reach the accuracy levels of other state-of-the-art (SOTA) baselines.
SBERT [40]: In this case, each training and validation example is encoded into sentence embedding using a pre-trained SBERT model. Cosine similarity is computed between training examples and the validation set, and those with the highest average similarity are selected. This favors examples that align semantically with the validation distribution.
For GREATS [52], each example's 's impact on the loss is approximated using first-order Taylor expansion of the objective. For model parameters and a batch fø1, ,...., gradients V ((,;; 8) used to estimate loss reduction. A greedy selection strategy then chooses the subset expected to most decrease validation loss under this approximation.
For fair comparison against our model we considered the configuration where subset selection happens at every epoch for all the basclines with a lazy optimizer. Due to our multi-class image classification setup utilise CrossEntropy loss for our model training.
BOSS [1]: For BOSS, select the subset, we first initialized a model by training using the full dataset. With the help of the training dynamics obtained from the initialized model, we calculated the difficulty score for each sample that is used select the subset. We evaluated the selected subset keeping the subset fixed and using it to train a new RANDOM initialized model. For the difficulty score, we experimented using the EL2N score because can be efficiently computed early on during training. We trained the model for 300 epochs across the CIFAR- 10, CIFAR-100 100, SVHN and TINYIMAGENET datasets, using subset ratios of 1. 0.3, and 0.5. We employed ResNet model using SGD with learning rate of 0. and momentum of 0.9 with a batch size of 128.
26

---

useful surrogate D.5 Comparison between DINO and Gradient-Basd Based Features for Submodular Selection
To evaluate how closely our feature representations must align with the downstream objective, we compared two ways of representing each training item when optimising submodular acquisition functions (and their mutual-informe information variants):
Dro
Figure 7: Comparison of Fashion-MNIST with DINO-embeddings, and with Gradient Features for submodular optimization
DINO embeddings. We obtain fixed d-dimensional feature vector for every image by running it through frozen DINO vision transformer, exactly as one would CLIP encoder. These representations are task aggnosggncicc and remain static throughout training.
2. Gradient-basse features. At every training step compute the gradient of the scalar loss with respect to the parameters of the final layer. We average these per-example gradients within the mini-batch to form single vector?. For mutual-information objectives, validation gradients serve as the query features.
Figure shows that gradient features yield substantially higher test accuracy across all subset sizes: they encode task-specific error signals that guide the submodular optimiser toward examples most useful for loss reduction, whereas DINO embeddings capture only generic visual similarity. Hence, directly leveraging gradicnts as features is the more effective choice for data subset selection in this setting.
D.6 Fisher Information Matrix
Fisher Information Matrix Approximation An alternative and potentially more informative ap- proach to approximating the Hessian is through the use of the Fisher Information Matrix (FIM) [10]. The FIM provides insights into the curvature of the loss landscape and for the Hessian. While the exact computation of the FIM requires calculating an expectation, which can be computationally intensive, can be efficiently approximated using an exponential moving average of the outer product of the gradients from the validation data points.
Let Ω2 = g ( 0, 9))g(z) Zz, 0T) denote the outer product of the gradient for the ith data point the current batch B. The
B5 Σ
22 Si (t-1)
ift =
(t) H
approximate FIM H.g at time step for the current mini-batch B, can be computed recursively
=
a B,-1 +
C [3,
Σ E. Si
else
where H (t-1) t for the mini-batch B; and (0, 1] is the smoothing
H..., is the approximate FIM at the previous time step
(9)
parameter for the exponential moving average. This recursive formulation provides computationally efficient approach approximating the Hessian, particularly in high-dimensional settings where direct Hessian computation prohibitively expensive.
'Using the batch-wal wise average was consistently superior to concatenating per-example gradients, and last- layer gradients sufficient while keeping the computation inexpensive.
27

---

E
Additional Experiments
E.1
Sensitivity of Validation Dataset Configuration
To better understand the influence of validation data composition model performance, investi- gate how sensitive the algorithm is to different validation set configurations. In particular, we examine what occurs during the early stages of training when the validation dataset includes harder samples that the model has not yet adequately learnt. This analysis provides a deeper perspective on how the affect optimization dynamics and generalization,
distribution and difficulty validation examples thereby strengthening the empirical validity of our findings.
Specifically, aim understand the following questions:
Q1: To what extent is the algorithm's 's performance sensitive to the configuration and composition of the validation dataset?
Q2: How does the presence of harder, yet-unlearned samples in the validation set during early training stages affect convergence and generalization?
To better understand this issue, we conducted a con- trolled experiment CIFAR-100 100 (300 epochs) where we varied the hardness of the validation dataset. Hardness was measured via gradient where the gradient is calculated w.r.f model parame- ter at that time step. In accordance with other litera- ture, a crude way to approximate difficulty of a sam- ple is check if the gradient norm is high. (higher gradient norm ~ harder example). We compared four validation subset configurations:
Validation Subset
10%
20 %
30% %
Easiest
72.3
74.4
76.03
EasyHard
73.1
74.5
76.4
HardEasy
72.29
74.6
76.2
Hardest
71.31
74.3
75.9
Table 5: Final test accuracies under different 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%.
Observations:
Validation sets composed of the most difficult examples tend to yield lower performance, particu- larly when smaller subsets are used. This decline likely stems from noisy overly pessimistic reward signals during the early stages training. In contrast, mixed validation configurations such EasyHard and HardEasy generally perform best, indicating that balanced distribution of sample difficulty across training can enhance robustness. These findings suggest that further exploring how validation sample difficulty and ordering interact especially through the lens of curriculum learning could be promising direction for future work. Importantly, even validation sets containing difficult samples early in training do not lead instability model collapse.
E.2 Effeet of Submodular Functions Individually and RANDOM Selection over Arms
To assess the contribution of the multi-armed bandit formulation in our framework, we perform ablation experiments on CIFAR-100 (10% subset, 300 epochs) under two simplified settings: (a) using a single, fixed submodular arm throughout training (i.e., no bandit-driven adaptation), and (b)R ANDOMly selecting arm at each round (i.e., explore-exploit balancing). These ablations isolate the effect of static versus dynamic subset selection policies on training efficiency and generalization.
28

---

Selection Strategy
Accuracy (%)
We compare various submodular selection strate- gies that define the reward structure of the cur- riculum. Representative functions (e.g., Graph- Cut, FacilityI.ocation ensure the selected subset reflects the global data distribution, while Divertety-oriented functions (e.g., DisparitySum, LogDeterminant) encour- age maximal dissimilarity among chosen sam- ples. These functions capture different inductive biases: representation versus decorrelation.
DisparitySum (Div., Static)
68.6
Lacilityl.ocation (Rep., Static)
72.0
LogDeterminant (Div., Static)
71.1
promote coverage and
GraphCut (Rep.. Static) Random arm per round
72.6
72.0
ONLINESURMOD (ours)
73.6
Table 6: Performance comparison of individ- ual and RANDOM arm selection strategies on CIFAR-100, ONLINESUBMOD adaptively bal- ances diversity and representativeness over train- ing epochs.
Our proposed ONUUUOOO method dynamically alternates hetween these functions through an adaptive explore exploit policy governed by the bandit controller. This dynamic weighting enables the model-whether ResNet-18 backbone or small LLM fine-tuning setup-to exploit high-yield submodular while continually exploring others that may improve validation loss or perplexity.
Observations:
Different submodular functions show complementary but limited strengths. Coverage-based methods such as GraphCut and FacilityLocation converge quickly early in training, while diversity- based ones like DisparitySum and LogDer encourage better generalization but can become unstable when applied uniformly. Random arm selection gives reasonable results, suggesting that diversity matters, but it lacks feedback to adapt to validation performance. In contrast, the proposed ONN.NESUBMOD approach adjusts arm selection based on past rewards, maintaining stable balance between exploration and exploitation. This supports our main hypothesis that adaptive, reward-driven selection leads to more robust and generalizable outcomes than static or random strategies.
29

---

E.3 Additional Experiments on Vision datasets
Table summarizes batchwise data selection results across multiple vision datasets. Across all budgets and datasets, ONLINESUBMON consistently achieves the highest test accuracy while maintaining competitive lower training time compared prior methods. Notably, surpasses strong baselines MILO, and RHO-LOSS, particularly at low data budgets (10%-30%),
such as indicating superior sample efficiency and adaptivity under constrained training regimes. The provement is most pronounced CIFAR 00 and I'NYIMAGENET, where the model benefits from dynamic online selection over diverse feature manifolds. In contrast, static coreset-base based meth- ods (e.g.. CRAIG, GLISTER) exhibit slower convergence and lower performance the budget increases.
Here, red highlights the best result and blue denotes the second-bes result for each setting, Over- all. these results confirm that ONLINESUBMOD provides strong trade-off between accuracy and computational efficiency across datasets of varying complexity.
Table (Batchwise) Data Selection Results on Vision Datasets
Dataset
Selection Strategy
Test accuracy (%)
Training time (hrs)
(5dget(5%
10%
30%
50%
10%
30%
50%
CIFAR1O
FULL (skyline test accuracy)
95.09
95.09
95.09
1.73
1.73
RANDOM (skyline for training time)
77.49
89.62
91.85
0.29
0.75
0.85
CRAIG
90.07
92.4
93.12
0.26
0.62
1.54
GLISTER
91.15
92.18
92.65
0.38
1.05
1.34
GRADMATCH
92.27
93.28
93.15
0.42
0.95
MILO
92.25
93.21
94.16
0.34
0.85
0.89
RHO-LOSS
90.16
91.54
94.03
0.76
1.13
1.54
BOSS
91.64
93.04
93.8
0.36
0.94
1.18
ONLINESUBMOD (ours)
92.44
93.75
94.18
0.32
0.87
0.83
CIEARTOO
FULL (skyline for test accuracy)
76.8
76.8
76.8
1.52
1.52
1.52
RANDOM (skyline for training time)
35.03
61.93
64.67
0.15
0.42
0.78
CRAIG
67.25
72.38
73.12
0.31
0.62
1.12
GLISTER
64.27
72.36
74.62
0.26
0.57
1.3
GRADMATCH
68.34
72.36
0.22
0.48
MILO
72.36
74.66
75.60
0.15
0.44
0.82
RHO-LOSS
71.37
74.82
75.74
0.53
0.86
1.46
BOSS
71.73
73.77
75.41
0.27
0.53
0.85
OULNNESUROOD (ours)
73.67
75.46
75.78
0.165
0.47
0.82
SVHN
FULL (skyline for test accuracy)
96.49
96.49
96.49
6.436
6,436
6.436
RANDOM (skyline for training time)
93.47
95.31
95.84
0.6383
1.90
3.19
CRAIG
95.27
96.15
96.40
0.934
2.332
4.17
GLISTER
95.52
95.69
96.42
0.83
2.42
4.26
GRADMATCH
95.64
96.4
96.42
0.789
2.398
4.19
MILO
95.62
96.36
96.41
0.69
2.09
3.25
RHO-LOSS
94.64
94.27
94.85
1.08
2.56
3.94
BOSS
94.31
95.75
96.01
0.76
2.39
3.56
OULMN (ours)
95.68
96.38
96.46
0.68
2.12
3.28
MAGENET
FULL (skyline line for test accuracy)
64.36
64.36
64.36
13.4
15.4
15.4
RANDOM (skyline for training time)
19.61
35.68
43.84
1.82
4.92
6.12
CRAIG
52.42
55.56
61.48
3.27
6.46
9.23
GLISTER
51.54
56.37
62.15
2.84
5.93
GRADMATCH
52,63
58.19
61.93
2.63
5.94
7.24
MILO
53.24
59.36
62.28
1.81
4.97
6.16
RHO- JOSS
54.46
59.78
62.15
3.16
6.38
7.94
BOSS ONLINESURMOD (ours)
52.63
60.17
62.13
2.85
5.47
7.26
55.3
60.74
62.58
1.84
5.16
6.14
30

---

E.4 Additional Experiments on Large Language Models
We evaluate the evolution of test perplexity during pretraining on the MMLU benchmark using the LLAMA-2-77 model under different online batch selection strategies, Each method is trained under identical hyperparameter and compute budgets to ensure fair comparison.
(Polks)
Test Perplexity (Anatomy)
GREATS
GREATS
MasLos
Maslasa
GaalNonn
Tox. Tos.oolodd
1,000 (00-),00 0000 (001
5001
Sayp
Tor Papienity (iedntogg)
Teat Perploutty (Chomiary)
GREAATS Masic ARE
GREATS
ONLINISI
Toe Propiccks
200 220
000
50
1000
200. 1.001,80 1,900
250
300
100
505
1,00
2000 200 1,031,00
Tol Poplesit (Mlttt Algessa)
Tox Paplesiy (hokononey)
GIILASS GraiNem Ovt ane Stasom
URLEAIS
GradSoen Ovi INESSER
Toa Poplesyy
The reppaarr
1001
(000 (001
201
1011
3003,
Stape
Saege
Paopledlyy
Popircty
MasLos
Madlor
Grachiem
Gradhorn
Tex Popleity
Stepe
Saype
Poplesly (Muniioo)
Paplesty (Machie Leaning?
GREATS
GREATS
MasLon
Missos
ONLINESUIHOO
Tea Paplesky
001
1/000
00003/0011.000
330
Figure 8: Test perplexity dynamics LLAMA-2-77 during training with various online batch selection strategies on MMLU. ONLINESUBMOD significantly outperforms baselines.
31

---

Details of Submodular Function used in all our training settings
We describe here the submodular functions we broadly utilised for all our experiments.
F.1 Diversity based Submodular Function
Here we share the details on the diversity based submodular functions we used for our training purposes.
Definition 1. Log-determinant Function is diversity- based submodular function. It is non- monotone in nature. Let L denote positive semidefinite kernel matrix and Ls denote the subset of rows and columns indexed by set S. Log-deterne dog-determinant function f is specified as:
((S) logdei(Lss)
(10)
The log-det function models diversity and is closely related to determinantal point process. Definition 2. Disparity Sum Function characterizes diversity by considering the sum of distances between every pair of points in subset S. For any two points i, E S, let dij denote the distance between them.
S(S)
Σ de
(11)
JES
The aim is select subset S such that ((S) is maximized.
Definition& 3. Disparity Min Function characterizes diversity by considering the minimum distance between any non-similar points subset S.
f(S)= = min dij
(12)
i.jE8.87)
The aim to select a subset S such that f(S) is maximized.
F.2 Representative based Submodular Function
Here we share the details on the representative based submodular functions we used for our training purposes.
Definition 4. Facility Location Function characterizes the representativeness in the dataset by
considering the minimum distance between any two non-similar points subset S.
f(S) =
max dij
(13)
JES
The aim is to select subset S such that f(S) is maximized.
Definition 5. Graph Cut Function characterizes representativensss by using the parameter X which governs the tradeoff between representation and diversity. When X becomes large, graph cut function also tries model diversity in the subset. S.
f(S)
Σ d
Σ dij
(14)
iEVJES
iJ88
The aim select a subset S such that f(S) is maximized.
Submodular Mutual Information We first provide a definition of Submodular Mutual Information:
((A)
f)AUB)
Definition 6. Log-Determinant Mutual Information Function is an instantiation of a submodu- lar mutual information function using a LogDeternt www.etterrmnaaaannttiiiie similarity matrix between the items in sets A and B. Also, denote SAB SAUB- We construct similarity matrix S" (on a base matrix S) such that the cross-similarity between A and Q is multiplied by (i.e., 5h.q = 11AA.Q) to control the trade-off between query relevance and diversity, Higher values of n ensure greater guery-relevance while lower values favor diversity. Using a similarity matrix defined above and with [(A) log dS) have:
Let SA,B B be the cross-
(A; Q) log (SA) log det(SA n7² SA.Q 1T
(15)
32

---

Definition 7 (Generalized Submodular Mutual Information). Let St be a ground set and V S S be domain of interest. Let f 2tt R2o be a restricted submodular function, i.e., submodular when restricted to subsets of V. A Submodular Mutual Information (SMI) function defined via such function f called a Generalized Submodular Mutual Information (GMI) function.
A notable instance of GMI is the Concave Over Modular (COM)functienn [21], defined for subsets A C and C V as:
(4:2)) =1
Σ REA
Σ JEQ
Sij
+
Σg JEQ
e
Σ VEEA
8ij
where 7 E I2z0 controls the trade-off' between query-relevance and diversity, 1/2 R2o + Rgo is concave function,5 [8ig] is kernel similarity matrix such that 8ij = 1 5) for i.j or i E V
Definition (Facility Location Mutual Information (FLIMM)). Let [A 2) denote
Submodular Mutual Information (SMI) function. An instantiation of SMI using the meciltyyocat.ionfunett is known as the Facility Location Mutual Information (FLIMI) function.
Formally, given subsets S V and QEV, FLIMI defined as:
1)AA = E min
max JEA
8kjs
maxx Sij JEQ
iEV
where: 7j R2u is a relevance-diversiyy trade-off parameter, Sij denotes similarity between elements i and j in the kernel similarity matrix S, V is the candidate set and V is the query set domain.
Definition 9 (Graph Cut Mutual Information (GCMI)). Let (AA 2) denote a Submodular Mutual Information (SMI) Sunction. An instantiation of SMI using the GraphCut on is called the Graph Cut Mutual Information (GCMI) function.
Formally, for subsets A C V and Q S V, GCMI is defined as:
(, Q) = 2A
Σ> Σ Sij-
SEAjEQ
where À E Rzo controls the scale of mutual information,s; Sij denotes the similarity between elements i and j in the kernel similarity matrix S,V is the candidate set and V is the query set domain.
G
Additional Related Work
G.1 Online Submodular Maximization
growing body of research has advanced our understanding of online submodular maximization under diverse feedback models and constraint classes. A notable contribution is the recent work on [13], which introduces principled framework leveraging first-order regret bounds from online linear optimization to derive improved guarantees in submodular settings. At each round f, the algorithm selects feasible set S, E C C 2%, where C encodes combinatorial constraints such as matroids or cardinality bounds, and observes an adversarially chosen submodular function fe. For monotone sub- modular functions under matroid constraints, the method achieves a (1 (1-c/e c/e e)-approximate regret bound of OkT log (ng()))) improving earlier results by Streeter and Golovin [45], and Golovin and Krause [11], even in the absence curvature (i.e., e = 1). For non-monotone unconstrained submodular functions, a novel algorithm based on Blackwell approachability achieves a 1/2-regret of Onn/T), extending Roughgarden and Wang [41].
These developments complement recent advances in bandit and semi-bandit feedback models, includ- ing those by Hassani et al. [14] and [47]. who analyze online submodular optimization in stochastic and adversarial environments, obtaining nearly minimax optimal regret bounds. Related efforts have also explored limited feedback settings with structure-aware exploration strategies (e.g., combinatorial Thompson sampling or optimism- based approaches), enhancing sample efficiency in large-scale decision spaces.
33

---

In the full-information setting, the online continuous greedy algorithm of Bian et al. [5] offers near-optimal (1 1-e)) for monotone submodular functions under matroid constraints, while extensions [56] tackle delayed feedback. Meanwhile, online versions of lazy greedy [31] and distributionally robust submodular maximization [44] have enabled scalable implementations in real-world domains such streaming recommendation and dataset summarization.
Although submodular maximization is NP-hard in general, approximation algorithms often yield near-optimal performance in practice across diverse applications [45, 111. These include influence maximization, budget-constrained recommendation, and online resource allocation, all of which ben- efit from the expressive yet structured nature of submodular objectives. As such, the aforementioned theoretical advances not only deepen our algorithmic understanding but also broaden the applicability of online submodular optimization frameworks to practical domains involving limited feedback, combinatorial constraints, and dynamic inputs.
G.2 Pruning Mechanisms
Several recent works have explored data pruning and subset selection for efficient training, including D2PRUNING [28], INFOMAX [48], and CCS [58]. While these methods offer valuable insights into coreset selection and dataset reduction, they predominantly operate in static, full-dataset settings, in contrast our dynamic, batch-level framework.
INFOMAX formulates an objective that can be interpreted as a reformulation of the Graph Cut function, which is monotone submodular, and leverages similarity kernels such DINO embeddings (for image tasks) or gradient-based features. This aligns conceptually with our approach, where Graph Cut is explicitly implemented as bandit arm. However, INFOMAX selects samples dataset in a static manner, whereas our framework is modular and dynamic: an InfoMax-like objective can be treated as bandit arm and applied in batch-level pruning during training. This flexibility enables more scalable deployment in real-world training pipelines where adaptive, online selection is erucial.
the entire
D2PRUNING frames data subset selection as a subgraph pruning task over the dataset, representing data points nodes in similarity graph. Selection is performed using message passing algorithms, which can be computationally intensive and challenging to scale to large datasets. Like INFOMAX, D2PRUNING operates at static, dataset-wide level, making it less suitable for dynamic batch-level pruning.
Similarly, CCS addresses static selection by optimizing for both coverage and diversity. A key contribution of CCS its theoretical characterization of the pruning budget, identifying thresholds beyond which accuracy degradation becomes catastrophic. While operate at the full-dataset level, we note that analogous effects could, in principle, occur batch-level selection; investigating such phenomena is potential avenue for future work.
method does not primarily
In summary, although INFOMAX, D2PRUNING, and CCS provide important foundations for data pruning and coreset strategies, they are largely static and dataset- wide in nature. Our approach extends these ideas to a dynamic, scalable setting by leveraging a bandit-driven curriculum where batch-level pruning decisions are guided by validation performance. Moreover, the modularity of our framework allows for seamless integration alternative reward signals, such as forgetting scores or other criteria discussed in prior works, enabling flexible and adaptive training in large-scale environments.
34

---

H Main Theoretical Results
H.1 Proof for permutation invariance of Expected Marginal Gain
Lemma (Permutation Invariance Expected Marginal Gain), Let denote the set of all permutations over the elements of B, B(C Then the expected marginal gain <i)
[44(Z B( =!a invariant under ant permutation т E 1L. i.e.
E E((()
EF (2,
AMi(Z; B <() |.a
2xa))) = IF. ( Ald TBB ) 2(2a))
Proof. Let S = B <i) with |S| = n. and let Zval Zial- We denote 9: :- 9o, (2:). 9:. ;= 9o. (Zvai). and H. := Hz... (0.). Then the expected marginal gain as per Eq 4 is given by:
- Σ9n
Mh 9: 9. - ni Hr
#ES
Let g = 1 a EzES 92. Then:
= 9 9,
2 l/
Σ
9.
H.g = 9 9. - H.g.
2,ES
This expression depends only the multiset S, not the order of its elements. Therefore, for any permutation π (S)) the same value holds:
Ez (z mTS), m = 9, -1/ H..9.
Hence,
Es [Z 8, zwa)] E2.ET(S) [All(Zz (()), Zval)]
which proves the claim.
H.2 Theorem: Captcity-Controlled Risk Convergence Theorem
Theorem 2 (Capacity- Conttrlled Risk Convergence). [([12]) Theorem 16.3] Let Me be
neural network with d parameters belonging to the parameter space O with an objective to minimize the empirical risk over the training data, D = Di) where X; R and y are almost surely bounded and where ), = 0(z;) ~ N (P2, ((22,,2a 22,) where : R - R and P denotes the data distribution. Then for d large enough, we have the following, for any 0.
/ [M
In(d) d
ED
(T((2) (F))))))){(())]
(16)
The above theorem follows from [39] and [12] and useful to prove further bounds in our case as below.
H.3 No-Regret Bounds under Constant X(-)
We first state here the main theorem under the following assumptions as stated in our main text:
Let R (t) denote the number of times the a-th submodular function f(() is chosen the first 1 steps by the uniform branch of the algorithm.
Assumption (a) (Constant Fractional Exploration Dampening): The exploration dampening parameter X(1) is time-invariant X()) where e (0,
Assumption (b) (Optimality Gap): There exists an optimality gap @ such that for every suboptimal arm E o {a"} 0 < < A (aa)(
35

---

Assumption (c) (Fractional Exploration Sharpness); The exploration sharpness parameter sr() is a bounded quantity π (t) (0, 1).
tion bound as per Theorem (Appendix) with constants ((a) for each satisfies the approxima-
Assumption (d) (Utility Metric Approximation): The utility metric Ue(:
af and let na be specific constant associated with arm such that Theorem 2 (Appendix) holds true.
Theorem (Regret Guarantees). Under Assumptions a d, for all f > to, with probability at least
exp (- (- 28K( - π
3(t (33(t
2) (1 (1 (1-x)e)
the expected instantaneous regret incurred by the selection policy satisfies
E[Regret, = EB, Ea, eor E [0(a] (B)) - -() [Bi)
K3 (max, C(a) + Cx) llott
(8)
0 +0
Ø
where C. is the approximation constani corresponding the optimal arm a² Proof.
EB, Eu (( - -((((a) [B))
=EB ((,) E (( (B.))BB)))
where m(o) Eo((())
Ess (B.)
Σ Ma (B.)) f(aa) BB))
EB. Ao (B.)P(f(an f(a)) (B))
Σ Eg, A (B.) ((a)) |B,)
Ex. A (B.) (B.) p(a) |B:)
S Es, A. (B,) E. + P(Me, 2 M Me, ((,))))
Let Mo. indicates the trained neural network in accordance to [39] for action fla+). By Markov's inequality
P(Me.fia 2 Mo, S
Mo, (B.) + (B:)/
(M, S ((.((B))) A. (B:)/2
J -
OP. + /
OI..
JIM (1MM),r0012MM0(())AA1111)1
JILM A.
(17)
OP. 111M (11) -10))) -BC))(B))
OI..
(c) (.
(o)))
{ MM, M(a) (B:))2
MM - ((,))(B))
OP +
OP.
(B,)²
(B,)
Based on Proposition we have T (a) (t) 2 2x[2-=] (1 for all a A. Let C(a) indicate the constant from Theorem and let n, the minimal training data size. We choose
to > (2K max maaxfe,nn me,, n. H) Since the + In(x)) is monotone decreasing for r > the above
expression is further bounded by
36

---

$ EBg A (a)
4 (Bi)
4
Vooiv
In (n(T(()(1))
+
e
In(T,(1))
K
((a)(t)
Tx(t)
In((
4
It))
Rg, A RB
(a) (B:)
(1)
0 V..
(t(
(18)
E3, 00)
(Br)
4
In( 2212 x) (1 (1 x)))
2-2
((a) + C.
tKC
\
2k12- r) (1 (1 (1-T)e) m))
1-2
Thus we have the following:
Σ
Eg, (B, = -f(a) (B,)
f(ne)
max pias EF Es, Dn
(19)
K3/2 22 σ) max ((a) + E.
In((t (1 + πE)) (2 T)) (1 (t- (1 + - TE)
To showcase the lower bound, we have for a-th arm not optimal that,
E.
Es, (B.)).)))))( = p(
B.) 2 Es, (B:) K.
2
B5, l
2
(20)
K.
t/C
n
Lemma 2 (Bound on Uniform Arm Selection Frequency). Since T (() (1) denotes the number
of times the a-th submodular function fla) is chosen in the first t steps by the uniform branch of the algorithm, we have the following:
K
t-2
P
(t) 2
(1 + (1 (1+(1-7)c)) T)p)}
(a)
2K(2 - π)
o=1
3(t 3(t-2)(11 1 (1 T)))
> 1 K-ep
28K T)
Proof.
E(T (1)
Σ
P(C < E, f((n) = )(al)
Σ P(C < E,)P(((a))
p(a))
Σ K
r
(21)
(r ((r)*
t-2
Or 2
(1+ + (1 - (1-
(
K((-
where, the last inequality is based on Proposition 1. We define the variance of T [8) as (T (1) and the corresponding upperbound Z ((o(()
(T
E EE-=
-=
(++x(r))* Z(o(t))
37

---

Using Bernstein's 's inequality
2(o(t))
= =P T (t) (t) 2(o(t)) - 2(0(1))
P
R (a)
(t)
2
2
-Z(a(t)²
-2(a(t))²
I exp
cxp
o(T(a) (a) (1)) + 1 B(o(t))
((o(t)) + 2(a(t))
32 (Z(
3(t 2)(1 (1 x)
S exp
S exp
28
28K T)
By union bound method
t-2
PP
21C12 - л)) (1 (1 - (1-)))]
t-2 (1 (1 (1- 2K(2 σ)
3(t- - 3[1-1)(1 + +(1 (1 T)E)
< KPP (()(1) S
SKexp
28K 17)
Therefore
2-2
3(t 3(t- 2) + (1 - TT)) 28K( -T)
P
(0) (1) T (a)
(1+ m]{}} 2- --xeex
2K(22 - x)
Proposition 1 (Integral Lower Bound (Constant X)). Let X(t) = with 0 << < 1, and 1. Then, for
I
dr,
(x + {(x))=
x=1
we have
I dx 2 2
I 2
(1+ (1 ()-
(x + cc)
2 -
==1
38

---

Proof.
-=t-1
dr
dx
(Substitute A(x) E)
Jam1
(x + ((x))*
(I + e)
(1 c))2-
(1 + c)2-
2 -
2-
[t - (1 - [1-6)]1- =))
+ (1 + (()1=x
1-
(1 (1- 7) 1)
It (1 6)
(1 (2 - TT)
1-7
[1 + d
(1- x)
(1 (1-1) m -
= Im + +c|'=x 1-x
(2- T)
(1- -C
[1 c)
(Letm=
[)- - m)
km - 6 ) - + cjs
k: -
im + c)
(Let = T)
k(k 1)
k:kk: 1)
1
(mm+ [kmm <) (c -1[[ + x)()
k<k + 1)
1
([1 + <) (kmmmmmmmm - 6) + (c k)(1 + +
k(k + 1)
(Since m + 2 1 +)
[1 + c (km- c c k)
k(k + 1)
1
[1 cl* (km k)
k(k + 1) 1
[1 + c - 1)
= h +
1
2
+ ke](m 1)
(Using (1+ 2 1 1 ke for small e)
1
[1 + (1 m)]{[t 2)
(Substitute A: == n, = 1 1)
2
t-2
(1 + (1 T)))
2 π
(22)
The above integral computation is used in the main paper for our proofs.
H.4 Regret bounds in the case of growing with time exploration dampening function
Proposition (Integral Lower Bound (Exponential Growing X)). Let X(t) e be a time-growing function with rate i > 0, and let O < < 1. Then, for
I
Jazi (a *(x))= dr,
the following lower bound holds:
1 In In((2elt-1)) -1) II((2e -
-1ee- 11])
1 s=1 (I 1 - e e
dx
39

---

Proof.
dr
dx
(x + *(x))*
(I: + 1-12)
x²
M
dx
[ + e-
ze
x
IV
dx
zetr
+ eix
-
rele
dx
Detr
+ xet
gir
dr
Using Jensen's Inequality
2elz -1
etz
dx
2 -1 1
In ((- -) 1) - -In(2ee - 11])
2i
R Lemma 3 (Exploration Dampening: Annealing). Since (a) (1) denotes the number of times the a-th submodular action is chosen in the first f - steps by the uniform branch of the algorithm, E [K], then in the case of (t)) enn for Ofi.. growing exploration dampening probability), we have the following:
e
P
(T R (t)
In In(2c((e-1) - 1) - In((2( -1n(26())-1)) )
21
2i
(-
3
1
[1( 1) In(2)(()) - 1|]
Keep
(-28K
28K
2i
Proof.
B(T = Σ
PPS < (f,
1=1
1-1
1-1
P(C E,
((0)) Σ
K.
K.
(r+)
x
Ox
e iz)= dx
a=1
(x (++X(x))
x=1
(x +
(t-1e 1) In(2e" - 11) 2i
K
The last inequality comes from Proposition 2
We define the variance of 7 (a) (t) as ( (t)) and the corresponding upperbound as ((a(t))
-
Σ
E,
(+1-- Z(o(t))
K
r=1
1=1
Using Bernstein's 's inequality
40

---

2(0(tt)
(t()) Z(o(t)) 2(0(t))
P
Ta (t)= -
2
2
-(()
-2(o(1))²
S eep
S exp 2(o((t) + 2(0
(t)
2(o(!!)
exp
(Z(()tt)
exp
3
1
In(2
1) Im(2ell) - 11
28
28K
2i
By union bound method
U
(1)
In In(2e((t-1) - 11 - -In(26(0) (ppp()))111)) -1}] )
2K
2i
==1
S KIP (T)())=
1
1
In(2c 1) ln(2 1)}
2K
2i
< Keep (-
3
1
In(26 -1) 1) In(e - 1)] 71.
28K
2i
Therefore
1
In (n(2 -1) 1) - -n(26 -1)] }
R (t) 2
2K
2i
(- (-28k
1
[n((ee((-1)) 1) In(20 - 11]
2 1 Kexp
-1)
28K
2i
41

---

Theorem 3 (Regret Guarantees). Under Assumptions b d, for all >> to and with 2(t)
e with probability at least
1 1-xexp (-
1
In In((e -ln(ee2)))) -111
28K
2i
the expected instantaneous regret incurred by the selection policy satisfies
E[ := EB, Ba Eo [0 [B:) - ((a) B,) ((( + C.), 1/2 Vint
=0 (
(23)
where C, the approximation constant corresponding to the optimal arm
Proof. Continuing from the same step in Section H.3 Theorem 1, we have the following:
x
For the case of (1) (t) 2x In(2e ln((e (0)2(())11)) - -1)] for all a via Proposition
2. Let ((a) indicate the constant from Theorem 2 and let be the minimal training data size. We
choose tu > e2K ma, n,)), Since the x - V /m(x)) is monotone decreasing for x > c, the above expression is further bounded by
Eg, A (0)
(B,
Ct
4
In(T(a)(t))
- C
4
In(T (t))
K
((a)(t)
0
Tt
4 K
[t))
4 C,
[n))
< Eg, A (a) (Bi)
+ E(a)
0
TR((t)
0
(t)
(24)
In 2k
1
In(2ei(t-1) - 1) In (n(2e(a) - 11]
21
E8, A (B.)
4 0
((a) te,
th
Im(2et(t-1) 1) - 1) - -In(2e(a) - 11]
2x
I Broader Impact
The primary aim of our work is improve the data efficiency of machine learning training pipelines via submodular subset selection. By leveraging principled selection algorithms- such as monotone submodular functions,
reduce the number of training examples needed without sacrificing model performance. This contributes directly to more sustainable and accessible machine learning, especially in scenarios where training data compute is limited.
Reducing the amount of data required for training has multiple practical benefits. For large-scale models, this can translate into lower energy consumption and reduced carbon footprint. For smaller research labs or applications low-resource settings, our approach can make training state-of-the-art models more feasible.
Societal and Environmental Benefits:
Equity and Fairness: By allowing for careful and task-informed selection of training data, our methods could help surface underrepresented or
samples early in training. However, care must be taken ensure that the subset selection process does not reinforce existing dataset biases. We encourage practitioners to combine our framework with fairness-awan selection techniques and audit the resulting models for any performance disparities across groups
Scientific Impact: More broadly, this work highlights the growing role of data-centric approaches in machine learning research, particularly for compute efficient machine learning research.
42


Reviews:
[{"review_id": "O2vhl9kWLi", "reviewer": "Reviewer_N27T", "summary": "The paper addresses a well known problem of curriculum learning by reformulating this to a multi-armed bandit problem. Specifically, the authors has pointed out the reliable criteria for difficulty is still not firmly established in previous works, which not only be calculated from separate modules but also not adaptive to the evolving training dynamics. The solution is to adopt a multi-armed bandit formulation with greedy utilization-based rewards with each arm of the bandit as a submodular guiding function for sampling. The authors has demonstrated their work in both language and vision tasks and have shown superior performance.", "questions": "1. How does different types of submodular functions affect the training quality *individually*? That is, does the dynamics change dramatically if only a single arm is selected over time? I am asking this question because I see only a small variance between the two options shown in Figure 1.\n2. Although Figure 5 seem to show the arm selection distribution does change over time, I am curious on the purely random selection of sampling policies compared to the multi-armed bandit. Will this make a change?\n3. Lastly, I believe that the training mechanism of CIFAR (which is trained from scratch) and the training mechanism of fine-tuning of LLMs can have different dynamics and therefore require different types of submodular functions. It will be interesting to see if there is a difference by plotting the distribution of arm selection for fine-tuning LLMs. \n\nPlease note that these questions are minor concerns and are not counted in my overall scoring.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "## Strengths\n\n1. The paper adopts theoretically plausible multi-armed bandit problem into practical continual learning problem. The integration seems to be successful as shown in experimental results.\n2. The proposed method is demonstrated thoroughly in both large-scale vision and language tasks, revealing its practical value.\n3. The proposed method adds minimal computational overhead and therefore is practical.\n\n---\n\n## Weaknesses\n\n### Motivation\n\n1. In Figure 1, the difference in differently scheduled samplers the authors tried to deliver seems to be negligible. The end points at 300 epochs are hard to discriminate from each other.\n2. The choice of submodular functions in Table 1 can be easier to be understood if there are elaborated reasons why the authors have chosen those. Without the explanation, the choice of submodular functions looks be arbitrary, despite the papers’ good results.\n\n### Experiments\n\n1. Figure 2 shows the first 1700 steps of training. Whereas GREATS paper has conducted experiments for longer period of time, e.g., 3k~10k iterations. Is there a reason the authors have trained only about half of the iterations?\n\n### Visualization & Presentation\n\nThese are minor concerns.\n\n1. I would like to mention that the paper is a bit hard to read due to excessively many highlights throughout the article. Please reconsider revising the manuscript in more planar tone and style.\n2. It would be nicer to have consistent styles throughout the figures. The styles in Figures 1, 2, 3, and 4 are not consistent and confusing. Furthermore, the dot size in Figure 4 is too large making it hard to interpret its value.\n3. Table styles can also be improved. Table 1 has italic caption whereas others do not have.\n4. It is hard to discern each lines in Figures 3, too.\n\n---\n\nOverall, I regard this paper has an acceptable level quality with both theoretical and practical contributions. However, I have a few unresolved issues. I will raise my score if all are resolved.", "was_revised": true, "final_justification": "Most of my initial concerns are resolved by the rebuttal, and the authors has promised significant revision regarding presentation. I will raise my score.", "rebuttal": "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:\n\n-----------\n\n**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**.\n\n---------------\n\n**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.\n\n-----------------\n------------\n**Addressing minor concerns over Visualization/Presentation**\nThank you for the detailed feedback on the presentation quality. We appreciate the suggestions and will incorporate them in the final version.\n- 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.\n- 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.\n- Thank you for pointing out the inconsistency in table captions. We will fix it to non-italics for uniformity across all table captions.\n- For Figure 3, we will improve line distinguishability through clearer labeling and contrast-adjusted color choices to make trends easier to follow.\n\n----------------\n-------------\n\n**Response to Questions raised by Reviewer**\n\n>    Effect of submodular functions indivually and simple random selection over arms\n\nThank 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:\n\n| Selection Strategy          | Accuracy (%) |\n|----------------------------|--------------|\n| DisparitySum (Div.) (Static)        | 68.6         |\n| FacilityLocation (Rep.)  (Static)    | 72.0         |\n| LogDeterminant (Div.)  (Static)      | 71.1         |\n| GraphCut (Rep.)  (Static)            | 72.6         |\n| Random arm per round       | 72.0         |\n| OnlineSubmod    | **73.6**     |\n\nThese 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.\n\n>    Difference in arm distribution between image and language training setups\n\nThis 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.\n\n-----------------------\n\nThank 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.\n\nWe would appreciate an appropriate increase in the score so as to get support on the paper acceptance from your end."}, {"review_id": "QHfDcUdhQv", "reviewer": "Reviewer_Bq1H", "summary": "The paper introduces an adaptive curriculum learning framework called ONLINESUBMOD, which casts subset selection as a multi-armed bandit problem, where each arm corresponds to a distinct submodular function guiding data sampling. ONLINESUBMOD uses a reward function defined based on the marginal utility of a training subset in improving validation loss. The authors theoretically show that the proposed greedy policy achieves no-regret performance under certain assumptions. Empirical evaluations in the vision and language domains demonstrate that ONLINESUBMOD outperforms baselines in terms of accuracy and efficiency trade-offs.", "questions": "- Can you clarify the sensitivity of the method to the choice and number of submodular arms?\n- Can you explain the role of exploration hyperparameters and how to tune them in practice?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Quality:\n  - ONLINESUBMOD is a technically sound and well-motivated method with no-regret guarantees.\n  - Empirical results show consistently superior performance over strong baselines.\n- Clarity:\n  - The authors describe the problem in a well-structured manner.\n  The algorithm and theoretical results are well-explained in the main document and supported by details in the appendix.\n- Significance:\n  - The method addresses adaptive data selection for efficient training, a practical problem, using a scalable and general approach.\n- Originality;\n  - The combination of submodular curriculum design via a multi-armed bandit and the reward formulation using validation-based utility seem novel.\n\nWeaknesses:\n- Quality:\n  - The assumption of stationary reward distributions does not seem realistic.\n- Clarity:\n  - A summary or diagram of utility and influence functions could be beneficial for the reader.\n- Significance:\n  - I'm unsure how complex it is to design a set of submodular functions as arms for a particular application.\n- Originality:\n  - Although the proposed method seems novel, the discussion on the related work can be extended for non-expert readers to get a deeper understanding of the novelty of the work.", "was_revised": true, "final_justification": "The authors' response has clarified my understanding of their work and its contribution.", "rebuttal": "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:\n\n--------------------\n\n\n**On Clarity of Utility and Influence Functions:**\n\nThank 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.\n\n**On the Complexity of Designing Submodular Arms:**\n\nIn 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.\n\n\n**On Related Work Discussion**\n\nWe 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.\n\n---------------------\n\n**Response to Questions raised by Reviewer**\n\n>      Can you clarify the sensitivity of the method to the choice and number of submodular arms?\n- 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). \n- 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.\n\n-------------------\n\n>      Can you explain the role of exploration hyperparameters and how to tune them in practice?\n\n- 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. \n- 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. \n- 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.\n- 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.\n----------\nIn 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.\n\n---------------\n\nThank 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.\n\nWe kindly request your support in reflecting this through an appropriate score increase to help strengthen the case for acceptance."}, {"review_id": "NAGwsLRl3x", "reviewer": "Reviewer_3iJi", "summary": "This paper tackles the curriculum learning problem by framing it as a multi-armed bandit problem, where each arm corresponds to a submodular function that defines a different difficulty-based sampling strategy. The authors leverage validation losses as the reward signal for a greedy policy that guides adaptive subset selection. They provide theoretical results demonstrating that the proposed subset selection strategy incurs almost no regret by the end of training. Experimental results on LLM fine-tuning, image classification, and ablation studies show that the proposed method significantly outperforms existing approaches.", "questions": "Regarding the concerns on the impact of the validation dataset, here are several questions for the authors.\n1) How sensitive is the performance to the configuration of the validation dataset?\n2) In the early stages of training, what happens if the validation dataset contains difficult samples that the model has not yet learned?", "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": "Strength:\n1. Framing the curriculum learning problem as a multi-armed bandit problem is a novel and interesting approach. This formulation is principled and general, allowing for a structured exploration-exploitation trade-off.\n\n2. The authors address computational cost issues by utilizing submodular relaxations and low-cost gradient proxies, such as last-layer gradients or LoRA adapters. This enables the proposed algorithm to be efficient and scales well.\n\n3. The theoretical results provide provable regret bounds that show the proposed method can guarantee no regret by the end of training.\n\n4. Comprehensive experimental results show that the proposed method consistently outperforms existing sample selection techniques and achieves better accuracy-efficiency trade-offs than prior work.\n\n\nWeakness:\n\nThe 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:\n1. How sensitive is the performance to the configuration of the validation dataset?\n2. In the early stages of training, what happens if the validation dataset contains difficult samples that the model has not yet learned?\nA more detailed analysis of the impact of the validation dataset would make the paper more convincing.\n\nSome typos:\nL270, L411, L411, L495: wrong reference \"Appendix ??\"\nL296: comparision, datsets\nL305: submdoular", "was_revised": true, "final_justification": "Most of my concerns are well addressed by the rebuttal. So, I'll keep my positive rating.", "rebuttal": "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.\n\nWe now move forward to addressing the questions raised by the reviewer\n   \n>      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:\n\n- 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.\n\n- 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.\n\n- 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.\n\n>       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.\n\nTo 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:\n\n- **Easiest**: Lowest gradient norms  \n- **EasyHard**: Easy samples early, hard samples later  \n- **HardEasy**: Hard samples early, easy samples later  \n- **Hardest**: Highest gradient norms  \n\nEach configuration was evaluated at validation subset sizes of 10%, 20%, and 30%. Below are the final test accuracies:\n\n| Validation Subset | 10%  | 20%  | 30%   |\n|-------------------|------|------|-------|\n| Easiest           | 72.3 | 74.4 | 76.03 |\n| EasyHard          | 73.1 | 74.5 | 76.4  |\n| HardEasy          | 72.29| 74.6 | 76.2  |\n| Hardest           | 71.31| 74.3 | 75.9  |\n\n**Findings**:  \n- **Hardest** validation sets yield lower performance, particularly at smaller subset sizes, likely due to noisy or overly pessimistic reward signals early in training.  \n- Mixed configurations like **EasyHard** and **HardEasy** perform best, suggesting robustness to how difficult samples are distributed over time.  \n\nThese 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.\nNonetheless, even validation sets containing difficult examples early in training do not lead to instability or collapse. \n\n--------------------\n\nWe 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.\n\n------------\n\n[1][Wang et al., 2024] GREATS: Online Selection of High-Quality Data for LLM Training in Every Iteration.\n\n[2][Pruthi et al., 2020] Estimating Training Data Influence by Tracing Gradient Descent. arXiv:2002.08484"}, {"review_id": "Fc7L4gsxna", "reviewer": "Reviewer_v9ha", "summary": "This paper addresses curriculum learning by reinterpreting adaptive subset selection as a multi-armed bandit problem, where each arm represents a submodular function guiding sample selection. The authors propose **OnlineSubmod**, an online greedy policy that optimizes a utility-driven reward and achieves no-regret performance. Unlike traditional methods that rely on predefined difficulty measures, OnlineSubmod adaptively learns effective curricula using validation-driven reward metrics. Experiments show it outperforms standard curriculum learning and bi-level optimization approaches in terms of accuracy and efficiency across vision and language tasks.", "questions": "Actually, I have two main questions or points of curiosity. \n\n\nFirst, some methods for coreset selection or data pruning could also be applied to perform a similar task. For instance, the three papers I listed below—could the authors discuss any existing gaps or differences in their applicability compared to the proposed method?\n\nCCS: Coverage-centric Coreset Selection for High Pruning Rates. ICLR-2023\n\nD2Pruning: D2 Pruning: Message Passing for Balancing Diversity and Difficulty in Data Pruning. ICLR-2024.\n\nInfoMax: Data Pruning by Information Maximization. ICLR-2025.\n\nSecond, 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)?\n\nI would consider further increasing my score if my questions were addressed with the responses provided.", "limitations": "Not any.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "In fact, I could hardly find any flaws or weaknesses in this paper. The presentation is thorough and well-structured, with ample theoretical analysis, visualization studies, and experiments covering a wide range of scales. I was unable to identify any significant shortcomings.", "was_revised": true, "final_justification": "Thank you for your reply, author! My questions have been answered! I recommended this article to be accepted", "rebuttal": "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.\n\n\n---------------------\n----------\n\n**Discussion on Additional Related Work**\n\n**InfoMax: Data Pruning by Information Maximization. ICLR-2025**\n\n- 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.\n\n- This is aligned with our work, where we are already using Graph Cut explicitly as a bandit arm in our current framework.\n\n- The key difference is that InfoMax operates in a static setting, selecting samples over the entire dataset.\n\n- 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.\n\n- This makes our method easier to deploy in real-world settings, where adaptive selection over batches is necessary for scalability.\n\n- Importantly, our framework is modular—methods like InfoMax can be seamlessly integrated and evaluated within OnlineSubmod, offering better scalability in large-scale training pipelines.\n\n------------------\n\n**D2Pruning: D2 Pruning: Message Passing for Balancing Diversity and Difficulty in Data Pruning. ICLR-2024.**\n\n- 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.\n\n- 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.\n\n- Similar to InfoMax, this method operates at a static level, not a dynamic batch-level setting.\n\n- 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.\n\n----------------\n\n**CCS: Coverage-centric Coreset Selection for High Pruning Rates. ICLR-2023**\n\n- Like other works, CCS considers a static setting to select examples that ensure both coverage and diversity.\n\n- A key contribution of CCS is its theoretical analysis of the pruning budget beyond which catastrophic accuracy drop can occur.\n\n- 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.\n\n\nIn 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.\n\n-------------------------\n\n>    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)?\n\n-  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.\n\n-  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.\n\n-  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.\n\n\nWe 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.\n\nWe 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."}]

Author rebuttal:

Meta-review: This paper frames curriculum learning as a multi-armed bandit problem, where each arm represents a submodular function guiding sample selection, and the reward function is defined by the marginal utility of the selected samples on validation set. The authors proposed OnlineSubmod, an online greedy policy that optimizes achieve no-regret performance under certain assumptions. Reviewers seem enthusiastic about the paper across the board, appreciating the MAB framing, finding the proposed method technically sound and with strong empirical confirmation. One potential weakness is the reliance on performance on validation set, but the authors argue it is a common practice in curriculum learning literature, and reviewers seem fine with it.
Decision: Accept (poster)