We present a selective sampling method designed to accelerate the training of deep neural networks. To this end, we introduce a novel measurement, the 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 marginbased 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 learningdrop regime while using the MMS selective sampling method.
### Summary of contributions
This paper aims to accelerate the training of deep networks using a selective sampling. 
They 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). 
Their 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. 
### Recommendation
Reject. The central premise of the paper is unclear, the writing/presentation needs improvement, and the experiments are not convincing. 
### Detailed comments/improvements: 
There is a central premise of the paper that I don't understand: that the forward pass is much cheaper than the backward pass. 
This 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. 
For a linear network with weights W, the forward pass is given by the matrix-matrix product (rows of X are minibatch samples):
Y = XW^T
and the backward pass is given by the two matrix-matrix products:
dL/dX = dL/dY*dY/dX = dL/dY*W
dL/dW = dL/dY*dY/dW = dL/dY*X^T
Similarly 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. 
Point 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.  
fprop: 0.009286s
bprop: 0.0240s
bprop/fprop: 2.5893x
In 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?
I 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. 
There 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?
More generally, it is unclear if there is really any improvement in the final performance from using the proposed method.
In Figure 2, all methods seem to have similar final performance. 
In 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. 
Why 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. 
My suggestions for improving the experimental section are as follows:
- include all methods together in all the plots/tables
- repeat experiments multiple times with different seeds to get error bars. Include these both in the learning curves and in the tables. 
- 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. 
Finally, in 2019 CIFAR alone is not longer a sufficient dataset to report experiments on. Please report results on ImageNet as well. 
One 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.  
    
### Code snippet timing forward/backward passes
import torch, torch.nn as nn, time
model =	nn.Sequential(nn.Linear(784, 1000),
                      nn.ReLU(),
                      nn.Linear(1000, 1000),
                      nn.ReLU(),
                      nn.Linear(1000, 10),
                      nn.LogSoftmax())
data = torch.randn(128, 784)
labels = torch.ones(128).long()
t = time.time()
pred = model.forward(data)
loss = nn.functional.nll_loss(pred, labels)
fprop_time = time.time() - t
t = time.time()
loss.backward()
bprop_time = time.time() - t
print('fprop: {:.4}s'.format(fprop_time))
print('bprop: {:.4f}s'.format(bprop_time))
print('bprop/fprop: {:.4f}x'.format(bprop_time / fprop_time))