Accelerating the Convergence Rates of Distributed Subgradient Methods with Adaptive Quantization
Thinh T. Doan, Siva Theja Maguluri, Justin Romberg · arXiv (Cornell University) · 2018
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.