We propose a novel algorithm for distributed stochastic gradient descent
(SGD) with compressed gradient communication in the parameter-server framework.
Our gradient compression technique, named flattened one-bit stochastic gradient
descent (FO-SGD), relies on two simple algorithmic ideas: (i) a one-bit
quantization procedure leveraging the technique of dithering, and (ii) a
randomized fast Walsh-Hadamard transform to flatten the stochastic gradient
before quantization. As a result, the approximation of the true gradient in
this scheme is biased, but it prevents commonly encountered algorithmic
problems, such as exploding variance in the one-bit compression regime,
deterioration of performance in the case of sparse gradients, and restrictive
assumptions on the distribution of the stochastic gradients. In fact, we show
SGD-like convergence guarantees under mild conditions. The compression
technique can be used in both directions of worker-server communication,
therefore admitting distributed optimization with full communication
compression.

我们提出了一种在参数服务器框架中实现梯度压缩的分布式随机梯度下降（SGD）的新算法。我们的梯度压缩技术名为压平一位随机梯度下降（FO-SGD），它依赖于两个简单的算法思想：（i）利用抖动技术的一位量化过程，和（ii）在量化之前使用随机快速 Walsh-Hadamard 变换来压平随机梯度。因此，在该方案中，真实梯度的近似是有偏的，但它避免了常见的算法问题，如在一位压缩制度下方差激增、在梯度稀疏情况下性能恶化和对随机梯度分布的限制性假设。实际上，我们证明了在温和条件下类似于 SGD 的收敛性保证。该压缩技术可在工作机 - 服务器通信的双向上使用，因此支持具有完整通信压缩的分布式优化。