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的收敛性保证。该压缩技术可在工作机-服务器通信的双向上使用，因此支持具有完整通信压缩的分布式优化。

扁平化一比特随机梯度下降：受控方差的压缩分布式优化