Accelerating the Convergence Rates of Distributed Subgradient Methods with Adaptive Quantization

By Thinh T. Doan, Siva Theja Maguluri, Justin K. Romberg. 2018

15 citations recorded by the source corpus.

We study distributed optimization problems over a network when the communication between the nodes is constrained, and so information that is exchanged between the nodes must be quantized. This imperfect communication poses a fundamental challenge, and this imperfect communication, if not properly accounted for, prevents the convergence of these algorithms. In this paper, our main contribution is to propose a novel quantization method, which we refer to as an adaptive quantization. The main idea of our approach is to quantize the nodes' estimates based on the progress of the algorithm, which helps to eliminate the quantized errors. Under the adaptive quantization, we then derive the bounds on the convergence rates of the proposed method as a function of the bandwidths and the underlying network topology, for both convex and strongly convex objective functions. Our results shows that using the adaptive quantization, the rate of convergence of distributed consensus-based subgradient methods with and without quantization are the same, except for a factor which captures the number of quantization bits. Finally, we provide numerical simulations to compare the convergence properties of the distributed gradient methods with and without quantization for solving the well-known regression problems over networks, for both quadratic and absolute loss functions.

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].”
FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, background): “…several works have considered communication-eﬃcient collaborative learning where there is no master node, and the computing nodes learn a model collaboratively in a decentralized manner [Doan et al., 2018, Koloskova et al., 2019, Lalitha et al., 2019, Reisizadeh et al., 2019a, Zhang et al., 2018].”
Robust and Communication-Efficient Collaborative Learning (2019, methodology): “…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 al., 2018a,b).”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, background): “Another line of work proposed adaptive schemes (with increasing compression accuracy) that converge at the expense of higher communication cost (Carli et al., 2010a; Doan et al., 2018; Berahas et al., 2019).”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, background): “(2018) could achieve only sublinear rate for smooth and strongly convex objectives, while (Doan et al., 2018) considered non-smooth objectives and provided sublinear rates, matching optimal rates up to logarithmic factor (Scaman et al.”
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].”