Selective sampling for accelerating  training of deep neural networks
Authors: Berry Weinstein
Shai Fine
Yacov Hel-Or
Venue:  (2020)

Abstract: We present a selective sampling method designed to accelerate the training of deep neural networks. To this end,  we introduce a novel measurement,  the {\it minimal margin score} (MMS), which measures the minimal amount of displacement an input should take until its predicted classification is switched.   For multi-class linear classification,  the MMS measure is a natural generalization of the margin-based selection criterion, which was thoroughly studied in the binary classification setting.  In addition, the MMS measure provides an interesting insight into the progress of the training process and can be useful for designing and monitoring new training regimes. Empirically we demonstrate a substantial acceleration when training commonly used deep neural network architectures for popular image classification tasks.  The efficiency of our method is compared against the standard training procedures, and against commonly used selective sampling alternatives: Hard negative mining selection, and Entropy-based selection.
Finally, we demonstrate an additional speedup when we adopt a more aggressive learning-drop regime while using the MMS selective sampling method.

Under review as a conference paper at ICLR 2020
SELECTIVE SAMPLING FOR ACCELERATING TRAINING OF DEEP NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We present selective sampling method designed to accelerate the training of deep neural networks. To this end, we introduce a novel measurement, the mini- mal margin score (MMS), which measures the minimal amount of displacement an input should take until its predicted classification is switched. For multi-class linear classification, the MMS measure is natural generalization of the margin- based selection criterion, which was thoroughly studied in the binary classifica- tion setting. In addition, the MMS measure provides interesting insight into the progress of the training process and can be useful for designing and monitor- ing new training regimes. Empirically we demonstrate a substantial acceleration when training commonly used deep neural network architectures for popular im- age classification tasks. The efficiency of our method compared against the standard training procedures, and against commonly used selective sampling al- ternatives: Hard negative mining selection, and Entropy-basee selection. Finally, we demonstrate additional speedup when we adopt more aggressive learning- drop regime while using the MMS selective sampling method.
INTRODUCTION
Over the last decade, deep neural networks have become the machine learning method of choice in variety of application domains, demonstrating outstanding, often close to human-level, perfor- mances in a variety of tasks. Much of this tremendous success should be attributed the availability of resources; massive amount of data and compute power, which in turn fueled the impressive and innovative algorithmic and modeling development. However, resources, although available, come with price. Data in the big data era is available, but reliable labeled data is always challenge, and so are the ETL (Extract-Transfong Trrasfoorm-Lod) processes, data transfer, and storage. With the introduc- tion of GPUs, compute power is readily available, making the training of deep architectures feasible. However, the training phase, which to a large extent, relies on stochastic gradient descent methods, substantial amount of time. A closer
requires large number of computational resources as well look at the compute processes highlights the fact that there is a significant difference the com- pute effort between the inference (forward pass) and the model update bbock-propagation) where the latter being far more demanding. The implication is evidenced by the performance charts that hardware manufactures publish, where performance matrices such as throughput (e.g. image per second) are up to 10x better at inference vs. training for popular deep neural network architectures.
In this paper, we address the computing challenge. Specifically, we suggest method to select for the propaaropagntion pass only those instances that accelerate the training convergence of the deep neural network, thus speeding up the entire training process. The selection process is continuously performed throughout the training process at each step and in every training epoch. Our selection criterion is based on computations that are calculated anyhow as an integral part the forward pass, thus taking advantage of the "cheaper" inference compute.
2 PREVIOUS APPROACHES
Accelerating the training process is stag-standing challenge that was already addressed by quite few authors. A common approach is to increase the batch size, thus mitigating the inherent time load. This approach represents delicate balance between available compute ingredients (e.g. memory

---

Under review as a conference paper at ICLR 2020
size, bandwidth, and compute elements). Interestingly, increasing the batch size not only impacts the computational burden but may also impact the final accuracy of the model (Goyal et al. 2017
Jia et al. 2018 Ying et al. 2018).
Sample selection is another approach that has been suggested to accelerate the training. The most notable one is probably the hard negative mining (Schroff et al. 2015) where samples are selected by their loss values. The underlying assumption is that samples with higher losses have significant impact on the model. Most of the previous work that utilized this approach was mainly aimed at increasing the model accuracy, but the same approach can also be used to accelerate training. e
Recent works employ selection schemes that examine the importance of the samples (Alain et al.) 2015 Loshchilov & Hutter 2013). During the training, the samples are selected based on their gradient norm, which turn leads to a variance reduction in the stochastic gradients. Inspired by the batch size approach, a recent work by Katharopoulos and Fleuret (Katharopoulos & Fleuret, 2018) uses selective sampling to choose the training samples that reduce the gradient variance, rather than increasing the size of the batch.
Our work is inspired by the active learning paradigm that utilizes selective sampling to choose the most useful examples for training. In active learning, the goal is to reduce the cost of labeling the training data by querying the labels of only carefully selected examples. Thus, unlike the com- mon supervised learning setting, where training data is randomly selected, in active learning, the learner is given the power to ask questions, e.g. to select the most valuable examples to query for their labels. Measuring the training value of examples is a subject of intensive research, and quite a few selection criteria have been proposed. The approach most related to our work is the uncer- tainty sampling [2Jlewis1994squentti their predict labels. Two heavily used approaches to measure uncertainty are entropy-based and margin- based (Settles, 2009). In the entropy- based approach (Lewis & Catlett 1994), uncertainty is measured by the entropy of the posterior probability distribution of the labels, given the sample. Thus, a higher entropy represents higher uncertainty with respect to the class label. This approach naturally handles both binary and multi-class classification settings, but it relies on an accurate esti- mate of the (predicted) posterior probabilities. In the margin- based approach Tong & Koller [000]] Campbell et al.) 2000), uncertainty is measured by the distance of the samples from the decision boundary. For linear classifiers, several works (Dasguptal 2006 [Blcaan et al., 2007) gave theoretical bounds for the exponential improvement in computational complexity by selecting few labels as possible. The idea is to label samples that reduce the version space (a set of classifiers consistent with the samples labeled so far) to the point where it has diameter at most (c.f (Dasgupta 2011)). ). This approach was proven to be useful also in non-realizable cases (Balcan et al. (007). However, generalizing it to the multi-class setting less obvious. Another challenge in adapting this approach for deep learning is how to measure the distance to the intractable decision boundary. Ducoffe and Precioso (Ducoffe & Precioso| 2018) approximate the distance to the decision boundary using the distance to the nearest adversarial examples. The adversarial examples are generated using a Deep- Fool algorithm Gooosavi-Dezfooll et al. 2016). The suggested DeepFool Active Learning method (DFAL) labels both, the unlabeled samples and the adversarial counterparts, with the same label.
where samples are selected based on the uncertainty of
Our selection method also utilizing uncertainty sampling, where the selection criterion is the closeness to the decision boundary. We do, however, consider the decision boundaries at the (last) fully-connected layer, i.c. a multi-class linear classification setting. To this aim, we introduce the minimal margin score (MMS), which measures the distance to the decision boundary of the two most competing predicted labels. This MMS serves us as a measure to score the assigned examples. A similar measure was suggested by Jiang et al. (Jiang et al.)) as loss function and measure to predict the generalization gap of the network. Jiang et al. used their measure in a supervised learning setting and applied it to all layers. In contrast, we apply this measure only at the last layer, taking advantage of the linearity of the decision boundaries. Moreover, we use it for selective sampling. based solely on the assigned scores, namely without the knowledge of the true labels. The MMS measure can also be viewed as an approximation measure for the amount of perturbation needed to cross the decision boundary. Unlike the DFAL algorithm, we are not generating additional (adversarial) examples to approximate this distance but rather calculate it based on the scores of the last-layer.
Although our selective sampling method is founded by active learning principles, the objective is different. Rather than reducing the cost of labelling, our goal is to accelerate the training. Therefore,
2

---

Under review as a conference paper at ICLR 2020
more aggressive in the selection of the examples to form batch group each learning step, at the cost of selecting many examples at the course of training.
The rest of the paper is organized follows. In section our selective sampling algorithm and discuss its properties. Section we present the performances of our algorithm the common datasets CIFAR1O and CIFAR 100 (Krizhevsky et al. 2009) and
present the MMS measure and describe
compare results against the original training algorithm and hard-negative sampling. We demon- strate additional speedup when adopt more aggressive learning-drop regime. We conclude Section 3 with discussion and suggestions for further research.
ACCELERATING TRAINING USING MINIMAL MARGIN SCORE SELECTION
As mentioned above, our method is based the evaluation of the minimal amount of displacement training sample should undergo until its predicted classification is switched. We call this measure minimal margin score (MMS). This measure depends on the best and the 2nd best scores achieved for a sample. Our measure was inspired by the margin-based quantity suggested by Jiang et al. TJang al.) for predicting the generalization gap of a given network. However, in our scheme, we apply measure to the output layer, and we calculate it linearly with respect to the input of the last layer. Additionally, unlike (Jiang et al.),, we do not care about the true label, and our measure is calculated based on the best and the 2nd best NN scores.
An illustrative example, demonstrating the proposed approach, is given in Figure In this example, multi-class classification problem is composed of three classes: Green, Red, and Blue along with three linear projections: W1, W2, and Wa. respectively. The query point is marked by an empty black circle. The highest scores of the query point are 8² and s² (assuming all biases are 0's), where s > x² and X is negative (not marked). Since the best two scores are for the Green and Red classes, the distance of the query point to the decision boundary between these two classes is d. The magnitude of d is the MMS of this query point.
Wi
D12
W2
Figure 1: Illustrative example of the MMS measure. For more details see text.
Formally, let X {xi, xB} be large set of samples and y; Fx;; 0) y be input to the last layer of the neural network F. Assume we have classification problem with classes. At the last layer the classifier f consists of linear functions: fs y - R for 1... ... where is linear mapping f: = w. + by. For sample X₁. E X', the classifier predicts its class label by the maximal score achieved: & = arg max, (x 0)) = arg max; f( Denote the sorted scores of {f(()))) by (54) s .... str)) where 8 2 s and s = fú, (yx). The classifier fú, (y+) gave the highest score and f., (x&) gave the second highest score. The decision boundary between class 1j and class iz is defined as:
tyl= fy f(,
Using this definition, the confidence of the the predicted label of point x is determined by the distance of yı to the decision boundary D12, namely the minimal distance y to D22:
dR eminsyllōy| s.t. (yk 5y) D12
3

---

Under review as a conference paper at ICLR 2020
It is easy to show (see Appendix A) that
Sk
dx
Wi,
Wial
The distance de is the Minimal Margin Score (MMS) of point Xς. The larger the da, the more confident we are about the predicted label. Conversely, the smaller the d2. the less confident we are about the predicted label 11. Therefore, dg can serve as a confidence measure for the predicted labels. Accordingly, the best points to select for the back-propagation step are the points whose MMS are the smallest.
Our implementation consists of generic but yet simple online selective sampling method as preliminary part of the training optimization step. Specifically, at each training step, selective batch of size b is produced out of a 10x larger batch before using it in the SGD optimization routine. At a specific iteration, we first apply a forward pass on a batch of size B, producing the prediction scores. Secondly, select b samples (b procedure is summarized in Algorithm
B) whose MMS measures the smallest. This
Algorithm 1: Selection by Minimal Margin Scores
Require: Inputs X' {x.) (() Training model, b batch size
t+
repeat
V+H PP(2;00-11
forward pass on batch of size B calculates the Minimal Margin Scores of y stores the index of the smallest scores subset of X' of size back prop. with batch of size b
MMS d(Y)
S inde (MMS, b)
X, = {x S}
02 - syd_step( (Xs; 1)-
t ++
until reached final model accuracy
EXPERIMENTS
In this section D we empirically examined the performance of the proposed selection scheme. As baseline, compared results against the original training algorithm using uniform sampling from the dataset. Additionally, we compared the MMS method against two popular schemes: hard- negative mining which prefers samples with low prediction scores, and entropy-based uncertainty sampling. Our experimental workbench was composed of the common visual datasets CIFARIO and CIFAR 100 (Krizhevsky et al., 2009) that consist of 32 32 color images in 10 100 classes and has 50,000 training examples and 10,000 test examples.
Hard negative samples. For this experiment, we implemented the "NM-samples" procedure (Hoffer et a..), similar to the classical methods for "harr-negaaive-minnng used by machine-learning practitioners over the years (Yu et al., 20188 Schroff et al. 2015). We used the cross-entropy loss as proxy for the selection, in which the highest loss samples were selected. We denote this approach as HNM-samples.
On both datasets we used ResNet-44 (He et al. 2016) and WRN-28-10 Zagoruyko & Komodakis, 2016) architectures, respectively. To compare our MMS selection scheme against the baseline and HNM, we applied the original sapeeeerrameterss and training regime using batch-size of 64. In addition, we used the original augmentation policy as described in He et al. (2016) for ResNet-44, while adding cutout (DeVries & Taylor (017)) and auto-augment (Cubuk et 2018) for WRN-28- 10. Optimization was performed for 200 epochs (cquivalent to 156K iterations) after which baseline accuracy was obtained with apparent improvement.
All experiments were conducted using PyTorc framework, and the code is publicly available at https: 7/gi thub. submi s ons/ mms sec
4

---

Under review as a conference paper at ICLR 2020
50
50
Seleet (ours)
Select HNM samples
30
30
20
20
steps
(a) CIFARIO training error
(b) CIFARIO test CITOr
60
60
40-
20
30000
Sooa
stops
steps
CIFARIOO training emror
(d) CIFARI00 test
Figure 2: Training and test error (ResNet44, CIFARIO and CIFAR 100, WRN-28-10). Comparing vanilla training, HNM-samples selection (hard negative sampling), and MMS (our) selection
CIFAR1O. For the CIFARIO dataset, sampling with the MMS scheme obtained significantly lower emror compared to the baseline and the HNM-samples throughout the entire training progress (> 25% 30% on average). The test results are depicted in Figure 2b Furthermore, the use of MMS provides a slight improvement of 0. % in the final test accuracy as well as a clear indication of a faster generalization compared to the baseline and the HNM schemes.
CIFAR100. Inspired by the results on CIFARIO 10 using the MMS method, we continued to evaluate performance on a more challenging 100 classes dataset. The MMS method obtained non-negliiible enror decrease, particularly after the first learning-rate drop (> 5% 10% on average) as can be seen in Figure 2d On the other hand, we did not observe similar behaviour using the HNM and the baseline schemes, similarly as in CIFARIO.
4.1 MEAN MMS AND TRAINING ERROR
To estimate the MMS values of the selected samples during training, we defined the mean MMS in training step the average MMS of the first 10 selected samples for the batch. This compared to the mean MMS of the samples selected by the bascline and the HNM methods.
present the trace of the mean MMS that was recorded at the experiments presented in Figure 2 in the course of training. The mean MMS of the suggested scheme remains lower compared to the baseline in most of the training process. We argue that this behaviour stems from the nature of the uncertain classification with respect to the selected samples. This result suggests that there are "better" samples to train the model on rather than selecting the batch randomly. Interestingly, the HNM method obtained a similar mean MMS at the early stages of training, On the other hand, the HNM method resulted in a similar mean MMS as our suggested method during the training, but increases after the learning-rate drop, and it deviates from the MMS scores obtained by our method. Lower mean MMS scores resemble better (more informative) selected batch samples. Hence, may conclude that the batches selected by our method, provides higher value for the training procedure vs. the HNM samples. Moreover, the mean MMS trace is monotonically increasing as the training progress, and it flattens when training converges.
All the selective sampling methods that we tested (HNM, entropy-based and our MMS method), yielded significantly higher error throughout the training (Figures 2a 2c
This coincides with
5

---

Under review as a conference paper at ICLR 2020
1.6
1.2
Bascline
1.4
Salest
1.2
MLS
0.8
Select HMM-semples
1
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0
20100
41100
40180
100
120000
140.00
23.930
40
100000 120 0000000
stops
(a) CIFARIO mean MMS
(b) CIFARIO 100 mean MMS
Figure 3: mean MMS of the samples selected by three methods: baseline, HNM-sample and MMS.
the main theme of selective sampling that strive to focus training on the more informative points. However, training loss can be a poor proxy this notion. For example, the selection criterion of the HNM favours high loss scores, which obviously increases the training eπrоr, while our MMS approach select uncertain points, some of which might be correctly classified, others might be miss- classified by small margin (low absolute loss scores). but they are all close to the decision boundary, and hence useful for training. Evidently, the mean MMS provides a clearer perspective into the progress of training and usefulness of the selected samples.
4.2 SELECTIVE SAMPLING USING ENTROPY MEASURE
Additionally, we tested the entropy- based selective sampling, which is popular form of uncertainty sampling. We select the examples with the largest entropy. thus the examples with the most class overlap, forming a training batch of size 64 out of a 10r larger batch. We compared performances with the vanilla training and the MMS selection method, using the same experimental setting.
50
Bascline
Seeecc MMS (ours
40
40
-Select
%6
30
30
20
10-
10
20:000
800
20:000
00:000
100
000
120
200
140
000
20
000
40 000
65 030
53 $3.300 steps
120 300
120
000
sleps
(a) CIFARIO training error
(b) CIFARIO test error
80
60
emorr
40
20
20106
10/0000
100
100
100
000
40100
143
ateps
steps
(c) CIFAR100 training error
(d) CIFAR100 test cITor
Figure 4: vanilla vs. entropy-ber WRN-28-10, CIFAR100).
e based selection: Training and test enror (ResNet44, CIFARIO and
This experiment shows (see Figure 4 that for a small problem as CIFARIO, this selection method efficient our MMS. However, CIFARIOK 100, inducing more challenging task, this method fails. This entropy measure relies on the uncertainty of the posterior distribution with respect to the examples class. We consider this batch size and the number of classes increases, this measure becomes less accurate. Finally, as the number of classes grows, in CIFAR100 100 compared to CIFAR10, the prediction scores signal has
inferior method for selection. Also, the ratio between the

---

Under review as a conference paper at ICLR 2020
longer tail with less information, which also diminishes its value. The last assumption is not valid for our method as we measure based on the two best predictions.
4.3 ADDITIONAL SPEEDUP VIA AN AGGRESSIVE LEANING-RATE DROP REGIME
The experimental results have led us conjecture that may further accelerate training using the MMS selection, by applying an early learning-rate drop. To this end, we designed a new, more aggressive leaning-rate drop regime. Figure present empirical evidence to our conjecture that with the MMS selection method we can speed up training while preserving final model accuracy.
50
Baseline
Sellect MMS lours) early ir drop
40
-Select HVM--samples eary Ir drop
-baseline early' Ir drop)
erto %
20
20
10:
10
300
stops
steps
(a) CIFARIO training error with early LR drop
(b) CIFARIO test error with early LR drop
40
40
60
emror
40
error
30
25
20
15
20:002
43 000
20 000
00 000
100 000
120 300
140 002
40 300
00:000
30:00C
100 000
120 000
140 000
steps
steps
(c) CIFARIOO training error with early LR drop
(d) CIFARI00 test error with early LR drop (zoomed)
Figure 5: Training and test accuracy (ResNet44, CIFARIO and WRN-28-100 10, CIFARIOO) Com- paring vanilla training, HNM-samples selection (hard negative mining), and MMS (our) selection method using a faster regime. We plot the regular regime bascline (dotted) for perspective. The MMS selection method achieves final test accuracy at a reduces number of training steps.
CIFAR10. For CIFAR1O and ResNet-44 we used the original learning rates 17 (0.1, 0.01, 0.001. 0.0001) while decreasing them at steps (24992, 27335, 29678) equivalent to epochs (32, 35, 38} with batch of size 64. As depicted in Figure 5b we can see that indeed our selection yields validation accuracy that is similar to the one obtained using the original training regime, in a much earlier step. As described in table [ training with our selection scheme almost reached final model accuracy in considerably less training steps as originally suggested. Specifi- cally, we reached 93% accuracy after merely 44K steps (a minor drop of 0.25% compared to the baseline). We also apply the early drop regime to the baseline configuration well the HNM- samples. Both failed to reach the desired model accuracy while suffering from degradation of 1.57% and 1. 1.22% for the baseline and HNM-samples, respectively.
Test accuracy (Top-1) results for CIFARI0/10M We compare model accuracy using our training scheme and early Bearning-rate drop as described in section 4.3 We emphasize the reduces number of steps required reaching this accuracy using our MMS method.
Table 1:
Network
Dataset
Steps
Accuracy
Baseline
Ours
Baseline
Ours
ResNet-44
10
156K 156K
44K 80K
93.24% 82.26%
93%
WRN-28-10
CIFAR 100
82.2%
7

---

Under review as a conference paper at ICLR 2020
CIFARI00. Similarly, applied the early learning-rate drop scheme for CIFAR100 and WRN- 28- 10, using 1/ = {0.1, 0.02, 0.004, 0.0008} and decreasing steps (39050, 41393, 43736] equivalent to epochs {50, 53, 56} and batch of size 64. As depicted in Figure 5d accuracy reached 82.2% with a drop of 0.07% compared to baseline with almost halving the baseline required steps (from 156K K to 80K steps). On the other hand, the baseline and the HNM-samples configurations failed to reach the desired accuracy after applying similar early drop regime similarly to CIFARIO 10. The degradation for the HNM-samples approach was the most significant, with a drop of 2.97% compared to the final model accuracy, while the baseline drop was approximately of 1%.
5 DISCUSSION
We presented a selective sampling method designed to accelerate the training of deep neural net- works. Specifically, we utilized uncertainty sampling. where the criterion for selection the dis- tance to the decision boundary. To this end, we introduced novel measurement, the minimal mar- gin score (MMS), which measure the minimal amount of displacement an input should take until its predicted classification is switched. For multi-class linear classification, the MMS measure is natural generalization of the margin-based based selection criterion, which was thoroughly studied in the binary classification setting, We demonstrate a substantial acceleration for training commonly used DNN architectures for popular image classification tasks. The efficiency of our method is compared against the standard training procedures, and against commonly used selective sampling methods: Hard negative mining selection, and Entropy-based selection. Furthermore, we demonstrate an ad- ditional speedup when we adopt more aggressive learning-drop regime.
Tracking the MMS measure throughout the training process provides an interesting insight into the training process. Figure 3 demonstrates that the MMS measure is monotonically increasing, even when training and validation errоrs are flattening, Subsequently, it flattens when training converges the final model. This suggests that improvement in training can be obtained as long as there is uncertainty in the class labels. Furthermore, tracking the MMS measure may turn out to be useful for designing and monitoring new training regimes.
Our selection criterion was inspired by the Active Learning methods, but our goal, accelerate train- ing, different. Active learning mainly concerns about the labelling cost. Hence, it is common to keep on training till (almost) convergence, before turning to select additional examples to label. However, such an approach is less efficient when it comes to acceleration. In such a scenario, we can be more aggressive; since labelling cost is not concern, we can re-select new batch of examples in each training step.
An efficient implementation is also crucial for gaining speedup. Our scheme provides many oppor- tunities for further acceleration. For example, fine-tuning the sample size used to select and fill up new batch, to balance between the selection effort conducted at the end of the forward pass, and the compute resources and efforts required to conduct the proppappaantioon pass. This also opens an opportunity to design and use dedicated hardware for the selection. In the past few years, custom ASIC devices that accelerate the inference phase of neural networks were developed (goy Hoffer al. Jouppi et al. 2017). Furthermore, in (Jacob et al. 2018), it was shown that using quantization for low-precision computation induces little or no degradation in final model accuracy. This obser- vation, together with the fast and efficient inference achieved by ASICs, make them appealing to be used as supplement accelerator in the forward pass of our selection scheme.
The MMS measure doesn't use the labels. Thus it can be used select samples in an active learning setting as well. Moreover, similarly to (Jiang et al.) the MMS measure can be implemented at other layers in the deep architecture. This enables to select examples that directly impact training at all levels. The additional compute associated with such calculating and selecting the right batch content, makes it less appealing for acceleration. However, for active learning, it may introduce an additional gain, since the selection criterion chooses examples which are more informative for various layers. The design a novel Active Learning method is left for further study.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Goya inference card.
labs goya wwitepaper.ppr
Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron Courville, and Yoshua Bengio. Variance reduction in sgd by distributed importance sampling. arXiv preprint 1eXiv:1511.064333 2015.
Maria-Florina Balcan, Andrei Broder, and Tong Zhang. Margin based active learning. In Interna- tional Conference on Computational Learning Theory, pp. 35-50. Springer, 2007.
Colin Campbell, Nello Cristianini, and Alex Smola. Query learning with large margin classifiers. In ICML, volume 20, pp. 0, 2000.
Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le. Autoaugment: Learning augmentation policies from data. arXiv preprint arXiv:1805.09550 2018.
Sanjoy Dasgupta. Coarse sample complexity bounds for active learning. Advances neural
information processing systems, pp. 235-242, 2006.
Sanjoy Dasgupta. Two faces of active learning. Theoretical computer science, 417711111767-1188 2011.
Terrance DrVeies and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint /708 04552, 2017.
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: margin based approach. arXiv preprint arXiv:/802.098441 2018.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint
2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Elad Hoffer, Berry Weinstein, Itay Hubara, Sergei Gofman, and Daniel Soudry. Infer2train: lever- aging inference for better training of deep networks.
Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko. Quantization and training of neural networks for inference. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7704-2713 2018.
efficient
Xianyan Jia, Shutao Song, Wei He, Yangzihao Wang, Haidong Rong, Feihu Zhou, Liqiang Xie, Zhenyu Guo, Yuanzhou Yang, Liwei Yu, et al. Highly scalable deep learning training system with mixed-procision: Training imagenet in four minutes. arXiv preprint arXiv.180.111205, 2018.
Yiding Jiang. Dilip Krishnan, Hossein Mobahi, and Samy Bengio. A margin- based measure of generalization for deep networks. ICLR 2019.
Norman P Jouppi, Cliff Young, Nishant Patil, David Patterson, Gaurav Agrawal, Raminder Bajwa, Sarah Bates, Suresh Bhatia, Nan Boden, Al Borchers, et al. In-datacenter performance analysis of tensor processing unit. In 2017 ACM/IEEE 44th Annuul International Symposium on Computer Architecture (ISCA), pp. 1-12. IEEE, 2017.
Angelos Katharopoulos and Franccois Fleuret. Not all samples are created equal: Deep learning with importance sampling. arXiv preprint arXiv:1803.0099: 2018.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
David D Lewis and Jason Catlett. Heterogeneous uncertainty sampling for supervised learning. In Machine learning proceedings 1994, pp. 148-156. Elsevier, 1994.

---

Under review as a conference paper at ICLR 2020
Ilya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. arXiv preprint arXiv:1511.03343, 2015.
Seyed-Mohsen Moosavi-Dezzooli, Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method fool deep neural networks. In Proceedings of the IEEE conference on com- puter vision and paltern recognition, pp. 2574-2582, 2016.
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings the IEEE conference on computer vision and pattern recognition, pp. 815-823, 2015.
Burr Settles. Active learning literature survey. Technical report, University of Wisconsin-Madisson Department of Computer Sciences, 2009.
Simon Tong and Daphne Koller. Support vector machine active learning with applications to text classification. Journal of machine learning research, 2(Nov):45-66, 2001.
Chris Ying, Sameer Kumar, Dehao Chen, Tao Wang, and Youlong Cheng. Image classification at supercomputer scale. arXiv preprint arXiv: 1.06992, 2018.
Hao Yu, Zhaoning Zhang, Zheng Qin, Hao Wu, Dongsheng Li, Jun Zhao, and Xicheng Lu. Loss rank mining: A general hard example mining method for real-time detectors. 2018 International Joint Conference on Neural Networks (IJCNN), pp. 1-8. IEEE, 2018.
Sergey Zagoruyko and Nikos Komodakis.
Wide residual networks.
arXiv preprint
115.::660..07146, 2016.
10

---

Under review as a conference paper at ICLR 2020
APPENDIX A
Assume given point x and its DNN latest layer output y = F(x, 0). W.L.o.g let's the largest and the second largest scores of the classifier be: s w y + bj and 5² w y + b2, respectively. We are looking for the smallest ōy satisfying:
w + σy) b1 w (y + by) + b2
Re-arranging terms we get:
- (w1 6y = (s - =²)
The least-norm solution of the above under-determined equation is calculated using the right pseudo- inverse of (w1- w2) which gives:
öy (s² =2) ||1 W2
W W2
and therefore the MMS of y is:
8² - s Ww W2 d | V Jy"ôy


Reviews:
[{"review_id": "rJglmTn5tS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary of contributions\n\nThis paper aims to accelerate the training of deep networks using a selective sampling. \nThey adapt ideas from active learning (which use some form of uncertainty estimation about the class of the label) to selectively choose samples on which to perform the backward pass. Specifically, they use the minimal margin score (MMS). \nTheir algorithm works by computing the forward pass over a batch of size B (which is much larger than the regular batch of size b), compute the uncertainty measure for each sample, and only perform the backward pass over the b samples with the highest uncertainty. The motivation is that the backward pass is more expensive than the forward pass, and that by only performing this pass on a subset of samples, computations are saved. \n\n\n### Recommendation\n\nReject. The central premise of the paper is unclear, the writing/presentation needs improvement, and the experiments are not convincing. \n\n\n### Detailed comments/improvements: \n\n\nThere is a central premise of the paper that I don't understand: that the forward pass is much cheaper than the backward pass. \nThis is claimed in the intro by referring to charts that hardware manufacturers publish (but there are no references included), but I don't see why this should be the case. \nFor a linear network with weights W, the forward pass is given by the matrix-matrix product (rows of X are minibatch samples):\nY = XW^T\n\nand the backward pass is given by the two matrix-matrix products:\ndL/dX = dL/dY*dY/dX = dL/dY*W\ndL/dW = dL/dY*dY/dW = dL/dY*X^T\n\nSimilarly the two operations in the backward pass for convolutional layers are given by a convolution of the output gradients with the transposed weigtht kernels and the input image respectively. \n\nPoint being, I don't see why the backward pass should be more than 3x more expensive than the forward pass. A simple experiment in PyTorch confirms this: the code snippet pasted at the bottom shows that the backward pass takes only around 2.6x longer than the forward pass.  \n\nfprop: 0.009286s\nbprop: 0.0240s\nbprop/fprop: 2.5893x\n\nIn algorithm 1, it is assumed that b << B. For this to be effective the forward pass would have to be *much* faster than the backward pass for this method to yield an improvement in computation. Can the authors comment on where this justification comes from?\n\nI am unclear on what the purpose of Section 4.1 is. This shows that the MMS of the proposed method is lower than the other two, but this should be completely expected since that is exactly the quantity being minimized. \nThere are also several unsubstantiated claims: \"Lower MMS scores resemble a better...batch of samples\", \"the batches selected by our method provide a higher value for the training procedure vs. the HNM samples.\", \"Evidently, the mean MMS provides a clearer perspective...and usefulness of the selected samples\". What does higher value, usefulness, clearer perspective mean?\n\nMore generally, it is unclear if there is really any improvement in the final performance from using the proposed method.\nIn Figure 2, all methods seem to have similar final performance. \nIn Figure 5, is there a reason why the curve for MMS is cut off? How does its final performance compare to that of the baseline method in red? It looks like the baseline might be better, but it's hard to tell from the figure. \n\nWhy are the experiments with the entropy measure in a seperate section? Please include them along with the other methods in the same plot, i.e merge Figure 2 and Figure 4. \n\nMy suggestions for improving the experimental section are as follows:\n- include all methods together in all the plots/tables\n- repeat experiments multiple times with different seeds to get error bars. Include these both in the learning curves and in the tables. \n- It's hard to see small differences in the learning curves, so including tables as well is important. Include best performance for all the methods in the tables. \n\nFinally, in 2019 CIFAR alone is not longer a sufficient dataset to report experiments on. Please report results on ImageNet as well. \n\nOne of the central premises of the paper is acceleration in terms of compute/time. To make this point, there should also be results in terms of walltime and floating-point operations. Please include these results in the paper.  \n    \n\n\n\n### Code snippet timing forward/backward passes\n\n\nimport torch, torch.nn as nn, time\n\nmodel =\tnn.Sequential(nn.Linear(784, 1000),\n                      nn.ReLU(),\n                      nn.Linear(1000, 1000),\n                      nn.ReLU(),\n                      nn.Linear(1000, 10),\n                      nn.LogSoftmax())\n\ndata = torch.randn(128, 784)\nlabels = torch.ones(128).long()\nt = time.time()\npred = model.forward(data)\nloss = nn.functional.nll_loss(pred, labels)\nfprop_time = time.time() - t\nt = time.time()\nloss.backward()\nbprop_time = time.time() - t\nprint('fprop: {:.4}s'.format(fprop_time))\nprint('bprop: {:.4f}s'.format(bprop_time))\nprint('bprop/fprop: {:.4f}x'.format(bprop_time / fprop_time))\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HkgDJXI-5B", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "A new approach is proposed to speed up training in deep models.\n\nThe idea is to select sample batches when back propagating the error based on the distance of the prediction foe the sample from the decision boundary. Specifically, we pick points closer to the boundary, i.e., ones that we are less confident about for backpropagation.\n\nExperiments are performed comparing the method with Hard negative sampling (HNM) , entropy-based sample selection as well as regular training. Experiments are performed on Cifar10 and Cifar100 datasets. \nWhy only two datasets, the method is general so there should be more datasets to verify its performance.\n\nThe results on Cifar100 in Fig 5 c seems to show that we cannot reach the training accuracy using the proposed method as compared to the other methods. What is the intuition here as to why it happens? In general though since the main goal is to speed up training I do not see very convincing evidence of this in the limited evaluation which seems to be the main weakness here.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "BJeWmNn3KS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a minimal margin score (MMS) criterion to speed up the training of the deep networks.\n\nI would vote for a clear rejection of this paper. This submission is a clearly unfinished one. The two biggest problems are as follows\n\n1. Lack of a comprehensive discussion on rules for sampling section, please see \"Automated Curriculum Learning for Neural Networks\". Why previous methods are worse than the proposed one is not clear.\n\n2. All experiments are only compared with baseline approaches. In some experiments, the improvements are really marginal (e.g., Figure 2). In these cases, the STD of these curves is not shown, it is not clear whether the improvements are significant or not.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a method to speed up training of deep nets by re-weighting samples based on their distance to the decision boundary. However, they paper seems hastily written and the method is not backed by sufficient experimental evidence.
Decision: Reject