Importance Sampling for Minibatches
  Minibatching is a very well studied and highly popular technique in
supervised learning, used by practitioners due to its ability to accelerate
training through better utilization of parallel processing power and reduction
of stochastic variance. Another popular technique is importance sampling -- a
strategy for preferential sampling of more important examples also capable of
accelerating the training process. However, despite considerable effort by the
community in these areas, and due to the inherent technical difficulty of the
problem, there is no existing work combining the power of importance sampling
with the strength of minibatching. In this paper we propose the first {\em
importance sampling for minibatches} and give simple and rigorous complexity
analysis of its performance. We illustrate on synthetic problems that for
training data of certain properties, our sampling can lead to several orders of
magnitude improvement in training time. We then test the new sampling on
several popular datasets, and show that the improvement can reach an order of
magnitude.
