Distributed Optimization in an Energy-Constrained Network: Analog Versus Digital Communication Schemes
Alireza Razavi, Wenbo Zhang, Zhi-Quan Tom Luo · IEEE Transactions on Information Theory · 2012
We consider a distributed optimization problem whereby a network of n nodes, Sℓ, ℓ ∈ {1, ..., n}, wishes to minimize a common strongly convex function f(x), x=[x1,...,xn]T, under the constraint that nodeSℓcontrols variablexℓonly. The nodes locally update their respective variables and periodically exchange their values with their neighbors over a set of predefined communication channels. Previous studies of this problem have focused mainly on the convergence issue and the analysis of convergence rate. In this study, we consider noisy communication channels and study the impact of communication energy on convergence. In particular, we study the minimum amount of communication energy required for nodes to obtain an ε-minimizer off(x) in the mean square sense. For linear analog communication schemes, we prove that the communication energy to obtain an ε-minimizer off(x) must grow at least at the rate of Ω(1/ε), and this bound is tight whenfis convex quadratic. Furthermore, we show that the same energy requirement can be reduced toO(log21/ε) if a suitable digital communication scheme is used.