  This paper presents a methodology for selecting the mini-batch size that
minimizes Stochastic Gradient Descent (SGD) learning time for single and
multiple learner problems. By decoupling algorithmic analysis issues from
hardware and software implementation details, we reveal a robust empirical
inverse law between mini-batch size and the average number of SGD updates
required to converge to a specified error threshold. Combining this empirical
inverse law with measured system performance, we create an accurate,
closed-form model of average training time and show how this model can be used
to identify quantifiable implications for both algorithmic and hardware aspects
of machine learning. We demonstrate the inverse law empirically, on both image
recognition (MNIST, CIFAR10 and CIFAR100) and machine translation (Europarl)
tasks, and provide a theoretic justification via proving a novel bound on
mini-batch SGD training.
