DynaMS: Dyanmic Margin Selection for Efficient Deep Learning
Authors: Jiaxing Wang
Yong Li
Jingwei Zhuo
Xupeng Shi
WEIZHONG ZHANG
Lixing Gong
Tong Tao
Pengzhang Liu
Yongjun Bao
Weipeng Yan
Venue: ICLR 2023 poster (2023)
Keywords: efficient training
data selection

Abstract: The great success of deep learning is largely driven by training over-parameterized models on massive datasets. To avoid excessive computation, extracting and training only on the most informative subset is drawing increasing attention. Nevertheless, it is still an open question how to select such a subset on which the model trained generalizes on par with the full data. In this paper, we propose dynamic margin selection (DynaMS). DynaMS leverages the distance from candidate samples to the classification boundary to construct the subset, and the subset is dynamically updated during model training. We show that DynaMS converges with large probability, and for the first time show both in theory and practice that dynamically updating the subset can result in better generalization over previous works. To reduce the additional computation incurred by the selection, a light parameter sharing proxy (PSP) is designed. PSP is able to faithfully evaluate instances with respect to the current model, which is necessary for dynamic selection. Extensive analysis and experiments demonstrate the superiority of the proposed approach in data selection against many state-of-the-art counterparts on benchmark datasets.

Published as a conference paper at ICLR 2023
DYNAMS: DYANMIC MARGIN SELECTION FOR EFFI- CIENT DEEP LEARNING
Jiaxing Wang', Yong Li Jingwei Zhuo', .upeeng Shi", Weizhong Zhang? Lixing Gong", Tong Tao', Pengzhang Liu', Yongjun Bao', Weipeng Yan
JJD.com NNotheesstern University FFudan University
[vangjlaxxing41111yyoggg oog.:/nggg...iggngggeei.....gog.
) @jd. com
(taotong, Liupengzhang y com
shi wwwpenortthesteer..cce. 2tann
ABSTRACT
The great success of deep learning is largely driven by training over-parameterrzed models on massive datasets. To avoid excessive computation, extracting and training only on the most informative subset is drawing increasing attention. Nev- ertheless, it is still an open question how to select such a subset on which the model trained generalizes on par with the full data. In this paper, we propose dy- namic margin selection (DynaMS). DynaMS leverages the distance from candidate samples to the classification boundary construct the subset, and the subset is dynamically updated during model training. We show that DynaMS converges with large probability, and for the first time show both in theory and practice that dynamically updating the subset can result in better generalization. To reduce the additional computation incurred by the selection, a light parameter sharing proxy (PSP) is designed. PSP is able to faithfully evaluate instances following the underlying model, which is necessary for dynamic selection. Extensive analysis and experiments demonstrate the superiority of the proposed approach in data selection against many state-of-the-art counterparts on benchmark datasets.
INTRODUCTION
Deep learning has achieved great success owing in part the availability of huge amounts of data. Learning with such massive data, however, requires clusters of GPUs, special accelerators, and excessive training time. Recent works suggest that climinating non-essential data presents promising opportunities for efficiency. It is found that small portion of training samples contributes majority of the loss (Katharopoulos Fleuret, 2018 Diang et al., (211)), so redundant samples can be left out without sacrificing much performance. Besides, the power law nature (Hestness et al.) [017]] Kaplan cet al., 2020) model performance with respect to the data volume indicates that loss incurred by data selection can be tiny when the dataset is sufficiently large. In this sense, selecting only the most informative samples can result in better trade-off between efficiency and accuracy.
The first and foremost question for data selection is about the selection strategy. That is, how to efficiently pick training instances that benefit model training most. Various principles have been proposed, including picking samples that ineur larger loss gradient norm (Paul al. 2021 Coleman et al. 2020), selecting those most likely to be forgotten during training, as well as util liiiiin subsets that best approximate the full loss (Feldman 2020 or gradient (Mirzasoleiman al. 2020 Killamsetty et al. 2021). Aside from selection strategies, existing approaches vary in the training schemes which can be divided roughly into two categories: static ones and dynamic (or adaptive) ones. Static methods (Paul et al. [202 Coleman et al. 2020. Toneva et al., 2019) decouple the subset selection and the model training, where the subset is constructed ahead and the model trained on such a fixed subset. Dynamic methods (Mindermann et al. 2022 Killamsetty et al., 202T). however, update the subset in conjunction with the training process. Though effectively eliminates amounts of samples, it is still not well understood how these different training schemes influence the final model.
"Corresponding author
Wee use the terms data, sample, and instance interchangeably

---

Published as a conference paper at ICLR 2023
In this paper, we propose dynamic margin selection (DynaMS). For the selection strategy, we inquire the classification margin, namely, the distance to the decision boundary. Intuitively, samples close to the decision boundary influence more and are thus selected. Classification margin explicitly utilizes the observation that the decision boundary is mainly determined by a subset of the data. For the training scheme, show the subset that benefits training most varies the model evolves during training, static selection paradigm may be sub-optimal, thus dynamic selection is a better choice. Synergistically integrating classification margin selection and dynamic training, DynaMS is able to converge to the optimal solution with large probability. Moreover, DynaMS admits theoretical generalization analysis. Through the lens of generalization analysis, we show that by catching the training dynamics and progressively improving the subset selected, DynaMS enjoys better generalization compared to its static counterpart.
Though training on subsets greatly reduces the training computaiton, the overhead introduced by data evaluation undermines its significance. Previous works resort to a lighter proxy model. Utilizing separate proxy (Coleman et al. 2020), however, is insufficient for dynamic selection, where the proxy is supposed to be able to agilely adapt to model changes. We thus propose parameter sharing proxy (PSP), where the proxy is constructed by multiplexing part of the underlying model parameters. As parameters are shared all along training, the proxy can acutely keep up with the underlying model. To train the shared network, we utilize slimmable training (Yu al. 2019) with which well-performing PSP and the underlying model can be obtained in just one single train. PSP is especially demanding for extremely large-scale, hard problems. For massive training data, screening informative subset with a light proxy can be much more efficient. For hard problems where model evolves rapidly, PSP timely updates the informative subset, maximally retaining the model utility,
Extensive experiments are conducted on benchmarks CIFAR-IO and ImageNet. The results show that our proposed DynaMS effectively pick informative subsets, outperforming a number of competitive baselines. Note that though primarily designed for supervised learning tasks, DynaMS is widely applicable as classifiers have become an integral part of many applications including foundation model training (Devlin et al., 2019 Brown et al.) 2020 Dosovitskiy et al., 2021 where hundreds of millions of data are consumed.
Chen et al. 2020).
In summary, the contributions of this paper are three-folds:
We establish dynamic margin select (DynaMS), which selects informative subset dynam- ically according the classification margin to accelerate the training process. DynaMS converges to its optimal solution with large probability and enjoys better generalization.
We explore constructing a proxy by multiplexing the underlying model parameters. The resulting efficient PSP is able to agilely keep up with the model all along the training, thus fulfill the requirement of dynamic selection.
Extensive experiments and ablation studies demonstrate the effectiveness of DynaMS and its superiority set of competitive data selection methods.
2 METHODOLOGY
To accelerate training, we propose dynamic margin selection (DynaMS) whose framework is presented in Figure [T] Instances closest to the classification decision boundary are selected for training, and the resulting strategy is named margin selection (MS). We show that the most informative subset changes as the learning proceeds, so that a dynamic selection scheme that progressively improves the subset can result in better generalization. Considering the computational overhead incurred by selection, we then explore parameter sharing proxy (PSP), which utilizes a much lighter proxy model to evaluate samples. PSP able to faithfully keep up with the underlying model in the dynamics selection scheme. The notations used in this paper are summarized in Appendix
2.1 SELECTION WITH CLASSIFICATION MARGIN
Given a large training set T = fx, ya | data selection extracts the most informative subset SC T trained which the model f(z) yields minimal performance degradation. Towards this end, we utilize the classification margin, that is, the distance to the decision boundary, to evaluate the informativeness of each sample. |S] examples with the smallest classification margin are selected.
2

---

Published as a conference paper at ICLR 2023
Learner
Cp
Cp
Selection
Selection
Train for Q epochs
Train for epochs
Figure The overall framework of dynamic margin select with parameter sharing proxy (Dy- naMS+PSP). The green model indicates the underlying model to be trained and the blue one the parameter sharing proxy which efficiently evaluates data. Instances are selected every epochs, then the model is trained on the selected subset.
Intuitively, these samples should be influential most to the model decision. Following (Mickisch
al 2020 Emam et al. 2021), the decision boundary between two classes C₁ and C2 {1.... C is
x (x)) Jea J. where fa(x:) is the entry of model output, indicating the probability
of belonging class c. The classification margin is then:
(x min ||01|2
s.t. x E
(I)
which is the minimal perturbation required
form 6 Cz. Directly computing the margin is infeasible for deep neural networks, so scoring is conducted in the feature space instead as in (Emam al., 202T). Typically neural networks applies linear classifier on top of the features (Goodfellow et al. 2016). so the classification margin M(x, c1, C2) can be easily obtained as: (x. C1, C2
h/x)/ [[ W Wazl12- where W E Rdxx is the weight of the linear classifier and h(x)) is the feature æ. this way, the classification margin of labeled The former indicates the distance moving (aryy) to class e while the latter is the distance moving (ær, y) to the nearest class other than y. To keep the subset balanced,
sample (ær, y) along class is M(x, y, c) if * or millayy M(x,, y. ē) if y
evenly pick [S|/C' samples with the smallest classification margin along each class. The resulting strategy is named margin selection (MS), denoted as MS( w. T, (S]). The procedure is detailed in Algorithm in Appendix A.
2.2
DYNAMIC SELECTION
Static
Dynamic
Grdd. Aignnent comig. (pre))
1.0
0.8
PSP Stand alone
0.9
Erre
0.6
0.8
0.1
0.4
0.0
Static Dyna. CIRAR-10 ImageHett
30
0.6 4
10
15
10
0
40
60
80
Selections
1.0
(a) Selection overlap ratio.
(b) Generalization emror.
(c) Gradient aligment.
Figure 2: (a) Overlap ratio of subsets extracted in two consecutive selections. A near 1 overlap ratio means the selection is converged. (b) Generalization of static as well as dynamic data selection according to classification margin. Selection budget Yavg = 60%. (c) The averaged gradient alignment cos(g. g 9proxy) parameter sharing proxy and an stand-alone proxy along model training.
Given the subset selected, model is subsequently trained on S. Conventional static training scheme assumes that the optimal subset converges and is not related to the model training dynamic (Paul) et al. 2021 Coleman et al. 2020). Though effectively eliminate instances, the "converged optimal
Without loss of generality, omit the hias term for notation elarity
3

---

Published as a conference paper at ICLR 2023
subset" assumption may be too strong. To investigate whether the most informative samples vary during training, we plot the overlap ratio of samples selected in two consecutive selections during the training of ResNet models, shown in Figure 2(a) We train for 200 epochs and 120 epochs on CIFAR-10 and ImageNet respectively, and conduct selection every 10 epochs. It can be observed that the overlap ratio is on average 0.83 for CIFAR-10 10 and 0.73 for ImageNet rather than 1.0, meaning that samples that most benefit model training vary as the model evolves. A fixed subset may be outdated after parameter updates, thus yielding sub-optimal results.
We thus resort to a dynamic scheme where data selection is performed after each Q epochs training By selecting in conjunction with training, the informative subset gets updated according to the current model status. For the kth selection, the informative subset Sj is constructed by picking portion *
samples so that [S& = 7hl [T]. The selection ratio "/k: determines the critical margin Kg,, where only samples with classification margin smaller than K& are kept. S₁ will then be used for training Q epochs. In the following, we provide a convergence analysis of DynaMS and show that DynaMS achieves better generalization by constantly improving the selected subset.
Convergence Analysis We now study the conditions for the convergence of training loss achieved by DynaMS. We use logistic regression (LR) to demonstrate and then show the conditions are well satisfied when LR used on top of deep feature extractors. We have the following theorem:
Theorem. Consider logistic regression f(x) 1+c-w with N Gaussian training samples æ (O,, E). Rd. Assume ||l|| D and 2 < Let w be the optimal parameters and X be the largest eigenvalue of the covariance E. For t E {l....T} and constants e >> -V 1,
1. n. >> a, select subset with critical margin H4z (1 + e) log(ST t) and update parameters with learning rate 17 EVT
ON Then with probability least 1
1
min [(wi) -(ww)) DE 1
1 T
Ce, Tite
Ce.CA T9
where E = vdx(1 + ), A.
8
(1+c)² 20
1. Ca,c and CE,C.A are constants depending on E, and
The proof left in Appendix B Theorem 2.2 indicates that dynamically selecting data based on the classification margin is able to converge and achieve the optima w" with large probability. The Gaussian input assumption is overly strong in general, but when the linear classifier is adopted on top of a wide enough feature extractor, the condition is well satisfied because infinitely wide neural network resembles Gaussian process
(Lee et al. 2019 Xiao et al. 2018 de G. Matthews et al.) 2018).
Generalization Analysis Recently, (Sorscher et 2022) developed an analytic theory for data selection. Assume training data I; ~ (O, and there exists an oracle model w. E IRd which generates the labels such that y: = sign (wo a..). Following static selection, when an estimator w used to pick samples that have small classification margin, the generalization error takes the form E(, 7, 0) in the high dimensional limit. a d
[ indicates the abundance of training samples before
shows the closeness of the estimator to the oracle. The full set of self-consistent equations characterizing E(a, 7, 0) is given in Appendix C By solving these equations the generalization error E(xx, 7, 0) can be obtained.
selection; 7 determines the selection budget and = arccos || w.
w Wa
We then extend to the dynamic scheme. For the kth selection, we use the model trained on S as
the estimator Wk. which deviates from oracle by angle 0g = arccos and select samples. The resulting subset S₃ will be used for subsequent training of model Wk++ which will later be used as an estimator at k + 1 to produce S2+1. In this way, generalization of dynamic scheme can be obtained by recurrently solving the equations characterizing E(a, Tkk 0%) with updated keeping ratio 7% and estimator deviation 0g. Note that in each round of selection, samples are picked with replacement, so the abundance of training samples a is kept fixed. The keeping ratio "/k determining the subset size, can be scheduled freely to meet various requirements.
[wa-1 w. 11 to evaluate
w ww
For extremely large dataset case where training can he accomplished within just one few epochs, the selection he performed every Q iterations
4

---

Published as a conference paper at ICLR 2023
We compare the generalization of dynamic selection and its static counterpart in Figure 2(b) We show the landscape of {(; Y; 8) with different y and 9 by solving the generalization equations numerically. = 3.2 is kept fixed, which means the initial training data is abundant; We use static training with 0₂ = 40 and 7 0.6 as control group. To make the comparison fair, we make sure 1 Ex= hisl = Yy. so that the averaged number of samples used in the dynamic scheme equals the subset size used in the static scheme. From (igure[(() we see that in dynamic selection, the estimator gets constantly improved (0,, decreases), so that the subsets get refined and the model achieves better generalization. Discussion on selecting with different a yand given in Appendix D
k
2.3 PARAMETER SHARING PROXY
With dynamic selection, the number of updates is re- duced. However, the computational overhead incurred by data selection undermines its significance, especially when the model is complex and samples are evaluated frequently. Aside from designing efficient selection strategies, previous works explored utilizing a lighter model as proxy to evaluate the instances so that the problem can be ameliorated. Pretrain a separate proxy and evaluate instances prior to model training (Cole man et al. 2020), however, is insufficient for dynamic selection, as static proxy can not eatch the dynam- ics of the underlying model. A proxy that fulfills the requirements of dynamic selection is still absent.
Proxy output channels
Kornel
Proxy channels
Modal input channels
Model output channels
Figure 3: Parameter sharing proxy which is
constructed with part of model parameters.
We thus propose parameter sharing proxy (PSP), where part of the model is used as the proxy. Taking convolutional neural network as an example, for a layer with kernel W E Rexxexxxx xuxi, where ca Co and u are number of input filters, number of output filters and kernel size respectively, the corresponding kernel of proxy is then: W factor. As shown in Figure 3 the proxy kernel is constructed with the first pc; input channels and first pe, output channels. A p times thinner proxy can be obtained by applying p to each layer.
W 1:pe,, I Lipn where E [o, 1] is a slimming
With separate batch normalization for proxy and model, PSP forms a slimmable network YYu et al. (201)), where multiple models of different widths are jointly trained and they all yield good performance. As the parameters are shared, the proxy can acutely keep up with the model change, thus applicable for dynamic selection. We further investigate the gradients alignment of the proxy and the original model through their cosine similarity:
cos(g 9proxy) ) 9 Srrxxy where g VWL 9proxy VwC (W proxy) |gg|22 lig/la"
positive cosine value indicates Irroxy stands the same side with g. thus updates on proxy and the model benefits each other. We compare the gradient alignment of PSP and a stand-alone proxy in Figure 2(c) on ResNet-50. With = 0.5, we see that cos(g. (proxy) for PSP is much larger than the stand-alone proxy. Given the well-aligned gradients, PSP requires fewer training epochs. Overall workflows of DynaMS and DynaMS+PSP is shown in Algorithm [2]add Algorithm of Appendix A PSP is especially advantageous for large and hard problems. When the data is extremely large, training PSP on a small subset is cheaper than evaluating the extremely large training set with the original model, making it much more efficient. When the task is hard and model changes rapidly during training, PSP can timely updates the informative subset, maximally retaining the model utility.
3 RELATED WORK
Accelerating training by eliminating redundant training instances has long been a research focus in academia. This is accomplished by adopting an effective selection strategy and appropriate training scheme. We summarize the related literature from these two strands of research in the following.
Selection Strategy Sample selection can be accomplished with various principles. (Loshchlovy & Hutter 2013] Jiang et al.) 2019 Paul et al. (021) tend to pick samples that incur large loss or gradient norm (CE-loss, EL2N, GraNd). [Toneva et al.] 2019) inspects the "unforgettable"
5

---

Published as a conference paper at ICLR 2023
examples that are rarely misclassified once learned, and believes these samples can be omitted without much performance degrada- tion. Other works adopt uncertainty. Sam- ples with the least prediction confidence preferred (Settles 2010). Recently (Mirza soleiman et al. 2020, Killamsetty et al. 2021) select subset that best covers or ap- proximates the full gradient (Craig, Grad- Match). However, these requires per-sample gradient as well as an additional optimiza- tion which is expensive both in run-time and in memory. Our work utilizes the classifica-
Table I: Computational and space complexity of dif- ferent selection strategies. For GraNd, Craig and Grad- Match, only gradients of the classification layer are considered to avoid overly large complexity.
Strategy
Time Complex.
Space Complex.
CF-loss
O . log [S)
(T)
EL2N
O((C log
O
GraNd
d O((C-d log|S]
O(7)
Craig
O d 17)
O(SI-
GradMatch
O d [7]
O (T)
MS
O (d log (S) I77)
(TC-
tion margin to identify informative samples, which is efficient and can synergistically adapt to various training schemes. Comparison of these strategies is given in Table [T where d is the dimension of data feature. MS is slightly slower than selection via loss (CE-loss and EL2N), but much more efficient than Craig and GradMatch. Here we consider only the complexity of the selection strategy itself, time spent for feature extraction is included. Classification margin has been previously explored in the active learning literature (Ducoffe Precioso 2018 Emam et al. 2021 here we utilize for training acceleration.
Training Schemes Data selection brings more options to training. Under the conventional static training scheme (Paul et al. 202T Toneva al., 2019; Coleman al. 2020). data selection is conducted prior to model update, and the informative subset is kept fixed. Contrastively, online batch selection picks batch data each iteration (Loshchilov & Hutter 2015 Alain et al. 2015 Zhang et al.) 2019; Mindermann et al., 2022). Though sufficiently considered the training dynamics, the overly frequent sample evaluation incurs prohibitive computational overhead. Recently, (Killamsetty et al.) 2021) tried selecting after several epochs' training. which is similar to our dynamic scheme. However, the dynamic training scheme is just utilized as a compromise to avoid overly frequent selection. A formal analysis of its advantage over the static scheme is absent.
By systematically considering the selection strategy, the model training, as well as the proxy design, Our proposed DynaMS forms an effective data selection framework for efficient training.
EXPERIMENTS
In this section, we first analyse the effectiveness of each design ingredient in Section 4.2 Then we compare to of-tee-o-tthear art algorithms in Section 4.3 Code is available at hntptts:/// / thub com/ylf2r/Dynay// Sessss-ssustttteeeeeeeeeeeeseeee
4.1 EXPERIMENTAL SETUP
We conduct experiments on CIFAR- Krizhevsky & Hinton 2009) and ImageNet Jia al. (2099).
following standard data pre- pre-processing in He et al. (2016). A brief summarization of the experimental setup is introduced below, while complete hyper-paramen settings and implementation details can be found in Appendix F
CIFAR-10 Experiments For CIFAR-10 10, we train ResNet-18 18 (He et al. 2016) for 200 epochs. Selection is conducted every 10 epochs, so overall there are 19 selections (K = 19). For subset size, we adopt a simple linear schedule: 7 = 1 k a for I: = 1,..., K, where determines the reduction ratio. We make sure "avg = K Di=1 7k = Ys- this way, the averaged number of data used in the dynamic scheme (Yivg) is kept equal to that of static training (%²) for fair comparison. For 0.6x acceleration, a = 0.042. We conduct experiments on a NVIDIA Ampere A-100.
ImageNet Experiments For ImageNet, we choose ResNet-18 and ResNet-50 as base models. Following the conventions, the total training epoch is 120. Selection is also conducted every 10 epochs, so altogether K 11. For subset size, aside from the linear schedule, we also explore power schedule where "ik decays following a power law: 7 = m h- + for A = 2.2....A. K.
For 0.6x acceleration, we set m 0.398, r 0.237 and h 0.290. Please see Appendix F for

---

Published as a conference paper at ICLR 2023
more details. The power schedule reserves more samples in late training, preventing performance degradation caused by over data pruning. We conduct experiments on four NVIDIA Ampere A-100s.
4.2 ABLATION STUDIES
Table 2:
Comparison of different data se- lection strategies. Except for DynaMS, all the other methods conduct training in the conventional static scheme.
Table 3: Accuracy of utilizing parameter sharing
proxy (PSP) with different width configurations.
FLOPs is the reduction of FLOPs required when use proxy for sample evaluation.
Strategy Topl Acc.
Top5 Acc.
Width
Topl Acc.
Proxy Topl Acc.
FLOPs
CE-loss
72.073
91.727
1.00x
74.558
EL2N
72.032
91.778
0.75x
73.694
72.882
43.75%
MS
72.888
91.807
0.50x
73.401
70.720
75.00%
DynaMS 74.558
92.334
0.25
73.390
62.349
93.75%
We use ResNet-50 on ImageNet to illustrate the effect of each ingredient in DynaMS, that is, the classification margin criteria, the dynamic training scheme as well as the parameter sharing proxy.
The effect of classification margin selection To inspect the effect of classification margin selec- tion (MS), we compare MS against two widely applied selection strategies CE-loss (Loshchilov & Hutter 2015; Jiang et al.) 2019) and EL2N (Paul et al. 2021). CE-loss selects samples explicitly through the cross-entropy loss they incur while EL,NN picks samples that incur large 1.2 error. We compare the three under the conventional static scheme any other factors aside from the selection strategy is excluded. Samples are evaluated after 20 epochs of pretraining. The model is then reinitialized and trained on the selected subset, which contains 60% original samples. As shown in MS achieves the best accuracy among the three, validating its effectiveness.
Table 2
The effect of dynamic training We then apply dynamic selection on MS, where the average subset size also kept to be 60% of the original dataset. From Table we see that DynaMS outperforms MS by 1.67%, which is significant on large scale dataset like ImageNet. The superiority of DynaMS validates that by constantly improving the model and updating the subset, dynamic selection scheme can result in better performance. Note that DynaMS can be more practical since it does not require the 20 epochs training prior to selection as required in the static scheme.
The effect of parameter sharing proxy We now study the parameter sharing proxy (PSP). An effective proxy is supposed to be faithful, and can agilely adapt model updates. In Figure 4 plot the Spearman rank correlation as well as the overlap ratio of samples selected with the proxy and the model. We see that all along the training, the rank correlation is around 0.68, and over 78% samples selected are the same, indicating that the proxy and the model are fairly consistent. We then investigate how will the complexity, measured by floating point operations (FLOPs), of proxy affect. We enumerate over the slimming factor p E {0.25, 0.5, 0.75, 1.0] to construct proxies of different widths, the corresponding FL.OPs are 6. 65%,%, 25.00% 56. 25%, 100% respectively. In Table we see that significant computation reduction can be achieved with moderate performance degradation.
4.3 COMPARISONS WITH THE
Finally, we compare DynaMS against various state-of-the-art methods. Aside from CE-loss and EL2N, Random picks samples uniformly at random. GraNd (Paul al., 2021) select samples that incur large gradient norm. Forget (Toneva et al. (019) counts how many times a sample is mis-classified (forget) after it is learned. Samples more frequently forgotten are preferred. We evaluate the forget score after 60 epochs training. To avoid noisy evaluation, many of these static selection approaches ensembles networks before selection. The number of ensambled models is given by the subscription. Auto-assist (Zhang et al. 2019) select samples that incur large loss value small proxy. Selection is conducted in each iteration thus forming an online batch selection (OLBS) scheme. DynaCE and DynaRandom apply the corresponding selection strategy, but trained in dynamic way. CRAIG and GradMatch propose to reweight and select subsets so that they best cover approximate the full gradient. In the experiments, we use the bat-hatch variant of CRAIG and
7

---

Published as a conference paper at ICLR 2023
Table 4: Comparison for ResNet-18 on Cifar- 10.
Figure 4: Correlation of proxy and model.
Methods
Types
Budget
Schedule
Acc.
Time(min)
Spearman Correlation
Original
100%
95.52
28.6
Random
Stat.
60%
94.09
17.4
EL2N,
Stat.
60%
94.55
17.442.0
EL2N
Stat.
60%
95.34
17.4
GraNd1o
Stat.
60%
95.21
27.4
Forgetio
60%
95.29
17.4
20
40
60
80
OnlineMS
OLBS.
60%
Const. Const.
95.21
9076.3
Auto-assist
OLBS.
60%
92.37
24.6
Overla Ratio
0.79
RanaRandom
Dyna.
60%
Linear 94.45
20.9
0.78
DynaCE
Dyna.
60%
Linear 94.96
21.0
Craig
Dyna.
60%
Const. 94.36
28.7
0.77
GradMatch
Dyna.
60%
Const. 94.84
26.7
DynaMS
Dyna. 60%
Linear 95.28
21.3
20
40
60
Epochs
GradMatch proposed in (Killamsetty et al. 2021) with 10 epoch warm start The two approaches utilize dynamic selection scheme, all the training settings are kept the same our DynaMS.
In table 4 average accuracy from runs on CIFAR-10 as well as their running time are reported. Due to limited space, the standard deviation is given in Appendix E We that DynaMS achieves comparable performance against the strongest baselines (EL.2 10- GraNd1o- Forget10) while being more efficient. Note that the static methods require pretraining one or several models for 20 epochs before selection. Considering this cost (subscript of the reported rumning time), the acceleration of these methods is less significant. also compare two online batch selection methods, OnlineMS and Auto-assist (Zhang et al.) 2019). OnlineMS picks samples with MS, but the selection is conducted each iteration. OnlineMS didn't outperform DynaMS, meaning more frequent selection is not necessary. Rather, selecting each optimization step incurs prohibitive computational overhead. Auto-assist didn't get good performance in this experiment. This may results from the overly simple proxy. The logistic regression proxy adopted may not sufficiently evaluate the candidate samples.
Table 5: Comparison for ResNet-18 and ResNet-50 on ImageNet.
ResNet 18
ResNet 50
Types
Budget Schedule
Acc@1
Acc@5
Time(hrs)
Acc@1
Accu5
Time(hrs)
Original
100%
70.56
89.95
12.8
75.96
92.75
18.2
Random
Stat.
60%
67.16
87.50
7.6
72.4
90.85
10.9
EL2N;
Stat.
60%
66.38
88.56
7.6
72.03
91.78
10.9
EL2N
Stat.
60%
66.46
88.73
7.6421.1
72.18
92.02
10.9
GraNd1o
Stat.
60%
66.50
88.76
7.6421.1
72.14
92.16
10.9
Forget1o
Stat.
60%
67.84
87.50
7.6
73.50
91.41
10.9+89.1
SVP+Forget
Stat.
60%
72.90
91.37
10.9+12.8
SVP+Entropy
Stat. 60%
73.00
91.52
10.9+
DynaRandom
Dyna.
60%
Power 67.59
87.62
8.9
72.63
90.91
12.1
DynaCE
Dyna.
60%
Power 67.58
88.10
9.2
72.80
91.31
12.5
Craig
Dyna.
60%
Const.
65.32
86.92
12.1
70.69
90.72
16.0
GradMatch
Dyna. 60%
Const.
66.48
88.61
11.7
71.79
91.67
15.2
DynaMS
Dyna.
60%
Linear
68.12
88.93
9.6
74.10
92.25
12.9
DynaMS
Dyna.
60%
Power
68.65
89.21
9.6
74.56
92.33
13.0
DynaMS+PSP
Dyna. 60%
Linear
73.59
91.79
12.8
DynaMS+PSP
Dyna. 60%
Power
73.40
91.80
12.8
'For cifar- 10, we the published implementation from https: http:///ghuu..oom/eeeeeeee////// For Ima- geNet, modify the implementation the distributed setting.
8

---

Published as a conference paper at ICLR 2023
ResMet-So@llageeNet Top1 Acc.
lmageeet Top5 Acc.
76.00
92.75
92.50
75.00
92.25
74.00
91.75
73.00
Rendom Sampling
Random Sampling
EL2N;
91.50
EL2%;
EL2Ng
EL2%o
72.00
GraNd
91.25
GraNd
DynaMS
91.00
DynaNs
71.00
SVP+forget
90.75
SVPrforget
60
Fraction Kept (%)
Fraction Kept (%)
Figure 5: Comparison under different (on average) sample budgets.
For ImageNet, we also report the average accuracy from 5 runs well their running time. The standard deviation is given in Appendix E it achieves 68. 68.65% and 74.56% top-1 accuracy given on average 60% samples for ResNet- 18 and ResNet-50 respectively, surpassing the most competitive counterpart Forget by 0.81 1%% and 1.06%. Compared to the static methods which require additional pretraining, 60 epochs for Forget and for the others, DynaMS is much more efficient. CRAIG and GradMatch didn't get good performance on ImageNet. This might because we use the ver-batch variant in (Killamsetty et al. 202I). and set batch size 512 in order to fit the per-sample gradients into memory. The per-batch variant treats each mini-batch as one sample and selects mini-batches during the gradient matching process. So larger batch size means more coarse grain selection which may lead inferior performance. We also compare a variant DynaRandom. DynaRandom adopts the dynamic selection scheme but a random subset is constructed each selection. DynaMS outperforms DynaRandom by 1.06% and 1.93% for ResNet- 18 and ResNet-50 respectively, indicating that the superiority of DynaMS over static methods comes from effectively identifying informative samples instead of witnessing more data.
DynaMS outperforms all the baselines. For instance,
ResNet-50 is rather complex and the data evaluation time is non-negligible. We thus apply parameter sharing proxy to reduce the evaluation time. The proxy is 0.5 width so the evaluation requires around 0.25x computation compared to the original model. As the gradients of the proxy and the underlying model are well aligned, we only train DynaMS+PSP for 90 epochs. From table [5] though utilizing proxy harms performance compared to DynaMS, it still outperforms all the other baselines. Specifically, SVP also uses proxy for sample evaluation. The proxy, however, a statically fully trained ResNet-18. The superiority of DynaMS+PSP over SVP shows the necessity of dynamic proxy that agilely keeps up with the change of underlying model. The advantages DynaMS+PSP DynaMS efficiency data is available while only a small fraction of data is sufficient for training. To further demonstrate DynaMS, draw the accuracy curvature of ResNet-50 against different (on average) sample budgets from 60% to 100% in Figure 5 It can be found that our DynaMS consistently outperforms all the other data selection strategies
be significant for extremely large scale problems where massive
different budgets. Finally, To get better understanding of how the selected samples look like and how they change over time, we visualize samples picked in different selection steps along the training. See for more details.
5 CONCLUSION
In this paper, we propose DynaMS, general dynamic data selection framework for efficient deep neural network training. DynaMS prefers samples that are close to the classification boundary and the selected "informative" subset is dynamically updated during the model training. DynaMS has high probability to converge and we pioneer to show both in practice and theory that dynamic selection im- proves the generalization by selection, we further design a proxy available for dynamic selection. Extensive experiments and analysis conducted demonstrate the effectiveness of our strategy.
previous approaches. Considering the additional computation incurred

---

Published as a conference paper at ICLR 2023
REFERENCES
Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron Courville, and Yoshua Bengio. Variance reduction in sgd by distributed importance sampling. arXiv preprint, 1eXvv1511.064811, 2015.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Merbert-Vosss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901, 2020.
Mark Chen, Alec Radford, Rewon Child, Jeff Wu, Heewoo Jun, Prafulla Dhariwal, David Luan, and Ilya Sutskever. Generative pretraining from pixels. In International Conference on Machine Learning, 2020.
Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. In International Conference on Learning Representations, 2020.
Alexander G. de G. Matthews, Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahramani.
Gaussian process behaviour in wide deep neural networks. In International Conference Learning Representations, 2018.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings the 2019 Conference of for the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 4171-4186, June 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition scale. In International Conference on Learning Representations, 2021.
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: margin based approach. In International Conference on Machine Learning. ICML, Proceedings Machine Learning Research. PMLR, 2018
Zeyad Ali Sami Emam, Hong-Min Chu, Ping- Ych Chiang, Wojeiech Czaja, Richard Leapman, Micah Goldblum, and Tom Goldstein. Active learning the imagenet scale, International Conference on Computer Vision and Pattern Recognition, 2021.
Dan Feldman. Introduction to core-sets: an updated survey. arXiv preprint, arXiv:2011 2011:01100000 S0ii::0111009844,, 2020.
Ian J. Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, Cambridge, MA, USA, 2016.
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.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md. Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically, arXiv preprint, arXiv:1712.00400: 2017.
Deng Jia, Dong Wei, Socher Richard, Li Li-Jia, Li Kai, and Fei-Fei Li. Imagenet: A large-scale hierarchical image database. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 248 255, 2009.
Angela H. Jiang, Daniel L.-K. Wong, Giulio Zhou, David G. Andersen, Jeffrey Dean, Gregory R. Ganger, Gauri Joshi, Michael Kaminsky, Michael Kozuch, Zachary C. Lipton, and Padman- abhan Pillai. Accelerating deep learning by focusing on the biggest losers. aXiv preprint, arXiv:1910.00762 2019.
10

---

Published as a conference paper at ICLR 2023
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint, 20Xii:200110886... 2020.
Angelos Katharopoolos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In International Conference on Machine Learning, 2018.
Krishnatejam Killamsetty, Durga Sivasubramanian, 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, 2021.
Alex Krizhevsky and Geffery Hinton. Learning multiple layers of features from tiny images. In Technical report, 2009.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems, volume 32, 2019.
Ilya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. arXiv preprint, arXiv:1511 11.5111.143,. 2015.
David Mickisch, Felix Assion, Florens Greßner, Wiebke Günther, and Mariele Motta. Under- standing the decision boundary of deep neural networks: An empirical study. arXiv preprint, arXiv:2002.01811 10100,001000000000 2020.
Sören Mindermann, Jan Brauner, Muhammed Razzak, Mrinank Sharma, Andreas Kirsch, Winnie Xu, Benedikt Höltgen, Aidan Gomez, Adrien Morisot, Sebastian Farquhar, and Yarin Gal. Prioritized training on points that are learnable, worth learning, and not yet learnt. arXiv preprint, arXiv:2206.07137, 2022.
Baharan Mirzasoleiman, Jeff A. Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In International Conference Machine Learning. ICML, volume 119 of Proceedings of Machine Learning Research, pp. 6950-6960 PMLR, 2020.
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on data diet: Finding important examples early in training. In M. Ranzato, A. Beygelzimer, Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 20596 20607. Curran Associates, Inc., 2021.
Burr Settles. From theories to queries: Active learning in practice. Active Learning and Experi- mental Design workshop in AISTATS, 2010.
Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari S. Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. arXiv preprint, arXiv:2206. 14486, 2022.
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. In International Conference of Representation Learning. 2019.
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel Schoenholz, and Jeffrey Penning- ton. Dynamical isometry and a mean field theory of CNNs: How to train 10,000-layer vanilla convolutional neural networks. In International Conference on Machine Learning, 2018.
Jiahui Yu, Linjie Yang, Ning Xu, Jianchao Yang, and Thomas Huang. Slimmable neural networks. In
International Conference on Learning Representations, 2019.
Jiong Zhang, Hsiang-fu fu Yu, and Inderjit S Dhillon. Autoassist: A framework to accelerate training of
deep neural networks. Conference on Neural Information Processing Systems, 2019.
11

---

Published as a conference paper at ICLR 2023
A
APPENDIX
ALGORITHM PROCEDURE
Algorithm I ooutliees the procedure of margin selection (MS). In MS, distances of the current sample (xc. y) to each other class c are computed. If y * c, the classification margin of (æ: y) and class c is M (ax, V. c), which is the distance of moving from class y to class If y c, the classification margin is mināşy M (æ, é), which corresponds to the distance moving (æ, u) to another class that the most close the classification margins are obtained, |S|/C samples with the smallest classification margin along each class are picked. This keeps samples collected in the subset balanced.
For the whole candidate set T, this generates [7] C' score matrix. After
Algorithm 1 Margin selection: MS(w, 7,7)
Input:
Candidate set T, keeping ratio number of classes C;
Network with weights w, including weights of the final classification layer W;
Output:
Selected subset according to the classification margin S.
1: Compute the keeping budget |S| = y (7), initialize the subset S = {}
Evaluating: compute the classification margin.
2: for (x, v) E T TT do
3: for c 1 C' do
4: Compute the classification margin of the sample to the (y, c) boundary:
M M y. {{ minzyy (,)
=
(4)
(xx y #c
5: end for
6: end for
Selecting: pick the samples according to classification margin (Equation +
7: for e == 1: do
8: Pick /S|/C samples which have the smallest classification margins (-)(: Toppspole)
9: S U (sp(s)/
10: Remove the already selected samples from the candidate T Top/si/c(e)
end for
Algorithm 2 Dynamic margin selection (DynaMS)
Input:
Training data
Base network with weights W, learning rate
Keep ratio of each selection where è = 1,..., K, selection interval Q
Output:
Model efficiently trained selected subsets.
1: A: = 1; 7h 1 thus Sn = T
2: for epochs = 1... 7' do
3: if & % Q == then
4:
Select subset, St MS(W T, 5: ==
6:
else
7:
Keep subset Sk.
8:
end
9:
Update W via stochastic gradient descent on St.
10:
end for
12

---

Published as a conference paper at ICLR 2023
Algorithm 3 Dynamic margin selection (DynaMS) with parameter sharing proxy (PSP)
Input:
Training data T:
Base network with weights W, learning 7 Keep ratio of selection "/e where = 1,.., K, selection interval Slimming factor of the proxy r, thus the proxy weights W poss is determined.
Output:
Model efficiently trained selected subsets.
1: 1; " thus S₁
2: for epochs = .,., 7 do
3:
if & % Q == 0 then
4:
Select subset,
MS(W Pmaays
praays T, 7k).
5:
6:
else
7:
Keep subset Sk.
8:
end if
9: Update W optimizing L(W) + poWy on Sx. (Slimmable training)
10:
end for
full workflow of efficient training with the proposed dynamic margin selection (DynaMS) shown in Algorithm 2] The model is first trained on the full dataset T for Q epochs to warm up. Subset selection kicks in each Q epochs, samples are evaluated with the current model so informative subset gets updated according to the distance of samples the classification boundary. After selection, the model is trained on selected subset until the next selection. The workflow incorporating parameter sharing proxy is shown in Algorithm evaluated and selected with the proxy instead the underlying model. During the Q epochs' training, the proxy and the original model updated simultaneously with slimmable training (Yu et al. 2019).
Different from naive DynaMS, samples
B PROOF FOR THEOREM
To prove Theorem 2.2 we first inspect the norm of æ. We get the following lemma.
Lemma For Gaussian data (0, 2)), let p > 0, T > be constants, d the dimension of x and X the largest eigenvalue of the covariance L, then with probability at least 1 pTd
||||| vdv(1+ + (2
Proof of Lemmal 7 For (O, E). ||=| follows generalized chi-squared distribution. The mean and variance can be computed explicitly [[]||=||]] tr = E3 As and Var(I<=11)) 2tr = Σ, X3. By Chebyshev's inequality, we have
Pr ||0||
<
HTd 2
>
>
uTd
where f > O and T are constants and d is the dimension of r. Then
Σ + Vurd 2Σ, X3 < (1+ /2y(T)d where max, Aÿ the largest eigenvalue of the
covariance E, we have:
Pr [10l12 < + >1 pTd
(5)
Then we can start proving Theorem 2.2
Theorem. Consider logistic regression (xx Ite-w with N Gaussian training samples
(0, E), Rdd Assume ||wi||2 D and N < Let un" be the optimal parameters and be
13

---

Published as a conference paper at ICLR 2023
2
the largest eigenvalue of the covariance E. For 1 E [T....T) and constants >
1, 1b >> O,, select subset with critical margin Ri = (1 + log(sT 1) and update parumeters with Then with probability least
learning rate 1j EVT
c C.C Tit
min ((wi) -L(w") - DE
+
(6)
T
T9
where E = (d + (2 B
(1++)² 2D2X
4. Ce and Cr,g, are constants depending Ç and
X.
Proof of Theorem 2.2
For logistic regression f(z)
with loss function
Itc
N
N yi log Di - (1 (1- log(1 - (1)
L
i=1
Where ÿJ is the predicted value. The gradient incurred training on the selected subset is then:
Ohix
N
(0 Yb );
I( w æxa < <k)
dw
N
For those |w TxTl 2 K. or "easy" samples, we have sgn((; ) wwww xil 2 x. and with probability at
least 1 uTd
0c
E.T. Ite
if sgn(y; - )) . w 0; 2 k
S
(8)
iw 2
F.
if sgn(yi 1) w mi I
where E vdX(1 + (2x)+), +). Note that the condition sgn(y; - ))
x; -K means H; misclassified by w well as the margin is at least Denote the portion of this kind of misclassified sample the whole training set by r, we have the estimate the gradient gap
0Lx
Oc
Oe Ow
Err.
Σ w
(x)
dw
2
20
2x
ET (1 - 7t)
ET
7r
1
Where "/ is the fraction of data kept by selecting with margin Ky. The inequality holds with probability / because of Equation 8
at least (1 wTal
Note that Lemma to be Lipschitz continuous with parameter ET By setting a constant learning rate 1j = EVT and
also suggest ||
Ae 1l < E. T with large probability, therefore L is highly likely
DN
critical margin n² (1 +) - > 1, have with probability least (1 +t 2 1
DE
D
min L(w:) L(ww))
Err
NT
T
DE
DE
T-1
1
DE T
NT
T
(CT -1
T
T1
(10)
DE
TO )
Ce,s
DE T-1
T
N
The first inequality follows the Theorem in (Killamsetty et al.
202
The last inequality holds
because ΣT-1 (CT-o)+++
CT J(G-1)T 1. ds < with Ce
e(5-1)e> Ve and Ç
To bound the sum of classification error (the last term of Equation 10 again we utilize the data distribution prior. Note that the data points contribute to r are quantified by the following set:
E (w OA -x) U [ x A w x > x} E Eg
14

---

Published as a conference paper at ICLR 2023
where w. is the oracle classifier such that the true label is generated according to y sgn( (w. ( x). Let & represent the probability density function standard Gaussian, we see that
d( = / o(x(E))dx
r=
En
(- (-V
K
22
0x 2d = 24
(w (wT
V w Ew
K DVA
<2
where À is the largest eigenvalue of 2. Therefore, we have the following estimation:
T
Tt
Σ
Kr t=1
24
7
DVA
2
((VA)(DVA)) Ke/
(Gaussian upper tail bound)
T
(DVA)
t=1
2DVĀ
1
0+02 202x
(11)
V2T(1 +E) T
log(CT -t)
2DVIT
2 +e)
log((s 1)T + +1) ((C ((5-1)T + 1) 2022
(++)
log((S-1)7+)
C
where 8 1 2 and assume log((( - 1)7' + ?(11 with respect to T. Together
prove the theorem
GENERALIZATION
Sorscher et al. (2022) analysed the generalization of static training scheme in the teacher-student perceptron setting, where the teacher is an "oracle" generating labels. For the training set T (æ:, Vi [7] N=z assume a;; (0, I) and there exists an oracle model Rd which generates the labels such that = sign (w, ax:) for all i. Without loss of generality, the oracle is assumed to be drawn form sphere. Sorscher et al. (2022) works in a high dimensional statistics where [T], + oo but the ratio a [T] d remains (11).
Following the static training scheme, lower fidelity estimator Westimate which has angle 0 relative the oracle w, is used evaluate the candidate instances, and those with smaller classification margin ID [st along the estimator Westimate are picked. The selection results in subset S. S follows p(2), truncated Gaussian distribution along Westimate. while the other directions are still kept isotropic. More specifically, given keeping ratio 7, the corresponding selection margin is == H-1 (2=7) and thus the subset distribution along Westimate is p(z) / (xx) where ((x) is the cumulative distribution
O - -12)), where
(z)) is the Heaviside function and (x) function (CDF) of standard Gaussian.
The generalization error of the model trained on the subset S takes the form E(a, y. 9). That is, the error is determined by " the keeping ratio, which indicates the abundance of training samples before selection, and 8 which shows the closeness the estimator to the oracle model. The full set of self-consistent equations characterizing E(,, 7, 0) is given
15

---

Published as a conference paper at ICLR 2023
R pcos
TA l dr drexp
A
exp
(v (V-T)
sin² 0
212
(r-02)2
p² + R²2 2pR cos 2a
L dt
6
2(1
H
T(T,2)
(v 1t-
sin 2
v 2T p²
/ p²
(1-00)2
p Reos
p dr
E 2(1-1)
VI - p²A/ )
I(T, z)
- pT
20r
H
1- ( p2
(v (T-T)
sin 0
2 /1 p²
-00
1
(- A(T
)
(pR (1- p2
cost 0)
) (v (W- 7) 7))
+
cxp
2xA
2A²
(12)
Where,
A V sin? R² p² + 22pR cos
T(t, 2) = a(pR cos 0) - T(R - pcos 8)
A14 = (0² + cos? 2 2p 0) + (r=(Recos - p) + ?
is an auxiliary field introduced by Hubbard-Stratonovve Strratooovott transformation. (+) denotes expectation on p(z). By solving these equations the generalization error can be easily read off as E cos -1 (R) n,
where w w0
100 10
D MORE RESULTS ON GENERALIZATION
Static
Dynamic
Dynamic
Dynamic
0.4
0.3
0.3
0.2
0.2
0.2
0.1
0.1
0.0
0.0
0.2
40
30
20
10
1.0
0.8
0.4
4
40
20
10
1.0
4
0.4
40
10
1.0
0.8
0.6
0.4
(a) Smaller budget (Ywng 50%). (b) Less abundant data (a 2.1). (c) Better estimator (0 30").
Figure 6: Effects of select ratio Ywg. initial data abundance and the closeness of the estimator to the oracle model on the generalization.
To better understand the generalization under classification margin selection E(a,7: 7, 0), we provide more results to indi- vidually inspect the effect of (on average) select ratio Tagg. initial data abundance a and the closeness of the estimator to the oracle mode 0. As shown in Figure 6(a) we changed Tavg from 60% to 50%. thus constructing smaller selection budget case. In Figure 6(b) we use a 2.1 instead of a 3.2 to construct less abundant data case, where the data before selection insufficient. In Figure 6(c) we start selecting sam- ples using a better estimator 0 30 instead of 0 40 All the other hyper- parem-eresetesss aside from the inspected one are kept consistent to those used Figure 2(b) that is, Vavg 0.6.
Static Dynamic
Error
0.3
0.2
0.2
40
0.4
0.6
1.0
Figure 7: Generalization in a data
scarce regime (a = 1.7).
a = 3.2 and 0 40% We see that with various Vavg and 8,
DynaMS outperforms its static counterpart. The abundance of initial data, however, significantly
16

---

Published as a conference paper at ICLR 2023
affects. When data is insufficient, data selection, both static as well dynamic cause obvious performance degradation. [ a even more serious a 1.7, the generalization landscape significantly changed and data selection is not recommended in this case.
COMPARISON WITH STANDARD DEVIATION
We test each method in Table 4 and Table 5 times. The averaged accuracy and standard deviation are reported below in Table 6 and Table 7
Table Comparison for ResNet- on Cifar- 10 with standard deviation.
Methods
Types
Budget
Schedule
Accuracy.
Original Random
100%
95.52
Stat.
60%
94.09 10.23
EL2N,
Stat.
60%
94.55
EL,2 10
Stat.
60%
95.34 10.13
GraNd1o
Stat.
60%
95.21 10.15
Forget1o
Stat.
60%
95.29
OnlineMS Auto-assist
OLBS. OLBS.
60%
Const.
95.21
60%
Const.
92.37
DynaRandom
Dyna.
60%
Linear
94.45.0.17
DynaCE
Dyna.
60%
Linear
94.96-0.21
Craig
Dyna.
60%
Const. 94.3611.19
GradMatch
Dyna.
60%
Const. 94.84
DynaMS
Dyna.
60%
Linear
95.28
Table 7: Comparison for ResNet-18 and ResNet-50 on ImageNet with standard deviation
ResNet 18
ResNet 50
Types
Budget
Schedule
Topl Acc.
Top5 Acc.
Topl Acc.
Top5 Acc.
Original
100%
70.56
89.95
75.96
92.75+0.2
Random
Stat.
60%
67.1644010
87.50 87.50
72.46
90.85+a04
EL2N;
Stat.
60%
66.38
88.56
72.03
91.78+0004
EI.2N
Stat.
60%
66.46.10.10
88. 73 18.03
72.18
92.02 1o.06
GraNd1o
Stat.
60%
66.50 10.06
76 10.03
72.14
92.16.0.03
Forget
Stat.
60%
67. 67.8440.08
87.50
73.50
91.41+004
SVP+Forget
Stat.
60%
72.90
91.37+0004
SVP+Entropy
Stat.
60%
73.00
91.52
DynaRandom
Dyna.
60%
Power
67.59 +0.05
87.62
72.63
90.91
DynaCE
Dyna.
60%
Power
67.58
88. 10,10.... 10.4
72.80
91.31 10.03
Craig
Dyna.
60%
Const. 65.32
86.92
70.69 0.00
90.72
GradMatch
Dyna.
60%
Const.
66.48
88. +0.04
71.79
91.67+00
DynaMS
Dyna.
60%
Linear
68. 12
88.93 -.006
74.10
92.25+000
DynaMS
Dyna.
60%
Power
68.65
89.21 1..01
74.56
92.33
DynaMS+PSP
Dyna.
60%
Linear
73.59
91.79+0.7
DynaMS+PSP
Dyna.
60%
Power
73.40
91.80+000
IMPLEMENTATION DETAILS AND HYPER- PARAMETERS
Subset size schedule Dynamic Selection admits freedom in subset size schedule. In the experiments we consider the linear schedule and the power schedule. For linear schedule, the keeping
ratio is determined by 7/ k for l: 1,2...., K, where determines the sample reduction
17

---

Published as a conference paper at ICLR 2023
K k= 7 Y where Y is the selection ratio when static training scheme applied. Thus K Σx=1 the dynamic scheme is kept equal to that of static training.
ratio. y is supposed to satisfy Yavg 1 Σ K
Th = |S|. meaning the averaged number of data used in
Aside from the linear scheduler, we also explore a power schedule where >> = m k- + b for samples in late training, preventing performance
k ...,..... K. Power schedule reserves degradation caused by over data pruning. Determining these hyper-parameterss m, r, is a bit tricky, K
we just require
A= " Ys for fair comparison. "iK should not be overly small, we empirically find 7K R 7 0.1 yield good results. For different budget
1.0 to warm start and Ywg
7s = {0.6, 0.7, 0.8, 0.9} the hyper-parameters are given in Appendix F Table Post process is
carried out to make sure the resulting subset size sequence satisfy the above requirements.
(Killamsetty al. 2021 utilize constant schedule, where each selection the subset size kept constant % |T]- This schedule how- ever, do not admit selection without replacement. Linear and power schedule all monotonically decreasing, thus are natural choices consider- ing this. Figure [8] plots the three schedules Te = 0.6 budget. In this paper we just provide primary exploration on the subset size schedule, in depth study on the relationship between the subset size and the model performance as well as automatic way determining the optimal subset size schedule is left for future work.
1.0
power
linear
Keep Ratio v
0.8
0.2
2.5
5.0
7.5
10.0
12.5
Number of Selection
Figure 8: Different schedules for % = 0.6 budget.
Hyper-parameters Finally, the detailed hyper-parameters for DynaMS on both CIFAR-10 and ImageNet datasets are shown Table g Note that for DynaMS+PSP, the Max Epochs is set to be 90 on ImageNet.
Table 8: parameras of DynaMS for different models on CIFAR-10 10 and ImageNet.
CIFAR-10
ImageNet
parametrrs
Re
ResNet-18
ResNet-50
Batch Size
128
512
512
Init. Learning Rate of W
0.1
0.1
0.1
Learning Rate Decay
Stepwise 0.2
Stepwise 0.1
Stepwise 0.1
Lr Decay milestones
(60.120,10))
(40.80)
(40,80)
Optimizer
SGD
SGD
SGD
Momentum
0.9
0.9
0.9
Nestrov
True
True
True
Weight Decay
5e-4
le-4
le-4
Max Epochs
200
120
120
Selection interval
10
10
60%: m = 0.3984, r= 0.2371, b= 0.2895
80%: m = 0.3532, 0.2300. b=0.4275
70%: m 0.3476,
Power Scheduler
0.1349, b= 0..978
90%: m = 0.2176. r 0.1035. b= 0.7078
a = 0.041
60%: a = 0.073
70%: 0.055
Linear Scheduler
80%: a = 0.036
90%: 0.018
18

---

Published as a conference paper at ICLR 2023
k=1
k=4
k=7
k=10
Figure 9: Images selected at different training stages of the model. As (orscheer et al. show results on ImageNet class 100 (black swan).
2022 we
G VISUALIZATION OF DYNAMICALLY SELECTED IMAGES
To get a better understanding of how the selected samples look like and how they change over time, we visualize samples picked in different selection steps along the training. For k = 1. = 4, k and h: 10, which corresponds to the 1,4,7 and 10th selection, we randomly visualize selected samples that are absent in the latter selection. E.g. the k 4 row shows images picked in the 4th selection but not the 7th selection. From Figure we see that the early selections, amounts of dusy-to-recognize samples are kept. As the training proceeds, these simple images screened out and the model focuses more on harder samples that are atypical, blurred, or with interfering objects, validating hypothesis that samples most informative change the model evolves. Dynamic selection is thus indispensable.
19

---

Published as a conference paper at ICLR 2023
H SUMMARY OF NOTATIONS
Table 9: Summary of the notations used throughout this paper. Variables only used in theoretical analysis including the convergence analysis and the generalization analysis are grayed for better readability.
Topic
Notation
Explanation
Data (sub) Sets
T
The full training set Cardinality of a set data sample
|
data label
The extracted subset The number of classes The cth class
C
C
Models and Parameters
f(-)
The model used for classification Parameters of the model
w
Optimal model parameter Oracle model parameter
W.
W
Parameter of the linear classifier
W
Kernel of convolutional layers gradient incurred by the model gradient incurred by the proxy The dimension of data feature Feature extractor part the model f(-)
Jaroxy
d
h(-)
P
Slimming factor, deciding the width of the proxy model
Selection schedule
Sample reduction ratio in the linear schedule paperr-prrmeters controlling the power schedule
m, r, b
Loss Functions
C
Generic reference to the loss function
Data Selection
B
Decision boundary of linear classifiers
Q
Selection interval
M
The classification margin aka. distance of sample decision boundary Selection budget, keep ratio of samples for the kith selection The averaged keep ratio of dynamic selection
Tave
Ts
Selection budget in static selection. Selection step
K
The total number of selections along training The generalization error of model trained on selected subset Relative angle of model to the oracle model. Aboundance of data before selection Selection margin.
0
Train
Training epoch
T
The total number of training epochs, T Q- +1) (1)))
Data Distribution
E
Covariance of a Gaussian distribution
The largest eigenvalue of the covariance matrix
Plyper-parameten
D
Upper bound of model parameter norm Constants appear in the convergence bound.
E, Ç, p
20


Reviews:
[{"review_id": "JYWrHAbHlFj", "reviewer": "Reviewer_UJJg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose a new selection method to make train deep networks efficiently, which dynamically selects a small training \n set from the original data set. The selecting criterion is based on the classification margin. The authors also propose a lighter proxy model to speed up the selection process. The authors conduct experiments on CIFAR-10 and ImageNet to verify the effectiveness, and the results are over many baselines. ", "summary_of_the_review": "I do not recommend this paper now. If the authors can add missing parts, I will re-evaluate this paper. ", "strength_and_weaknesses": "Strength:\n1. The topic of this paper is relatively new and can be used in many applications.\n2. The performance of the proposed paper is strong.\n\nWeakness:\n1. The critical parts of this paper, the “SELECT” function and Power schedule, are missing. There are numerous hyperparameters in the supplementary, but no equation and process in the paper and supplementary. \n2. “The Gaussian input assumption … infinitely a wide neural network resembles Gaussian process”. I think this assumption is against the research problem that uses smaller datasets and models. With limited number of data, the input will not follow Gaussian distribution.\n3. The analysis on computational complexity is good but not enough. The comparison of the total training time between the proposed method and the original method from the ResNet paper is necessary.\n\nSmall issues:\n1. In introduction, “redundant samples can be left out without sacrificing performance”. From 4, there is a clear drop in terms of performance, and Top 1 Acc. decreases over 1%.\n2. The Top 1 Acc. results of “Original” in Table 4 and “Full” in Figure 4 are different. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JQ7tXrDo-x0", "reviewer": "Reviewer_8YeC", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper introduces a dynamic margin selection (DynaMS) method to dynamically construct the training subset by utilizing the distance from candidate samples to the classification boundary. In addition, a light parameter sharing proxy is designed to reduce the additional computation incurred by the selection. Extensive analysis and experiments demonstrate the superiority of the proposed approach in data selection.", "summary_of_the_review": "The major concerns of this work are as\n- The paper claims that the existing sample selection methods are expensive both in run-time and in memory efficiency, however, the paper lacks comparisons with different methods in run-time and memory.\n- In Table 3, the proposed DynaMS does not perform better than Stat.-based methods, and performs slightly better than Dyna.-based method such as CRAIG and GradMatch.\n- In Table 4, the results of DynaMS+PSP are not competitive, so the contribution of PSP is limited.", "strength_and_weaknesses": "Strength：\n+ A dynamic margin selection (DynaMS) method is proposed to dynamically construct the training subset by utilizing the distance from candidate samples to the classification boundary.\n+ Extensive analysis and experiments are conducted to show the performance of the proposed method.\n\nWeaknesses：\n- The paper claims that the existing sample selection methods are expensive both in run-time and in memory efficiency, however, the paper lacks comparisons with different methods in run-time and memory.\n- In Table 3, the proposed DynaMS does not perform better than Stat.-based methods, and performs slightly better than Dyna.-based method such as CRAIG and GradMatch.\n- In Table 4, the results of DynaMS+PSP are not competitive, so the contribution of PSP is limited.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5Y7xZ3aB4q", "reviewer": "Reviewer_hmw5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes to dynamically select partial training data for efficient learning. The main idea is updating informative subset according to their margin to class decision boundary. A parameter sharing proxy strategy is devised to further evaluate instance prior. As a result, the proposed method achieves superior performance compared with other SOTA data selection strategies on different budgets.", "summary_of_the_review": "This paper present a good idea to select informative subset for efficient training. The proposed method achieves superior performance and generalization. However, the PSP module seems redundant for the whole pipeline and it weakens the contribution based on my current understanding. I am glad to change my score if my concerns are well addressed.", "strength_and_weaknesses": "Strength:\n1. Selecting informative subset by class margin is reasonable, and the generalization of DynaMS has been well supported both in practice and theory.\n2. The performance is superior compared with previous SOTA methods.\n3. This paper is well written and the implementation is described in detail which is easy to follow.\n\nWeaknesses:\n1. The need for PSP is not significant. As mentioned in this paper, the selection procedure is efficient and its overhead is negligible since it is conducted only 19 times during training (200 epochs in total). \n2. Training slimming networks is not efficient because multiple sub-networks are trained separately. For example, compared to the original training time, with a 60% budget, the overall training cost of DynaMS+PSP is $0.6\\times (1+\\frac{9}{16}+\\frac{1}{4}+\\frac{1}{16})>1$, while other methods almost strictly cost 0.6 of the original one.\n3. For the results shown in Figure 2(a), only 10 epoch training on one dataset is not convincing enough. Why not report overlap ratio of all evaluated epochs on both CIFAR-10 and ImageNet?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0EokwoGNm2", "reviewer": "Reviewer_6uhW", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose a subset selection method for training DNNs. The idea is to select the samples that are close to the margin dynamically. To reduce computation, the authors also propose Parameter Sharing Policy for sample selection. The authors show that the proposed DynaMS can converge tot the optimal solution with large probability. Experiments are conducted on CIFAR10 and ImageNet to show the effectiveness of the proposed approach.", "summary_of_the_review": "The authors propose a dynamic sample selection method for DNN training and conduct extensive experiments to show the benefits. However, there are several issues with the current draft as stated in the drawbacks. ", "strength_and_weaknesses": "Strength:\n\n1. Reducing sample complexity is an important topic in deep learning. The authors propose some interesting ideas to address this problem.\n2. Overall, the paper is clearly written and the proposed idea is intuitive.\n3. Extensive ablation studies are conducted to show the benefit of the proposed approach.\n \nWeaknesses:\n1. The use cases of the proposed approach is not clear. If all the training samples are available for dynamic selection, then why not just use all the samples? Also, the authors did not show results of using all the samples. If sample selection is for computational complexity, there is also no time comparison.  \n\n2. Compared with dataset distillation, does the proposed approach have benefits in terms of accuracy and complexity?\n\n3. It is not clear which samples are selected and how the samples selected will change over time. \n\n4. Several typos:\n\ni. \"Our proposed DynaMS form\" -> \"Our proposed DynaMS forms\"\nii. \"is keep fixed\" -> \"is kept fixed\"\niii. \"as the model evolve\" -> \"as the model evolves\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster