OrderDP: A Theoretically Guaranteed Lossless Dynamic Data Pruning Framework
Authors: Chenhan Jin
Shengze Xu
Qingsong Wang
Fan JIA
Dingshuo Chen
Tieyong Zeng
Venue: ICLR 2026 Poster (2026)
Keywords: Dynamic Data Pruning; Training acceleration; Convergence Analysis;Bias Analysis;
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: Data pruning (DP), as an oft-stated strategy to alleviate heavy training burdens, reduces the volume of training samples according to a well-defined pruning method while striving for near-lossless performance. However, existing approaches, which commonly select highly informative samples, can lead to biased gradient estimation compared to full-dataset training. Furthermore, the analysis of this bias and its impact on final performance remains ambiguous. To address these challenges, we propose OrderDP, a plug-and-play framework that aims to obtain stable, unbiased, and near-lossless training acceleration with theoretical guarantees. Specifically, OrderDP first randomly selects a subset and then chooses the top-$q$ samples, where unbiasedness is established with respect to a surrogate loss. This ensures that OrderDP conducts unbiased training in terms of the surrogate objective. We further establish convergence and generalization analyses, elucidating how OrderDP affects optimal performance and enables well-controlled acceleration while ensuring guaranteed final performance. Empirically, we evaluate OrderDP against comprehensive baselines on CIFAR-10, CIFAR-100, and ImageNet-1K, demonstrating competitive accuracy, stable convergence, and exact control---all with a simpler design and faster runtime, while reducing training cost by over 40\%. Delivering both strong performance and computational efficiency, our method serves as a robust and easily adaptable tool for data-efficient learning.

Published as a conference paper at ICLR 2026
ORDERDP: A THEORETICALLY GUARANTEED Loss- LESS DYNAMIC DATA PRUNING FRAMEWORK
Chenhan Jin Shengze Xu Qingsong Wang² Fan Jia Dingshuo Chen Tieyong Zeng?.3t 'The Chinese University of Hong Kong BBijjing Normal-Hong Kong Baptist University GGungghoou Nanfang College *Institute of Automation, Chinese Academy of Sciences
Xiangtan University University of Utah
ABSTRACT
Data pruning (DP), as an oft-stated strategy to alleviate heavy training burdens, reduces the volume of training samples according to well-defined pruning method while striving for near-lossless performance. However, existing approaches, which commonly select highly informative samples, can lead to biased gradient estimation compared to full-dataset training. Furthermore, the analysis of this bias and its impact on final performance remains ambiguous. To address these challenges, we propose OrderDP, plug-and-play framework that aims to obtain stable, unbiased, and near-lossless training acceleration with theoretical guarantees. Specifically, OrderDP first randomly selects a subset and then chooses the top-q samples, where unbiasedness is established with respect surrogate loss. This ensures that OrderDP conducts unbiased training in terms of the surrogate objective. We further establish convergence and generalization analyses, elucidating how OrderDP affects optimal performance and enables well-controlled acceleration while ensuring guaranteed final performance. Empirically, we evaluate OrderDP against comprehensive baselines CIFAR-10, CIFAR-100, and ImageNet-IK, IK, demonstrating competitive accuracy, stable convergence, and exact control all with a simpler design and faster runtime, while reducing training cost by over 40%. Delivering both strong performance and computational efficiency, our method serves robust and easily adaptable tool for data-efficient learning. The code is publicly available at https: / //te:://gtttie /iithuu. com/ shengze xu/OrderDP.
estimaatooo
INTRODUCTION
Neural scaling laws have revealed consistent empirical pattern across wide range of do- mains (Amari et al., 1992; Hestness et al., 2017: Kaplan et al., 2020): model performance tends to improve predictably, often a power law (Hernandez et al., 2021; Cherti al., 2023; Chen et al., 2023), with increased model size and the data volume. This observation has fueled a surge in computational demands and financial costs, as larger models and datasets leveraged to push the boundary of model capabilities. In this context, data pruning (DP) has emerged as a promising strategy to alleviate training costs by selectively removing less informative samples (Killamsetty et al., 202 Mirzasoleiman et al., 2020; Qin et al., 2024; Raju et al., 2021), offering pathway to enhance training efficiency without compromising model performance.
Depending on when sample selection is performed, data pruning strategies can be broadly classified into static pruning and dynamic pruning. & Static pruning assigns an informativeness score each training sample before training, typically using data influence functions (Borsos et al., 2020; Koh Liang. 2017: Yang et al., 2022) or coreset selection strategies (Huggins et al., 2016; Campbell Broderick, 2019; Kim et al., 2023). @ Dynamic pruning, on the other hand, performs sample selection during training, updating scores on-the-fly based on evolving model states or gradients (Raju et al., 2021; Qin et al., 2024; Chen al., 2024). By continuously adapting to the training dynamics, it can better identify and retain the most influential samples at each stage, potentially yielding higher
'These authors contributed equally to this work.
1 *ooresponning author: t cieyongzzngg@ee edu. en, di ninnuucc. chenecripac. an.

---

Published as a conference paper at ICLR 2026
(a)
80
(b)
10
Test Accuracy (%)
Gradient Norm
8
65
60
55
Baseline
50
InfoBatch OrderDP
45
40
50
100
1.0 Epoch
200
250
300
50
100
150 Epoch
200
250
300
(c)
(d)
Rolling Std Dev
0.8
Test Accuracy (%6
0.6
60
0.4
50
Baseline
0.2
InfoBatch
OrderDP
0.0
100
150
200
250
300
Epoch
Grudient Norm
Figure 1: Training dynamics of ResNet-18 on the CIFAR-100 under a 70% data pruning ratio. Method comparison: full-dataset training (Baseline). representative dynamic pruning strategy (InfoBatch), and our proposed method (OrderDP). (a-c) Test accuracy, gradient norm (shadow area denotes standard deviation), and temporal stability of gradient norm over training epochs. (d) Joint distribution of test accuracy and gradient norm throughout training.
performance under constrained training budgets. A more comprehensive survey of static and dynamic pruning methods is included in Appendix B.
Within supervised learning, data pruning aims to reduce data volume without sacrificing performance, thereby achieving ncar-lossless' pruning. However, the discarded data can cause the distribution shift and bias gradient. Although selecting portion of the discarded data randomly via calibration protocols (Ayed & Hayou, 2023) can theoretically ensure unbiasedness, finding the optimal proportion can be difficult practice. Inspired by this method, recent dynamic methods such as InfoBatch (Qin et al., 2024) achieve this goal by rescaling the bias gradient toward the expected loss. However, when training on specific dataset, gradient bias in both scale and direction may still arise from the discrepancy between empirical and expected loss. This bias is further amplified under extreme pruning, where large scaling factors are applied and stabilization techniques such as annealing are often required. These challenges reveal an incomplete understanding of the principles underlying "near-lossless" pruning. A critical questions arise as what ensures this property? how the bias should be analyzed, and whether pruning be pushed further toward more extreme regimes? To investigate these questions, we conduct comparative studies and report a representative result on CIFAR-108 100, comparing full-dataset training with InfoBatch (Qin et al., 2024) under 70% pruning ratio to test its limits. Further experiments are presented in Appendix D, E, and we highlight several key observations as follows:
1 Gradient norm serves as a reliable proxy for model performance: Under full-dataset training, test accuracy exhibits a strong linear correlation with gradient norm (Pearson's 's R -0.93), shown in Figure (d), which suggest the magnitude of gradients is stable and informative indicator of both training progress and generalization, which echoes prior observations in related studies (Zhao et al., 2022: Zhang et al., 2023).
Dynamic data praning suffers from training instability: Compared full-dataset training, dynamic one displays pronounced fluctuations in test accuracy and volatile gradient norms. Moreover, the rolling standard deviation reveals irregular and noisy optimization dynamics, indicating reduced training stability, as shown in Figure I (a-c).
Here, near-lossless means matching full-data accuracy up to normal stochastic fluctuations (typically within 0.1 ()) while achieving noticeable training speedup.
2

---

Published as a conference paper at ICLR 2026
Step I: Ordered Selection
Step Dynsmic Training Process
Compuse subgredient: if
Update parameters: of))
Full Dataset D
Uni 4)
Select top-q scores
Update score values: He..
Retained subset Q
Score updale
Figure 2: Illustration of the proposed OrderDP framework: at each iteration, a candidate batch is sampled uniformly, the top-q examples are selected by score compute subgradient and update model parameters, and scores are refreshed only for the retained samples.
@ Gradient estimation under dynamic pruning is still biased: Figure 1 (b.d) demonstrate that the dynamic method induces a noticeable shift in the overall scale of gradient norms relative to the baseline. This shift is more significant for InfoBatch, as a large scaling factor is imposed. The previously observed linear relationship between accuracy and gradient norm weakens, suggesting that it still distorts gradient estimates and introduces bias during training.
Together, these findings highlight that training instability and biased gradient estimation are two key limitations of existing dynamic DP strategies. We provide extended empirical analysis of gradient bias in Appendix E. To this end, we take a step towards designing a DP method to mitigate both issues, thus achieving stable, unbiased, and near-lossless data pruning. Inspired by the recent stochastic optimization based on ordering statistics (Kawaguchi & Lu, 2020; Mehta et al., 2023), we propose a simple yet effective DP framework, OrderDP, which aims to obtain near-lossless pruning with improved efficiency. even at large pruning ratios. At the beginning of each epoch, we randomly sample a batch of data points from the full dataset to form pruming candidate pool. These candidates are then ranked in descending order based on their loss values, and the Top-q samples are selected as the most informative ones for model training. We formulate OrderDP as an optimization algorithm that minimizes a proposed surrogate loss. We theoretically establish convergence analyses using an unbiased gradient estimation of the surrogate loss. Furthermore, generalization analysis is provided in terms of the surrogate loss and expected loss, demonstrating the effectiveness of OrderDP.
Our approach has several desirable properties. First, OrderDP ensures unbiased gradient estimation and works with standard training pipelines without architectural changes auxiliary approximations. maintains an exactly controlled pruning ratio with rigorous theoretical guarantees on convergence and generalization. The surrogate loss fully captures the bias and enables principled, loss-aware prun- ing while sustaining strong stability. Empirically, we validate OrderDP on CIFAR-10 (Krizhevsky al., a), CIFAR-ION (Krizhevsky et al., b), and ImageNet-IK (Deng et al., 2009). Across all benchmarks, OrderDP achieves near-lossless performance at moderate pruning ratios and surpasses of methods. On ImageNet- 1K, it retains full accuracy at 40% pruning with the lowest total computation, leading to faster runtime. These results show that OrderDP not only sustains strong performance but also delivers superior efficiency, robustness, and simple plug-and-play design, making it practical solution for scalable deep learning.
METHOD
Inspired by the iterative update process of stochastic gradient descent (SGD) (Kawaguchi Lu, 2020; Amari, 1993), we propose Ordered Data Pruning (OrderDP). dynamic strategy that integrates adaptive sample selection into the SGD pipeline to reduce training cost without sacrificing accuracy. The overall framework is illustrated in Figure 2. OrderDP leverages score-value mechanism to rank and retain the most informative samples at each itcration.
2.1 PRELIMINARIES
We begin with the standard empirical risk minimization formulation over a dataset D = =(2,)/
[(0) = Σ Ci 2;)
(1)
3

---

Published as a conference paper at ICLR 2026
Algorithm 1: Dynamic Training Process with OrderDP
Input: Initial parameters 0', initial scores Hi (0), 2.) for all i E [n], learning rates (n'} > 0, exploration size s, exploitation size q.
Output: Final parameters 67 for t= 1.2.... do
// Ordered Data Pruning (OrderDP)
Sample candidate batch S _ uniformly at random, with |S = Select subset Q C of top-q scores:
Q' E arg max QCS 10 EE
Σ 24)
1/ Compute subgradient
g' E (Lg(()) where Lo (f')
Σ c,(0",20 21).
q iE
// Update model parameters g++1 + H - n'gg'.
10
// Update score values [L((0)))))
iE Q' (0' zi), otherwise.
H441 ,2) (2)
where Rd denotes the model parameters and each per-sample loss C, 2:): Fd R>o measures the discrepancy on example 24. Solving this ERM via (mini-batch) stochastic gradient descent is at the core of most modern machine learning tasks.
Score Value Function. To drive dynamic pruning. we associate each sample 2; with nonnegative score value H.) (0) H. (6, 2;), which quantifies its importance. In general, Hi can be any function of model state and data (e.g., gradient norm influence measure), but we adopt the instantaneous loss H.) = (0, z;) as simple, adaptive proxy: higher loss indicates greater need for retention. By updating scores only for samples that remain active, we avoid full-dataset recomputation each step. Concretely, if Qs C D denotes the set of retained examples at epoch t, then
[c,(0 21), i Q., 2:) = (Hi(0* zi), i i
Het1 1
This rule ensures that only the losses of selected samples are refreshed, while others retain their previous scores. Together, the ERM objective and the score value function enable dynamic data pruning: by ranking samples via (0). we focus computation on the most informative subset each iteration, reducing training cost without hurting accuracy.
2.2 THE ORDERDP PRAMEWORK
Building on the ERM and score-value preliminaries, Ordered Data Pruning (OrderDP) integrates dynamic sample selection into the SGD loop. At each iteration, candidate batch is uniformly sampled, the top-q samples are selected by score values. and a subgradient computed on this subset is used for parameter update. Scores are refreshed only for the retained samples, while others remain unchanged. The complete procedure given Algorithm 1.
OrderDP combines uniform sampling with casee-based ranking to preserve diversity while focusing on informative samples, and enforces an exact prune ratio of - (g/s) s) (s/[D)) for predictable speed- ups. Uniform sampling ensures every sample has non-zero chance of being selected, improving robustness (see Part 4.2, (Shah et al., 2020)) and reducing dependence on sorting. The sorting step can be reduced to Ollog q) time per sample (even (1)) when 1), with constant memory overhead, unlike other dynamic methods such as UCB (Raju et al., 2021) and InfoBatch (Qin et al., 2024), which require either Olog n) time ((n) storage.
4

---

Published as a conference paper at ICLR 2026
3 THEORETICAL ANALYSIS
In this section, we show that OrderDP provides unbiased gradient estimates for a surrogate loss and achieves standard convex-Lipschizz convergence rates, then establish its generalization error bound via a spectral-risk analysis. Full proof's are provided in Appendix A.
3.1 BIAS AND CONVERGENCE ANALYSIS
In this subsection, we analyze the convergence of OrderDP by first capturing the bias introduced by selective pruning. Specifically, we define surrogate loss that yields unbiased gradient updates:
min Σ
(E)
(g) = Σ To (0), and where
(3)
(1,
where (-) is the j-th rank of per-sample loss and each weight N/ depends only on (n, s, q). This construction guarantees that the gradient estimator ÿ" produced by OrderDP unbiased with respect to Lg.
Theorem 1. Under the definitions above, the update gf in Algorithm I satisfies
Elg') & OC(0') but TEGg E (0',
Le., it is an unbiased estimator of a (sub- huub--gradient of Lug
Theorem I shows that the biased gradient estimation of OrderDP w.r.t. empirical loss L can be interpreted as an unbiased method for minimizing the surrogate objective Lg Lu is well-defined for any 0, and OrderDP enjoys three key advantages: @ By choosing and q. the prune ratio 1 - 2 is easily adjusted; @ Computing 7i adds no per-epoch cost, unlike other dynamic methods requiring Onn) time and memory for weight tables; @ OrderDP preserves unbiased, estimates for el-miinnaai the need for annealing. See Appendix A.1 for the complete proof.
gradient
Another view of Theorem is that the parameters s,9) shape the surrogate loss (g) via the weights (15}, which inherently represent the selective pruning. Inspired by the asymptotic approximation in (Kawaguchi & Lu, 2020), obtain:
Proposition 2. Denote = = j/ and ((2) = Ei z (1- -1-- (1-1)](s-1 Then, as j, + co. it holds that
lim j,n-vo,, j/n=z
7 = 72))
(5)
Furthermore, 1- 7(2) is the cumulative distribution of Beta( - g).
The weight sequence //// generated by OrderDP forms a non-uniform probability distribu- tion (Kawaguchi & Lu. 2020; Mchta et al., 2023; Shah et al., 2020), which can be easily verified through a numerical simulation showing that Σ/= 7// q-= = for given s, A non-trivial proof also provided. For the structure of 7 itself, Fig 5 shows that "/ monotonically decays. we fix increase. Similar observations are also found in (Kawaguchi & Lu, 2020), but we make a more general formulation of yy. More discussions, proof and empirical validation are deferred to Appendix A.2 and Appendix D.2.
(s, q), the cliff becomes smoother and closer r(z)
Building on the unbiased gradient estimates of OrderDP, we leverage the classic mini-batch SGD analysis to obtain the following guarantee.
Theorem 3. Let (8 be the sequence generated by Algorithm 1. Suppose there exists a finite 0" arg ming (0), E, (0*) < oc. efcch L,(-) is convex and G-Lipschitz, then
min [(C,((0') - (0)) Tmax (1102 100--0-133 G2 G² ostST
(6)
1min Din
This matches the standard O(1/VT) convergence rate of mini-batch SGD under the same convexity and Lipschitz assumptions, demonstrating that OrderDP attains identical theoretical guarantees
despite pruning. In particular, choosing 1/ 0 0" 0//|2/ (la/(GVT yields the error bound (G (0
5

---

Published as a conference paper at ICLR 2026
8" 12)/ By using the averaged iterate 67 = (1/ -1 n'0' the dependence on Mumax and Mmin can be removed, that is -0,)))(,00))))1 - full proof is provided in Appendix A.3, Empirical evidence supporting the convergence assumptions is provided in Appendix D.3.
The
Thus, despite pruning large fraction of data each epoch, OrderDP does not slow optimization in expectation, ensuring computational savings without loss in convergence speed.
3.2 GENERALIZATION ANALYSTS
Having established convergence for the surrogate loss (0), we now quantify its approximation to the expected risk L(0*) B.-D| (E(0", =)]. Pruning creates a non-uniform sampling bias. Motivated by the I-Wasserstein distance (Mehta et al., 2023), we rewrite (0) =Ez=1 2á (()) and L()) =
Σj=1 n (0),, thereby revealing the bias from the gap between {///4} and uniform weights (1/m). Noting that (0, D) = E ( Lig (0) with 93 = (n/s) we decompose the generalization gap E ( D)1 [( into a bias term B|c, (0. D)] - E| D)] and a sampling error ([ D)] - L( where the expectation is over the random minibatch (i.....,de)) .d)..
Theorem 4. (Generalization error bound). Under the same assumption of Theorem 3, the following satisfies for any O in the sequence O = {0}T=1 generated by OrderDP:
Tmaa (110² 0 112 + G2 ET (T')))
(((0) (0,, (D] V s(n
(0';
2mmin Ex 118
bias term
unbiased term
where C. = SUP)e((0 (s(()- P. B = inface max.e( (4(0, D:) < xo, and Qn =
infoge Σ (). (0, D:). The expectation is over the random batch sampling.
The bias term bounds the bias from selective pruning of OrderDP; the unbiased term is the standard optimization error, which vanishes as T - oo with suitable 1/'_ The dependence on 7max and mmin can be removed by using the averaged iterate; see proof in Appendix A.4. In contrast, the value C, and Qx (0; s, q) remain finite and quantify the deviation of {7;) } from uniformity (Mehta et al., 2023), as confirmed by simulations in Figure 6. As g + 8, (r,(0, D)/4 1/n) - O, so (n; 8, 9) - O; and nー - O, implying C( )= - E|C, (0', D)]. Thus, by minimizing (0', D). as s + n, V2,BB (n--1)
OrderDP also minimizes expected generalization error. In the special case s g. it reduces to standard mini- batch SGD (r. D 1/n, C, 0) and the bias vanishes. The approximation behavior characterized in Theorem 4 further illustrated empirically Appendix D.2.
Theorem 4 shows that OrderDP 's modifies the distribution shift the gap between the surrogate loss Eg and the original loss L, and the gap fully captured by the values C, and Qn of the biased term. For high pruning ratio, i.e., small exploitation size q or a small exploration size since q S 8, the distribution of 21, compared to the uniform distribution (which has a range of 0), a substantial discrepancy between C, and Qn (0; 8, 4), and consequently, poor approximation. As the pruning ratio decreases (i.e., 9 approaches 8), the range of the 7, distribution narrows, and its shift from the uniform distribution diminishes and both C. and Q, (0: s, 9) decrease, thereby improving the approximation. Specifically, when q == s. OrderDP reduces to standard SGD. In this case, the bias term vanishes, yielding C.y L. We visualize the distribution shift in Figure? 7.
q j. E (I..... exhibates a large range. This leads to significant bias
In summary, Theorem 4 demonstrates that OrderDP 's generalization error comprises a vanishing optimization term and a bounded pruning bias, maintaining SGD-rate convergence while controlling dynamic pruning bias, which is consistent with the observation in Figure (a-c).
*s(t) and u(t) refer to the prohability density of the spectrum "y distribution and uniform distribution on (0, 1). Details can be found in (Mehta et al., 2023).

---

Published as a conference paper at ICLR 2026
4 EXPERIMENTAL SETTINGS
4.1 DATASETS AND TASKS
To comprehensively validate the effectiveness of our proposed OrderDP, we conduct experiments on range of image classification benchmarks: CIFAR- 10 and CIFAR- 100 (Krizhevsky et al., a:b), ImageNet- 1K (Deng et al., 2009).
CIFAR datasets comprise 32 32 color images across 10 and 100 categories, respectively. Each split includes 50,000 training and 10,000 test samples, providing balanced classification evaluation. ImageNet- K 1,000-class subset of ImageNet-21k,, contains 1, 1,281,167 training images and 50,000 validation images, spanning variety of object categories.
4.2 IMPLEMENTATION DETAILS
In this section, we provide a succinct overview of the implementation details for our experiments, including backbone models and training details.
Backbone models. For classification, we train ResNet- 18 and ResNet-50 (He et al., 2016) on CIFAR-10/100 and ImageNet- 1K.
Training Details. For OrderDP. an exploration ratio of 0.5 related to (i.e., s/|D) DD 0.5) and an exploitation ratio of 0.6 related to q (i.e., g/s s 0.6) are used by default when no other values are specified. All models are trained with the OneCycle scheduler, which employs cosine annealing, using SGD with a momentum of 0.9 and a weight decay 5 x 10-4, Images are augmented through normalization, random cropping, and horizontal flipping unless stated otherwise. The implementation based on Py PyTorch (Paszke, 2019). All other details are deferred to the Appendix and D.I.
5
EMPIRICAL STUDIES
5.1 EMPIRICAL ANALYSIS ON CIFAR
For a comprehensive comparison on CIFAR-10/100, we consider two categories of DP methods baselines: static DP and dynamic DP. From static DP, include 15 representative methods: static random pruning, CD (Agarwal et al., 2020), Herding (Welling, 2009), K-means (Sorscher al., 2022), Least Confidence and Entropy (Coleman al., 2019), Forgetting (Toneva et al., 2018), GraNd and EL2N (Paul et al., 2021). DeepFool (Ducoffe & Precioso, 2018), Craig (Mirzasoleiman al., 2020), Glister (Killamsetty al., 2021b), Influence (Koh & Liang, 2017), and DP (Yang et al., 2022). From dynamic DP, we adopt four methods: dynamic random pruning, é-greedy (Raju et al., 2021), UCB (Raju et al., 2021), and InfoBatch (Qin al., 2024), along with our proposed method OrderDP, which also belongs here.
Performance comparison. From Tables and 2, our systematic study suggests the following trends: @ Dynamic random pruning outperforms static random by preserving higher sample diversity, and both e-greedy and UCB adaptively explore sample importance, but OrderDP consistently surpasses other baselines in accuracy and robustness across all prune ratios. @ At 30% pruning, only OrderDP matches full-data accuracy. @ Under 50% and 70%, OrderDP has the smallest accuracy drop, outperforming both static and existing dynamic methods. @ Compared InfoBatch, OrderDP consistently yields higher accuracy as pruning becomes more aggressive.
Efficiency comparison. Table reports end-to-end training time and GPU-hours under identical settings. OrderDP achieves the fastest training and lowest GPU-hours, improving upon InfoBatch without loss in accuracy. Additional CIFAR results and extended comparisons are Appendix D.
Extended comparison of varying pruning ratios. To further evaluate the performance of OrderDP, we compare with InfoBatch, a sfate-of-the-ar data pruming algorithm, across different prune ratios on the CIFAR-10 and CIFAR- 100 datasets. The results are demonstrated in Figure 3. It can be observed that OrderDP not only achieves higher accuracy at every pruning ratio, but also remains
In the original experiments of InfoBatch (Qin et al., 2024), an annealing algorithm was incorporated. To ensure fair comparison, we have removed this component from all implementations.
7

---

Published as a conference paper at ICLR 2026
Table Static pruning results (accuracy, %) on CIFARI0 and CIFAR100 with ResNet-18. Accu- racy (%, 1). Best in bold. Performance gaps to full-data are in blue / orange.
Dataset
CIFARIO
CIFAR100
Prune Ratio
70
Static Random
94.6
93.3
90.2
73.8 (4.4
72.1
69.7
CD (Agarwal ct al., 2020)
95.0
94.3
90.8,4.8
74.2
72.3
70.3
Herding (Welling. 2009)
92.2
88.0
80.1
73.1
71.8,6.4
69.618.0
K-Center (Sener & Savarese, 2018)
94.7
93.9.1.7
90.9
74.1
72.2.6.
70.2
Least Confidence (Coleman et al., 2019)
95.0
94.5
90.3
74.2
72.3
69.8|8.4
Margin (Coleman et al., 2019)
94.9 10.7
94.3
90.9
74.0
72.2
70.2
Forgetting (Toneva al., 2018)
94.7 10.0
94.1.1.5
91.7 (3.9
75.3
73.1
69.9 18:3
GraNd-4 (Paul al., 2021)
95.3
94,6,1.
91.2
74.613.8
71.4
68.8
DeepFool (Ducoffe & Precioso, 2018)
95.1
94.1,1.5
90.0
74.2
73.2.5.0
69.8
Craig (Mirzasolciman et al., 2020)
94.8
g3.3
88.4
74.4
71.9.6.
69.7
Glister (Killamsetty et 2021b)
95.2,0.4
94.0,1.6
90.9
74.6,a.6
73.2
70.4
Influence (Koh & Liang, 2017)
93.1
91.3
88.3
74.4
72.0,6.
68.9
EL2N-2 (Toneva et al., 2018)
94.4
93.2
89.8.5.8
74.1
71.0,
68.5
EL.2N-20 (Toneva al., 2018)
95.3
95.1
91.9
77.2
72. 72.1
(Yang al., 2023)
94.9
93.8,1.8
90.8p1.
77.2
73.1g5.1
OrderDP
95.6
95.3,aa
95.0gaa
78.2
77.9.ka
76.7
Whole Dutaset
95.6:0.1
78.2:0.11
Table 2: Dynamic pruning results (accuracy, %) on CIFARI0 and CIFARICO with ResNet- 18 and ResNet-50. Accuracy (%, 1). Best bold. Performance gaps to full-data are blue /range.
Dataset
CIFARIO
CIFARI00
Backbone
ResNet-18
ResNet-50
ResNet-18
ResNet-50
Prune Rario
30
70
30
30
50
70
Dynamic Random
94.8.u
94.5
93.0.2.
g5.
94.9.o.7
93.6.24
77.3,uu
35.3
72.8
17.9
76.1
u3.9
e-gracdl
95.2,n.
94.9
94. 94.1,1.5
95.4go.2
95 15.s
94.3.1.1
76.4_.a
74.8
72.9,sa
27.2
76.3
74.1
UCB
95.3,0.3
94.7
93.9.1.7
95.5pm.
95.0,a.
94.2.14
77.3,ng
75.3
73.2
78.0
76.5
74.3
InfoBatch
95.6.0.
95.0
91.5
95.6gn.
95.3
94.7
78.1.u.1
77.7
25.9.2
80.4pn.2
78.6
76.4
OrlerDP
95.6
45.3
95.0
95.6
95.4
95.0
78.2
77.9
76.7
MIL6
79,8,ax
77.9
Whole Dataset
95.6go.1
95.6...1
78.2
80.gg.
comparable to other algorithms and reduces total training time in most cases. Moreover, InfoBatch cannot prune to an extreme ratio (limited by 77.9% on CIFAR-10 or 72.2% on CIFAR- 100 in our setting) due to its fixed retention mechanism. OrderDP supports arbitrary pruning ratios because data retention is fully specified by the the exploration size and exploitation size (see Section 5.3). These results confirm that OrderDP 's sample-selection strategy delivers near-optimal efficiency and robustness, making it particularly well-suited for resource-constraing scenarios where preserving accuracy paramount.
5.2 EMPIRICAL ANALYSIS ON IMAGENET- KK
We evaluate Dynamic Random, UCB (Raju et al., 2021). InfoBatch (Qin et al., 2024) and our OrderDP ImageNet-IK with ResNet-50 40% pruning (Table 3). OrderDP matches/exceeds all baselines in accuracy while not significantly increasing the total GPU runtime; retains full-data performance 40% pruning and incurs only 0.4% drop 60% (Table 4). @ Efficiency: OrderDP completes training faster and uses fewer GPU-hours than all competing methods. @ Robustness: It shows no loss moderate prune ratios and only minimal degradation under aggressive pruning. Together, these findings confirm that OrderDP achieves near-lossless accuracy with substantial reduction compute, making ideal for large-scale training under tight resource budgets.
5.3 ABLATION EXPERIMENT
We study how two-stage pruning decomposition, parameterized by the exploration size and ex- ploitation size q, affects OrderDP 's performance CIFAR-10/100 with ResNet-18 18 (Figure 4).
8

---

Published as a conference paper at ICLR 2026
10/
(a) Accuracy vs. Training Time on CIFAR- 10
(b) Accuracy vs. Training Time on CIFAR-100
Figure 3: More accuracy and time results for different prune ratios on CIFAR-I0/100 for OrderDP and InfoBatch, using ResNet-18. The lossless pruning ratios are marked in the figure. Table 3: Comparison of performance and time cost on ImageNet- IK. Results are reported with ResNet-50 under 40% prune ratio for 90 epochs on a 2-L40-GPU server.
Table 4: Experiments on ImageNet- IK. The models here are all implemented based on ResNet-50pytoche
"Total hn* is the total node hour.
Prune Ratio
30
r-greedy
Ours
Full
InfoBatch
76.4.am
75.6,ux
74.9
Acc (8)
73.4
75.2
75.4g0.
75.6
76.420.
76.40.3
OnderDP
76.4
76.4
76.0,a4
Time (h)
21.5
Total (n"h)
42,2
42.2
42.2
43.2
43.0
70.4
Whole Dataset
76.420.1
Fixed prune ratío Under a fixed effective prune ratio, we vary the decomposition of the retained data portion by adjusting the exploration ratio s/| and the exploitation ratio g/s, while keeping their product (q/s). (I) unchanged.
As shown in Figure 4, OrderDP achieves identical accuracy across all decompositions on both datasets, demonstrating its precise control over the prune ratio. The training time remains stable across different decompositions, indicating consistent computational cost when the overall prune ratio is fixed.
Varying prune ratios. As the prune ratio grows, training time drops sharply while accuracy degrades more slowly-up about 70% pruning, where CIFAR- 100 with half the compute. Beyond that, further pruning gives diminishing accuracy but continues to cut runtime. This shows OrderDP 's ability
95% CIFAR- 10 and over 76%
smooth efficieney-performmne performance frontier and lets practitioners pick the "sweet spot" matching their compute budget.
Our ablation shows that decoupling exploration (s) and exploitation (g) achieves exact pruning ratios without efficiency loss and yields a smooth accuracy-cost frontier, enabling straightforward budget selection. We further provide stability results under multiple runs Appendix D.6.
5.4 SENSITIVITY ANALYSIS
Cross-architecture robustness evaluation. Table 6 reports the maximum lossless prune ratios of InfoBatch and OrderDP on ResNet-18/50 across CIFAR-10, CIFAR-I00, and ImageNet- IK. InfoBatch usually caps in the mid-30% range, while OrderDP extends this by 4-6 points, especially on harder datasets, showing its ability to prune more aggressively without accuracy loss.
We adopt the Timm (Wightman et al., 2021) ImageNet training stack, which com- bines mixeddpreeisioe training with strong augmentation and regularization methods such MixUp, and CutMix (Zhong et al., 2017; Zhang et al., 2018; Yun et al., 2019), and observe that OrderDP continues yield lossless speedups under this stronger recipe, indicating that it is compatible with existing acceleration and augmenta- tion pipelines. Beyond CNN-based architectures, OrderDP also maintains lossless accuracy
Table Cross-architecture robustness evaluation on ImageNet-IK. ViT-Base (MAE) is pretrained with OrderDP for 300 epochs and fine-tuned for 100 epochs. Swin-Tiny trained from scratch with OrderDP.
Model
Prune Ratio
Original
OrderDP
R-50mm
29.8%
78.4
78.3
Swin-T
22.1%
81,5
81.4
ViT-B (MAB)
30.8%
82.8
82.8

---

Published as a conference paper at ICLR 2026
CIEAR-10
CIFAR-100
retta 0.7
Pitta 0.7
rablo 0.5
Time (1ea))
Tato 0,5
Accimay (H0)
Eatt 5.55
rello
rato
Figure 4: Performance with different ratio parameters. Here (q/s) (s) represents the retained data ratio, and thus the prune ratio is caleulated (g/s) (s/(D)). Results reported with ResNet-18. 18.
Table Cross-architecture robustness results of OrderDP. 'Full Dataset' denotes training on the original dataset without pruning-
Table 7: Comparison of accuracy (%) and saved
cost (%) on CIFAR-10 when trained with R-50 using different optimizers.
CIFAR- 10
CIFAR 100
ImageNet- IK R-18
SGD
AdamW
LARS
LAMB
R-18
R-50
R-18
R-50
R-50
Full Dataset
95.6
94.3
95.5
95.0
Full Dataset
95.6
95.6
78.2
80.6
70.5
76.4
InfoButch
95.6
94.3
95.5
95.0
InfoBatch
95.5
95.6
78.2
80.6
70.4
76.4
Saved (%)
37.1
37,0
37.1
37.1
Saved (%)
36.5
37.1
30.8
36.3
21.8
34.3
OrderDP
95.5
95.6
78.2
80.6
70.5
76.5
OrderDP
95.6
94.4
95.0
Saved (%)
41.2
42.6
35.8
41.1
27.3
39.8
Saved (%)
42.6
42.4
42.5
42.6
Note: All the results obtained from 2-L40-GPU server.
20%-30% pruning on Swin-Tiny (Liu et al., 2021) and ViT-Base (MAE) (He et al., 2021) (Table 5). showing that the loss-based ordering remains stable on Vision Transformers, and that OrderDP naturally transfers across heterogeneous architectures
plug-and-play module.
Cross-optimizer robustness evaluation. We test widely used optimizers SSD (Bottou et al., 1991), Adam W (Loshchilov & Hutter, 2019), LARS (You et al., 2017), and LAMB (You et al., 2019) ResNet-5OCCIFAR-I 10 (Table 7). InfoBatch saves 37.1% training cost across all optimizers, while OrderDP raises savings about 42.5%. This consistent gain shows that OrderDP 's dynamic sample selection aptimizer-agnostiie by focusing on high-loss examples, reduces redundant computation and delivers plug-and-pll and-play efficiency without accuracy loss.
6 CONCLUSION
In this paper, we introduced OrderDP, novel dynamic data pruning framework that provides rigor- ous theoretical guarantees while achieving substantial training acceleration. Unlike prior approaches, OrderDP ensures unbiased gradient estimation and offers exact control of the pruning ratio, leading to more stable and efficient data pruning. Our theoretical analysis establishes both convergence guarantees and generalization bounds, demonstrating its robustness across datasets and pruning levels. Empirically, OrderDP consistently attains equal or better accuracy than state-of state-of-the-ar baselines, while reducing runtime and overall computational cost by 40-45%. Moreover, its simpler plug-and-play design makes easy to integrate into existing pipelines. These findings highlight the potential of our method scalable solution that balances efficiency, accuracy, and theoretical rigor.
ETHICS STATEMENT
Our work focuses on improving training efficiency in deep learning through dynamic data pruning. All experiments are conducted on widely used public benchmark datasets (CIFAR-10, CIFAR- 100, and ImageNet-IK), which do not involve any personally identifiable information, sensitive attributes, or human subjects. The study does not pose foreseeable risks related to privacy, fairness, or security. Moreover, external sponsorship conflicts of interest have influenced the design, analysis, or reporting of this work. As such, we believe our research complies with the ICLR Code of Ethics and raises ethical concerns.
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY STATEMENT
We are committed to ensuring the reproducibility of our results. To this end, we provide detailed descriptions of datasets (CIFAR-10, CIFAR-100, ImageNet-1K), model architectures (ResNet- 188 ResNet-50), hyperparameters, and training protocols in the main text and Appendix. For reprodueibil- ity, our implementation based on PyTorch, with standard data augmentation (normalization, random cropping, horizontal flipping), SGD optimizer with momentum, weight decay, and OneCycle learning rate scheduling. We will submit the full source code and configuration files in the supplementary material to enable independent verification of our experiments. In addition, ablation studies and sensitivity analyses provide transparency into the robustness of our method across pruning ratios, optimizers, and architectures.
ACKNOWLEDGMENTS
This work was supported in part by the BNBU Research Grant (No. of UICR0100031, UICR0700108- 25, and UICR0900003) at Beijing Normal-Hong Kong Baptist University, Zhuhai, PR China. This research was also supported by the National Natural Science Foundation of China (Grant No. 12401415), the Natural Science Foundation of Hunan Province (Grant No. 2025J160009), and the Project of Scientific Research Fund of Hunan Provincial Science and Technology Department (Grant No. 25B0148).
REFERENCES
Carlo Acerbi and Dirk Tasche. On the coherence of expected shortfall. Journal of banking & finance,
26(7):1487-153, 2002. 18
Sharat Agarwal, Himanshu Arora, Saket Anand, and Chetan Arora. Contextual diversity for active learning. In ECCV, pp. 137-153. Springer, 2020. 7, 8, 20
Shun-ichi Amari. Backpropagation and stochastic gradient descent method. Neurocomputing, 5(4-5); 185-196, 1993.
Shun-ichi Amari, Naotake Fujita, and Shigeru Shinomoto. Four types of learning curves. Neural Computation, 4(4):605-618 1992.
Fadhel Ayed and Soufiane Hayou. Data pruning and neural scaling laws: fundamental limitations of score-based algorithms. arXiv preprint arXiv:2302.00 3332006660, 2023. 2, 21
Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. Advances in neural information processing systems, 33:14879-14890 2020. 1
Léon Bottou al. Stochastic gradient learning in neural networks. Proceedings of Neuro-Nimes, 91 (8):12, 1991. 10
Trevor Campbell and Tamara Broderick. Automated scalable bayesian inference via hilbert coresets. Journal of Machine Learning Research, 20(15); 2019.
Yihan Cao, Yanbin Kang, Chi Wang, and Lichao Sun. Instruction mining: Instruction data selection for tuning large language models. arXiv preprint arXiv:2307.06299. 2023. 21
Haw-Shiuan Chang, Erik Maanedd-Milles and Andrew McCallum. Active bias: Training more accurate neural networks by emphasizing high variance samples. Advances in Neural Information Processing Systems, 30, 2017. 20
Dingshuo Chen, Yanqiao Zhu, Jieyu Zhang, Yuanqi Du, Zhixun Li, Qiang Liu, Shu Wu, and Liang Wang. Uncovering neural scaling laws molecular representation learning. Advances in Neural Information Processing Systems, 36: 1452-1475, 2023. 1
Dingshuo Chen, Zhixun Li, Yuyan Ni, Guibin Zhang, Ding Wang. Qiang Liu, Shu Wu, Jeffrey Yu, and Liang Wang. Beyond efficiency: Molecular data pruning for enhanced generalization. Advances in Neural Information Processing Systems, 37:180364 18061, 2024. 1
11

---

Published as a conference paper at ICLR 2026
Mchdi Cherti, Romain Beaumont, Ross Wightman, Mitchell Wortsman, Gabriel Ilharco, Cade Gordon, Christoph Schuhmann, Ludwig Schmidt, and Jenia Jitsev. Reproducible scaling laws for contrastive language-iman image learning. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 2818-2829, 2023.
Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailís, Percy Liang, Jure Leskovee, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. In ICLR, 2019. 7, 8, 20
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 JEEE conference on computer vision and pattern recognition,
pp. 248-22882 248-255. Icee, 2009. 3,
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: a margin based approach. arXiv preprint arXiv: 099401 2018. 7, 8, 20
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 pattern recognition, pp. 770-778, 2016.7
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders scalable vision learners, 2021. 10
Muyang He, Shuo Yang, Tiejun Huang, and Bo Zhao. Large-scale dataset pruning with dynamic uncertainty. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition, pp. 7713-7722, 2024. 20
Danny Heraadezz, Jared Kaplan, Tom Henighan, and Sam McCandlish. Scaling laws for transfer. arXiv preprint 112iv:2102.01293, 2021.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Hcewoo Jun, Hassan Kianinejad, Md Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically, arXiv preprint 1712.0049,, 2017.
Jonathan Huggins, Trevor Camphell, and Tamara Broderick. Coresets for scalable bayesian logistic regression. Advances in neural information processing systems, 29, 2016.
Minyoung Huh, Pulkit Agrawal, and Alexei A Efros. What makes imagenet good for transfer learning? arXiv preprint arXiv:/608.000
2016. 20
Rishabh Iyer, Ninad Khargoankar, Jeff Bilmes, and Himanshu Asanani. Submodular combinatorial
information measures with applications in machine learning. In Algorithmic Learning Theory, pp. 722-754. PMLR, 2021. 20
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alee Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint 2rXiv:2001.08366 2020. 1
Kenji Kawaguchi and Haihao Lu. Ordered sgd: A new stochastic optimization framework for empirical risk minimization. In International Conference on Artificial Intelligence and Statistics, pp. 669-679, PMLR, 2020. 3,5
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, pp. 5464-5474. PMLR, 2021a. 20
Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glister: Generalization based data subset selection for efficient and robust learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021b. 1, 7, 8, 20
Sungnyun Kim, Sangmin Bae, and Se- Young Yun. Coreset sampling from open-set for fine- grained sulf-supe learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7537-7547, 2023. 1
12

---

Published as a conference paper at ICLR 2026
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1885-1894. JMLR. org, 2017. 7, 7,7,8.2 20
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced research), a. URL http: : /www. cs. www.cnnttoeuu/kriiiii.i citfriiccciaaaaaaeeeeeeeaaeeeaee html. 3, 7
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- 100 (canadian institute for advanced research). b. URL http::/ www. CS toronto.oooooooooo www.oot..oooooeeee.oooo /tterriicfffaa cirar.rraee fa..farr......mm.mm....mm....... 3,
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows, In Proceedings of the IEEF/CVF International Conference on Computer Vision (ICCV), 2021. 10
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization, 2019, 10
Zhiyun Lu, Yongqiang Wang, Yu Zhang, Wei Han, Zhehuai Chen, and Parisa Haghani. Unsupervised data selection via discrete speech representation for arXiv preprint arXiv:2204.01981, 2022.
21
Katerina Margatina, Giorgos Vernikos, Loic Barrault, and Nikolaos Aletras. Active learning by
acquiring contrastive examples. arXiv preprint arXiv:2 100.::2449 2021. 20
Max Marion, Ahmet Üstün, Luiza Pozzobon, Alex Wang, Marzich Fadace, and Sara Hooker.
When less is more: Investigating data pruning for pretraining Ilms at scale. arXiv preprint 23l.:23009.0564, 2023. 21
Ronak Mchta, Vincent Roulet, Krishna Pillutla, Lang Liu, and Zaid Harchaoui. Stochastic optimiza- tion for spectral risk measures. In International Conference on Artificial Intelligence and Statistics, pp. 10112-10159, PMLR, 2023. 5,5, 6, 18, 19
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In ICML. PMLR, 2020. 1, 7,
Patrik Okanovic, Roger Waleffe, Vasilis Mageirakos, Konstantinos Nikolakakis, Amin Karbasi, Dionysios Kalogerias, Nezihe Merve Gürel, and Theodoros Rekatsinas. Repeated random sampling for minimizing the time-to-accuracy learning. The Twelfth International Conference on Learning Representations, 2024. URL
IuTe. 20
Paszke. Pytorch: An imperative style, high-performance deep learning library. arXiv preprint arXiv:1912.0177 2019.
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on data diet: Finding important examples early training. Advances neural information processing systems, 34: 20596-20607, 2021. 7, 8, 20
Ziheng Qin, Kai Wang, Zangwei Zheng, Jianyang Gu, Xiangyu Peng. xu Zhao Pan, Daquan Zhou, Lei Shang, Baigui Sun, Xuansong Xie, and Yang You. Infobatch: Lossless training speed up by unbiased dynamic data pruning. In The Twelftth International Conference on Learning Representations, 2024. 1, 2, 4, 7, 8, 20
Ravi Raju, Kyle Daruwalla, and Mikko Lipasti. Accelerating deep learning with dynamic data pruning, 2021. 1, 4, 7, 8, 20
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In ICLR, 2018. 8, 20
Vatsal Shah, Xiaoxia Wu, and Sujay Sanghavi. Choosing the sample with lowest loss makes sgd robust. In International Conference on Artificial Intelligence and Statistics, pp. 2120-2130. PMI.R, 2020. 4.5
Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. Advances in Neural Information Processing Systems, 15:19533-19566, 2022. 7, 20
13

---

Published as a conference paper at ICLR 2026
Haoru Tan, Sitong Wu, Fei Du, Yukang Chen, Zhibin Wang. Fan Wang, and Xiaojuan Qi. Data pruning via weeiinn-one-sapllle Advances in neural information processing systems, 36: 18251-18262, 2023. 20
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey Gordon. An empirical study of example forgetting during deep neural network learning. arXiv preprint arXiv: 2018. 8, 20
Max Welling. Herding dynamical weights to learn. ICMLg, pp. 1121-1128, 2009. 7,
20
Ross Wightman, Hugo Touvron, and Hervé Jégou. Resnet strikes back: An improved training procedure in timm, 2021. 9
Sang Michael Xie, Hieu Pham, Xuanyi Dong, Nan Du, Hanxiao Liu, Yifeng Lu, Percy S Liang, Quoc V Le, Tengyu Ma, and Adams Wei Yu. Doremi: Optimizing data mixtures speeds up language model pretraining, Advances in Neural Information Processing Systems, 36:69798-6988 2023. 21
Shuo Yang, Zeke Xie, Hanyu Peng. Min Xu, Mingming Sun, and Ping Li. Dataset pruning: Reducing training data by examining generalization influence. arXiv preprint arXiv:2205.09322 2022. 20
Shuo Yang, Zeke Xie, Hanyu Peng, Min Xu, Mingming Sun, and Ping Li. Dataset pruning: Reducing training data by examining generalization influence. In The Eleventh International Conference on Learning Representations, 2023. 8
Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks. arXiv preprint arXiv: 708. 03888, 2017. 10
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv preprint arXiv: 1904000,, 2019. 10
Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo.
Cutmix: Regularization strategy to train strong classifiers with localizable features, 2019,
Hongyi Zhang, Moustapha Cisse, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization, 2018.
Xingxuan Zhang, Renzhe Xu, Han Yu, Hao Zou, and Peng Cui. Gradient norm aware minimization seeks first-order flatness and improves generalization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 20247-20257, 2023.
Yang Zhao, Hao Zhang, and Xiuyuan Hu. Penalizing gradient norm for efficiently improving generalization in deep learning. In International conference machine learning, pp. 26982- 26992. PMLR, 2022. 2
Zhun Zhong, Liang Zheng, Guoliang Kang, Shaozi Li, and Yi Yang. Random erasing data augmenta- tion, 2017.
14

---

Published as a conference paper at ICLR 2026
A PROOF OF THEORETICAL ANALYSIS
A.1 PROOF OF THROREM
Proof. We just need to show that g is unbiased estimator of sub-gradien of (0) at 0*, namely Eg E (0'). At first, it holds that
1 Eg'
E
EEE' Σ P(i Q)9
q
SEQ
n
P(G) Quiin
where of E (L; is a sub-gradient of L, at f¹, In the above equality chain, the third equality simply the definition of expectation, and the last equality is because ((1), (2)..... (n)) is
permutation of (1, 2.....
For any given index P(()) Q) thus Eg' & OL(0).. To analyze P(()) E Q), define
A, = (2),
(j - 1)), and A3 (G 11,
(j 2), (v)...,,) then
P(G) E Q) = P (()) g- (0) xH,
= =P(()) E S and contains at most g items in AT)
=P(()) E P (S contains at most
items in A (1) S)
(7)
P(( E S) E/e, ((j) appears at position in S),
where < < S measures the possible positions of (j) E These two variables vary depending on the choice of (j). For examples, if (j) = (1), (j) should be included in Q since (1) would be at the top-1 position of
Notice that S is randomly chosen from sample index set (1, ..... n) without replacement. There are in total (*) different sets S such that S = Among them, there are (-=1) different sets S which contains the index (j), thus
(())
(8)
Given the condition ()) S, (j) appears at position means S contains / items in Aj and items in AG, thus we have the constraints:
1 S j and 1
Thus we conclude 8 -n jjj < j. i.e., = max (1, + j} and l2 = min (1,j.. There are (*=)) such possible set S for (j) E S, whereby it holds that
PS contains most items in A, (0) S)
P P(j) appears at position in S ( S)
(9)
min(gg)
[=max 11 +
Substituting Equations (7) and (8) into Equation (6), we arrive at min(g.i)
min(ag)
P(G) EQ)
Σ
Σ
=7--
(10)
(1.
mmax
Therefore,
Eg'
1 Σ P(U) E Q190
Σ T99h (
(11)
q j=1
j=1
where the last inequality due to the additivity of -rbddent (for both convex and weakly convex function) D.
15

---

Published as a conference paper at ICLR 2026
A.2 PROOF OF PROPOSITION 2
Proof. We will show that
1 s j.n j/n=z n (1 - 1) 1)!
9
j
1-1
(1-2)=
lim Vi
1
(12)
1=1
We begin the proof by changing the variable = = 4
At first, the Stirling's approximation yields that when n. and j are both sufficiently large, it holds that
n2
(13)
i
2 - 5) ju - 5)
Thus,
nー
jr (n (n)
1-1
lim
j-i
3
(n 3)n
1
J
(14)
(n-j)-
n
72
π
where the first equality utilizes Equation (10) and the fact that 8, 1, are negligible in the limit case (except the exponent terms).
On the other hand, it holds by rearranging the factorial numbers that
(1-)
s!
(12)
1)1(s - 1)!
Recall 73 = > min(a..)
(-
-==max(1, 11
(>)
Let
min(a.)
(E)
7==
Σ
(15)
I=max 11.aax1,33-220 (1,s-n+j)
1=1
where we set the value to 0 for 1 E [1, n + 5] and [J. if s - n + > and < q. Therefore, we conclude the following by noticing > q.
72) Σ 1=2
1)2² 1)2'-2(11
21 2)
s! (1 - 1)1(s f)!
Σ
1)2- 11 2)0-1-1
s!
(I - 1)!(s - 1)!
1=1
s!
9
8!
2- 2)
1-
2) 1-1-1
(1 2){(s - 1)!
(1 - 1)!(s - -1- 1)!
s!
1- (1 2) 1-1 1-1
(1 2) 1-1-1
- 1)!(s 1 1)!
(1 - 1)1(s - -1 1)!
1=1
s!
--1(( 2) 2- 1-
(q 1)!(s - 1)! (s 1)!
-- (1 2) 2-8-9- 1
(q - 1)1(s - 1)!*
(16)
In other words, 1 1 * (2) is the cumulative distribution function of Beta(g, s q) when n + co.
A.3 PROOF OF THEBREMS 3
Full version of Theorem 3: Let TTo be the sequence generated by Algorithm 1. Suppose there exists a finite 0* E arg ming (0). (0*) < xo. If each Lx(-) is convex and G-Lipschitz, then
min (O), (,,( < Mmnxx (110) - -8- + G2 EL (t=()))) 151S0
(17)
Mmin Σt= 17¹
16

---

Published as a conference paper at ICLR 2026
Moreover, if we define the weighted average H*
Eisi 9¹ Σ 1/80, then
- < 110 0" _ + G² Σ (17))²
(18)
2 >t m= 1¹
Proof. Consider the one update at epoch 1, we have
| 0 1 = 110' 0 l12 2n' (g', 0r - 0-) (1")3110'11.
(19)
Taking the conditional expectation of given of equation 19 yields
11| 11 - |10' 0 11 2n/ [El'"), 0r 0*) + (T7))22
(20)
where we use l l2 S G. Because maintain unbiased gradient estimator Ejg"] E OL, (0'), we have that with convexity of Cg. we have
- -(E(g'), - = - (C) - (0)))
(21)
where the 8x def
arg ming (0). Substituted equation 21 into equation 20 gives
E [ 11]] s ||0t 11 2n'² (0') (0)) + G2.
(22)
2n' (Ly (0*) L.g (0))) = (110* 0- Elllett1 0* 1²) + Gr
Take the expectation over the entire sequence 0t ,..., 0++1, sum over .... T, we have
T
Σ 1/ B0(
(110) (0')0)) s 002 -0000)+100113)) G2
Σ (1/)).
(23)
It shows that
T E1 of
Σ n (0') c,(0')] ||0| - 10 + G2 T (n'))
(24)
2 T
2Σ 17
With the observation that
E Σ (B -C)(0))
T
Σ 1 (( (0))
1 DI 1/d T 1=
(25)
minisisT 1f (0') - (6")
max T/¹
Mmin
min (0)) - (0")) Imar 151ST
where Mann = min of and Mmaa = max max " Therefore, it holds that
Amin
min (0" (g(0
<
n 'EEL (g))
1SAST
Σ o 1=1
(26)
110 00 1 G2 TT ET= (17))
ΣT 17'
Then we can derive that
G2 (0)) - -,((0)) < Mmaa - -1-112+ G22 LT GT (T'()))) (1')3
min
(27)
2mmmin Σt=19 77'
17

---

Published as a conference paper at ICLR 2026
A.4 PROOF OF THEOREM 4
Proof. We begin this proof by leveraging the concepts of spectral risk measure (Acerbi & Tasche, 2002: Mehta et al., 2023). the surrogate loss (0, D) = -i=1 Li=1 Is (0)) = Σ oj ( is called an L-risk with spectrum o; = li and [(s = La) (0) for i E [n], which can be regarded as functional of the CDF known as spectral risk measure. { are arbitrary real-valued i.i.d. random variables drawn from CDF F. For our case, these refer to data instance D; of n samples drawn from distribution D under parameter vector 0.
q
Let (z) == 1 - [-o0.. (Z,) denote the (random) empirical CDF of the sample and define the empirical quantile function (or inverse CDF) as
a
F (1) == [= 2=) for E (0, 1).
(28)
The population quantile function is defined similarly as
F (t) == inf F(2) t}.
(29)
The empirical quantile function can be written in terms of the order statistics as (t) = ((n))))
Notice in partieular that when & E ( a). have that (t) Z(i), where end-points chosen make Fz= left continuous.
The spectrum a of an L-risk is typically defined as discretization of probability density on (0, 1), such that
s/n
s(t) dt,
(30)
(1-1//n
so that need not be redefined for every n. Given both the construction of and F,-1, we can rewrite the Z-risk as
jinn
(0 D)
Σ
0, =
Σ i=1
(
s())d di
Z
t=1
(r s(t) -)(]Z(rn]) )t
i//n
(31)
(1-1)/1
S s(1) F (1) =: IL. [Fx),
where L. [G] = So ((t) df is called spectral risk measure with spectrum applied to CDF G.
It stands to reason that IL, [Fx] converges to L. [F] in an appropriate sense. This convergence is governed by the Wasserstein distance between the empirical and population distribution, which we briefly recall here. In this section, The following lemmas consider a set of real numbers, representing losses at a single 0 E Rd Let IR be call the full batch, and let X1,... X, be random sample selected uniformly without replacement from { }n ). called the minibatch. Let
control the bias term appearing in the convergence analysis.
2n .1,...,
(z) Σ 1 [(000,)] and (x)
Σ 1 (-00,))
(32)
be the empirical CDFs, and let
(t) = inf (x) 2 1) and (t.m(t) = inf(x: (r)
(33)
be the empirical quantile functions of the full batch and minibatch, respectively. Similarly, let
Say and fn,m
8x;
(34)
be the empirical measures of the full batch and minibatch, respectively, with 6, indicating a Dirac point mass Let u(t) : (o.1)) be the uniform spectrum.
18

---

Published as a conference paper at ICLR 2026
Recall the expressions of the C-risk. We denote [(0*) EDwD|C((" D)] as the optimal value. For the sampled distribution, we have
Σ 2i Cis
(0, =
= LF
(35)
and for the uniform distribution, we define
E[C.(0', = E
Σ Cis (0))
Cisy
BLL 0']]
(36)
Moreover, the full-batch loss satisfies
C(0', D) Lf' (00')'))) D) [[_[a[(((:)))))
(37)
Here, the distributions and correspond to the sampling distribution of in (0', D) at step and the uniform distribution, respectively. The expectation is taken over the minibatch (ii....,iah i.).
Therefore, we establish the generalization error over the set θ {0+)
[(0*) - ((', D)]
sup ((00) (0', D)] lee
sup ((0") EIIL, [F,, n. IL. [Fa] + [F]] E[L,, [n. + ([L.([Fndd) [F]] + IL [Fr)
aee
sup _(0") [[ [ [] + IL.. [x]] L, [Fr]
(EIIL [ [n..]] L, [P.] - [E | [ II. [Frl)
< sup ((0") E3 L [] ]] + sup (L..) La (P
808
150
+ sup
BILL P |]] + L. [P)] + E| 1 | n. LL [Ph)]
< inf dee
[E [n. [(0') + sup 6E
(L.. [P] IL. (Fwl)
sup a08
B[L. (P 1] 11 L. [F,]]
L. [P([))))
(10] 84 11 G2 Σt Σt
7max
2mmin Σi= 17
+ sup (Lu(EE)) Lo (Fn)) 0E0
+ sup
||s ul B|| -F Fm
DEB
Mmnn (110 1-1 G2 Et (11)2)
(0' 8. + v2C, B, n 5
21mmin
Σtm 11
s(n 1)
unbiased part
biased part
(38)
where the third inequality follows the Theorem and the fourth inequality follows Lemma 14 in (Mehta et al., 2023). We denote C, suPre(o,1) [s(() u(t)). B =
infog maxe(1..) (0, 2;)l < oo, and Q, (0:8s, q) = infaee Σn_ (0. (0,,))
Moreover, if we use the weighted average 0r S Σt= n7'0 as output of OrderDP, the dependence Mmnx and Mhoin be removed and holds that:
19

---

Published as a conference paper at ICLR 2026
[(0*)- (0" D)]
=L(6") G[L,[FR,: [F
- E[ Fn.s]] - Iu [Fa] + [ [F.]
= -C(0") [[ T.
[T [Fn,)] T. [Fr]] (BI [Fr,s]] - TI,,, [Fx])
s [T [n,el] (Fr.el
+ |[L, (TTua)
[00)
(T..[Fr)
_ (1 [F IL (Fr))
(E[L
< |B|L. [Fn.e] - _(0)) + sup
[L [F]] - F.
AE
+ - [Fn,o]] [1 - L [Fr] - (E L Fn, Lu [Frl)
(100) 11 G2
T ビ 2n 10'00%'' 8) + V2C, B
n 5 s(n -
2 2 n¹
unbiased part
biased part
(39)
where the last inequality follows from (18) and other terms remain unchanged.
B RELATED WORKS
Static Data Pruning. Static pruning techniques aim to pre-select compact subset of the training data that can approximate the utility of the full dataset. A wide range of criteria have been proposed for this purpose. Diversity-based methods such as Contextual Diversity (CD) (Agarwal et al., 2020), Herding (Welling, 2009), and k-Center (Sener & Savarese, 2018) remove redundant samples by ensuring broad feature-space coverage. Difficulty-based strategies including Cal (Margatina et al., 2021) and Deepfool (Ducoffe & Precioso, 2018) prioritize hard-to-leary examples near decision boundaries. Error- and gradient-driven approaches such as GraNd and EL2N (Paul et al., 2021) and MOSO (Tan et al., 2023) instead exploit training dynamics or loss sensitivity. In parallel, uncertainty- based sampling (Coleman et al., 2019), influence-function analysis (Koh & Liang, 2017), and gradient matching approaches like GradMatch (Killamsetty et al., 2021b:a) provide alternative means of quantifying informativeness. More principled frameworks include bilevel optimization (Killamsetty al., 2021b) and submodular subset selection (lyer al., 2021), where algorithms such as FL and Graph Cut (GC) (lyer et al., 2021) explicitly balance coverage and information gain. Early computer vision work such as (Huh et al., 2016) also emphasized the importance of dataset diversity for transferable representations. While effective in specific cases, static approaches often require costly pre-computation, and their heuristics may not generalize well across architectures or datasets, particularly at ImageNet scale.
Dynamic Data Pruning. Dynamic methods instead make pruming decisions adaptively during train- ing by leveraging information from the evolving model state. Early efforts such ActiveBias (Chang et al., 2017) adjusted sampling probabilities based on prediction confidence, while forgetting- based measures (Toneva al., 2018) revealed that unstable or frequently forgotten examples often provide valuable signal. Raju et al. (Raju et al., 2021) introduced exploration-based policies such as e-greedy and UCB, where uncertainty estimates guide the retention of high-value samples. Recent work has also examined improving random sampling policies themselves: Okanovic et al. (Okanovic et al., 2024) showed that repeated random sampling can significantly reduce time-to-acoen --ccuurcc,, offering complementary perspective to loss-based dynamic pruning approaches such as InfoBatch and OrderDP. More recently, InfoBatch (Qin al., 2024) proposed an unbiased gradient estimator, showing that loss-based pruning can accelerate training without compromising accuracy on bench- marks like CIFAR-10/100 and ImageNet- IK. Building on this line of research, Yang et al. (Yang et al., 2022) and Sorscher et al. (Sorscher et al., 2022) extended dynamic pruning principles to large-scale pretraining, while He et al. (He et al., 2024) incorporated dynamically updated uncertainty estimates. In particular, Sorscher et al. (Sorscher al., 2022) demonstrated that the optimal choice between hard and easy samples can depend on dataset scale, an observation that is complementary to the top-g strategy analyzed in this work. Despite these advances, dynamic methods still face challenges: the
20

---

Published as a conference paper at ICLR 2026
achievable "lossless" pruning ratio datasets is unpredictable, sorting operations can become expensive at scale, and empirical instability often emerges under aggressive pruning ratios. Ayed and Hayou (Ayed & Hayou, 2023) further analyze the fundamental bias of score-based pruning and show that reweighting can recover unbiasedness with respect to the original loss. Their perspec- tive is complementary ours: while they study limitations under I,, provide guarantees for lanking-induced surrogate Lg whose gap to L is explicitly controlled.
Cross-domain Data Selection and Pruning. Beyond computer vision, pruning and selection strategies have been expanded to other domains such as NLP and speech. In speech recognition, unsupervised data selection has been explored through discrete speech units (Lu et al., 2022). For lcrge-scale NLP pretraining, several studies investigate pruning and mixture optimization to accelerate convergence. (Marion al., 2023) explored pruning strategies for pretraining corpora, while (Xie et al., 2023) introduced DoReMi, a framework that dynamically optimizes data mixtures for faster language model pretraining. Instruction tuning has further motivated task task-specifie pruning, exemplified by (Cao al., 2023), who proposed instruction mining to select relevant subsets for downstream tasks. These works highlight that pruning is not limited to vision but constitutes broader principle of efficient data utilization across modalities.
C EXPERIMENTAL INFRASTRUCTURES
Software infrastructures. All experiments are implemented in Python 3.12.4 using PyTorch 2.3.1 1 with CUDA 11.8 support. Key libraries include NumPy 1.26.4, pandas 2.2.3, torchvision 0.18.1, matplotlib 3. 1, and scikit-learn 1.6.1 for data processing and analysis. We also employ accelerate 1.6.0 for multi-GPU training and tqdm 4.67.1 for progress visualization.
Hardware infrastructures. We conduct all experiments on a computer server with NVIDIA L40 GPUs (with 48GB memory each), single Intel Xeon Gold 6448Y CPU (32 physical cores), and 944 GiB of system RAM.
D ADDITIONAL EMPIRICAL RESULTS
D.1 EXPERIMENTAL SETUP DETAILS
We provide software/hardware infrastructures in Appendix C; here detail dataset-specifie training setups throughout this paper.
CIFAR-10/106 The CIFAR-10/100 experiment with R can be reproduced with SGD using maximum learning rate of 0.2 for the OneCycle scheduler under a batch size of 128. For experiments with ResNet-50, SGD is used with a maximum learning rate of 0.03 and batch size of 128 for baseline, InfoBatch, and OrderDP.
ImageNet-1K: The tests are implemented based on Pytorch/ examples, The LARS optimizer and maximum learning rate of 6.4 / 1.98 are used for batch size 1024 on ImageNet-IK experiments with ResNet-50/18.
D.2 VALIDATION OF THEORETICAL PROPERTIES
Both Figure 5 and Figure 6 illustrate theoretical properties derived in Appendix A. Figure 5 empirically validates Proposition by fixing (s, q) = (100, 30) and increasing n, showing how n ni converges to 7(2) n, and increase. Figure 6 illustrates Theorem by comparing % uniform sampling for different q (fix (n, s) = (200, 100) and increase q - 100), highlighting that the gap between the two distributions vanishes (i.e., (8; q) and C, approach 0) q increases.
In addition to the above validations, we further examine the normalization behavior of the weights {yy} } derived in Eq. (10). Although providing fully symbolic proof for the combinatorial form of 7 is algebraically involved, the construction of Algorithm implics that exactly q samples are selected
at each iteration, suggesting that Σラ=1 "i should be close g, and therefore ΣØ=1 73/9 / R 1.
21

---

Published as a conference paper at ICLR 2026
6:2
Figure Empirical weight decay curves n "i versus normalized index j/n, demonstrating con- vergence to the limiting density 7(2) and the smoothing of the "cliff" as increases.
Figure 6: Comparison of the sampling weights " against uniform sampling for different ex- ploitation sizes q, illustrating the deviation cap- tured by the bias term C. in Theorem 4.
Figure plots the normalized distributions 73/4 for different values of (with (n, 8) (400, 100)). As increases, the curves gradually flatten and approach the uniform distribution, consistent with Theorem 4.
Figure 8 further shows the empirical values of Σi 7//9 across & E {10, 20,.... 1003, all which lie extremely close to 1 (within soating-poim error). This provides strong numerical evidence that the weights induced by Algorithm 1 are properly normalized in practice.
Proof. We also provide proof of the claim Σy=1 7//9 = 1 via Mathematical Induction.
For any n, 8, when g = 1, we can show exactly that
Σ
2/4
1.
Suppose E, 93/9- for any 9 = m where m N and 1 S m S s 1, we show E for q = + 1. The case q be rewritten
min mm
Σ m J
Σ
Thus for the case q = + 1, we have
Σ 71 1 min mi
Σ
j q
m ===ax(1+-ntt
min (m.))
(zm)) (
m
+
J
I=max (1a-n++))))
n- ++t+++1
n-j
s-m--1)
m +
m +
1=
where the last equality follows that (2-1)
0 for m 11ssjsn - m + else The
1-m--
remain proof is to show Σi-str
-
Consider selecting a subset of size from the set {1, 21.2..... n). Arrange the elements the subset in increasing order: 01 2 ag i.e. the (m + 1)-th largest element is at position j.
a, Then am+1 is the (m 1)-th largest element. Let m
To construct such subset, the following conditions must be satisfied:
22

---

Published as a conference paper at ICLR 2026
daliiuttio with 40C,
Z/m
2751 199
Figure 7: Normalized distributions 7//9 for dif-
Figure 8: Empirical normalization of
ferent 9 under (n, s) = (400, 100). As q in- creases, the curves flatten and approach the uni- form distribution.
2j=1 tg/g. Across all E {10..... ... 100). the values remain extremely close to
Choose m elements from the first elements (i.e., ..,.... Om), which can be done in (3m") choices.
Choose s - m elements from the remaining n - elements (i.e., am+2..... ag), which can be done a-j ) choices.
Thus, the number of subsets where the 1-th largest element exactly at position is: (.-²
Summing j from m 1 to n --8 8 + m + to ensure enough elements remain), we obtain the total number of subsets size s: E) > 12=1) ()-=L) (3),
+ 1 (since j must be at least m and at most
Therefore, the original claim holds for all q: 3//9/
D.3 VALIDATION OF CONVERGENCE ASSUMPTIONS
To further support the validity of Theorem 3, we analyze whether the selected coreset stabilizes during training. Although the selection depends on sampling scores H, which may vary across epochs, our analysis shows that the coreset indeed becomes stable later stages training.
Coreset Dynamics. Our analysis does not assume fixed coreset. Instead, OrderDP naturally determines the coreset through the pruning strategy (captured by Yy in Proposition 2), where the sample 2, E coreset follows approximate Beta-distribution.
Thcoretical Parallel to SGD. The applicability of Theorem is analogous to SGD's convergence guarantees: (i) SGD converges by deterministic batches per epoch (the sample 2j selected follows uniform sampling): (ii) OrderDP achieves convergence after the coreset stabilizes (via Beta-distributed sampling).
To empirically verify this stabilization, we measure the Jaccard Similarity between the coreset at the current epoch and that from the immediately preceding epoch, defined as
IAnB
J B)
(40)
AUU
A higher similarity indicates that the selected set of samples remains consistent across epochs. Table 8 shows that OrderDP consistently achieves higher coreset stability than InfoBatch, confirming the practical applicability of Theorem 3.
D.4 SAMPLE COVERAGE UNDER DIFFERENT PRUNING RATIOS
To further examine the exploration behavior of OrderDP, we track for each training sample the number of times it is selected into the update throughout the entire training process. Figures 9, 10,
23

---

Published as a conference paper at ICLR 2026
Table 8: Jaccard Similarity between consecutive checkpoints on CIFAR-I00 with ResNet-18. In-
foBatch and OrderDP are trained for 200 epochs (checkpoints at 20%, 40% 60%, 80%, and final 100%). with learning rate 0.03 and batch size 128. Each setting repeated times, and mean = std are reported. Higher values indicate greater stability of the coreset.
Prune Ratio
Method
0-20%
20-40%
40-60%
60-80%
80-100%
100%
InfoBatch
0.583
0.49611.0010
0.479:10.003
0.48110.0066
0.512:10.010
0.522:10.007
40%
OrderDP
0.645=0.057
0.692-1.023
0.713:1.008
0.74310.023
0.75710.034
0.767:10.008
InfoBatch
0.593 0.012
0.532.10.024
0.459.1..019
0.40311.0188
0.512.10.012 0.4051
70%
OrderDP
0.552=0.049
0.592
0.647-10.020
0.66110.018
0.678-1.023
0.704:10.090
aage
Liage Stant
Clurd
Figure 9: Sample usage count distribution (30% prune ratio).
Figure 10: Sample usage count distribution (50% prune ratio).
and 11 show the empirical distributions of sample usage counts on CIFAR-10 under prune ratios of 30%, 50%, and 99%, respectively.
Across all pruning ratios, we observe that sample has zero usage count: every example is selected at least once during training. Under practical pruning settings (e.g., 30%-50%), most samples fall within a reasonably concentrated range of usage counts, indicating that OrderDP does not permanently discard any data point but instead explores the entire dataset with a frequency controlled by (s,
These empirical findings are fully consistent with our theoretical analysis of coverage and directly support response to reviewer questions regarding whether OrderDP eventually the entire dataset.
D.5 TIME-TO-ACCURACY CURVES
To complement the wall-clock results in Figure and to directly address the reviewer's suggestion evaluating time-to-accuracy. we report curves showing the relationship between training time and accuracy. These curves provide a practical view of how fast different methods reach comparable accuracy levels in real training scenarios.
Figures 12 and 13 present the Time-to-Accuracy curves on CIFAR-10 using ResNet-18 under prune our findings throughout the paper. OrderDP achieves faster accuracy improvement and maintains stable convergence compared with both InfoBatch and Random, especially under higher pruning levels.
ratios of 40% and 70%. Consistent with
D.6 STABILITY ANALYSIS
We further include stability study of dynamic pruning methods under multiple independent runs. In this analysis, we evaluate CIFAR-100 with ResNet-18 at 70% real pruning ratio across 10 runs. InfoBatch often exhibits large mid-training gradient oscillations and occasional convergence failures, while OrderDP consistently converges smoothly in every trial. Moreover, InfoBatch relies on late-stage full-data "annealing" to stabilize training, whereas OrderDP maintains exact pruning control via (s, q) without requiring such rescue. This highlights the robustness and practicality of our approach. Under aggressive pruning, InfoBatch's 'ss rescaling further causes severe fluctuations in both gradient and accuracy.
24

---

Published as a conference paper at ICLR 2026
Ordyr Sengle Usage iPrund Mato 99%)
Sarpl Usags Coun.
Figure 11: Sample usage count distribution under 99% prune ratio. Even under extreme pruning, every sample is selected at least once.
OPARTO Tew---AAoaac (Trune
CPAR TreeSAADORN DCU ('inn Tadoo
Figure 12: Time-to- Come-to-Accuracy on CIFAR-10 at 40% prune ratio.
Figure 13: Time-to-Accurase on CIFAR- at 70% prune ratio.
Detailed results are summarized in Table 9 (real prune ratio 0.61, InfoBatch nominal prune ratio A 0.99; 200 epochs; learning rate 0.03; batch size = 128; averaged over 10 runs).
E EXTENDED ANALYSIS OF GRADIENT BIAS
E. MECHANISMS AND Toy EXAMPLE
This subsection provides additional clarification on how OrderDP eliminates biased gradient estima- tion. The method addresses the issue through three main mechanisms. Uniform exploration. Before pruning, & points are randomly sampled so that every sample, regardless of gradient magnitude, has equal probability of entering the coreset. This ensures the gradient distribution is much closer that of full-data SGD compared with InfoBatch's 's biased rescaling strategy. Unbiased surrogate loss. Instead of pruning the original loss directly, new loss Cg constructed with dosed-form weights Yj derived from two-stage sampler. Theorem 1 guarantees each update is unbiased estimator of (O,, while Theorems 2, 3, and 4 provide convergence and generalization guarantees, avoiding the need for late-stage full-data annealing. Exact pruning control. By explicitly setting (s, q). any target prune ratio (e.g., 70%, 80%, 90%) can be realized precisely, unlike InfoBatch's mean-threshold scheme, which fluctuates around 77%.
To make the difference clear, we present a toy comparison under an 80% prune ratio with samples of gradients g {1, 3, 4, 5). In InfoBatch thran-threshold + rescale), samples 3, 4, 5 are always kept, while and are included with probability 0.2, and their gradients rescaled by factor 1/(1 0.8) = 5. This leads four possible outcomes summarized in Table 10.
From Table 10, the expected gradient estimate is 4.336 with prune ratio < 0.8, indicating bias.
In contrast, for OrderDP (5 samples, 80% prune), randomly sample batch with size (1....,5) 55 and select the top-1 element. The detailed probability calculation for each index as follows:
25

---

Published as a conference paper at ICLR 2026
Table 9: Stability comparison on CIFAR-I00 with ResNet-50 across 10 runs under varying training progress (percentage of epochs). Reported are Accuracy (% = Std) and Gradient Std. OrderDP shows smoother convergence and eliminates instability observed InfoBatch.
Method
Metric
0-30%
30-50%
50-70%
70-100%
Final
Acc + Std
48.01 +: 4,60
49.77 +: 2.54
52.61 1.42
66.24 + 1.23
74.77 + 0.30
e-Greedy
Grad + Sud
3.08 + 1.19
3.49 0.62
2.78 + 0.57
2.05 + 0.45
1.53 = 0.37
Acc + Std
49.70 4.80
50.66 + 2.31
54.34 1.82
67.97 1.12
75.41 + 0.40
UCB
Grad
4.08 +:
3.69 1.02
2.99 0.27
2.35 + 0.38
1.33 =
Acc + Std
45.74 + 3.56
52.08 + 2.55
47.72 + 3.63
68.92 + 3.01
76.72 = 0.70
InfoBatch
Grad + Std
7.35 + 1.78
5.88 + 1.24
4.35 + 9.48
3.56 + 4.55
2.89 1.67
Acc + Std
48.00 + 3.23
56.00 + 2.01
61.00 1.34
72.00 + 0.56
78.32 = 0.20
OrderDP
Grad + Std
4.08 + 1.19
3.49 0.62
2.78 + 0.47
2.05 + 0.55
1.03 0.33
Acc + Std
56.58 1.56
62.36 + 0.76
66.84
0.52
72.24 0.40
80.60 + 0.20
Whole Dataset
Grad Std
3.88 + 0.79
3.09 0.41
2.45 1 0.42
1.93 + 0.55
0.88
Table 10: Toy example of InfoBatch under an 80% prune ratio with 5 gradients. The table shows the kept set, probability of selection, rescaled gradients, average gradient, and prune rate.
Kept set
Probability
Gradients
Avg. grad.
Prune rate
[3, 4, 5]
0.64
3,4,5
4.0
0.60
[1, 3, 4,5)
0.16
3,3,,
4.25
0,20
[2, 3, 4,5)
0.16
5 5.2,3,4,5-10,,3
5.5
0.20
1,2,3,4,55
0.04
5 5.1,5.2,3,433 3,
5.4
0.00
(1): : (s 1)
(2): 3 (==11 1) + ( (s= 50
(3): ; : (s= 1) + 10 1 (s= 2) (s= 25'
(4): f (==1) + 3/ ( 2) 3
(s= + ()=
{5) 3. (s 1) + (s= 2)
(s 3) + (8= 4) + (s=
The expected gradient estimate under this distribution 4.06 with prune ratio exactly 0.8. Therefore, OrderDP not only maintains the target pruning ratio precisely but also achieves gradient estimates closer to the true full gradient (= 3), effectively eliminating the bias observed InfoBatch.
E.2 GRADIENT DIRECTION ANALYSIS
In addition to gradient magnitude analysis, also examine gradient directions by measuring the cosine similarity between the gradients computed with each pruning method and the full-data gradient matched checkpoints (same model weights). We train on CIFAR- 100 with ResNet-18 for 200 epochs, evaluate at 20%, 40%, 60%, 80%, and 100% of training progress, using a learning rate of 0.03 and batch size of 128. Each setting repeated times, and we report mean std. Results under pruning ratios 40% and 70% are summarized in Table 11.
These results demonstrate that OrderDP's gradients align more closely with full-data gradients, particularly at high pruning ratios, thereby reducing directional bias compared with InfoBatch.
F LIMITATIONS AND FUTURE WORK
While OrderDP excels moderate-scale vision benchmarks, its performance very large ar- chitectures, streaming inference scenarios, and heterogeneous hardware platforms, as well as in self-supervised multi-modal settings. remains to be explored. In future work, will extend OrderDP to adaptive pruning schedules, investigate its integration with transformer and graph models, and study its behavior under distribution shift and noisy labels.
26

---

Published as a conference paper at ICLR 2026
Table 11: Cosine similarity between pruned and full-data gradients on CIFAR-100 (ResNet-18) under pruning ratios 40% and 70%. Each experiment is repeated 5 times, and mean + std are reported. Higher values indicate stronger alignment with full-data gradients.
Prune Ratio
Method
0-20%
20-40%
40-60%
60-80%
80-100%
100%
InfoBatch
0.915=0.044
0.940=00.008
0,916+0.0077
0.904=0.011
0.897++0.008
0.895++0.009
40%
OrderDP
0.943
0.951=00.00
0.904
0.921 0.009
0.908:10.014
0.906:1.0011
InfoBatch
0.825=0.037
0.807=00.027
0.763++:0.02
0.758=0.002
0.743:1:0006
0.716:+0.022
70%
OrderDP
0.853 0.004
0.896
0.901+000015
0.014
0.868 0.021
0.844400018
Another promising direction is to develop noise-robust variants of OrderDP. Although the current work focuses the top-q strategy, the surrogate-los framework introduced in this paper is more general and can naturally incorporate min-q selection or mixed hard/easy sampling schemes by modifying the weight structure {7₂)- Such extensions may help suppress extreme outliers, improve stability under label noise, and adapt the pruning strategy across different stages of training (c.g.. hard-sample emphasis in early stages and easy-sample regularization in later stages). We plan to further explore these variants and evaluate their performance in noisy or adversarial settings.
G
THE USE OF LARGE LANGUAGE MODELS (LLMs)
Large language models (LLMS) were used solely for linguistic refinement and editing of the manuseript. All scientific ideas, methodological contributions, and experimental results are en- tirely conceived, implemented, and validated by the authors.
27


Reviews:
[{"review_id": "GqzAuEVUtR", "reviewer": "Reviewer_S9Z2", "summary": "The paper proposes a dynamic data pruning framework, termed OrderedDP, to speed up the model training process by reducing the number of samples needed for each epoch. The author proposes to use the loss to measure the importance of the data sample together with a ranking method, where a larger loss indicates a higher demand for retention. The experiments were conducted on CIFAR-10/100 and ImageNet-1k using ResNet-50 as the model backbone. The authors have done some analysis on the generalization of the proposed method.", "questions": "Please refer to the weakness session.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The motivation of the paper is well justified. Also, the authors try to give some theoretical analysis of the proposed method to justify its generalization capability.\n\n2. The paper is properly written and it is not hard to follow the paper's story.", "weaknesses": "1. The selected backbone is not strong enough. The reproduced accuracy of the ResNet-50 backbone is lower than the model trained with a stronger training recipe and data augmentation strategy. Actually, it is important to justify that the proposed method is compatible with state-of-the-art training recipes. It is not clear if the \"unimportant samples\" are indeed not that important with a stronger data augmentation strategy and learning schedule.\n\n2. The experiments are only verified on classification tasks. It is unclear whether the proposed method can be applied to other tasks, such as segmentation, detection, or generative tasks.\n\n3. The method is only verified on CNN-based networks (ResNet-18/50), which typically show faster convergence speed over transformer-based models. It is also not clear how the proposed method performs on transformer-based model architectures.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KdsgoCnm4k", "reviewer": "Reviewer_TnEE", "summary": "This paper presents OrderDP, a novel framework for dynamic data pruning aimed at addressing the biased gradients and training instability inherent in existing methods. The core idea is a two-stage selection process: uniformly sampling a candidate pool, then selecting the top-q highest-loss examples for the gradient update. The key innovation is theoretical: rather than fixing the bias for the original objective, the authors introduce a surrogate loss function and prove that their method provides an unbiased gradient estimate for this new objective. This allows them to establish formal convergence and generalization guarantees. Empirically, OrderDP demonstrates superior performance and stability on CIFAR and ImageNet benchmarks, achieving significant training speed-ups with minimal to no accuracy loss.", "questions": "1. Can the authors clarify how minimizing the surrogate loss $L_q(\\theta)$ reliably approximates minimizing the original objective $L(\\theta)$? Are there empirical results or theoretical analyses demonstrating when this approximation may fail?\n\n2. Would the authors consider explicitly discussing the methodological shift from bias correction for $L(\\theta)$ to optimization under $L_q(\\theta)$, and how this affects the paper’s claimed contributions?\n\n3. Regarding the ``loss-less'' claim, could the authors specify the exact pruning conditions under which this property holds, and whether ``near-loss-less'' might be a more accurate description?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1.\tThe paper introduces a novel two-stage sampling method that combines uniform random sampling for exploration with a top-q, high-loss selection for exploitation. This straightforward design effectively balances the need for data diversity with the selection of informative samples and is simple to integrate into existing training pipelines.\n\n2.\tTheoretical Analysis The work is supported by a relatively thorough theoretical analysis, which is a key differentiator from many heuristic-based approaches. By introducing a surrogate loss function, the authors reframe the biased pruning problem into an unbiased optimization of a new objective. This allows them to establish formal convergence rates and generalization bounds.", "weaknesses": "Major concern: \n1.\tThe authors motivate their work by highlighting the critical issue of biased gradient estimation in existing dynamic data pruning methods, where the bias is defined with respect to the full-dataset empirical risk, L(θ). However, the proposed OrderDP method does not directly yield an unbiased estimator for the gradient of L(θ). Instead, it cleverly reframes the problem by introducing a surrogate loss, L_q(θ), for which the computed gradient is indeed an unbiased estimator.This constitutes a subtle but significant mismatch between the initial problem formulation and the solution. The central premise of the paper shifts from 'fixing the bias for the original objective' to 'optimizing a different, tractable objective'. The validity of this entire approach hinges on the crucial assumption that minimizing L_q(θ) is a sufficiently good proxy for minimizing L(θ).While the authors attempt to bridge this gap through the generalization analysis in Theorem 4, which bounds the bias between the two objectives, the paper would be strengthened by a more direct discussion of this methodological pivot.\n\n2.\tThe authors make a strong claim of achieving 'loss-less' performance, which is central to the paper's positioning. The empirical results, however, suggest that this claim holds under specific, moderate pruning ratios (e.g., 30% on CIFAR-10) but not universally across more aggressive pruning settings. This discrepancy between the strong, general claim and the nuanced, conditional results could be misleading. The authors should consider refining their claim to be more precise, perhaps by using terminology like 'near-loss-less' or by explicitly stating the conditions under which true 'loss-less' performance is achieved. This would align the paper's claims more accurately with its empirical evidence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1ebTPmcNpy", "reviewer": "Reviewer_fvbi", "summary": "This paper presents OrderDP, a dynamic data pruning framework that reduces training costs by selectively using informative samples during neural network training. Unlike previous approaches that address gradient bias through importance reweighting (which increases variance and gradient norms), OrderDP takes a different strategy: rather than seeking unbiased estimates of the original loss, it defines a surrogate loss function for which the method provides provably unbiased gradient estimates. Experiments on CIFAR and ImageNet datasets show OrderDP achieves competitive accuracy specially in the challenging high compression regime. The authors also provide theoretical guaranties for convergence and generalisation.", "questions": "- The algorithm is described for the general (random) mini-batch SGD setting used in the theoretical analysis. However, it is not clear how this translates to the empirical training setup, where batches are predefined, and the model cycles through them rather than resampling. Is the “exploration” and “exploitation” sampling and selection performed within each batch ?\n- A related question concerns the definition of the compression ratio $r = 1 - q/n$, which depends only on $q$ and makes sense for the mini-batch SGD setting. In the empirical setup, however, this seems to differ. For instance, lines 407–408 and Section 5.3 suggest that $r$ depends on both $q$ and $s$.\n* On lines 316–317, $s$ and $q$ are defined as fractions (0.5 and 0.6) rather than integers as in the rest of the paper. What exactly are these fractions referring to, and why is $q$ larger than $s$ ?\n\nMinor:\n- Lines 240–241: Could the authors provide a proof that the (\\gamma_j) sum to 1? This would be preferable to empirical validation alone.\n- Regarding the statement that “the analysis of the bias and its impact on the final performance remains ambiguous,” it may be useful to consider [1], which provides such an analysis and first proposes a reweighting-based exploration–exploitation correction (to my knowledge).", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall I found this to be an interesting work that addresses the gradient bias induced by data pruning from a different and, to my knowledge, novel angle. The empirical results indicate strong performance of this methodology compared to an extensive list of competing methods, especially in the challenging high compression regime. The theoretical analysis brings interesting guarantees and is an appreciated plus to the methodology.", "weaknesses": "- I find the title somewhat overstated. From my understanding, the theoretical results do not establish that OrderDP is a guaranteed lossless framework. I would interpret such a statement as $\\mathcal{L}(\\theta^\\star_{unpruned})-\\mathcal{L}(\\theta^\\star_{pruned})$ converging to 0 with $n$ for all pruning ratios $r$, which can be proved for unbiased pruning methods using reweighting, for example (see [1]). Such a result would be interesting to include in this framework as well, if it holds.\n\n- OrderDP is presented as a plug-and-play framework, which could be understood as being applicable to any base data scoring method, but the paper only deals with one specific score based on the loss function.\n\n[1] Ayed, Fadhel, and Soufiane Hayou. Data pruning and neural scaling laws: fundamental limitations of score-based algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aowo833AXY", "reviewer": "Reviewer_umfZ", "summary": "The paper proposes OrderDP, a method for dynamic data pruning. OrderDP first randomly selects a subset, and then chooses top-q samples based on the loss function value. Paper shows convergence and generalization bounds for OrderDP. OrderDP outperforms other static and dynamic baselines in terms of accuracy for CIFAR10/100, and ImageNet.", "questions": "1. Does OrderDP end up seeing the entire dataset (since there is a uniform sampling at random s samples)? If yes, could you clarify how long it takes to see the entire dataset depending on the pruning ratio? \n\n2. [1] have shown that depending on the size of the dataset one should keep either hard or easy examples. Does this finding hold also for OrderDP? Is there a pruning ratio at which one should sample min-q scores?\n\n3. Could you clarify how you implement dynamic random? For example, [2] shows that a simple modification of the random baseline can further improve its results. Furthermore, how does your convergence and generalization bound compare to [2]?\n\n4. The paper does a good job in showing the practicality of OrderDP by showing end-to-end wall clock time, and the convergence analysis. However, I believe it could further strengthen the paper to plot its time-to-accuracy, that is, accuracy on the y-axis and wall-clock time on the x-axis.\n\n5. How does OrderDP perform in situations with noisy labels, could you elaborate whether sorting by top-q could be misleading or not in that scenario? \n\nI look forward to the responses from the author(s) and would reconsider my score based on the clarifications and revisions provided. Thanks.\n\n[1] Sorscher, Ben, et al. \"Beyond neural scaling laws: beating power law scaling via data pruning.\" Advances in Neural Information Processing Systems 35 (2022): 19523-19536.\n\n[2] Okanovic, Patrik, et al. \"Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learning.\" The Twelfth International Conference on Learning Representations.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written.\n- OrderDP provides both bias and convergence analysis, as well as a generalization error bound.\n- OrderDP outperforms both static and dynamic pruning methods across all settings.\n- Additionally, paper also shows the method works with different optimizers.", "weaknesses": "Clarity: \n- I believe it could benefit the paper if the authors were more clear when writing things like “near-lossless”, for example, do they consider near-lossless when the relative accuracy drop is within 1% or something different?\n- I also believe it could benefit the paper to clarify sooner that OrderDP can work with various optimizers.\n\nFor further questions and weaknesses see Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)