On the Convergence of Distributed Subgradient Methods under Quantization

摘要

Motivated by various applications in wireless sensor networks and edge computing, we study distributed optimization problems over a network of nodes, where the goal is to optimize a global objective function composed of a sum of local functions. In these problems, due to the large scale of the network, both computation and communication must be implemented locally resulting in the need for distributed algorithms. In addition, the algorithms should be efficient enough to tolerate the limitation of computing resources, memory capacity, and communication bandwidth shared between the nodes. To cope with such limitations, we consider in this paper distributed subgradient methods under quantization. Our main contribution is to provide a sufficient condition for the sequence of quantization levels, which guarantees the convergence of distributed subgradient methods. Our results, while complementing existing results, suggest that distributed subgradient methods achieve desired convergence properties even under quantization, as long as the quantization levels become finer and finer with a proper rate. We also provide numerical simulations to compare the convergence properties of such methods with and without quantization for solving the well-known least square problems over networks.