  Currently, progressively larger deep neural networks are trained on ever
growing data corpora. As this trend is only going to increase in the future,
distributed training schemes are becoming increasingly relevant. A major issue
in distributed training is the limited communication bandwidth between
contributing nodes or prohibitive communication cost in general. These
challenges become even more pressing, as the number of computation nodes
increases. To counteract this development we propose sparse binary compression
(SBC), a compression framework that allows for a drastic reduction of
communication cost for distributed training. SBC combines existing techniques
of communication delay and gradient sparsification with a novel binarization
method and optimal weight update encoding to push compression gains to new
limits. By doing so, our method also allows us to smoothly trade-off gradient
sparsity and temporal sparsity to adapt to the requirements of the learning
task. Our experiments show, that SBC can reduce the upstream communication on a
variety of convolutional and recurrent neural network architectures by more
than four orders of magnitude without significantly harming the convergence
speed in terms of forward-backward passes. For instance, we can train ResNet50
on ImageNet in the same number of iterations to the baseline accuracy, using
$\times 3531$ less bits or train it to a $1\%$ lower accuracy using $\times
37208$ less bits. In the latter case, the total upstream communication required
is cut from 125 terabytes to 3.35 gigabytes for every participating client.
