  Modern machine learning models are typically trained using Stochastic
Gradient Descent (SGD) on massively parallel computing resources such as GPUs.
Increasing mini-batch size is a simple and direct way to utilize the parallel
computing capacity. For small batch an increase in batch size results in the
proportional reduction in the training time, a phenomenon known as linear
scaling. However, increasing batch size beyond a certain value leads to no
further improvement in training time. In this paper we develop the first
analytical framework that extends linear scaling to match the parallel
computing capacity of a resource. The framework is designed for a class of
classical kernel machines. It automatically modifies a standard kernel machine
to output a mathematically equivalent prediction function, yet allowing for
extended linear scaling, i.e., higher effective parallelization and faster
training time on given hardware.
  The resulting algorithms are accurate, principled and very fast. For example,
using a single Titan Xp GPU, training on ImageNet with $1.3\times 10^6$ data
points and $1000$ labels takes under an hour, while smaller datasets, such as
MNIST, take seconds. As the parameters are chosen analytically, based on the
theoretical bounds, little tuning beyond selecting the kernel and the kernel
parameter is needed, further facilitating the practical use of these methods.
