Quantized Decentralized Consensus Optimization

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

30 citations recorded by the source corpus.

We consider the problem of decentralized consensus optimization, where the sum of $n$ convex functions are minimized over $n$ 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 local cost functions, QDGD achieves a vanishing mean solution error. 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 experimental results.

Subfields: Artificial Intelligence, Computer Networks and Communications, Optimization & Training, Algorithms & Complexity

How researchers see this paper

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

In Artificial Intelligence

In Computer Networks and Communications

In Optimization & Training

In Algorithms & Complexity

Citations in the corpus

Distributed Fixed Point Methods with Compressed Iterates (2019, methodology): “Exact methods usually exchange compressed gradients or compressed iterates [6, 14,19,21,26,33].”
Robust and Communication-Efficient Collaborative Learning (2019, methodology): “The ﬁrst exact decentralized optimization method with quantized messages was given in (Reisizadeh et al., 2018; Zhang et al., 2018), and more recently, new techniques have been developed in this context for convex problems (Doan et al., 2018; Koloskova et al., 2019; Berahas et al., 2019; Lee et…”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, background): “Reisizadeh et al. (2018a) propose an algorithm that can still converge, though at a slower rate than the exact scheme.”
Accelerating the Convergence Rates of Distributed Subgradient Methods with Adaptive Quantization (2018, methodology): “Thus, there is a gap in the rate of convergence of such methods between us-ing quantization [7, 28] and no quantization.”
An Exact Quantized Decentralized Gradient Descent Algorithm (2018, background): “Following our preliminary work [1], there has been a growing interest in developing quantized decentralized optimization methods [38]–[40].”
Compressed Distributed Gradient Descent: Communication-Efficient Consensus over Networks (2018, methodology): “The algorithm in [22], focusing on the strongly convex problems, used the diminishing step-size strategy to guarantee the convergence.”
Decentralized Federated Averaging (2021, unknown): “QuantizedDSGDhas been proposed in [36].”
SPARQ-SGD: Event-Triggered and Compressed Communication in Decentralized Stochastic Optimization (2019, background): “In decentralized setting, [TGZ + 18,RMHP18], propose unbiased stochastic compression for gradient exchange.”
Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization (2018, background): “In contrast, different variants of distributed gradient methods under quantized communication have been studied in [2], [3], and [11]–[15].”
Federated Learning with Compression: Unified Analysis and Sharp Guarantees (2020, background): “Recently a few attempts are made to explore the compression schema in a decentralized setting where each device shares compressed messages with direct neighbors over the underlying communication network [21, 38, 39, 42].”
Finite Rate Quantized Distributed optimization with Geometric Convergence (2018, background): “Roughly speaking, the current literature [13]–[19] can be categorized in two groups, namely: algorithms requiring infinite rate (quantized) communications [13], [14] and those using a finite number of bits per communication [15]–[19].”