QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding

Dan Alistarh, etc

Intro

分布式的SGD训练方法：每一个iteration，master先从woker接收graident，然后更新gradient，最后将gradient广播给所有的worker。

为了减少communication，一个方法是采用lossy compression of the gradients，也就是减少表达的精度。一个极端的情况是采用 1BitSGD，将gradient的每一部分都只用一个bit表示。

这篇paper提出了Quantized SGD（QSGD），探究在使用不同n-bit进行压缩的时候，communication和convergence的trade-off。

quantization function用$$Q_s(v)$$表示，其中$$s$$是quantization level。

对于任意$$v \in \mathbb{R}^n$$（即gradient）

$$ Q_s(v_i) = | v |_2 \cdot sgn(v_i) \cdot \xi_i(v,s)

另$$0 \le l < s$$，且$$\xi$$定义是一个分段函数。

$$[l/s, (l+1)/s]$$就是当前$$v_i$$所在地quantization interval。