  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 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.
