Distributed optimization in an energy-constrained network using a digital communication scheme

We consider a distributed optimization problem where n nodes, S _l, l ∈ {1, . . . , n}, wish to minimize a common strongly convex function f(x), x = [x₁, . . . , x_n]^T , and suppose that node S_l only has control of variable x_l. 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 ∈-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 Ω (∈^-1) to obtain an ∈-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 ∈^-1)³) to obtain an ∈-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.