In distributed training, the communication cost due to the transmission of gradients
 or the parameters of the deep model is a major bottleneck in scaling up the number
 of processing nodes. To address this issue, we propose dithered quantization for
 the transmission of the stochastic gradients and show that training with Dithered
 Quantized Stochastic Gradients (DQSG) is similar to the training with unquantized
 SGs perturbed by an independent bounded uniform noise, in contrast to the other
 quantization methods where the perturbation depends on the gradients and hence,
 complicating the convergence analysis. We study the convergence of training
 algorithms using DQSG and the trade off between the number of quantization
 levels and the training time. Next, we observe that there is a correlation among the
 SGs computed by workers that can be utilized to further reduce the communication
 overhead without any performance loss. Hence, we develop a simple yet effective
 quantization scheme, nested dithered quantized SG (NDQSG), that can reduce the
 communication significantly without requiring the workers communicating extra
 information to each other. We prove that although NDQSG requires significantly
 less bits, it can achieve the same quantization variance bound as DQSG. Our
 simulation results confirm the effectiveness of training using DQSG and NDQSG
 in reducing the communication bits or the convergence time compared to the
 existing methods without sacrificing the accuracy of the trained model. In recent years, the size of deep learning problems has increased significantly both in terms of the number of available training samples as well as the complexity of the model. Hence, training deep models on a single processing node is unappealing or nearly impossible. As such, large-scale distributed machine learning in which the training samples are distributed among different repository or processing units (referred to as workers) has started to be a viable approach for tackling the memory, storage and computational constraints.The requirement to exchange the gradients or the parameters of the model incurs significant communication overhead which is a major bottleneck in distributed training algorithms. In recent years, there has been a great amount of effort on reducing the communication overhead. The majority of existing methods can be categorized into two groups: The first group mitigates the communication bottleneck by reducing the overall transmission rate via sparsification, quantization and/or compression of the gradients. For example, BID15 reduces the communication overhead significantly by one-bit quantization of the stochastic gradients (SG). However, the reduced accuracy of gradient may impair the convergence rate. Using different quantization levels or adaptive quantizers, one can alleviate such issues by decreasing the error in the quantized gradients in the expense of increased communication bits BID4 . Moreover, applying entropy coding algorithms such as Huffman coding on the quantized values can further reduce the communication bit-rate BID13 ; BID17 . BID0 introduced QSGD which uses probabilistic (stochastic) quantization of SGs instead of ordinary fixed (deterministic) quantization methods. They investigated its convergence guarantee and the trade-off between the quantization precision and variance of QSG. Terngrad BID18 probabilistically quantizes the gradients into {−1, 0, +1} and it is shown that the convergence rate can be improved by layer-wise quantization and gradient clipping.The second group of works attempts to attenuate the communication bottleneck by relaxing the synchronization between workers. Each worker may continue its own computations while some others are still communicating and exchanging parameters. Carefully scheduling and managing the asynchronous parameter exchange can lead to a better utilization of both the communication bandwidth and the computational power of the distributed system. Examples of such approaches include DownpourSGD BID3 , Hogwild! Niu et al. (2011 ), Hogwild++ Zhang et al. (2016 and Stale Synchronous Parallel model of computation BID7 .Our Contributions. Our work in this paper falls within the first line of research, i.e. reducing the communication overhead by quantizing and compressing the gradients. We first introduce using dithered quantization in the distributed computations of the stochastic gradient and show that stochastic quantizer of BID0 and ternarization of BID18 can be considered as special cases of our proposed method, although the reconstruction algorithms are slightly different. The convergence of dithered quantized stochastic gradient descent algorithm is analyzed and its convergence speed w.r.t. the number of workers and quantization precision is investigated. Next , we observe that in a typical distributed system, the stochastic gradients computed by the workers are correlated. However , the existing communication methods ignore that correlation. We tap into the question of how that correlation can be exploited to further reduce the communication without sacrificing the precision or convergence of the learning algorithm. We model the correlation between the stochastic gradients computed by each worker and propose a nested quantization scheme to reduce the communication bits without increasing the variance of the quantization error or reducing the convergence speed of the distributed training algorithm.
The paper proposes and analyzes two quantization schemes for communicating Stochastic Gradients in distributed learning which would reduce communication costs compare to the state of the art while maintaining the same accuracy.   The authors propose applying dithered quantization to the stochastic gradients computed through the training process, which improves quantization error and achieves superior results compared to baselines, and propose a nested scheme to reduce communication cost. Authors establish a connection between communication reduction in distributed optimization and dithered quantization and develops two new distributed training algorithms where communication overhead is significantly reduced.