An Exact Quantized Decentralized Gradient Descent Algorithm

By Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ramtin Pedarsani. 2018

139 citations recorded by the source corpus.

We consider the problem of decentralized consensus optimization, where the sum of <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> smooth and strongly convex functions are minimized over <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> distributed agents that form a connected network. In particular, we consider the case that the communicated local decision variables among nodes are quantized in order to alleviate the communication bottleneck in distributed optimization. We propose the Quantized Decentralized Gradient Descent (QDGD) algorithm, in which nodes update their local decision variables by combining the quantized information received from their neighbors with their local information. We prove that under standard strong convexity and smoothness assumptions for the objective function, QDGD achieves a vanishing mean solution error under customary conditions for quantizers. To the best of our knowledge, this is the first algorithm that achieves vanishing consensus error in the presence of quantization noise. Moreover, we provide simulation results that show tight agreement between our derived theoretical convergence rate and the numerical results.

Subfields: Computational Mechanics, Computer Networks and Communications, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Networks and Communications

In Optimization & Training

Citations in the corpus

FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, methodology): “…and compression in distributed learning has recently gained considerable attention for both master-worker [Alistarh et al., 2017, Bernstein et al., 2018, Seide et al., 2014, Smith et al., 2016] and masterless topologies [Koloskova et al., 2019, Reisizadeh et al., 2019a, Zhang et al., 2018].”
Robust and Communication-Efficient Collaborative Learning (2019, background): “• Quantized Decentralized SGD (Q-DSGD) (Reisizadeh et al., 2019a): Iterates are updated according to (8).”
Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning (2019, unknown): “Hence, (9) can be written as: pn,i = ( [cn(θ k n)]i − b[cn(θ n)]ic ) (10) The pn,i selection in (10) ensures that the quantization error is unbiased, yielding the quantization error variance E [( n,i )2] ≤ (∆n) (2)/4 [59].”
A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent (2019, background): “In this setting, the gradient estimation of f i ( x ) can incur noise from various sources such as minibatch random sampling of the local dataset and discretization for reducing communication cost [11].”
Nested Distributed Gradient Methods with Adaptive Quantized Communication (2019, methodology): “and local information [13], [18], [21], designing custom quantizers [12], [14], [26] and employing encoding/decoding schemes to alleviate communication load [18], [19], [27].”