signSGD: Compressed Optimisation for Non-Convex Problems
  Training large neural networks requires distributing learning across multiple
workers, where the cost of communicating gradients can be a significant
bottleneck. signSGD alleviates this problem by transmitting just the sign of
each minibatch stochastic gradient. We prove that it can get the best of both
worlds: compressed gradients and SGD-level convergence rate. The relative
$\ell_1/\ell_2$ geometry of gradients, noise and curvature informs whether
signSGD or SGD is theoretically better suited to a particular problem. On the
practical side we find that the momentum counterpart of signSGD is able to
match the accuracy and convergence speed of Adam on deep Imagenet models. We
extend our theory to the distributed setting, where the parameter server uses
majority vote to aggregate gradient signs from each worker enabling 1-bit
compression of worker-server communication in both directions. Using a theorem
by Gauss we prove that majority vote can achieve the same reduction in variance
as full precision distributed SGD. Thus, there is great promise for sign-based
optimisation schemes to achieve fast communication and fast convergence. Code
to reproduce experiments is to be found at https://github.com/jxbz/signSGD .
