Parallel implementations of stochastic gradient descent (SGD) enjoy excellent scalability properties. One of the methods is the synchronous Data-Parallel SGD, a fundamental barrier when scaling the method is the high bandwidth cost of communicating gradient updates between nodes. Consequently, some lossy and biased compression methods have been proposed, by which the gradient updates will be quantized or sparsified. These heuristics are effective in practice but don’t always converge.
In this paper, we propose unbiased MLMC based quantization and sparsification methods with convergence guarantees in the convex framework and good practical performance in reducing the communication cost of the Data-Parallel SGD setup.
The compression methods used in this paper are Fixed-Point and Floating-Point quantization and the Top-k sparsification techniques.
When applied to training deep neural networks for image classification (MNIST), the suggested MLMC based estimators lead to significant reduction in the communication cost, along with improvement in the convergence rate with respect to training without compression or training with lossy and biased compression.