Qsparse-local-SGD (Distributed SGD with Quantization, Sparsification, and Local Computations)

When composing a k-contraction sparsifier Comp_k in R^d and an unbiased stochastic quantizer Q_s with relative variance E||Q_s(u) - u||_2^2 <= beta_{k,s} ||u||_2^2, the unscaled operator Q_s(Comp_k(x)) has contraction factor gamma = (1 - beta_{k,s})(k / d) which fails whenever beta_{k,s} >= 1 (Lemma 1), whereas the rescaled operator Q_s(Comp_k(x)) / (1 + beta_{k,s}) (Lemma 2, Corollary 1) is unconditionally a gamma-contraction for all beta_{k,s} > 0 with strictly larger contraction coefficient gamma = k / (d (1 + beta_{k,s})) > (1 - beta_{k,s})(k / d).

Under synchronization period H and contraction parameter gamma, the local error memory satisfies E||m_t^{(r)}||_2^2 <= 4 (1 - gamma^2) / gamma^2 * eta^2 H^2 G^2 (Lemma 4), yielding smooth non-convex convergence at rate O(1 / sqrt(R T)) + O(H^2 / (gamma^2 T)) (Theorem 1, Corollary 2) and strongly convex convergence at rate O(1 / (R T)) + O(H^2 / (gamma^2 T^2)) (Theorem 2).

Relies on a uniform second-moment bound E||g(x)||_2^2 <= G^2 to bound the block error accumulator m_t^{(r)}, and the higher-order error term scales quadratically with the ratio H / gamma.

Applied to distributed training of ResNet-50 on ImageNet and ResNet-20/VGG-11 on CIFAR-10, combining Top-k sparsification, 2-bit/4-bit QSGD quantization, and H = 4-8 local SGD steps to achieve up to 1000x communication reduction.