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.

We consider a distributed optimization problem where n nodes, Sl, l isin {1,..., n}, wish to minimize a common strongly convex function f(x), x = [x1,..., xn]T, and suppose that node Slonly has control of variable xl. The nodes locally update their respective variables and periodically exchange their values over noisy channels. Previous studies of this problem have mainly focused on the convergence issue and the analysis of convergence rate. In this work, we focus on the communication energy and study its impact on convergence. In particular, we study the minimum amount of communication energy required for nodes to obtain an isin-minimizer of f(x) in the mean square sense. In an earlier work, we considered analog communication schemes and proved that the communication energy must grow at the rate of Omega(isin-1) to obtain an isin-minimizer of a convex quadratic function. In this paper, we consider digital communication schemes and propose a distributed algorithm which only requires communication energy of O ((log isin-1)3) to obtain an isin-minimizer of f(x). Furthermore, the algorithm provided herein converges linearly. Thus, distributed optimization with digital communication schemes is significantly more energy efficient than with analog communication schemes.

We consider a distributed optimization problem whereby two nodes Si, S2 wish to jointly minimize a common convex quadratic cost function f(x1,x2), subject to separate local constraints on x1and x2, respectively. Suppose that node S1has control of variable x1only and node S2has control of variable x2only. The two nodes locally update their respective variables and periodically exchange their values over a noisy channel. Previous studies of this problem have mainly focused on the convergence issue and the analysis of convergence rate. In this work, we focus on the communication energy and study its impact on convergence. In particular, we consider a class of distributed stochastic gradient type algorithms implemented using certain linear analog messaging schemes. We study the minimum amount of communication energy required for the two nodes to compute an ∈-minimizer of f(x1,x2) in the mean square sense. Our analysis shows that the communication energy must grow at least at the rate of Ω(∈-1). We also derive specific designs which attain this minimum energy bound, and provide simulation results that confirm our theoretical analysis. Extension to the multiple node case is described.