Finite Rate Quantized Distributed optimization with Geometric Convergence

By Chang-Shen Lee, Nicolò Michelusi, Gesualdo Scutari. 2018

27 citations recorded by the source corpus.

This paper studies distributed (strongly convex) optimization over multi-agent networks, subject to finite rate communications. We propose the first distributed algorithm achieving geometric convergence to the exact solution of the problem, matching thus the rate of the centralized gradient algorithm (although with different constants). The algorithm combines gradient tracking with a quantized perturbed consensus scheme. The impact on the convergence (rate) of design and network parameters, such as number of bits, algorithm step-size, and network connectivity, is also investigated. Finally, numerical results validate our theoretical findings. They demonstrate the existence of an interesting trade-off among solution accuracy, convergence time and communication cost, defined as the total number of bits transmitted on one link to achieve a target solution error.

Subfields: Computer Networks and Communications, Public Health, Environmental and Occupational Health

How researchers see this paper

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

In Computer Networks and Communications

In Public Health, Environmental and Occupational Health

Citations in the corpus

Distributed Fixed Point Methods with Compressed Iterates (2019, methodology): “oximate methods. Among inexact methods, some provide algorithms that compute (sub)gradients at compressed iterates: [23,24]. Exact methods usually exchange compressed gradients or compressed iterates [6,14,19,21,26,33]. Our focus in this work is on centralized methods, and we leave an extension to d”
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).”
Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization (2018, methodology): “Finally, we have recently noticed that the work in [35] considers a similar adaptive quantization method as the one used in this article but for distributed gradient tracking algorithms.”
Nested Distributed Gradient Methods with Adaptive Quantized Communication (2019, methodology): “The authors of [26] extend [28]; however, while gradient tracking algorithms (e.”